10645 - Menu

[miras]

Hello

Can anyone post me some tests ?? becouse i get WA ..


(i used DP in this prob.)

Regards.

Miras

[Adrian Kuegel]

Input:

Code: Select all

18 39 76
21 9266
38 922
34 6140
32 4301
35 4587
5 3063
4 8323
36 5906
11 6850
9 4718
30 8640
48 2044
38 6858
10 7710
38 1453
36 9082
9 2078
43 567
45 5939
46 8288
10 7937
26 9416
23 9896
46 1177
5 697
38 5048
5 2315
15 3229
9 7911
11 307
18 8048
10 6239
16 2972
15 1577
12 314
10 5740
10 4105
6 6212
18 2552 
0 0 0

Output:

Code: Select all

74674.5
7 7 6 7 7 6 7 7 6 7 7 6 7 7 7 7 7 7 

[miras]

my output is the same...

but i still get WA...
is there any tricky case... ??

Regards.
Miras

[titid_gede]

input :

Code: Select all

5 3 21
2 5
1 4
3 4

output should be:

Code: Select all

23.0
1 2 1 2 1

hope it helps.

[miras]

hm...

it seems to be OK but hm... i get WA

BTW. (My Output is the same )

is thre any faster solution ...becouse i think tak my prog is quit slow it rans 8 sec. and gets WA ;-(


Miras

[windows2k]

hm...

it seems to be OK but hm... i get WA

BTW. (My Output is the same )

is thre any faster solution ...becouse i think tak my prog is quit slow it rans 8 sec. and gets WA ;-(


Miras

Hello, I tried to solve the problem.
But I can't find the right recurrence equation.
Could someone give me some hints?
Thx

[Krzysztof Duleba]

I'm having hard time with this one and I don't know why. I'm using dynamic programming in O(n * k * m) time and O(k * m) memory.

Could anyone check this input data for me?

Input:
8 13 59
25 4648
2 203
26 9241
30 9004
5 6268
25 9309
10 1059
46 4759
7 5320
26 1180
12 618
26 3214
29 3628

13 26 89
17 9652
6 3813
5 5186
13 2877
18 5582
15 3043
3 968
19 7794
12 8339
49 2339
2 8629
44 248
23 8036
13 6410
27 8394
47 978
38 9880
39 4039
8 8846
1 4280
26 2833
2 287
13 2274
29 6722
30 9764
2 8679

10 40 21
43 5213
25 1368
42 6026
40 9660
48 6848
44 3691
23 9239
43 4635
50 7757
46 2149
49 8451
25 8265
13 2428
1 8908
24 7784
16 2207
44 5759
1 7658
2 6179
37 8018
24 5064
9 6898
9 4346
32 7126
22 9884
27 4504
46 9269
1 4664
28 6251
12 9428
18 8220
38 9681
26 9385
26 8151
32 651
21 9251
45 4226
23 2241
42 4323
9 5433

20 17 30
46 9030
15 4484
34 4703
8 2205
21 9307
2 2824
47 5216
28 1990
18 9808
31 7458
48 4071
13 5621
43 6604
13 3467
37 1386
50 1461
26 6614

19 7 5
39 1831
37 5403
49 9074
26 9456
49 6653
29 425
45 6354

12 25 12
17 3634
32 8698
44 44
7 227
23 4917
33 5025
46 7705
49 265
42 8852
42 2514
46 2339
48 4585
3 7013
29 423
20 4237
6 8754
10 5008
13 9343
22 3238
16 6425
18 79
24 5558
12 8367
14 8814
10 418

7 37 42
22 6799
31 6545
35 9390
40 2403
44 9008
23 8167
35 7860
9 4889
48 8558
21 4001
9 7732
20 8074
20 9935
5 2628
49 457
14 1360
5 7332
40 3166
19 2626
29 9291
8 436
21 2736
9 2589
8 1411
14 4117
8 2293
3 1035
35 1212
6 1203
33 5357
10 8540
2 2502
46 3467
50 2288
20 617
30 6931
10 2670

2 6 51
22 4135
28 8434
7 7828
18 3345
30 2539
24 5938

10 20 82
34 9653
9 8833
24 9175
28 940
23 6439
20 5302
33 2536
6 4982
50 9991
23 7086
26 3816
19 1795
6 8953
32 1318
8 7637
23 4132
46 6133
11 1883
17 3162
16 8984

11 26 6
18 3118
8 3738
29 702
45 2051
33 8952
24 3333
17 3593
15 7226
21 1151
47 8426
31 2747
20 655
18 9045
49 7183
28 2697
32 2761
32 8017
43 9013
6 4329
25 5052
33 9166
12 2415
40 9023
6 1655
30 5023
44 5681

16 15 56
29 5661
29 7031
8 4495
42 5559
13 2134
31 3218
15 8110
12 8037
24 11
5 5123
32 7944
8 9819
15 3411
3 6357
33 8491

21 20 25
38 5567
3 9959
7 2582
8 4378
11 6507
24 4479
14 1639
25 5947
3 4191
17 6946
48 388
34 2379
24 6777
37 8043
8 3703
41 7880
32 8260
1 2669
39 8413
8 504

2 41 61
30 5448
36 7690
23 7294
7 1088
39 5383
50 2722
26 8681
39 1403
14 4485
24 7754
41 5591
38 8406
28 2426
1 6681
16 4512
9 5235
44 8078
15 7031
45 4524
2 9145
25 9301
35 4748
34 6602
36 3698
10 4687
10 2856
43 8791
10 4441
2 4609
42 1375
9 7870
33 9094
23 7294
4 6230
21 4562
22 348
46 9002
41 7373
32 2159
35 7626
35 3661

13 6 55
36 4120
44 5777
9 6582
36 2133
45 6700
4 4777

18 15 41
39 7972
37 4270
4 4976
11 8206
18 626
45 5447
2 5433
41 2328
3 2959
7 1799
19 9453
22 2222
8 8296
42 3819
21 4258

8 15 86
18 6927
38 7230
11 7811
34 8510
17 7943
39 4245
46 6595
40 5963
40 6301
10 7192
40 1318
15 3988
9 4311
11 3340
13 5278

21 1 75
34 7608

5 12 67
31 2294
7 3204
21 6333
36 7559
38 857
43 8048
27 9967
5 7482
20 8317
32 6352
6 6027
46 6168

10 43 64
20 7252
33 3238
11 4989
13 4296
15 8862
12 8843
28 6656
43 5625
2 1095
17 4134
37 8186
18 9225
46 6057
3 435
30 2115
6 1595
45 1361
37 1074
14 4735
17 7821
12 7077
11 2389
33 881
37 4737
14 5772
17 3457
49 3678
2 5428
22 3459
40 2167
36 6752
18 5870
30 5875
3 6945
19 9665
47 6227
14 4359
4 8484
38 9588
31 547
15 6923
48 8731
38 5617

2 44 86
24 6368
23 3356
7 8889
15 1553
41 717
33 4705
49 7460
41 6064
35 9396
24 7097
22 7711
48 5804
20 8689
3 1785
1 7666
30 6723
3 3124
23 9571
28 753
24 9644
28 3754
21 8908
48 1452
48 9161
15 7114
26 313
13 5145
32 4814
50 119
16 751
1 678
32 5423
1 4322
12 6314
29 8294
33 7846
19 935
26 9773
46 5088
2 2516
39 3120
49 1687
48 4185
37 6008

1 41 50
39 73
25 1052
30 7529
47 2955
47 1960
19 426
19 9671
1 3467
2 3903
21 6701
27 8975
4 2670
2 4039
20 9951
32 2234
41 8657
10 6534
21 6689
28 8931
1 6142
37 6064
37 2173
19 3616
24 2022
6 2437
37 6937
22 1238
3 716
12 4032
50 2853
34 2246
11 2722
11 843
14 6147
24 2332
18 9118
20 6693
44 1244
21 2169
2 1175
17 906

4 34 77
6 8003
24 5283
42 6677
32 9427
38 7884
17 854
49 450
33 9588
37 4031
44 3773
19 5767
5 7560
1 6287
30 5722
31 8770
26 2028
14 7512
50 7335
42 4285
15 190
24 4083
18 8174
36 8638
23 859
38 9142
31 2581
50 5217
40 67
48 476
15 8317
8 620
21 4486
7 2277
47 2443

5 25 38
48 2749
36 8012
13 9189
9 9578
42 2785
6 5409
10 2485
5 7863
7 7422
48 7388
19 1617
43 7287
27 1018
6 2834
45 6977
27 7652
34 4494
27 8515
36 9501
20 7129
12 4390
40 8634
41 3634
44 7926
7 2385

21 16 17
34 1338
11 1739
1 4876
12 3699
47 6864
16 8171
39 6405
43 131
26 3847
32 6277
18 2149
46 3862
41 6963
18 9278
33 7617
22 9801

21 17 38
1 1367
14 4962
23 2430
46 216
38 461
3 6605
50 7334
50 9747
48 5160
21 4995
43 8715
43 9329
48 5532
17 6344
43 1272
33 1864
31 742

16 10 29
25 5185
31 6112
18 3213
43 2059
27 4290
23 9585
18 5279
6 3740
50 2785
42 673

16 19 78
11 5254
35 6031
16 8964
23 3745
5 6901
32 5094
14 5696
26 5933
46 7163
48 6603
42 705
45 3806
20 8026
28 4742
35 8030
14 2332
39 3840
2 1407
6 2910

3 10 9
36 6629
30 3233
11 333
16 2714
34 5486
5 8611
30 5145
2 4621
4 1212
24 1399

11 33 12
12 1101
16 8384
44 9951
48 2028
36 938
24 6168
9 9851
5 7366
38 9496
22 2242
6 6586
10 7853
24 7957
8 8901
18 9355
4 3013
4 190
10 6796
5 8650
34 9034
48 9228
17 4243
16 6419
47 8252
5 290
9 7598
29 8254
3 8410
13 3997
38 1317
9 3273
28 5828
14 3365

21 39 31
11 7397
8 1341
32 2419
44 5997
22 9859
34 9013
5 6527
48 4029
35 7786
28 6638
29 5030
50 6005
23 285
28 3785
20 8054
36 1268
37 6037
11 9325
35 6967
12 7563
35 7000
50 7037
10 5596
30 5944
3 5101
14 9717
6 3518
27 9386
6 1700
19 8248
26 8851
22 9293
30 642
8 2674
14 5047
34 9165
15 8644
43 4257
47 1496

0 0 0

My output:
46352.0
5 9 5 9 5 9 5 9
116619.0
26 11 26 11 26 1 26 1 26 1 26 1 26
84600.0
30 14 18 14 18 14 18 14 18 14
0.0
0.0
0.0
46635.0
17 11 17 27 17 31 17
16262.0
3 2
89081.0
13 2 13 2 13 2 13 20 13 2
0.0
55455.5
14 10 14 10 14 10 14 10 14 14 14 14 14 14 14 14
29259.5
18 2 18 2 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18
18446.0
21 20
7165.5
6 6 6 6 6 6 6 6 6 6 6 6 6
55542.5
7 9 7 7 9 7 9 7 7 9 7 9 7 7 7 7 7 7
60012.0
3 10 3 10 3 10 3 10
0.0
39275.0
8 11 9 8 7
82839.0
38 34 38 34 38 6 38 6 38 6
19417.0
38 20
9951.0
14
34739.0
8 1 8 12
42304.0
8 4 8 4 9
0.0
64459.5
6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 1 1 1 1 1
0.0
74117.0
5 5 19 18 5 18 5 18 5 18 5 18 5 3 5 5
17853.0
8 6 8
0.0
0.0

[shuniu]

My AC output:

Code: Select all

46352.0
9 5 9 5 9 5 9 5
116619.0
26 11 26 11 26 1 26 1 26 1 26 1 26
84600.0
30 14 18 14 18 14 18 14 18 14
0.0
0.0
0.0
48910.0
17 32 17 31 17 31 17
16262.0
3 2
89081.0
13 20 13 2 13 2 13 2 13 2
0.0
68169.5
14 14 14 14 10 14 14 10 14 14 10 14 14 10 14 14
31928.5
18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 2 18 18 2 18 18
18446.0
21 20
7165.5
6 6 6 6 6 6 6 6 6 6 6 6 6
63692.0
7 7 7 9 7 7 9 7 7 9 7 7 9 7 7 9 7 7
60012.0
10 3 10 3 10 3 10 3
0.0
40730.0
8 9 8 7 8
82839.0
38 34 38 34 38 6 38 6 38 6
19417.0
38 20
9951.0
14
35021.0
8 1 4 1
44460.0
4 8 4 8 4
0.0
67877.0
1 1 6 1 1 6 1 1 6 1 1 6 1 6 1 6 1 6 1 6 1
0.0
77567.5
5 5 19 5 18 5 18 5 18 5 18 5 18 5 3 5
17853.0
8 6 8
0.0
0.0

[Krzysztof Duleba]

Thank you for fast reply. Now I know that my idea was incorrect and my algo will need some changes.

[Robert Gerbicz]

I'm having hard time with this one and I don't know why. I'm using dynamic programming in O(n * k * m) time and O(k * m) memory.

My solution runs in O(n*k^2*m) time and using O(k*m*n) memory. But it works, and really fast: 0.01 sec. (first place).
I like this problem, very good and interesting in dp method.

[sikder1588]

Does the person have to cook a dish every day??
Can anyone give me the output for the following input??

Code: Select all

10 1 50
10 50
0 0 0

[brianfry713]

Yes, your input is similar to the first sample input. AC output

Code: Select all

0.0

My code is AC in 0.136 seconds and has a runtime of O(k*k*n*n*m), using O(k*k*n*m) memory.
I rewrote it with a runtime of O(k*n*n*m), using O(k*n*m) memory and got AC in 0.164 seconds. The difference was if I stored the full dish history per day or just a previous pointer.

[Helaluddin_brur]

removed