\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

Test:
3 3
+.+-+.+
|1|2| |
+-+.+.+
| | . |
+-+.+.+
| | | |
+-+.+.+
Answer:
8


Just look( in back order ):
 +.+-+.+
 | | | |
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+
    0 0


 +.+-+.+
 | | | |
 +-+.+.+
 | | . |
 +-+.+.+
 | | |0|
 +-+.+.+
    0


 +.+-+.+
 | | | |
 +-+.+.+
 | | . |
 +-+.+.+
 | |0|0|
 +-+.+.+



 +.+-+.+
 | | | |
 +-+.+.+
 | | .0|
 +-+.+.+
 | |0| |
 +-+.+.+



 +.+-+.+
 | | | |
 +-+.+.+
 | |0.0|
 +-+.+.+
 | | | |
 +-+.+.+



 +.+-+.+
 | |0| |
 +-+.+.+
 | | .0|
 +-+.+.+
 | | | |
 +-+.+.+



 +.+-+.+
 | |0|0|
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+


      0
 +.+-+.+
 | |0| |
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+


    0
 +.+-+.+
 | |0| |
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+


  0
 +.+-+.+
 | |0| |
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+



 +.+-+.+
 |0|0| |
 +-+.+.+
 | | . |
 +-+.+.+
 | | | |
 +-+.+.+

Hi,

I am just beginning to write code although i am bit familiar with algorithms and datastructures.

I wrote this solution. But its wrong. I kinda feel that i am overcounting but not sure where it is.

if( n == 0) return 1;
if(n == 1) return k-1;
return k-1 * ( k * f(n-2,k) + k * k-1 * f(n-3,k) )

if digit n-1 can have zero there are k ways we can fill it, hence k * f(n-2,k)
else if digit n-1 cannot have zero then we can use k-1 ways for digit n-1 and k ways for n-2.

Edited by author 14.01.2013 18:41

My solution is a BFS using deque, but i am gettign WA 4.
Please Help me someone...

Edited by author 13.01.2013 19:42

Edited by author 13.01.2013 19:42

UPD: At last I got AC, there was just a really stupid bug. Wrong output is replaced with correct one produced by my AC solution.



Please, anybody who has AC solution, check my solution's answer for this big random test:

INPUT

50 50
GRYBYYWWRYBBGRGGBRRGGYRWRRGGWBRGGWYRRYBYWGRWWYGGWW
RYRRRYWGYWGBBRWGBRYWGBBYBBGGWWYWYYGBGGGWYYGWRWWRYG
WBYWYBRGWGGBYRBYRWRRGBGGBRBYGRBBGYGBRGRRRRWWBYYWGW
RGGBWWBGRBBYYRWWBGRBGGYBGGWYWYGYWYWWBWRRWWWWRGBRWY
YGBGBYYGWWYWYYYRBBWWWRYWWBWWBGWGYWYRRRWRWYBRWGBWGG
RYRBWGRGBWYRYGGWRGGYRGRYBRBBWYGWGYBWRBRBWGRRRRYYGY
GYWRBBYYGRBBWWYWYGRYYRGYWBRGGBWRBYYGGGGWWBBWRWRBWG
GWGRGYGRYGBBWGYYRYWYYBBYGWYRWWRBWGRBRYYYYYRYWBRRWR
WBWWRBRBWRRYRBWYWRGGWRBWBGRRRGYBRBWYBBBWGBGRBBBYBY
YBGYWRGGWWGYWYYRBRBGBRBBGRWWYYRGBRRYBRYWWBRRWGRGBB
YBRGBGGGGRWBBYWWBGRYBWWWBRRBWYWBRYRWWRGBBWWYBBGYBG
RBWBGGGRGRRGYGGRRRRGBGWYYBYRGBWRYYYRRYRWRWGBRWBWWR
YGGBYBGBGYBWBWYGWYRYGWGBRWGBWGBBRRGRYWRWGWBWBRWBRR
RBYGBWBBRYBBWYGBYWBYRBYGWYBWRRYGGRRGYBWYGRBWWRYGRY
BWRYBGWBRRYWGWGWBGYBYRYWGYWRBBBYWRWRYWGYWBBRGWYRYB
YYBBBWWBGWRRRRBWGWWRBYBBWWRWWRYWYGWRWBGWYWGBYWBBWR
GWBGBWWYYWWYRGYBWGGBBGYGYBYRBWRGWRGGWYYBGRBWBGGGYY
GRGWRBBGBGBGRGBBRYWWGRWRWYWYWGWYRWYWBBWWBBGYWGWYRG
YWRWYBRWGYWYWYGWBGYRBWWYRWRBGYWGYWBYRYWBGYRBBBBYRW
RYBBYYBBGGBYBWWWRRGYWWGBWWWYWBGBYGWRWBWBGYBWYWGBGY
RWYYGBGGGGGRGYBGGRGYYBRWYGBRWGGWWRRRGRGBYYYGBWGRYB
WWGRGYYWRYBRYYWWWGYWGGRWWRGRRBRWRRWBRBWYRWRBBBRRGR
WRWGGBYBWYBBBRRBBRGYWGYGWYWWBBGBBWYBBYRRGYYYBWBWBB
RGRWWGYYGYBBRYRWYBWWGBRWRYGGGRYBYYWGGYYBBBGBBYYGWY
YBBWYGRWWGWGBRYYBRRGBYYYRBBYRGRRRYBBYBWYGRRYWRRRWB
WWYYYGYWBGGBRRRRGYRGWRGGWWWRWGBGRGBBYGRYWYRWWGGWWR
GGRRWRWBWBWRWWGBWGBYRYYGBRWWYRRBGRRRBRYGBWRWYBYRRB
RWGRBWGWWBWGRBRWYGWWRBWGRBYWWGWGRWYBBBGGWBBWWRWBGB
BYRRRWRYYYWRRRBWYRWYBGYBRWWGYWGBYBRYBWGYBRYBWWRWRG
BYBRBYBBGRBYWYGRWWBRGGBRWYWYYYYRBWRWRWBRGYRGYGGBWW
GRRGYWRGBBYYGBWRRYBRGBGRYWWBGBGGWWYWRBRYGBWGWYYBWW
RWYYWBGWRWGGYGRRYGYGYRGWGBYRBRGGRGRBWYBRBBWGWWWBGR
BBBYBYWBYRRRGRRRBGGRBYGWGRWGGYYRGGBWYBWRWWGGRBRGRG
GGGBRYWBGYYWYWRBWWWRRBGWBGGYBWGWGBWYBWGRYBWBRYGRGG
RBGBRRYBBGWWGWWGGGGRBYYWYYYWRBGYWGWRWBYBGYBBGWBBWB
GRRYGRBRYGRGWWBRGYRGWRWBRRWWBYRGWYRGWRGRRBWYYBBGYG
RGGWWBBWGWWGGYWBGWYWYWGBBYBBBGBBGWYGRRBBBRBRBGRRWB
BGWWBGYWRBBRBRBGGWGWBGBYRGBRWRGRRWWWRYBBBYYBWBYYBG
GGRWWYRRWWBYWYWYRYYBBRYRGGWBYBWBGBGBWYBWYGRBRGWWBY
WBRBGBRRYYGRWBRWWYRWWYGWBYGRRRGWGWGBGBBBGRRGBBWWYR
WYRRBWYBYYYWBWYGBWWYBGRBBGBYWWBRYBYWRYBRWBYGGGYBRY
GRYYYWRGBWRWYRRGGBBGWRGBBRYYYBGGGYBYRGYRBYWWWGWBGY
BYWWWYBGWGRWWGYWGWWYWYRRRGRGGRWBGBRBGBRRBYBYWRBGBW
WGBRBRYRWRRRYWGWWGBGWRGBGRYBGGBYGWWBBYRGWWBRYBYWBR
WWBWBWRGGBWGWRRWYRWBRWRBBWGRYYWWRRGRYBBWYBGBWYRWRY
YYRYYBYYYWBWRWBGRGYWWWRYWWRWWYBRBGRGBRGGWBBWWYBRWR
RRBBRWGGWRRRWRYBYRYGWBWGYRBRYRBWGBBRGGYWBWRWBYWRWG
BRRRGWBRBWGWGYBGGBGBYRWBWGBGRGRYYYWBBGWBBWYRWBWBGY
RWGGGWBWGBRGBRWWBBGGYYWWWRWWRWBGYWRWYWYRYGYBWYGYWW
GYGYBRGWYGWWWYRRWYBGYBRWYYYBGWYWYYRBWYBGYWGRBBGBGG

OUTPUT

B: 43900
G: 47932
R: 26046
W: 38176
Y: 21310

Am I correct?

Edited by author 14.02.2012 18:03

Edited by author 14.02.2012 18:03

3 3
WYY
YWR
WYR

answer:
R: 4
W: 12
Y: 8

I am good man!
In promlem it is said that:
"05      If there is a figure of the main color:"
But I have wrote in my program:
"WHILE there is a figure of the main color:"
Stupid bug! =)

Edited by author 13.01.2013 19:05

What does the number under column Test # mean?

can anybody explain to me why f[0]=1????....i mean it's logically wrong....but the algo is giving AC with these assumption....

here is my code. please help me :((

#include <stdio.h>
#define HMAX (1<<17)

int N;
unsigned int H[HMAX];

void sift(int x)
{
        int aux, up = x>>1;

        if (x < 1) return;

        if (H[x] > H[up])
        {
           aux = H[x]; H[x] = H[up]; H[up] = aux;
           sift(up);
        }
}

void perc(int x, int n)
{
        int l = x<<1, r = (x<<1)+1, max, aux;

        if (r > n) return;

        max = l;
        if (H[l] < H[r]) max = r;

        if (H[max] > H[x])
        {
           aux = H[max]; H[max] = H[x]; H[x] = aux;
           perc(max, 1+N/2);
        }
}

int main()
{
        int i, val;
        long double sol;
        unsigned int last, blast;

//        freopen("1306.in", "r", stdin);
        scanf("%d", &N);

        H[0] = 4294967295;

        for (i = 1; i <= 1+(N/2); i++)
                scanf("%lu", H+i);
        for (i = 1; i <= 1+(N/2); i++) sift(i);

        for (i = 2+(N/2); i <= N; i++)
        {
                scanf("%d", &val);
                if (val < H[1]) { H[1] = val; perc(1, 1+(N/2)); }
        }


        blast = H[1];
        H[1] = 0;
        perc(1, (N/2));
        last = H[1];

        sol = last*0.5;
        sol += blast*0.5;
        if ( (N&1) == 0 ) printf("%0.1llf\n", sol);
        else printf("%u\n", blast);

        return 0;

}