_iris_'s blog

problem "secret" in "Codeforces Round #194 (Div. 2)"
By _iris_, 11 years ago, In English

i have trouble understanding this problem . can any one explain? thanks :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The secret costs n marks.

Now, the unlucky buyer does not have coins such that it is possible to pay exactly n marks. But he has enough coins to pay more than n marks. He will also use as few coins as possible to pay more than n marks.

Now you want to find what might be the worst possible case for the unlucky buyer. You want to find out the maximum number of coins the unlucky buyer might be forced to pay.

For example, if the cost of the secrets is 15.

The unlucky buyer must have enough money to pay more than 15 marks. But he must not be able to pay exactly 15 marks.

If he has 5 coins of 3, then he will be able to pay exactly 15. Therefore, we must not consider this case at all. If he has 2 coins of 9, 1 coin of 3, 2 coins of 1, then he will use 2 coins of 9 to pay 18 marks. If he has 1 coin of 27, he will use 1 coin of 27 to pay 27 marks.

The worst possible case, such that the unlucky buyer can pay more than 15, is when he has to pay using 2 coins of 9.

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

let's consider all the combinations with this conditions :

  1. sum of coins in each one of this combinations should be greater than N.
  2. if you remove one arbitary coin from this combination, sum of remaining coins become less than N for example for N=4 this combination is should not consider : {three 1 mark, one 3 mark} because if you remove one of the 1 mark coins, sum of remaining coins still is greater than N.

in this problem you should calculate maximum number of coin between valid combinations.

→ Reply