10599 - Robots(II)

[Red Scorpion]

Hi,..

I used DP to solve this, but always got WA.
Is there any trick in this prob?
can someone who have got AC give me some test cases?

Thanks.

[Whinii F.]

I got accepted this problem with DP in last contest, but now it results in WA. What is wrong?!

[rotoZOOM]

I got accepted this problem with DP in last contest, but now it results in WA. What is wrong?!

Yes I got accepted at online contest but now I get WA too.
I think problem in special correction program (sign is yellow).

[hujialie]

I have met the same problem, accepted codes during the
contest now got wrong answer, and I noticed that no one
has passed. Administrator, plz have a look.

[Red Scorpion]

After rejudge I got AC, thanks.

[hj]

hello !
could somebody check this, thanks
input :
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
0 0
-1 -1
output:
CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 10
is it correct ??, is there any tricky input ?

[rotoZOOM]

hello !
could somebody check this, thanks
input :
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
0 0
-1 -1
output:
CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 10
is it correct ??, is there any tricky input ?

Last number is 100.

CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100

And don't forget about avoiding trailing space, i.e. no space at the end of line.

[kiha]

Hi

I also use Dynamic Programming to solve this problem , but I never can get AC. I ckecked my program on your test case with garbage on each field and it wrote that the number of ways to collect 19 garbages is 19! (factorial) I realised that I have made a mistake in counting the ways ... can somebody give me a hint ? I has been working on this problem for 3 hours during the cotest , but of course I got WA :<
This is the only thing I can't do about this problem - my program [in Pascal] correctly outputs the maximum amount of garbage that can be collected , corretly writes the sample path , but I can't invent how to count the ways. Please help

Kiha (tm)

[Dreamer#1]

Is this a valid output for the test case given above?

CASE#1: 19 48620 1 11 21 31 41 51 61 71 81 91 92 93 94 95 96 97 98 99 100

Someone please give a few more test cases. I can't remember when was the last time I got so many WA-s

Thanks in advance

Dreamer.

[Whinii F.]

Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle.

[rotoZOOM]

Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle.

No. Resulting number fit into 64-signed integer.

[Red Scorpion]

Hi, I used 'long long' to solved this problem.
But maybe the judge data fit into 64-signed integer.

[Whinii F.]

Oops. Is it true?? For test cases like 100 100 (and 10000 garbages, one in each grid square), the resulting number should easily overtake 2^64, where my program outputs

22750883079422934966181954039568885395604168260154104734000

..

I got WA using int during the contest and noticed this to get AC. Of course this problem's core is not bigint, but they should have commented about upper limit of the resulting number.

[rotoZOOM]

Oops. Is it true?? For test cases like 100 100 (and 10000 garbages, one in each grid square), the resulting number should easily overtake 2^64, where my program outputs

22750883079422934966181954039568885395604168260154104734000

..

I got WA using int during the contest and noticed this to get AC. Of course this problem's core is not bigint, but they should have commented about upper limit of the resulting number.

I use long long during contest and my program got AC.
I think problemsetter don't want contestant to use long arithmetic,
because problem is enough difficult.
Though, I agree with Whinii that problemsetter had to comment it in problem description.

[windows2k]

Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle.

Hello, Whimi F.
Could you say how to calculate the ways that the maximum garbage ?
Thx