I always thought that right way to solve coin exchange problem is using DP.
But
a) my asserts shows that in judge input there are game scores greater than 5000000.
b) little joey's solution used only 413Kb memory.
So I wonder, what are the lower and upper limits for game score and sequence score?
351  "Cheapest" Scores
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
So maybe DP isn't the right way to solve it...
As you can read in the description, the only limit given in this problem, is the number 20 for the maximum number of scoring events. But you may further assume that all scores in the input will fit in a 32bit signed integer.
(Wouldn't it be rather dull if this was the umpteenth coin exchange problem that was solvable by DP? Once you've seen a few, you've seen them all )
As you can read in the description, the only limit given in this problem, is the number 20 for the maximum number of scoring events. But you may further assume that all scores in the input will fit in a 32bit signed integer.
(Wouldn't it be rather dull if this was the umpteenth coin exchange problem that was solvable by DP? Once you've seen a few, you've seen them all )
Output format
Since output doesn't formally described in the problem,
please check my output.
I'm not sure about indentation, events order, plural form, etc.
Input:
Output:
please check my output.
I'm not sure about indentation, events order, plural form, etc.
Input:
Code: Select all
7
halfpenny 1
penny 2
threepence 6
sixpence 12
shilling 24
florin 48
halfcrown 60
96
0
4
cyclea 2 cycleb
cycleb 2 cyclea
dirty 1
loop 2 loop
2147483647
0
2
one 1
verydirty 2147483647
2147483646
2147483647
0
5
gusher 6 douser
soaker 3 douser
douser 2
spray 1 soaker
bucket 7
30
239
0
3
6 6
9 9
20 20
62
0
0
Code: Select all
Case 1.1 (96):
2 florins (96)
Case 2.1 (2147483647):
2147483647 dirtys (2147483647)
Case 3.1 (2147483646):
2147483646 ones (2147483646)
Case 3.2 (2147483647):
1 verydirty (2147483647)
Case 4.1 (30):
3 gushers (18)
1 soaker (3)
4 dousers (8)
1 spray (1)
Case 4.2 (239):
29 gushers (174)
29 dousers (58)
1 bucket (7)
Case 5.1 (62):
1 6 (6)
4 9s (36)
1 20 (20)

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Re: 351  ``Cheapest'' Scores
1. I create a array with size only 1,000,000 characters to do marking.
2.Use dfs to generate relations of events first, then use DP to solve it. Think about coin change.
3.ATTENTION!! If the event has 2 or above, you have to add 's' after event name. See the sample output.
2.Use dfs to generate relations of events first, then use DP to solve it. Think about coin change.
3.ATTENTION!! If the event has 2 or above, you have to add 's' after event name. See the sample output.
Judge World  problem solving is a routine.
http://bleed1979.myweb.hinet.net
http://bleed1979.myweb.hinet.net