10980 - Lowest Price in Town

[Ivan]

Let Items[j] be the number of items in the j-th offer, P[j] is the the price in the j-th offer. Let's define a function F - the minimum price to buy exactly i items. Obviously F[0] = 0. The recurrence relation shoud be:
F = MIN(F[i - Items[j]] + P[j]), for every j for which Items[j] does not exceede i.
The answer is the smallest value of F in the interval from k (the number of items in the query) to some upper limit of items that might be necessary to buy to satisfy the conditions of the problem (I used 205).
This is a bit of a spoiler, but should we let Darko go insane?

[mamun]

100 is a key. 200 is the safe side. I've the feeling that you aren't considering the fact that buying more things can be cheaper, seriously. If you've passed my previously posted I/O then try the following
Input

Code: Select all

10.00 3
3 15.00
4 35.00
5 36.00
3 4 5 6 7 8 9 10 11 12 13 14 15
10.00 4
3 15.00
4 35.00
5 36.00
99 4.95
3 4 5 6 7 8 9 10 11 12 13 14 15 100

Output

Code: Select all

Case 1:
Buy 3 for $15.00
Buy 4 for $25.00
Buy 5 for $30.00
Buy 6 for $30.00
Buy 7 for $40.00
Buy 8 for $45.00
Buy 9 for $45.00
Buy 10 for $55.00
Buy 11 for $60.00
Buy 12 for $60.00
Buy 13 for $70.00
Buy 14 for $75.00
Buy 15 for $75.00
Case 2:
Buy 3 for $4.95
Buy 4 for $4.95
Buy 5 for $4.95
Buy 6 for $4.95
Buy 7 for $4.95
Buy 8 for $4.95
Buy 9 for $4.95
Buy 10 for $4.95
Buy 11 for $4.95
Buy 12 for $4.95
Buy 13 for $4.95
Buy 14 for $4.95
Buy 15 for $4.95
Buy 100 for $9.90

[Darko]

Ivan, thanks for trying to help bratko, but it seems that I'm inside the Twilight Zone.

Mamun, I get the same results as you do.

What the worst part is, I see why Ivan's algorithm works, but I can't see why my doesn't (and it obviously doesn't).

I reimplemented my solution according to Ivan's instructions, it works OK on my PC (well, I just keep getting the same answers), but it keeps crashing on OJ (WA in 0.006 or something).

I narrowed it down to the line of code. Which adds two integers. With any non-zero integers, it crashes there. I have no idea what's going on. Well, must be the Twilight Zone.

I will get 100 more WAs then I will post the complete code, I really have no idea what to do.

Darko

[tan_Yui]

Hi, Darko.
Although your idea uses mathematical methods in some part,
my idea is DP solution like knapsack.
This DP is same as Ivan's one, probably.
If your algorithm are correct and got WA, your code may be included any small bugs.

By the way, I also prepare the I/O.

Code: Select all

50.00 3
2 22.00
4 60.00
6 18.00
1 2 3 4 5 6 8 12
50.00 4
2 22.00
4 44.44
6 60.00
3 29.50
1 2 3 4 5 6

Output should be :

Code: Select all

Case 1:
Buy 1 for $18.00
Buy 2 for $18.00
Buy 3 for $18.00
Buy 4 for $18.00
Buy 5 for $18.00
Buy 6 for $18.00
Buy 8 for $36.00
Buy 12 for $36.00
Case 2:
Buy 1 for $22.00
Buy 2 for $22.00
Buy 3 for $29.50
Buy 4 for $44.00
Buy 5 for $51.50
Buy 6 for $59.00

Best regards.

[Ivan]

Darko, this is some randomly generated input:

Code: Select all

834.82 5
31 373.46
6 338.80
25 759.83
14 592.36
35 108.96
86 76 59 58 93 71 14 80 13 48 
636.92 5
77 324.87
83 641.32
7 876.63
88 468.90
16 188.20
13 4 94 63 78 16 34 99 38 34 
652.03 5
34 13.19
71 852.35
26 30.49
74 349.60
27 37.44
12 19 4 94 87 66 4 41 59 91 
225.43 5
93 217.56
58 719.06
43 276.05
49 128.63
65 281.24
78 2 77 1 40 61 59 39 88 38 
147.08 5
69 302.21
78 7.47
24 686.74
12 909.41
34 99.68
34 99 58 79 90 19 4 66 16 62 
717.11 5
1 481.65
90 779.53
28 967.61
2 729.66
66 993.37
37 59 90 12 61 21 85 19 9 81 
86.86 5
19 560.57
49 52.16
82 117.07
70 697.64
9 234.66
72 99 20 51 8 87 71 11 49 61 
484.45 5
26 424.79
63 374.31
92 755.60
24 356.70
49 371.93
8 29 10 29 8 14 19 3 33 76 
739.36 5
63 495.31
47 548.63
77 525.20
35 1.25
96 912.89
90 62 80 74 44 59 0 47 38 48 
443.27 5
92 908.96
31 735.10
52 687.96
91 375.62
3 580.25
31 73 9 84 48 64 37 42 41 37 
123.45 0
1 2 3 5 7 9

and my corresponding output:

Code: Select all

Case 1:
Buy 86 for $326.88
Buy 76 for $326.88
Buy 59 for $217.92
Buy 58 for $217.92
Buy 93 for $326.88
Buy 71 for $326.88
Buy 14 for $108.96
Buy 80 for $326.88
Buy 13 for $108.96
Buy 48 for $217.92
Case 2:
Buy 13 for $188.20
Buy 4 for $188.20
Buy 94 for $649.74
Buy 63 for $324.87
Buy 78 for $468.90
Buy 16 for $188.20
Buy 34 for $324.87
Buy 99 for $649.74
Buy 38 for $324.87
Buy 34 for $324.87
Case 3:
Buy 12 for $13.19
Buy 19 for $13.19
Buy 4 for $13.19
Buy 94 for $39.57
Buy 87 for $39.57
Buy 66 for $26.38
Buy 4 for $13.19
Buy 41 for $26.38
Buy 59 for $26.38
Buy 91 for $39.57
Case 4:
Buy 78 for $217.56
Buy 2 for $128.63
Buy 77 for $217.56
Buy 1 for $128.63
Buy 40 for $128.63
Buy 61 for $217.56
Buy 59 for $217.56
Buy 39 for $128.63
Buy 88 for $217.56
Buy 38 for $128.63
Case 5:
Buy 34 for $7.47
Buy 99 for $14.94
Buy 58 for $7.47
Buy 79 for $14.94
Buy 90 for $14.94
Buy 19 for $7.47
Buy 4 for $7.47
Buy 66 for $7.47
Buy 16 for $7.47
Buy 62 for $7.47
Case 6:
Buy 37 for $779.53
Buy 59 for $779.53
Buy 90 for $779.53
Buy 12 for $779.53
Buy 61 for $779.53
Buy 21 for $779.53
Buy 85 for $779.53
Buy 19 for $779.53
Buy 9 for $779.53
Buy 81 for $779.53
Case 7:
Buy 72 for $104.32
Buy 99 for $156.48
Buy 20 for $52.16
Buy 51 for $104.32
Buy 8 for $52.16
Buy 87 for $104.32
Buy 71 for $104.32
Buy 11 for $52.16
Buy 49 for $52.16
Buy 61 for $104.32
Case 8:
Buy 8 for $356.70
Buy 29 for $371.93
Buy 10 for $356.70
Buy 29 for $371.93
Buy 8 for $356.70
Buy 14 for $356.70
Buy 19 for $356.70
Buy 3 for $356.70
Buy 33 for $371.93
Buy 76 for $731.01
Case 9:
Buy 90 for $3.75
Buy 62 for $2.50
Buy 80 for $3.75
Buy 74 for $3.75
Buy 44 for $2.50
Buy 59 for $2.50
Buy 47 for $2.50
Buy 38 for $2.50
Buy 48 for $2.50
Case 10:
Buy 31 for $375.62
Buy 73 for $375.62
Buy 9 for $375.62
Buy 84 for $375.62
Buy 48 for $375.62
Buy 64 for $375.62
Buy 37 for $375.62
Buy 42 for $375.62
Buy 41 for $375.62
Buy 37 for $375.62
Case 11:
Buy 1 for $123.45
Buy 2 for $246.90
Buy 3 for $370.35
Buy 5 for $617.25
Buy 7 for $864.15
Buy 9 for $1111.05

Hope it helps to catch the bug...

[Darko]

Thanks guys for going through this trouble...

I did find a small difference in Ivan's output, I printed "Buy 0 for $0.00" for k=0, changed that to ignore input out of bounds, but still WA (everything else is the same).

I got it finally accepted, I changed the array of pairs into two arrays. But that is with Ivan's algorithm. Mine is still not working, but no idea why, I haven't seen the case that breaks it.

Darko

[C]

I had the same output with all the given input. And I use DP.
But I got WA. I don't even know where may be wrong.
Can anyone help me, I can send my code to u.

[arsalan_mousavian]

actually i have solved this problem long time ago , at first i got WA because i didn't consider that we can use items more than once ( of course if it has more profit ) , i hope it helps

[C]

actually i have solved this problem long time ago , at first i got WA because i didn't consider that we can use items more than once ( of course if it has more profit ) , i hope it helps

arsalan,thanks,but i have thought this point. Well I use DP, and the recurrence looks like,
p[n]= min(p[n-c]+q),i=0,..,n
where c is the count of items that must be bought and q is the price,and I use c[0]=1, q[0]=price of each item,and the basis case is for k<=0,p[k]=0;

I really got the same output for all given input here, And I want to post my code here,but I know someone doesn't like that. So PLS give more test input or give me a PN, and I send my code to You. Thanks!

[DD]

actually i have solved this problem long time ago , at first i got WA because i didn't consider that we can use items more than once ( of course if it has more profit ) , i hope it helps

arsalan,thanks,but i have thought this point. Well I use DP, and the recurrence looks like,

p[n]= min(p[n-c]+q),i=0,..,n

where c is the count of items that must be bought and q is the price,and I use c[0]=1, q[0]=price of each item,and the basis case is for k<=0,p[k]=0;



I really got the same output for all given input here, And I want to post my code here,but I know someone doesn't like that. So PLS give more test input or give me a PN, and I send my code to You. Thanks!

I think your DP formula is fine, maybe you should try to use large size of array such that all possible answers can be retained.

[brianfry713]

Input:

Code: Select all

93.84 4
16 27.78
36 77.94
93 53.87
22 66.50
28 91 60
77.64 7
27 5.41
37 91.73
69 52.12
30 25.68
31 57.83
24 28.63
36 40.68
3 23 59 70 68 94 57 12 43 30
73.74 12
85 49.20
99 85.38
16 43.25
14 43.71
92 35.27
57 89.81
63 18.74
97 91.71
6 72.82
85 9.26
37 63.28
47 65.06
14 58 25 96 83 46 15 68 35 65
40.44 14
9 10.88
79 72.77
85 57.89
52 54.04
100 27.55
61 99.33
69 96.77
13 77.40
87 62.27
40 80.95
71 7.96
79 14.35
2 74.68
3 0.98
93 53 57 2 81 87 42 66 90 45 20 41 30 32 18 98 72 82
6.76 15
68 89.28
98 78.57
87 23.54
7 69.66
20 46.84
29 86.25
33 28.72
4 88.30
71 0.20
9 33.69
41 67.16
97 81.50
19 7.24
47 22.46
22 34.52
80 89 65 29 42 51 94 1 35 65 25 15 88 57 44 92
22.28 1
37 98.60
52 38 29 76 8 75 22 59 96 30 38 36 94
58.19 5
12 61.44
30 59.29
5 87.77
64 44.44
39 46.14
41 5 19 29 89 70 18
99.18 6
44 33.25
84 94.71
100 84.91
26 97.73
91 56.45
40 75.06
87 70 83 43 65 98 8 56 5 49 12 23 29 100 44
57.47 8
23 43.41
11 33.12
2 76.06
31 56.62
6 48.79
37 93.21
27 94.45
66 85.23
17 83 59 25 38 63 25 1 37
34.53 8
51 93.80
72 74.69
32 9.74
31 38.82
95 89.34
64 86.61
82 72.00
97 89.00
74 14 69 91 96 27 67 85 41 91 85 77 43 37 8 46 57 80 19 88
94.13 1
60 21.73
37 11 43 88 7 2 14 73 22 56
48.20 13
5 77.22
12 59.40
68 39.41
29 17.06
51 11.28
59 59.85
25 39.21
70 24.23
82 13.97
85 56.31
73 92.93
51 76.73
86 76.26
100 41 43
38.99 14
91 22.99
91 5.25
82 82.10
37 88.20
56 77.33
5 59.95
70 3.80
77 52.74
56 88.51
43 18.61
85 55.80
6 19.94
68 76.22
14 25.05
55 27
42.60 7
3 82.03
85 35.07
43 20.22
29 8.69
73 51.90
59 99.09
37 4.99
54 49 4 34 34 49 91 55 68
17.47 2
1 95.30
89 80.47
50 91 4 34 64 98 54 93 87 26 53 97 76 89 58 30 37 61
34.15 0
5
0.29 19
49 80.51
3 75.57
98 47.95
44 87.00
3 10.40
4 4.29
82 45.01
39 76.48
52 61.60
35 25.36
93 43.40
28 22.16
30 5.05
65 0.50
30 82.86
36 53.44
1 31.78
72 52.39
90 69.50
89 93 96 44 45 30 91 83
53.41 12
27 5.70
62 42.33
61 60.43
24 91.18
82 67.62
91 63.10
97 54.26
78 63.68
91 42.35
25 16.27
15 60.58
6 31.69
13 87 1 47 27 95 17 53 79 30 47 91 48 71 52 81 32 94 58
86.28 17
15 18.87
13 83.56
13 0.91
11 94.80
90 89.70
56 22.75
21 76.42
88 54.34
39 78.89
71 45.67
57 72.85
7 4.18
50 22.61
6 2.38
18 30.60
46 85.19
74 7.84
74 38 90 84 8 79 58 15 72 30 1 60 19 39 26 89 75 34 58
36.82 18
71 3.59
18 7.00
70 18.40
23 83.64
74 87.95
32 98.48
83 74.63
93 93.91
58 57.92
22 51.16
75 61.58
48 14.92
32 29.52
38 50.22
55 37.41
99 40.31
82 53.26
17 75.17
32 40 97
54.05 5
19 45.81
71 90.22
13 98.63
78 53.80
37 26.86
77 84 8 60 58
97.45 18
28 99.12
37 39.51
19 75.61
64 51.06
45 0.50
6 87.12
92 99.35
56 73.76
90 36.15
94 37.69
6 49.19
23 68.83
18 69.83
94 40.31
27 15.75
87 65.94
44 2.54
15 30.75
80 78 63 76 89 20 11 33 95 18 47 36 38 92
51.54 14
29 25.74
92 9.26
19 67.11
37 72.18
56 69.64
59 70.91
5 81.31
62 85.72
86 96.34
74 47.90
52 26.05
51 98.06
4 78.69
7 94.86
40 50 21 68 27 64 78 97 82 66 61 37 56 71 19 12
63.43 5
80 51.97
71 73.22
73 49.85
35 44.28
84 20.41
99 31 64 48 51 31 74 15 60 23 48 25 83
94.36 9
55 92.05
99 4.44
41 54.87
60 42.79
63 2.63
42 96.84
24 98.49
73 83.25
55 91.23
22 58 66 48 72 77 70 19 2 4 54 34 8 60 29 7
57.98 9
9 70.85
99 53.35
77 9.92
16 88.99
72 10.53
60 81.90
11 25.07
25 90.17
40 31.10
79
81.10 18
15 50.82
90 13.39
68 94.27
24 51.48
32 67.88
23 65.33
76 12.82
80 48.51
55 65.91
32 53.51
58 38.14
82 14.95
4 60.82
34 57.21
82 79.83
16 74.88
26 92.97
23 54.05
52 98 33 35 82 7 16 58 9 96 100 63 98
74.84 10
78 1.55
88 13.10
83 99.33
67 50.22
61 35.64
12 36.83
87 76.86
31 42.86
84 59.91
77 73.15
21 93 26 29 40 26 91 37 61 19 44 38 29 83 22 11 56
8.89 20
71 68.16
54 34.38
23 0.09
51 17.84
98 86.58
27 38.28
72 12.70
50 66.52
29 9.11
99 6.40
11 18.89
78 23.94
77 38.91
53 52.00
88 69.32
100 87.78
67 6.58
18 9.53
36 26.42
99 93.69
96 77 6 67 29
89.55 19
94 3.09
98 72.79
73 25.56
46 7.75
26 50.01
84 9.98
28 84.13
22 83.83
35 46.94
35 24.40
60 84.22
58 49.86
62 13.55
73 87.63
17 15.42
51 18.53
83 36.63
18 4.00
74 51.55
7 52 65 91 64 92 73 38 38 60 29 72 81 88 57 91
83.42 15
66 53.53
70 55.12
62 95.18
52 30.84
1 41.13
39 65.07
65 46.68
33 14.90
5 41.55
80 98.76
13 61.42
70 25.39
71 6.37
45 19.57
50 27.61
66 15 27 87 84 40 70 36 53 22 94 91 90 10 32
46.74 5
49 57.36
78 42.96
34 43.14
50 31.99
56 93.56
69 57 61 34 24 87 72 59 78 41 46 82 62 91
3.24 7
55 41.01
65 10.76
25 20.43
20 26.60
45 62.90
39 34.70
77 15.52
20 34 44 5
19.57 4
67 24.76
68 80.12
93 69.13
3 17.30
32 3 75 8 19 17 84 78 88
74.73 13
63 89.58
34 61.26
97 67.98
42 34.19
27 81.54
81 54.75
86 53.94
6 59.49
30 0.31
99 95.60
63 21.61
20 64.25
42 42.81
11 81 27
75.84 16
9 41.41
39 27.24
94 25.58
11 4.32
6 42.21
14 76.91
39 93.92
22 82.71
30 76.68
81 26.72
96 87.44
25 39.00
55 70.89
70 23.87
70 82.33
74 57.11
34 64 88 80 95 50 100 52 40 65 43
73.31 4
50 75.16
87 99.16
12 38.82
34 56.35
23 88 74 44 20 43 55 45
31.25 7
64 62.60
54 74.19
70 17.13
5 87.06
100 27.34
20 27.35
36 43.16
54 70 51 88 3 38 63 90
36.11 17
5 59.61
58 69.12
4 98.30
93 88.17
23 8.22
44 36.06
62 65.80
79 15.29
1 44.48
83 40.46
100 37.88
90 55.52
54 13.87
49 94.27
37 47.95
8 85.07
18 60.93
22 21 81 67 95
63.55 17
34 84.38
18 94.85
32 63.13
10 90.18
57 51.66
70 16.09
96 17.46
72 74.23
70 62.96
2 5.60
53 56.77
41 65.72
44 89.26
92 1.73
28 40.90
79 35.67
51 58.13
25 34 14 87 100 71 95 69 16 42 43 40 38 64 99 91 40
62.03 20
29 16.32
5 82.58
47 45.72
39 46.84
96 12.26
22 75.41
27 89.73
59 6.35
57 57.26
46 9.53
47 54.73
12 33.40
4 58.84
26 76.62
17 75.43
75 23.40
97 53.45
68 73.31
14 92.95
20 7.58
51
32.93 20
80 18.77
54 19.91
96 6.36
8 15.99
38 27.42
77 5.71
85 25.41
84 8.02
93 48.01
97 56.10
40 64.41
36 27.64
74 13.05
65 26.07
52 45.24
52 43.50
40 25.31
66 67.05
3 19.87
80 56.26
48 8 85 32 62 20 32 54 29 28 95 20
75.44 19
69 11.24
40 1.88
39 46.44
95 19.89
81 13.21
87 40.99
53 30.19
99 64.64
11 46.96
80 65.06
67 61.43
26 80.99
79 14.73
67 28.54
49 47.98
73 45.48
87 5.17
60 99.13
1 98.78
98 33 4 36 52 8 99 50 55 62 7 35 4 26
67.85 6
64 67.98
16 36.34
82 65.61
86 10.15
1 8.98
9 50.98
50 14 80 35 17 15 86 76 66 87
79.31 19
17 78.93
70 66.30
10 97.53
16 63.67
34 73.96
77 44.29
14 38.48
1 50.27
87 10.63
64 6.30
9 51.01
17 33.98
83 7.76
41 45.45
27 33.21
66 65.19
100 17.95
47 71.35
54 69.09
4 87 43
84.33 15
11 98.08
70 88.35
16 35.97
97 79.85
83 23.25
52 44.66
62 97.17
38 93.44
62 41.88
82 6.03
89 53.61
21 38.80
94 39.42
29 29.25
9 71.36
43 71 97
41.64 0
1 16 88 35 33 91 51 94 34 40 81 95
22.94 4
83 28.55
76 54.45
39 3.24
52 7.52
12 66 69 82 14 84 100 78 36 15 65 70 47 8
30.73 1
12 57.41
88 58 37 94
34.40 12
15 66.21
72 83.72
97 34.19
84 85.35
68 97.65
1 46.98
75 60.68
34 3.36
58 54.91
50 21.33
24 5.30
93 16.91
30 50 36 23 41 69 44 56
3.40 9
37 20.26
61 16.54
21 70.53
5 29.58
84 12.88
22 95.41
98 48.27
28 72.06
29 38.79
71 28 99 21 64 22 61 84 17 68
82.24 2
12 42.93
54 70.36
9 63 69 96
11.99 19
77 49.69
74 10.10
88 95.04
74 12.55
82 40.58
30 38.24
45 43.97
81 19.43
10 80.13
48 68.56
67 48.55
60 31.35
43 12.82
2 19.74
72 16.39
59 34.14
23 19.00
56 14.85
91 56.62
72
39.24 14
21 80.01
43 20.01
13 69.53
8 5.05
59 97.60
95 25.26
59 91.18
91 46.37
27 95.61
74 6.15
66 19.38
22 37.49
10 66.21
1 88.64
87 5 34 59 57 28 11 69 32 70 29 42 47
53.75 3
11 36.06
66 49.02
68 89.90
27 33 39 100 6 1 63 58 33 49 62
0.18 13
98 61.70
39 5.70
40 91.29
71 50.19
93 85.86
43 12.81
34 67.55
44 17.08
51 44.01
86 30.22
21 67.89
41 51.91
48 96.35
84 62 95 43 31 92
50.64 11
55 33.21
43 5.39
31 14.93
35 84.23
9 76.86
81 80.95
45 17.09
46 28.03
23 17.85
26 10.88
36 61.58
93 49 97
89.87 6
50 8.41
13 70.52
90 69.57
49 76.55
29 48.73
58 84.83
77 38 98 21 40 95 6 15 83
2.83 5
37 28.70
18 50.16
54 18.85
25 93.00
51 7.55
11 93 43 59 65 24 42 22 12 70 11 61 91 3 56 48 17
10.90 13
59 64.40
7 80.18
2 53.76
75 45.12
66 89.79
67 73.78
70 29.77
35 21.62
37 28.34
7 1.28
98 30.00
61 33.17
71 68.40
87 87 9 68 78 67 37 36
86.94 13
20 49.47
13 53.68
35 70.97
18 95.41
75 60.96
32 39.51
9 88.03
52 36.31
43 5.26
48 96.91
77 11.62
70 79.35
64 47.96
32 52 81 21 98 1 89 62 97 75 2 15 70 29 17 53
85.83 19
34 36.83
78 85.03
50 11.24
52 67.91
61 72.36
100 49.47
30 84.48
29 15.03
100 75.50
90 5.29
77 90.14
67 75.64
85 39.91
60 71.95
77 70.37
72 63.85
39 72.10
85 27.01
91 5.40
76 51 82 27 51 63 29 79 65 80 59 54 45 35 70 12
69.78 4
37 62.58
35 11.43
66 44.73
11 55.96
33 50 8 68 77 59
76.02 16
64 51.61
39 20.83
15 62.28
34 17.97
31 9.59
70 65.55
60 54.08
96 99.28
14 18.02
19 79.68
30 2.61
93 63.36
44 26.32
8 47.13
14 93.54
14 16.63
97 52 57 11 100 42 70 82 96
30.91 6
70 78.55
9 77.37
5 76.83
96 87.27
15 57.34
65 11.88
52 25 11 65 39 24 94 35 27 2 46 26 95 67 7 90 57 48
27.96 4
4 27.85
41 38.61
56 38.83
49 5.74
91 6 47 67 68 64 5 91 9 91 69 62 36 94 56 2
62.52 5
52 94.11
89 82.92
48 4.36
76 94.49
57 36.82
30
96.52 18
50 78.35
2 95.61
65 91.65
73 70.44
12 19.56
43 67.34
41 32.57
60 24.97
59 91.37
29 35.11
98 38.47
95 8.76
57 19.25
26 72.51
54 98.86
72 43.20
81 35.56
20 73.25
68 45 4 31 30 47 87 71 95 46 59 53 9 87 99 6 14
73.45 9
48 44.22
59 2.08
79 42.01
8 47.30
54 47.59
8 31.80
76 27.73
3 92.11
9 59.05
27
79.03 3
7 44.86
24 9.47
52 58.05
2 34 11 49 93 70 1 72 51 9 82 57 88 89 29 63 52 84
67.19 10
46 14.24
62 15.15
73 31.83
58 58.08
12 81.30
31 72.95
58 57.45
38 80.79
79 71.27
29 57.61
42 85 26 83 66 40 34
8.49 16
24 34.45
11 50.56
90 34.86
45 72.84
13 12.47
94 65.56
1 30.43
21 99.51
29 57.90
50 65.51
38 0.57
42 70.43
25 59.15
55 34.59
59 81.10
55 82.65
20 17
91.19 5
64 65.00
64 55.07
100 13.19
71 13.06
78 67.02
30 29 13 87 18 56 80 84 80 90 38 90
52.48 15
81 49.96
12 45.25
85 100.00
15 7.12
27 6.44
43 87.85
8 66.33
62 40.97
26 72.19
32 34.42
11 7.64
95 42.87
18 68.95
84 28.36
83 30.59
54 16 14 18 15 99 81 81 42 7 65 36 39 24 32 53 43 10
55.46 2
57 78.25
72 44.64
81 7 86
34.92 17
45 91.75
89 86.57
71 1.62
42 27.39
80 31.03
19 68.49
39 37.67
51 40.43
85 29.43
89 9.60
36 44.62
25 25.97
99 12.07
14 93.57
48 44.36
63 34.55
11 7.45
58 33 41
94.52 1
100 51.72
90 90 47 40 85
75.83 11
44 12.73
69 79.87
93 73.20
77 38.19
54 56.58
64 58.76
20 82.16
70 39.26
10 38.78
81 67.10
33 45.96
1 23 21 47 14 57 30 65 29 25 51 49
77.45 7
73 66.19
73 38.05
68 66.48
20 94.40
10 31.94
55 98.49
29 17.71
56 60 51 30 32 49 43 89 78 7 69
39.55 17
99 43.70
88 43.04
8 24.71
70 22.12
4 37.27
72 14.41
89 30.65
87 55.27
77 8.17
28 75.42
23 30.79
27 30.60
100 17.66
24 54.05
59 99.68
89 5.33
88 74.09
31 95 40 52 73 43 93 45 7 81 23 94 50 99 87 29 77
65.10 9
27 82.03
59 11.39
59 26.50
82 56.69
29 81.47
75 7.21
15 56.59
63 64.15
57 57.40
36 16 35 58 61 36 8 47 65 84 56 4 38 34 43
33.49 20
69 93.01
47 72.17
38 11.50
60 36.22
88 43.04
43 32.22
76 10.44
11 47.78
87 94.63
98 8.71
18 28.94
29 20.62
18 88.25
59 87.67
67 9.60
60 78.94
10 1.87
36 40.58
31 30.47
3 44.96
17 97 14 93 75 24 7 61 95 4 7 64 18 35 40 35 53 50
88.94 8
5 64.43
5 0.06
93 59.14
45 73.03
5 21.88
57 3.62
27 11.02
28 67.49
55 40 97 10 46 12 27 81 3 13 33
95.53 11
47 22.04
61 36.62
28 2.51
54 62.53
41 58.72
85 85.58
11 10.49
49 71.12
14 83.38
78 35.55
64 86.62
25 43 55 27 55 40 79 65 43 26 78 3 28 5 55
83.81 18
91 59.47
95 1.61
24 93.01
91 11.43
97 54.89
50 26.20
94 44.13
55 18.26
52 14.49
88 3.61
25 23.83
60 19.30
84 19.03
7 37.87
68 43.38
37 75.35
47 18.10
10 36.31
26 52 58 74 71 59 86 65 84 40
15.65 12
4 60.53
77 83.69
28 54.33
68 4.31
38 14.67
34 93.05
93 15.72
18 17.95
56 22.76
1 96.39
48 7.08
78 55.74
60 94 93 51 58 79 3 61 48 32 45 27 62 12 93 99 69 78
48.22 2
91 62.72
80 32.88
88
25.87 20
64 86.14
25 74.37
29 86.10
67 49.75
30 17.60
59 50.28
72 76.61
74 64.85
30 98.36
4 1.25
46 81.59
83 32.16
4 80.89
69 26.62
48 95.43
56 55.01
37 89.63
72 16.32
59 77.18
77 26.39
18 35 100 41 71 73 28 52
91.97 8
95 76.11
93 50.99
54 85.83
3 10.54
53 38.48
56 76.55
92 16.15
39 99.87
45
45.29 18
46 74.84
35 34.23
45 20.38
66 51.08
56 49.97
7 72.48
98 11.50
84 73.51
4 30.03
51 82.39
93 10.56
22 52.06
92 28.36
96 9.12
40 44.89
24 79.84
58 3.37
27 43.59
66 92 51
1.21 7
23 36.09
59 63.89
91 0.58
96 93.62
69 62.41
98 5.41
76 21.42
54 24
38.30 12
53 15.59
17 15.34
60 65.11
28 89.71
73 43.51
41 88.01
75 35.81
39 47.81
72 28.32
80 39.00
20 67.64
62 80.20
47 55 18 70 84 63 29 88 96 97 51 55 67
41.30 15
30 11.39
19 42.97
30 20.56
88 56.09
8 96.01
16 87.19
38 28.79
91 36.29
83 8.36
6 33.09
23 43.18
58 86.86
82 70.70
24 87.08
37 84.00
90 19 28 8 74 57 16 13 9 75 31 77 5 20 57 47 56 40 7 13
65.09 10
66 88.98
31 21.98
73 84.73
62 45.30
19 44.04
84 61.32
57 73.78
45 55.92
53 20.70
52 83.71
27 24 85 73 31 76 80 95 85
92.60 1
10 72.50
75 82 3 36 38 73 67 21 2 75 12 46 44 16
81.68 0
94 23 81 18
92.05 6
99 3.97
9 15.92
94 22.90
63 38.18
51 72.68
55 1.17
41 73 60 42 47 24 39 43
0.39 17
83 15.90
64 82.51
68 48.15
22 94.68
66 76.17
25 68.66
59 44.07
21 74.42
92 93.26
80 79.89
29 98.32
91 82.52
98 39.70
60 3.14
53 7.92
33 39.17
67 83.87
1 86 15 74 2 80 39 78 38 97 19 58 74 63 46 5
31.94 6
36 67.08
6 17.47
6 49.50
54 65.49
82 18.74
40 0.40
92 78 92 65 31 23 56 9 61 52 27 70 78 41 16 82 34
51.93 20
40 20.70
71 11.47
95 48.97
71 50.24
15 29.76
5 71.62
39 10.06
22 26.96
70 0.70
78 51.77
81 24.30
100 10.56
97 52.58
39 27.67
59 90.82
3 56.80
26 12.50
47 72.25
48 8.73
48 29.17
78 52
10.19 20
41 64.99
69 34.38
67 16.17
97 3.50
49 10.22
70 19.06
97 84.67
78 17.52
6 78.76
54 40.27
73 28.31
30 19.26
73 30.89
19 14.44
62 95.77
27 28.87
24 89.02
71 39.95
97 62.90
63 35.19
25 33 64 21 36 41 48 93 19 1 23 44 26 5 84 51 48

AC otuput:

Code: Select all

Case 1:
Buy 28 for $53.87
Buy 91 for $53.87
Buy 60 for $53.87
Case 2:
Buy 3 for $5.41
Buy 23 for $5.41
Buy 59 for $16.23
Buy 70 for $16.23
Buy 68 for $16.23
Buy 94 for $21.64
Buy 57 for $16.23
Buy 12 for $5.41
Buy 43 for $10.82
Buy 30 for $10.82
Case 3:
Buy 14 for $9.26
Buy 58 for $9.26
Buy 25 for $9.26
Buy 96 for $18.52
Buy 83 for $9.26
Buy 46 for $9.26
Buy 15 for $9.26
Buy 68 for $9.26
Buy 35 for $9.26
Buy 65 for $9.26
Case 4:
Buy 93 for $15.80
Buy 53 for $7.96
Buy 57 for $7.96
Buy 2 for $0.98
Buy 81 for $11.88
Buy 87 for $13.84
Buy 42 for $7.96
Buy 66 for $7.96
Buy 90 for $14.82
Buy 45 for $7.96
Buy 20 for $6.86
Buy 41 for $7.96
Buy 30 for $7.96
Buy 32 for $7.96
Buy 18 for $5.88
Buy 98 for $15.92
Buy 72 for $8.94
Buy 82 for $11.88
Case 5:
Buy 80 for $0.40
Buy 89 for $0.40
Buy 65 for $0.20
Buy 29 for $0.20
Buy 42 for $0.20
Buy 51 for $0.20
Buy 94 for $0.40
Buy 1 for $0.20
Buy 35 for $0.20
Buy 65 for $0.20
Buy 25 for $0.20
Buy 15 for $0.20
Buy 88 for $0.40
Buy 57 for $0.20
Buy 44 for $0.20
Buy 92 for $0.40
Case 6:
Buy 52 for $197.20
Buy 38 for $120.88
Buy 29 for $98.60
Buy 76 for $241.76
Buy 8 for $98.60
Buy 75 for $219.48
Buy 22 for $98.60
Buy 59 for $197.20
Buy 96 for $295.80
Buy 30 for $98.60
Buy 38 for $120.88
Buy 36 for $98.60
Buy 94 for $295.80
Case 7:
Buy 41 for $44.44
Buy 5 for $44.44
Buy 19 for $44.44
Buy 29 for $44.44
Buy 89 for $88.88
Buy 70 for $88.88
Buy 18 for $44.44
Case 8:
Buy 87 for $56.45
Buy 70 for $56.45
Buy 83 for $56.45
Buy 43 for $33.25
Buy 65 for $56.45
Buy 98 for $84.91
Buy 8 for $33.25
Buy 56 for $56.45
Buy 5 for $33.25
Buy 49 for $56.45
Buy 12 for $33.25
Buy 23 for $33.25
Buy 29 for $33.25
Buy 100 for $84.91
Buy 44 for $33.25
Case 9:
Buy 17 for $43.41
Buy 83 for $128.64
Buy 59 for $85.23
Buy 25 for $56.62
Buy 38 for $85.23
Buy 63 for $85.23
Buy 25 for $56.62
Buy 1 for $33.12
Buy 37 for $85.23
Case 10:
Buy 74 for $29.22
Buy 14 for $9.74
Buy 69 for $29.22
Buy 91 for $29.22
Buy 96 for $29.22
Buy 27 for $9.74
Buy 67 for $29.22
Buy 85 for $29.22
Buy 41 for $19.48
Buy 91 for $29.22
Buy 85 for $29.22
Buy 77 for $29.22
Buy 43 for $19.48
Buy 37 for $19.48
Buy 8 for $9.74
Buy 46 for $19.48
Buy 57 for $19.48
Buy 80 for $29.22
Buy 19 for $9.74
Buy 88 for $29.22
Case 11:
Buy 37 for $21.73
Buy 11 for $21.73
Buy 43 for $21.73
Buy 88 for $43.46
Buy 7 for $21.73
Buy 2 for $21.73
Buy 14 for $21.73
Buy 73 for $43.46
Buy 22 for $21.73
Buy 56 for $21.73
Case 12:
Buy 100 for $22.56
Buy 41 for $11.28
Buy 43 for $11.28
Case 13:
Buy 55 for $3.80
Buy 27 for $3.80
Case 14:
Buy 54 for $9.98
Buy 49 for $9.98
Buy 4 for $4.99
Buy 34 for $4.99
Buy 34 for $4.99
Buy 49 for $9.98
Buy 91 for $14.97
Buy 55 for $9.98
Buy 68 for $9.98
Case 15:
Buy 50 for $80.47
Buy 91 for $115.41
Buy 4 for $69.88
Buy 34 for $80.47
Buy 64 for $80.47
Buy 98 for $160.94
Buy 54 for $80.47
Buy 93 for $150.35
Buy 87 for $80.47
Buy 26 for $80.47
Buy 53 for $80.47
Buy 97 for $160.94
Buy 76 for $80.47
Buy 89 for $80.47
Buy 58 for $80.47
Buy 30 for $80.47
Buy 37 for $80.47
Buy 61 for $80.47
Case 16:
Buy 5 for $170.75
Case 17:
Buy 89 for $1.00
Buy 93 for $1.00
Buy 96 for $1.00
Buy 44 for $0.50
Buy 45 for $0.50
Buy 30 for $0.50
Buy 91 for $1.00
Buy 83 for $1.00
Case 18:
Buy 13 for $5.70
Buy 87 for $22.80
Buy 1 for $5.70
Buy 47 for $11.40
Buy 27 for $5.70
Buy 95 for $22.80
Buy 17 for $5.70
Buy 53 for $11.40
Buy 79 for $17.10
Buy 30 for $11.40
Buy 47 for $11.40
Buy 91 for $22.80
Buy 48 for $11.40
Buy 71 for $17.10
Buy 52 for $11.40
Buy 81 for $17.10
Buy 32 for $11.40
Buy 94 for $22.80
Buy 58 for $17.10
Case 19:
Buy 74 for $5.46
Buy 38 for $2.73
Buy 90 for $6.37
Buy 84 for $6.37
Buy 8 for $0.91
Buy 79 for $6.37
Buy 58 for $4.55
Buy 15 for $1.82
Buy 72 for $5.46
Buy 30 for $2.73
Buy 1 for $0.91
Buy 60 for $4.55
Buy 19 for $1.82
Buy 39 for $2.73
Buy 26 for $1.82
Buy 89 for $6.37
Buy 75 for $5.46
Buy 34 for $2.73
Buy 58 for $4.55
Case 20:
Buy 32 for $3.59
Buy 40 for $3.59
Buy 97 for $7.18
Case 21:
Buy 77 for $53.80
Buy 84 for $80.58
Buy 8 for $26.86
Buy 60 for $53.72
Buy 58 for $53.72
Case 22:
Buy 80 for $1.00
Buy 78 for $1.00
Buy 63 for $1.00
Buy 76 for $1.00
Buy 89 for $1.00
Buy 20 for $0.50
Buy 11 for $0.50
Buy 33 for $0.50
Buy 95 for $1.50
Buy 18 for $0.50
Buy 47 for $1.00
Buy 36 for $0.50
Buy 38 for $0.50
Buy 92 for $1.50
Case 23:
Buy 40 for $9.26
Buy 50 for $9.26
Buy 21 for $9.26
Buy 68 for $9.26
Buy 27 for $9.26
Buy 64 for $9.26
Buy 78 for $9.26
Buy 97 for $18.52
Buy 82 for $9.26
Buy 66 for $9.26
Buy 61 for $9.26
Buy 37 for $9.26
Buy 56 for $9.26
Buy 71 for $9.26
Buy 19 for $9.26
Buy 12 for $9.26
Case 24:
Buy 99 for $40.82
Buy 31 for $20.41
Buy 64 for $20.41
Buy 48 for $20.41
Buy 51 for $20.41
Buy 31 for $20.41
Buy 74 for $20.41
Buy 15 for $20.41
Buy 60 for $20.41
Buy 23 for $20.41
Buy 48 for $20.41
Buy 25 for $20.41
Buy 83 for $20.41
Case 25:
Buy 22 for $2.63
Buy 58 for $2.63
Buy 66 for $4.44
Buy 48 for $2.63
Buy 72 for $4.44
Buy 77 for $4.44
Buy 70 for $4.44
Buy 19 for $2.63
Buy 2 for $2.63
Buy 4 for $2.63
Buy 54 for $2.63
Buy 34 for $2.63
Buy 8 for $2.63
Buy 60 for $2.63
Buy 29 for $2.63
Buy 7 for $2.63
Case 26:
Buy 79 for $19.84
Case 27:
Buy 52 for $12.82
Buy 98 for $25.64
Buy 33 for $12.82
Buy 35 for $12.82
Buy 82 for $13.39
Buy 7 for $12.82
Buy 16 for $12.82
Buy 58 for $12.82
Buy 9 for $12.82
Buy 96 for $25.64
Buy 100 for $25.64
Buy 63 for $12.82
Buy 98 for $25.64
Case 28:
Buy 21 for $1.55
Buy 93 for $3.10
Buy 26 for $1.55
Buy 29 for $1.55
Buy 40 for $1.55
Buy 26 for $1.55
Buy 91 for $3.10
Buy 37 for $1.55
Buy 61 for $1.55
Buy 19 for $1.55
Buy 44 for $1.55
Buy 38 for $1.55
Buy 29 for $1.55
Buy 83 for $3.10
Buy 22 for $1.55
Buy 11 for $1.55
Buy 56 for $1.55
Case 29:
Buy 96 for $0.45
Buy 77 for $0.36
Buy 6 for $0.09
Buy 67 for $0.27
Buy 29 for $0.18
Case 30:
Buy 7 for $3.09
Buy 52 for $3.09
Buy 65 for $3.09
Buy 91 for $3.09
Buy 64 for $3.09
Buy 92 for $3.09
Buy 73 for $3.09
Buy 38 for $3.09
Buy 38 for $3.09
Buy 60 for $3.09
Buy 29 for $3.09
Buy 72 for $3.09
Buy 81 for $3.09
Buy 88 for $3.09
Buy 57 for $3.09
Buy 91 for $3.09
Case 31:
Buy 66 for $6.37
Buy 15 for $6.37
Buy 27 for $6.37
Buy 87 for $12.74
Buy 84 for $12.74
Buy 40 for $6.37
Buy 70 for $6.37
Buy 36 for $6.37
Buy 53 for $6.37
Buy 22 for $6.37
Buy 94 for $12.74
Buy 91 for $12.74
Buy 90 for $12.74
Buy 10 for $6.37
Buy 32 for $6.37
Case 32:
Buy 69 for $42.96
Buy 57 for $42.96
Buy 61 for $42.96
Buy 34 for $31.99
Buy 24 for $31.99
Buy 87 for $63.98
Buy 72 for $42.96
Buy 59 for $42.96
Buy 78 for $42.96
Buy 41 for $31.99
Buy 46 for $31.99
Buy 82 for $63.98
Buy 62 for $42.96
Buy 91 for $63.98
Case 33:
Buy 20 for $10.76
Buy 34 for $10.76
Buy 44 for $10.76
Buy 5 for $10.76
Case 34:
Buy 32 for $24.76
Buy 3 for $17.30
Buy 75 for $49.52
Buy 8 for $24.76
Buy 19 for $24.76
Buy 17 for $24.76
Buy 84 for $49.52
Buy 78 for $49.52
Buy 88 for $49.52
Case 35:
Buy 11 for $0.31
Buy 81 for $0.93
Buy 27 for $0.31
Case 36:
Buy 34 for $17.28
Buy 64 for $23.87
Buy 88 for $25.58
Buy 80 for $25.58
Buy 95 for $29.90
Buy 50 for $21.60
Buy 100 for $29.90
Buy 52 for $21.60
Buy 40 for $17.28
Buy 65 for $23.87
Buy 43 for $17.28
Case 37:
Buy 23 for $56.35
Buy 88 for $137.98
Buy 74 for $99.16
Buy 44 for $75.16
Buy 20 for $56.35
Buy 43 for $75.16
Buy 55 for $99.16
Buy 45 for $75.16
Case 38:
Buy 54 for $17.13
Buy 70 for $17.13
Buy 51 for $17.13
Buy 88 for $27.34
Buy 3 for $17.13
Buy 38 for $17.13
Buy 63 for $17.13
Buy 90 for $27.34
Case 39:
Buy 22 for $8.22
Buy 21 for $8.22
Buy 81 for $23.51
Buy 67 for $15.29
Buy 95 for $23.51
Case 40:
Buy 25 for $1.73
Buy 34 for $1.73
Buy 14 for $1.73
Buy 87 for $1.73
Buy 100 for $3.46
Buy 71 for $1.73
Buy 95 for $3.46
Buy 69 for $1.73
Buy 16 for $1.73
Buy 42 for $1.73
Buy 43 for $1.73
Buy 40 for $1.73
Buy 38 for $1.73
Buy 64 for $1.73
Buy 99 for $3.46
Buy 91 for $1.73
Buy 40 for $1.73
Case 41:
Buy 51 for $6.35
Case 42:
Buy 48 for $5.71
Buy 8 for $5.71
Buy 85 for $6.36
Buy 32 for $5.71
Buy 62 for $5.71
Buy 20 for $5.71
Buy 32 for $5.71
Buy 54 for $5.71
Buy 29 for $5.71
Buy 28 for $5.71
Buy 95 for $6.36
Buy 20 for $5.71
Case 43:
Buy 98 for $5.64
Buy 33 for $1.88
Buy 4 for $1.88
Buy 36 for $1.88
Buy 52 for $3.76
Buy 8 for $1.88
Buy 99 for $5.64
Buy 50 for $3.76
Buy 55 for $3.76
Buy 62 for $3.76
Buy 7 for $1.88
Buy 35 for $1.88
Buy 4 for $1.88
Buy 26 for $1.88
Case 44:
Buy 50 for $10.15
Buy 14 for $10.15
Buy 80 for $10.15
Buy 35 for $10.15
Buy 17 for $10.15
Buy 15 for $10.15
Buy 86 for $10.15
Buy 76 for $10.15
Buy 66 for $10.15
Buy 87 for $19.13
Case 45:
Buy 4 for $6.30
Buy 87 for $10.63
Buy 43 for $6.30
Case 46:
Buy 43 for $6.03
Buy 71 for $6.03
Buy 97 for $12.06
Case 47:
Buy 1 for $41.64
Buy 16 for $666.24
Buy 88 for $3664.32
Buy 35 for $1457.40
Buy 33 for $1374.12
Buy 91 for $3789.24
Buy 51 for $2123.64
Buy 94 for $3914.16
Buy 34 for $1415.76
Buy 40 for $1665.60
Buy 81 for $3372.84
Buy 95 for $3955.80
Case 48:
Buy 12 for $3.24
Buy 66 for $6.48
Buy 69 for $6.48
Buy 82 for $9.72
Buy 14 for $3.24
Buy 84 for $9.72
Buy 100 for $9.72
Buy 78 for $6.48
Buy 36 for $3.24
Buy 15 for $3.24
Buy 65 for $6.48
Buy 70 for $6.48
Buy 47 for $6.48
Buy 8 for $3.24
Case 49:
Buy 88 for $459.28
Buy 58 for $287.05
Buy 37 for $202.96
Buy 94 for $459.28
Case 50:
Buy 30 for $3.36
Buy 50 for $6.72
Buy 36 for $6.72
Buy 23 for $3.36
Buy 41 for $6.72
Buy 69 for $10.08
Buy 44 for $6.72
Buy 56 for $6.72
Case 51:
Buy 71 for $12.88
Buy 28 for $12.88
Buy 99 for $25.76
Buy 21 for $12.88
Buy 64 for $12.88
Buy 22 for $12.88
Buy 61 for $12.88
Buy 84 for $12.88
Buy 17 for $12.88
Buy 68 for $12.88
Case 52:
Buy 9 for $42.93
Buy 63 for $113.29
Buy 69 for $140.72
Buy 96 for $140.72
Case 53:
Buy 72 for $10.10
Case 54:
Buy 87 for $12.30
Buy 5 for $5.05
Buy 34 for $6.15
Buy 59 for $6.15
Buy 57 for $6.15
Buy 28 for $6.15
Buy 11 for $6.15
Buy 69 for $6.15
Buy 32 for $6.15
Buy 70 for $6.15
Buy 29 for $6.15
Buy 42 for $6.15
Buy 47 for $6.15
Case 55:
Buy 27 for $49.02
Buy 33 for $49.02
Buy 39 for $49.02
Buy 100 for $98.04
Buy 6 for $36.06
Buy 1 for $36.06
Buy 63 for $49.02
Buy 58 for $49.02
Buy 33 for $49.02
Buy 49 for $49.02
Buy 62 for $49.02
Case 56:
Buy 84 for $12.48
Buy 62 for $9.84
Buy 95 for $14.46
Buy 43 for $6.42
Buy 31 for $5.58
Buy 92 for $13.92
Case 57:
Buy 93 for $16.17
Buy 49 for $10.78
Buy 97 for $16.17
Case 58:
Buy 77 for $16.82
Buy 38 for $8.41
Buy 98 for $16.82
Buy 21 for $8.41
Buy 40 for $8.41
Buy 95 for $16.82
Buy 6 for $8.41
Buy 15 for $8.41
Buy 83 for $16.82
Case 59:
Buy 11 for $7.55
Buy 93 for $15.10
Buy 43 for $7.55
Buy 59 for $15.10
Buy 65 for $15.10
Buy 24 for $7.55
Buy 42 for $7.55
Buy 22 for $7.55
Buy 12 for $7.55
Buy 70 for $15.10
Buy 11 for $7.55
Buy 61 for $15.10
Buy 91 for $15.10
Buy 3 for $7.55
Buy 56 for $15.10
Buy 48 for $7.55
Buy 17 for $7.55
Case 60:
Buy 87 for $16.64
Buy 87 for $16.64
Buy 9 for $2.56
Buy 68 for $12.80
Buy 78 for $15.36
Buy 67 for $12.80
Buy 37 for $7.68
Buy 36 for $7.68
Case 61:
Buy 32 for $5.26
Buy 52 for $10.52
Buy 81 for $10.52
Buy 21 for $5.26
Buy 98 for $15.78
Buy 1 for $5.26
Buy 89 for $15.78
Buy 62 for $10.52
Buy 97 for $15.78
Buy 75 for $10.52
Buy 2 for $5.26
Buy 15 for $5.26
Buy 70 for $10.52
Buy 29 for $5.26
Buy 17 for $5.26
Buy 53 for $10.52
Case 62:
Buy 76 for $5.29
Buy 51 for $5.29
Buy 82 for $5.29
Buy 27 for $5.29
Buy 51 for $5.29
Buy 63 for $5.29
Buy 29 for $5.29
Buy 79 for $5.29
Buy 65 for $5.29
Buy 80 for $5.29
Buy 59 for $5.29
Buy 54 for $5.29
Buy 45 for $5.29
Buy 35 for $5.29
Buy 70 for $5.29
Buy 12 for $5.29
Case 63:
Buy 33 for $11.43
Buy 50 for $22.86
Buy 8 for $11.43
Buy 68 for $22.86
Buy 77 for $34.29
Buy 59 for $22.86
Case 64:
Buy 97 for $10.44
Buy 52 for $5.22
Buy 57 for $5.22
Buy 11 for $2.61
Buy 100 for $10.44
Buy 42 for $5.22
Buy 70 for $7.83
Buy 82 for $7.83
Buy 96 for $10.44
Case 65:
Buy 52 for $11.88
Buy 25 for $11.88
Buy 11 for $11.88
Buy 65 for $11.88
Buy 39 for $11.88
Buy 24 for $11.88
Buy 94 for $23.76
Buy 35 for $11.88
Buy 27 for $11.88
Buy 2 for $11.88
Buy 46 for $11.88
Buy 26 for $11.88
Buy 95 for $23.76
Buy 67 for $23.76
Buy 7 for $11.88
Buy 90 for $23.76
Buy 57 for $11.88
Buy 48 for $11.88
Case 66:
Buy 91 for $11.48
Buy 6 for $5.74
Buy 47 for $5.74
Buy 67 for $11.48
Buy 68 for $11.48
Buy 64 for $11.48
Buy 5 for $5.74
Buy 91 for $11.48
Buy 9 for $5.74
Buy 91 for $11.48
Buy 69 for $11.48
Buy 62 for $11.48
Buy 36 for $5.74
Buy 94 for $11.48
Buy 56 for $11.48
Buy 2 for $5.74
Case 67:
Buy 30 for $4.36
Case 68:
Buy 68 for $8.76
Buy 45 for $8.76
Buy 4 for $8.76
Buy 31 for $8.76
Buy 30 for $8.76
Buy 47 for $8.76
Buy 87 for $8.76
Buy 71 for $8.76
Buy 95 for $8.76
Buy 46 for $8.76
Buy 59 for $8.76
Buy 53 for $8.76
Buy 9 for $8.76
Buy 87 for $8.76
Buy 99 for $17.52
Buy 6 for $8.76
Buy 14 for $8.76
Case 69:
Buy 27 for $2.08
Case 70:
Buy 2 for $9.47
Buy 34 for $18.94
Buy 11 for $9.47
Buy 49 for $28.41
Buy 93 for $37.88
Buy 70 for $28.41
Buy 1 for $9.47
Buy 72 for $28.41
Buy 51 for $28.41
Buy 9 for $9.47
Buy 82 for $37.88
Buy 57 for $28.41
Buy 88 for $37.88
Buy 89 for $37.88
Buy 29 for $18.94
Buy 63 for $28.41
Buy 52 for $28.41
Buy 84 for $37.88
Case 71:
Buy 42 for $14.24
Buy 85 for $28.48
Buy 26 for $14.24
Buy 83 for $28.48
Buy 66 for $28.48
Buy 40 for $14.24
Buy 34 for $14.24
Case 72:
Buy 20 for $0.57
Buy 17 for $0.57
Case 73:
Buy 30 for $13.06
Buy 29 for $13.06
Buy 13 for $13.06
Buy 87 for $13.19
Buy 18 for $13.06
Buy 56 for $13.06
Buy 80 for $13.19
Buy 84 for $13.19
Buy 80 for $13.19
Buy 90 for $13.19
Buy 38 for $13.06
Buy 90 for $13.19
Case 74:
Buy 54 for $12.88
Buy 16 for $6.44
Buy 14 for $6.44
Buy 18 for $6.44
Buy 15 for $6.44
Buy 99 for $25.76
Buy 81 for $19.32
Buy 81 for $19.32
Buy 42 for $12.88
Buy 7 for $6.44
Buy 65 for $19.32
Buy 36 for $12.88
Buy 39 for $12.88
Buy 24 for $6.44
Buy 32 for $12.88
Buy 53 for $12.88
Buy 43 for $12.88
Buy 10 for $6.44
Case 75:
Buy 81 for $89.28
Buy 7 for $44.64
Buy 86 for $89.28
Case 76:
Buy 58 for $1.62
Buy 33 for $1.62
Buy 41 for $1.62
Case 77:
Buy 90 for $51.72
Buy 90 for $51.72
Buy 47 for $51.72
Buy 40 for $51.72
Buy 85 for $51.72
Case 78:
Buy 1 for $12.73
Buy 23 for $12.73
Buy 21 for $12.73
Buy 47 for $25.46
Buy 14 for $12.73
Buy 57 for $25.46
Buy 30 for $12.73
Buy 65 for $25.46
Buy 29 for $12.73
Buy 25 for $12.73
Buy 51 for $25.46
Buy 49 for $25.46
Case 79:
Buy 56 for $35.42
Buy 60 for $38.05
Buy 51 for $35.42
Buy 30 for $35.42
Buy 32 for $35.42
Buy 49 for $35.42
Buy 43 for $35.42
Buy 89 for $55.76
Buy 78 for $53.13
Buy 7 for $17.71
Buy 69 for $38.05
Case 80:
Buy 31 for $5.33
Buy 95 for $10.66
Buy 40 for $5.33
Buy 52 for $5.33
Buy 73 for $5.33
Buy 43 for $5.33
Buy 93 for $10.66
Buy 45 for $5.33
Buy 7 for $5.33
Buy 81 for $5.33
Buy 23 for $5.33
Buy 94 for $10.66
Buy 50 for $5.33
Buy 99 for $10.66
Buy 87 for $5.33
Buy 29 for $5.33
Buy 77 for $5.33
Case 81:
Buy 36 for $7.21
Buy 16 for $7.21
Buy 35 for $7.21
Buy 58 for $7.21
Buy 61 for $7.21
Buy 36 for $7.21
Buy 8 for $7.21
Buy 47 for $7.21
Buy 65 for $7.21
Buy 84 for $14.42
Buy 56 for $7.21
Buy 4 for $7.21
Buy 38 for $7.21
Buy 34 for $7.21
Buy 43 for $7.21
Case 82:
Buy 17 for $3.74
Buy 97 for $8.71
Buy 14 for $3.74
Buy 93 for $8.71
Buy 75 for $8.71
Buy 24 for $5.61
Buy 7 for $1.87
Buy 61 for $8.71
Buy 95 for $8.71
Buy 4 for $1.87
Buy 7 for $1.87
Buy 64 for $8.71
Buy 18 for $3.74
Buy 35 for $7.48
Buy 40 for $7.48
Buy 35 for $7.48
Buy 53 for $8.71
Buy 50 for $8.71
Case 83:
Buy 55 for $0.66
Buy 40 for $0.48
Buy 97 for $1.20
Buy 10 for $0.12
Buy 46 for $0.60
Buy 12 for $0.18
Buy 27 for $0.36
Buy 81 for $1.02
Buy 3 for $0.06
Buy 13 for $0.18
Buy 33 for $0.42
Case 84:
Buy 25 for $2.51
Buy 43 for $5.02
Buy 55 for $5.02
Buy 27 for $2.51
Buy 55 for $5.02
Buy 40 for $5.02
Buy 79 for $7.53
Buy 65 for $7.53
Buy 43 for $5.02
Buy 26 for $2.51
Buy 78 for $7.53
Buy 3 for $2.51
Buy 28 for $2.51
Buy 5 for $2.51
Buy 55 for $5.02
Case 85:
Buy 26 for $1.61
Buy 52 for $1.61
Buy 58 for $1.61
Buy 74 for $1.61
Buy 71 for $1.61
Buy 59 for $1.61
Buy 86 for $1.61
Buy 65 for $1.61
Buy 84 for $1.61
Buy 40 for $1.61
Case 86:
Buy 60 for $4.31
Buy 94 for $8.62
Buy 93 for $8.62
Buy 51 for $4.31
Buy 58 for $4.31
Buy 79 for $8.62
Buy 3 for $4.31
Buy 61 for $4.31
Buy 48 for $4.31
Buy 32 for $4.31
Buy 45 for $4.31
Buy 27 for $4.31
Buy 62 for $4.31
Buy 12 for $4.31
Buy 93 for $8.62
Buy 99 for $8.62
Buy 69 for $8.62
Buy 78 for $8.62
Case 87:
Buy 88 for $62.72
Case 88:
Buy 18 for $6.25
Buy 35 for $11.25
Buy 100 for $25.07
Buy 41 for $13.75
Buy 71 for $16.32
Buy 73 for $17.57
Buy 28 for $8.75
Buy 52 for $16.25
Case 89:
Buy 45 for $16.15
Case 90:
Buy 66 for $6.74
Buy 92 for $6.74
Buy 51 for $3.37
Case 91:
Buy 54 for $0.58
Buy 24 for $0.58
Case 92:
Buy 47 for $15.59
Buy 55 for $28.32
Buy 18 for $15.59
Buy 70 for $28.32
Buy 84 for $31.18
Buy 63 for $28.32
Buy 29 for $15.59
Buy 88 for $31.18
Buy 96 for $31.18
Buy 97 for $31.18
Buy 51 for $15.59
Buy 55 for $28.32
Buy 67 for $28.32
Case 93:
Buy 90 for $16.72
Buy 19 for $8.36
Buy 28 for $8.36
Buy 8 for $8.36
Buy 74 for $8.36
Buy 57 for $8.36
Buy 16 for $8.36
Buy 13 for $8.36
Buy 9 for $8.36
Buy 75 for $8.36
Buy 31 for $8.36
Buy 77 for $8.36
Buy 5 for $8.36
Buy 20 for $8.36
Buy 57 for $8.36
Buy 47 for $8.36
Buy 56 for $8.36
Buy 40 for $8.36
Buy 7 for $8.36
Buy 13 for $8.36
Case 94:
Buy 27 for $20.70
Buy 24 for $20.70
Buy 85 for $41.40
Buy 73 for $41.40
Buy 31 for $20.70
Buy 76 for $41.40
Buy 80 for $41.40
Buy 95 for $41.40
Buy 85 for $41.40
Case 95:
Buy 75 for $580.00
Buy 82 for $652.50
Buy 3 for $72.50
Buy 36 for $290.00
Buy 38 for $290.00
Buy 73 for $580.00
Buy 67 for $507.50
Buy 21 for $217.50
Buy 2 for $72.50
Buy 75 for $580.00
Buy 12 for $145.00
Buy 46 for $362.50
Buy 44 for $362.50
Buy 16 for $145.00
Case 96:
Buy 94 for $7677.92
Buy 23 for $1878.64
Buy 81 for $6616.08
Buy 18 for $1470.24
Case 97:
Buy 41 for $1.17
Buy 73 for $2.34
Buy 60 for $2.34
Buy 42 for $1.17
Buy 47 for $1.17
Buy 24 for $1.17
Buy 39 for $1.17
Buy 43 for $1.17
Case 98:
Buy 1 for $0.39
Buy 86 for $6.28
Buy 15 for $3.14
Buy 74 for $6.28
Buy 2 for $0.78
Buy 80 for $6.28
Buy 39 for $3.14
Buy 78 for $6.28
Buy 38 for $3.14
Buy 97 for $6.28
Buy 19 for $3.14
Buy 58 for $3.14
Buy 74 for $6.28
Buy 63 for $4.31
Buy 46 for $3.14
Buy 5 for $1.95
Case 99:
Buy 92 for $1.20
Buy 78 for $0.80
Buy 92 for $1.20
Buy 65 for $0.80
Buy 31 for $0.40
Buy 23 for $0.40
Buy 56 for $0.80
Buy 9 for $0.40
Buy 61 for $0.80
Buy 52 for $0.80
Buy 27 for $0.40
Buy 70 for $0.80
Buy 78 for $0.80
Buy 41 for $0.80
Buy 16 for $0.40
Buy 82 for $1.20
Buy 34 for $0.40
Case 100:
Buy 78 for $1.40
Buy 52 for $0.70
Case 101:
Buy 25 for $3.50
Buy 33 for $3.50
Buy 64 for $3.50
Buy 21 for $3.50
Buy 36 for $3.50
Buy 41 for $3.50
Buy 48 for $3.50
Buy 93 for $3.50
Buy 19 for $3.50
Buy 1 for $3.50
Buy 23 for $3.50
Buy 44 for $3.50
Buy 26 for $3.50
Buy 5 for $3.50
Buy 84 for $3.50
Buy 51 for $3.50
Buy 48 for $3.50

[ahmad.diaa]

Can anyone help me .. i tried all the test cases provided here and i got similar output to the AC one but still WA

Code: Select all

#include<bits/stdc++.h>

using namespace std ;

double prices[205];
double memo[205][105];
int c;int co; 
double solve(int target , int used , int usedindex)
{
    if (used >= target)return 0;
    if (memo[used][target] != -1){return memo[used][target];}

    double e = 10000000;
    for (int i = 1 ;i < 205 ; i++)
    {
    	if(prices[i] == 10000000)continue;
        if (i >= target){
            if(prices[i]!= 10000000)e= min (e,prices[i] + solve(target,used + i,i));}
         if (i < target)
        {	
           int div = target/i ; int r = target%i;
           if (r ==0){ e = min (e,div*prices[i] + solve(target,used + div*i ,i));continue;}
            r = target-div*i ;
           	for (int k = 1 ; k  < target ; k++)
           	{
           	 int rem = ceil(r*1.0/k);
           	 if(k > r)rem = 1;
             if(prices[k] != 10000000) e = min (e, div*prices[i] + rem*prices[k]+ min(solve(target , used + div*i+rem*k,i) , solve(target,used+rem*k+div*i, k)));
           	
           	}
        	int c = ceil(target*1.0/i);
        	e = min (e , c*prices[i] + solve(target,used+c*i,i));
        }
    }
    return memo[used][target] = e;
}



int main ()
{
 double price ; int t; co = 1;char s[100];
 while (~scanf("%lf %d\n",&price , &t))
 {

     for (int i = 0 ; i < 205 ;i++)
        for (int j = 0 ; j < 105 ; j++)
            memo[i][j] = -1;
    for (int i = 0 ; i < 205 ;i++)prices[i] = 10000000;
    prices[0] =0;
    prices[1] = price ;
    c = t;
    for (int i = 0 ; i < t; i++)
    {

        int x ; double y;
        scanf("%d %lf\n",&x,&y);
        prices[x] = min(prices[x],y);
    }

    printf("Case %d:\n",co++);
    int z;
    string ee;
    getline(cin, ee);
    stringstream  linestream(ee);
    while(linestream >> z)
    {
       double e = solve(z,0,0);
       printf("Buy %d for $%.2lf\n",z,e);
    }
 }
    return 0;
}

[brianfry713]

Try solving it without using floating point.

[ahmad.diaa]

Try solving it without using floating point.

do you think my approach is totally right ??!