## 10980 - Lowest Price in Town

Moderator: Board moderators

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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:
Case 2:

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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:
Case 2:
``````
Best regards.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
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:
Case 2:
Case 3:
Case 4:
Case 5:
Case 6:
Case 7:
Case 8:
Case 9:
Case 10:
Case 11:

``````
Hope it helps to catch the bug...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

### I also got WA.

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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
arsalan_mousavian wrote: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
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10980 - Lowest Price in Town

C wrote:
arsalan_mousavian wrote: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.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10980 - Lowest Price in Town

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:
Case 2:
Case 3:
Case 4:
Case 5:
Case 6:
Case 7:
Case 8:
Case 9:
Case 10:
Case 11:
Case 12:
Case 13:
Case 14:
Case 15:
Case 16:
Case 17:
Case 18:
Case 19:
Case 20:
Case 21:
Case 22:
Case 23:
Case 24:
Case 25:
Case 26:
Case 27:
Case 28:
Case 29:
Case 30:
Case 31:
Case 32:
Case 33:
Case 34:
Case 35:
Case 36:
Case 37:
Case 38:
Case 39:
Case 40:
Case 41:
Case 42:
Case 43:
Case 44:
Case 45:
Case 46:
Case 47:
Case 48:
Case 49:
Case 50:
Case 51:
Case 52:
Case 53:
Case 54:
Case 55:
Case 56:
Case 57:
Case 58:
Case 59:
Case 60:
Case 61:
Case 62:
Case 63:
Case 64:
Case 65:
Case 66:
Case 67:
Case 68:
Case 69:
Case 70:
Case 71:
Case 72:
Case 73:
Case 74:
Case 75:
Case 76:
Case 77:
Case 78:
Case 79:
Case 80:
Case 81:
Case 82:
Case 83:
Case 84:
Case 85:
Case 86:
Case 87:
Case 88:
Case 89:
Case 90:
Case 91:
Case 92:
Case 93:
Case 94:
Case 95:
Case 96:
Case 97:
Case 98:
Case 99:
Case 100:
Case 101:
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 2
Joined: Tue Feb 04, 2014 2:01 pm

### Re: 10980 - Lowest Price in Town

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);
}
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10980 - Lowest Price in Town

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!