There is no direct hint in task description that first n/2 and last n/2 should sum up in n case instead of first 3 and last 3 digits. Wouldn't it be more correct to replace "the first 3 digits" with "the first half of digits"?

Why crash tell me please?
program My;
var
   n,k,i,i2,en,j,count:longint;
   a,b:array [1..4000] of longint;
   block:array[1..3,1..4000]of longint;
   ready:boolean;
begin
en:=1;
     for i:=1 to 3 do
     begin
          readln(n);
          for i2:=1 to n do
          begin
               read(k);
               ready:=true;
               for j:=1 to en do
               begin
                    if k=a[j] then
                    begin
                         ready:=false;
                         if block[i,j]=0 then
                         begin
                              inc(b[j]);
                              block[i,j]:=1;
                         end;
                    end;
               end;
               if ready = true then
               begin
                    a[en]:=k;
                    b[en]:=1;
                    block[i,en]:=1;
                    inc(en);
               end;
          end;
     end;

     for i:=1 to en do
     begin
          if b[i]=3 then inc(count);
     end;
     writeln(count);
end.

Who gets WA#21 try this test:
- IS IT CORRECT?
- YES, IT IS.

answer:
- Is it correct?
- Yes, it is.

Edited by author 02.11.2008 21:33

Edited by author 02.11.2008 21:34

The input is of multiple testcases, and each testcase starts with N, the length of the sequence, and K, the number of pairs of intervals. You only know when you stop after got N == -1.

Naive ideas will get TLE even for testcase #1, and you will see your code runs out of 2s limit when feeding a testcase with N=10^9 and K=5000, when all pairs are good and you should output 5000.

My program 4729094 got AC, but the same program gives WA2 on problem 1593 (harder tests). So, there is a class of numbers those my solution gives incorrect answer and I think some of such numbers must be below 60000

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace timusPin
{
    class Program
    {
        static void Main(string[] args)
        {
            int max;
            int e=0, m=0, l=0;

            max = int.Parse(Console.ReadLine());
            string[] arr = new string[max];

            for (int v = 0;v <= max -1 ;v++)
            {
                arr[Convert.ToInt32(v)] = (Console.ReadLine());
            }
            for (int v = 0;v <= max -1 ;v++)
            {
                if (arr[v] == "Emperor Penguin")
                {
                    e++;
                }
                if (arr[v] == "Macaroni Penguin")
                {
                    m++;
                }
                if (arr[v] == "Little Penguin")
                {
                    l++;
                }
            }
            if (e > m && e > l)
            {
                Console.WriteLine("Emperor Penguin");
            }
            if (m > e && m > l)
            {
                Console.WriteLine("Macaroni Penguin");
            }
            if (l > e && l > m)
            {
                Console.WriteLine("Macaroni Penguin");
            }
           // Console.ReadKey();
        }
    }
}




WHY Wrong Answer????

Please add this test

2
1
10000
1
1

my program showed YES this test but Accepted

\u002f\u002a
public class Main {}
\u002a\u002f
\u0069\u006d\u0070\u006f\u0072\u0074\u0020\u006a\u0061\u0076\u0061\u002e\u0069\u006f\u002e\u002a\u003b\u000d\u000a\u0069\u006d\u0070\u006f\u0072\u0074\u0020\u006a\u0061\u0076\u0061\u002e\u0075\u0074\u0069\u006c\u002e\u002a\u003b\u000d\u000a\u000d\u000a\u0070\u0075\u0062\u006c\u0069\u0063\u0020\u0063\u006c\u0061\u0073\u0073\u0020\u004d\u0061\u0069\u006e\u0020\u007b\u000d\u000a\u000d\u000a\u0009\u0053\u0063\u0061\u006e\u006e\u0065\u0072\u0020\u0069\u006e\u003b\u000d\u000a\u0009\u0050\u0072\u0069\u006e\u0074\u0057\u0072\u0069\u0074\u0065\u0072\u0020\u006f\u0075\u0074\u003b\u000d\u000a\u0009\u000d\u000a\u0009\u0076\u006f\u0069\u0064\u0020\u0073\u006f\u006c\u0076\u0065\u0028\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u0069\u006e\u0074\u0020\u0061\u0020\u003d\u0020\u0069\u006e\u002e\u006e\u0065\u0078\u0074\u0049\u006e\u0074\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u0069\u006e\u0074\u0020\u0062\u0020\u003d\u0020\u0069\u006e\u002e\u006e\u0065\u0078\u0074\u0049\u006e\u0074\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u006f\u0075\u0074\u002e\u0070\u0072\u0069\u006e\u0074\u006c\u006e\u0028\u0061\u0020\u002b\u0020\u0062\u0029\u003b\u000d\u000a\u0009\u007d\u000d\u000a\u0009\u000d\u000a\u0009\u0076\u006f\u0069\u0064\u0020\u0072\u0075\u006e\u0028\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u0069\u006e\u0020\u003d\u0020\u006e\u0065\u0077\u0020\u0053\u0063\u0061\u006e\u006e\u0065\u0072\u0028\u0053\u0079\u0073\u0074\u0065\u006d\u002e\u0069\u006e\u0029\u003b\u000d\u000a\u0009\u0009\u006f\u0075\u0074\u0020\u003d\u0020\u006e\u0065\u0077\u0020\u0050\u0072\u0069\u006e\u0074\u0057\u0072\u0069\u0074\u0065\u0072\u0028\u0053\u0079\u0073\u0074\u0065\u006d\u002e\u006f\u0075\u0074\u0029\u003b\u000d\u000a\u0009\u0009\u0074\u0072\u0079\u0020\u007b\u000d\u000a\u0009\u0009\u0009\u0073\u006f\u006c\u0076\u0065\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u007d\u0020\u0066\u0069\u006e\u0061\u006c\u006c\u0079\u0020\u007b\u000d\u000a\u0009\u0009\u0009\u006f\u0075\u0074\u002e\u0063\u006c\u006f\u0073\u0065\u0028\u0029\u003b\u000d\u000a\u0009\u0009\u007d\u000d\u000a\u0009\u007d\u000d\u000a\u000d\u000a\u0009\u0070\u0075\u0062\u006c\u0069\u0063\u0020\u0073\u0074\u0061\u0074\u0069\u0063\u0020\u0076\u006f\u0069\u0064\u0020\u006d\u0061\u0069\u006e\u0028\u0053\u0074\u0072\u0069\u006e\u0067\u0020\u0061\u0072\u0067\u0073\u005b\u005d\u0029\u0020\u007b\u000d\u000a\u0009\u0009\u006e\u0065\u0077\u0020\u004d\u0061\u0069\u006e\u0028\u0029\u002e\u0072\u0075\u006e\u0028\u0029\u003b\u000d\u000a\u0009\u007d\u000d\u000a\u007d

Could you please check my submissions.

The accepted one (I actually copy-pasted it from this forum) gives wrong answer to the following data set:
tram
(only 4 symbols in input.txt file)
The output is "Bus driver".

My original solution (#4725054) gives "Tram driver" answer to the mentioned data set, but fails on test #6. Can you please give information what is wrong with this test?

Thank you.

Just use diagonal painting:
1 2 3 ... k ... (total n times)
2 3 4 ... 1 ... (total n times)
. . . ... . ... (total n times)
Calculate, how many 1,2, ... k in this table. Answer will be minimal
of them(every rectangle 1xK covers K different colors).
I don't no is this mathematically correct, but this solution got AC.
Don't forget, that if N < K answer is 0.
P.S. Sorry for bad English.

Can you generate me some tests with answers?
I'd like to check my program.

4 3
3 1 2 4
2 2 3
2 3 4
3
27 1 0
15 4 0
45 4 0

Hi, guys! In the problem statement input is a string, that consists of a..z or A..Z.
Let me guess, Test 7 has some other chars ? If so, please, correct prom statement with this note.
4 my submissions were with WA#7 until I added char check

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int M1 = 555;
const int INF = 111111111;
int N,K;
int ans;
int w[M1][M1];//w[i][j] is the number of white horses in the last stable when the first i horses were placed in 1st j stables with minimum unhappiness
int b[M1][M1];//b[i][j] is the number of black horses in the last stable when the first i horses were placed in 1st j stables with minimum unhappiness
int f[M1][M1];//f[i][j] means the minimum unhappiness when the first i horses were placed in 1st j stables
//function: f[i][j] = min(f[i-1][j-1],f[i-1][j]+w[i-1][j] or b[i-1][j]);

int main()
{
    memset(w,0,sizeof(w));
    memset(b,0,sizeof(b));
    memset(f,0,sizeof(f));
    scanf("%d%d",&N,&K);
    for(int i=0;i!=M1;++i)
    {   for(int j=i+1;j!=M1;++j)
            f[i][j] = INF;
        f[i][0] = INF;
    }
    int tmp;
    scanf("%d",&tmp);
    if(tmp) ++b[1][1];
    else ++w[1][1];
    f[1][1] = 0;
    for(int i=2;i<=N;++i)
    {   scanf("%d",&tmp);
        for(int j=1;j<=min(i,K);++j)
        {   f[i][j] = f[i-1][j-1];
            b[i][j] = 0;
            w[i][j] = 0;
            if(tmp)
            {   ++b[i][j];
                if(f[i-1][j]+w[i-1][j]<f[i][j])
                {   b[i][j] = b[i-1][j]+1; w[i][j] = w[i-1][j];
                    f[i][j] = f[i-1][j]+w[i-1][j];
                }
            }
            else
            {   ++w[i][j];
                if(f[i-1][j]+b[i-1][j]<f[i][j])
                {   b[i][j] = b[i-1][j]; w[i][j] = w[i-1][j]+1;
                    f[i][j] = f[i-1][j]+b[i-1][j];
                }
            }
        }
    }
    ans = f[N][K];
    printf("%d",ans);
    return 0;
}

I think I have precision problems, please inspect my code (CSharp) and give some hints:

UPD: ok, I found some mistakes in my algorithm.

Edited by author 08.01.2013 14:49