ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1244. Gentlemen

any hint ?
Posted by Locomotive 3 Mar 2003 22:41
Hint (+)
Posted by Oberon (Yura Znovyak) 5 Mar 2003 02:02
For each mass store amount of possibilities you can get it. If this
number exceeds to than you can lower it downto 2.
NumGet: array[0..MaxCardMass * MaxCards] of byte;

For each mass store atleast one (if possible) card wich can create
that mass.
WhatGet: array[1..MaxCardMass * MaxCards] of byte;

You need 1000*100 * 2 arrays of bytes.

Start DP with 0 cards;
NumGet[0] := 1;

for CurrentCard <- 1 to CardCount do
    for i <-SumOfAllCards - CardWeight[CurrentCard] DOWNTO (!!!) 0 do
      if NumGet[i] <> 0 then
         Inc(NumGet[i + CardWeight[CurrentCard]], NumGet[i]);
         if NumGet[i + CardWeight[CurrentCard]] > 2 the
              NumGet[i + CardWeight[CurrentCard]] := 2
         if WhatGet[i + CardWeight[CurrentCard]] = 0 then
              WhatGet[i + CardWeight[CurrentCard]] := CurrentCard;

Downto needed to avoid next trap:
consider we can get mass 100
know we check card with mass 10
when i = 100 we mark that we can get 110
when i = 110 and it is (already marked) we mark 120
when i = 120 ...
...

Hope this will be helpfull...
Help me!
Posted by aa 31 Mar 2003 19:41
I have the same idea as you.but i got WA.Please help me.
I think we should check if there is no solution(output 0) first,and
then check if there is more than one solution(output -1). am I right?

Here is my program:

[code deleted]

Edited by moderator 27.03.2007 09:45
Re: Help me!
Posted by PSV 25 Mar 2007 22:41
Knapsack at all, guys, as well :)
Re: Hint (+)
Posted by Lavin 23 Aug 2008 22:02
It's so helpfull...
Thank you.
:)