## 351 - "Cheapest" Scores

Moderator: Board moderators

avm
New poster
Posts: 33
Joined: Sat Aug 20, 2005 9:59 pm
Location: St. Petersburg

### 351 - "Cheapest" Scores

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?

little joey
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 )

avm
New poster
Posts: 33
Joined: Sat Aug 20, 2005 9:59 pm
Location: St. Petersburg

### Output format

Since output doesn't formally described in the problem,
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
``````
Output:

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)
``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Looks like I screwed it up big time. Please hold on...

avm, can you PM me an email adress? I like to send you some files.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Yes, my solution was wrong, so please don't submit to this problem. I hope to fix it ASAP...

bleed1979
New poster
Posts: 8
Joined: Thu Oct 08, 2009 5:34 am

### 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.
Judge World - problem solving is a routine.
http://bleed1979.myweb.hinet.net