351 - "Cheapest" Scores

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

351 - "Cheapest" Scores

Post by avm »

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

Post by little joey »

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

Post by avm »

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:

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

Post by little joey »

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

Post by little joey »

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

Post by bleed1979 »

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

Post Reply

Return to “Volume 3 (300-399)”