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;

}

from the betting coefficient k is (m + n) / n
I think k must be greater  than 1.

Don't you think so?

What is test 6?

Edited by author 11.01.2013 21:21

Can somebody give test #16?
Getting TLE
Thnx

when you search x and y (A*x+B*y = N)
use something like
this for x:= 0 to min(n div a, trunc(sqrt(n))) do
=)

if stones are sorted then answer is n-1

It took me a while to find out this special case :)

this is very bad problem :(

Try the following test:
50
3081 30488 b
16217 39416 w
7248 11364 w
17676 32492 w
25292 30974 w
1686 28199 w
9576 25807 w
18823 21457 w
30775 38642 w
7758 15847 b
6289 19805 b
1546 26246 w
27602 30148 w
9296 14836 w
19435 26471 w
27882 35227 w
24453 42158 w
943 1752 b
4080 12268 w
31529 41419 w
6238 22445 w
6262 13797 w
16616 31697 w
9990 12426 w
31675 46085 w
15149 32698 b
16029 18700 b
32372 50450 w
19642 25152 b
21096 30699 b
27244 35134 b
29951 43374 w
8869 9499 w
3375 28256 w
2060 14099 b
19972 37822 b
30222 33297 b
5433 9482 w
28735 54469 b
19053 31004 w
12234 27889 b
19117 19750 b
11927 17069 w
30056 32152 b
21756 25680 w
25656 44214 b
5308 18661 b
21710 26158 b
9196 32476 b
9917 11034 b

I don't know what the output is. Mine was 54496 1000000000

Nice to see, but "higher" relation is not transitive ;-)

can anybody explain me how to use reals with big range like 10^18 or 10^19 more precisely in pascal?

Please help
Why am I getting floating-point invalid operation on test 3?
Would it be possible to see the test values?

program pr_1;
var n, i, x: longint;
a: real;
begin
read(n);
for i:=1 to n do
begin
  read(x);
  a:= (1 + sqrt(8*x-7))/2;
  if (Frac(a) = 0.0) then
    write('1 ')
  else
    write('0 ');
end;
end.