Edited by author 25.09.2016 18:07

Let n=4 and i-1=2. Why ans is 0.687500?
We have 6 variants:
(carousel moves to the "left")

0011
=> Waiting time = 0+0+2+1=3
   Conditional expectation(0011) = 0*(1/4)+0*(1/4)+2*(1/4)+1*(1/4)=3/4
   Probality(0011)=(1/4)*(2/4)+(1/4)*(1/4)=3/16

0101
=> Waiting time = 0+1+0+1=2
   Conditional expectation(0101) = 0*(1/4)+1*(1/4)+0*(1/4)+1*(1/4)=2/4
   Probality(0101)=(1/4)*(1/4)+(1/4)*(1/4)=2/16

0110
=> Waiting time = 0+2+1+0=3
   Conditional expectation(0110) = 0*(1/4)+2*(1/4)+1*(1/4)+0*(1/4)=3/4
   Probality(0110)=(1/4)*(1/4)+(1/4)*(2/4)=3/16

1001
=> Waiting time = 1+0+0+2=3
   Conditional expectation(1001) = 1*(1/4)+0*(1/4)+0*(1/4)+2*(1/4)=3/4
   Probality(1001)=(1/4)*(1/4)+(1/4)*(2/4)=3/16

1010
=> Waiting time = 1+0+1+0=2
   Conditional expectation(1010) = 1*(1/4)+0*(1/4)+1*(1/4)+0*(1/4)=2/4
   Probality(1010)=(1/4)*(1/4)+(1/4)*(1/4)=2/16

1100
=> Waiting time = 2+1+0+0=3
   Conditional expectation(1100) = 2*(1/4)+1*(1/4)+0*(1/4)+0*(1/4)=3/4
   Probality(1100)=(1/4)*(2/4)+(1/4)*(1/4)=3/16

ans = Expected value = Sum(Conditional expectation(mask) * Probality(mask))
ans = (3/4)*(3/16)+(2/4)*(2/16)+(3/4)*(3/16)+(3/4)*(3/16)+(2/4)*(2/16)+(3/4)*(3/16)=(3/4)*(3/16)*4+(2/4)*(2/16)*2=3*(3/16)+2*(2/16)=11/16.


Edited by author 21.06.2017 12:40

Test 4 What?

Test 4 What?

the problem says that comments may contain every symbol so, comments may contain *)
so, should take the *) as we like so it will match as good as we can, or should we take *) as we meet it in the text?

try changing the float to long double

Задачу нельзя сдать на Java, несмотря на условие

When you have WA #3, perhaps you check condition in integer values, so use 64-bit integer values. To avoid WA #3 try below test:

100000
10000 10000
100 100

Correct answer is:
Cash
51400000.00

Good luck!

Milking Cows


Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).

Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):
•The longest time interval at least one cow was milked.
•The longest time interval (after milking starts) during which no cows were being milked.

PROGRAM NAME: milk2

INPUT FORMAT

Line 1: The single integer
Lines 2..N+1: Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500

SAMPLE INPUT (file milk2.in)
3
300 1000
700 1200
1500 2100



OUTPUT FORMAT
A single line with two integers that represent the longest continuous time of milking and the longest idle time.
SAMPLE OUTPUT (file milk2.out)
900 300
=======following is C code==================
#include <stdio.h>
void doSort(long nums[5000][2],int n);

int main(int argc){
    long nums[5000][2];
    long max_line[2],cur_line[2],max_gap;
    int n,i,j;

    scanf("%d",&n);
    for (i=0;i<n;i++){
        scanf("%d",&nums[i][0]);
        scanf("%d",&nums[i][1]);
    }

    doSort(nums,n);
    max_line[0] = nums[0][0];
    max_line[1] = nums[0][1];

    cur_line[0] = nums[0][0];
    cur_line[1] = nums[0][1];
    //printf("%d,%d\n",nums[0][0],nums[0][1]);
    for (j=1;j<n;j++){

        // case of line
        if (nums[j][0] <= cur_line[1] ){
            if (nums[j][1]>cur_line[1]){
                // line be extended
                cur_line[1] = nums[j][1];
            }
            // printf("l:%d,%d\n",nums[j][0],nums[j][1]);
        }
        else{ // case of gap
            // get gap value
            if ((nums[j][0] - cur_line[1])> max_gap){
                max_gap = nums[j][0] - cur_line[1];
            }

            // save current line into max line if cur > max
            if ((cur_line[1] - cur_line[0] )> (max_line[1] - max_line[0]))
            {
                max_line[0] = cur_line[0];
                max_line[1] = cur_line[1];
            }
            cur_line[0] = nums[j][0];
            cur_line[1] = nums[j][1];
            // printf("g:%d,%d\n",nums[j][0],nums[j][1]);
        }
    }
    // save current line into max line if cur > max
    if ((cur_line[1] - cur_line[0] )> (max_line[1] - max_line[0]))
    {
        max_line[0] = cur_line[0];
        max_line[1] = cur_line[1];
    }


    printf("%d ",max_line[1]-max_line[0]);
    printf("%d",max_gap);
    return 0;
}

void doSort(long nums[5000][2],int n){
    int j,p;
    int temp[2];
    for (p=1;p<n;p++){
        temp[0] = nums[p][0];
        temp[1] = nums[p][1];
        for(j=p;j>0 && nums[j-1][0] > temp[0];j--){
            nums[j][0]=nums[j-1][0];
            nums[j][1]=nums[j-1][1];
        }
        nums[j][0]=temp[0];
        nums[j][1]=temp[1];
    }
}

can anyone please tell me what is test case 2

#include<stdio.h.>
#include<string.h>


int main()
{
    int i,j,temp,re,q;
    int a[6]={0,0,0,0,0,0};
    int b[6];
    char c[6][20];
    for(i=0;i<6;i++)
    {
        char d[20];
        scanf("%s",d);
        scanf("%s",c[i]);
        scanf("%d",&b[i]);
    }
    for(i=0;i<6;i++)
    {
        for(j=0;j<6;j++)
        {
            if(strcmp(c[j],c[i])==0)
                a[i]++;
        }
    }

    temp=a[0];
    re=b[0];
    for(i=0;i<6;i++)
    {
        if((a[i]>temp)||((a[i]==temp)&&b[i]<=re))
        {
            temp=a[i];
            re=b[i];
            q=i;
        }
    }

    printf("%s",c[q]);
    fflush(stdin);
    getchar();
    return 0;
}

I got WA on test 3 and cant find error on my code despire of using lots of random test. I using suffix array and lcp. Can anyone give me any test to check :(

program z1000;
var a,b:integer;
begin
  write('Vvedite a b: ');
  read(a,b);
  write('a+b= ',a+b);
end.

Why 'Wrong answer 1' ?

Wa9. Хотелось бы несколько наглядных тестов или указание на ошибку в решении.
Решение:
1)n<=2 => ans=1
2)n>=3;
  если есть вершина степени >=3 => ans=0
  иначе
   в графе (неориентированном) есть либо циклы, либо цепи, причём они не пересекаются (т.е. от цикла ни одна цепь не отходит)
   а)пусть найден некоторый цикл
     если его длина = n => ans=2
     иначе ans=0
   б)циклов нет
     пусть p-общее число цепей в графе, len(i)-длина i цепи
     если len(i)>2 то положим len(i)=2
     => ans=len(1)*len(2)*...*len(p)*(p-1)!

Edited by author 19.09.2016 19:13

Edited by author 19.09.2016 19:34

Edited by author 29.10.2016 23:21

#include<stdio.h>
void merge(int a[],int b[],int c[],int d[],int left,int mid,int right)
{
    int i=left,j=mid+1;
    int k=left;
    while((i<=mid)&&(j<=right))
    {
        if(a[i]>=a[j])
        {b[k++]=a[i++];
        k--;
        i--;
        d[k++]=c[i++];}
        else
        {b[k++]=a[j++];
        k--;
        j--;
        d[k++]=c[j++];}
    }
    if(i>mid)
        for(int q=j;q<=right;q++)
        {b[k++]=a[q];
    k--;
         d[k++]=c[q];
    }
    else if(j>right)
        for(int q=i;q<=mid;q++)
        {b[k++]=a[q];
    k--;
    d[k++]=c[q];}
    for (int l = left;l <= mid;l++) {
        a[l] = b[l];
        c[l]=d[l];
    }
    for (int l = mid+1;l <= right;l++) {
        a[l] = b[l];
        c[l]=d[l];
    }
}
void mergesort(int a[],int b[],int c[],int d[],int left,int right)
{
    if(left<right)
    {
        int mid = (left + right) / 2;
        mergesort(a,b,c,d,left,mid);
        mergesort(a,b,c,d,mid+1,right);
        merge(a, b,c,d, left, mid, right);
    }
}
int main()
{
    int n,i;
    int c[15000],a[15000],b[15000],d[15000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&c[i]);

        scanf("%d",&a[i]);
    }
    mergesort(a,b,c,d,0,n-1);
    for(i=0;i<n;i++)
    {
        printf("%d %d\n",d[i],b[i]);
    }
    fflush(stdin);
    getchar();
    return 0;
}

708591 179659 (or 531444 2512)
387600148 708591 (or 387423001 531444)
19686 324

I got WA2, but after that I changed limits for N and K from 501 to 503 and it worked. (indexing starting from 1).

#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,c,d,i,t;
    scanf("%d %d %d %d",&a,&b,&c,&d);

    for(i=1;i<10000;i++)
    {
        a=a+b;
        if(a>c)
        {
            t=c;
            break;
        }
        c=c-d;
        if(a>=c)
        {
            t=a;
            break;
        }
    }
    printf("%d",t);
    return 0;
}

Any idea about this test?
I used Python2.7

Долго не мог понять, в чём проблема.
Не используйте вещественные типы, всё должно быть целочисленное, нельзя даже умножать период на 0.4 и 0.7, лучше домножить на 10. Может кому-то это поможет...