|
|
I got ac on this problem using heuristic. Please, add anti-heuristic tests. I use greedy to solve this problem. First,I scanned all the boxes.If it had N new different coins that Tom wanted.The purchase will added about N*100 Then,I think Tom would buy this box.And it costs him 100 yen. At last.If the purchase>0 ,then I would buy some boxes that Tom did not have been bought. I was WA on #1 Am I wrong? At last,I'm sorry for my poor English. Thanks a lot. My solution got AC but it fails following tests 5 5 5 1 2 3 4 5 1 1 1 1 1 1 1 1 5 1 2 3 4 5 5 4 5 1 2 3 4 5 1 1 1 2 2 1 2 5 1 2 3 4 5 What is your answers for this tests? I'm very interesting, what answer is rigth for test: 5 5 4 2 3 4 5 1 2 1 3 1 4 1 5 5 1 2 3 4 5 My program returns: 5 1 2 3 4 5 and get AC! But in this case professor get 4 target coin and paid 500 yen. So 125 yen for coin. It's srange :) Edited by moderator 01.03.2009 16:39 What is your answers for this tests? I'm very interesting, what answer is rigth for test: 5 5 4 2 3 4 5 1 2 1 3 1 4 1 5 5 1 2 3 4 5 My program returns: 5 1 2 3 4 5 and get AC! But in this case professor get 4 target coin and paid 500 yen. So 125 yen for coin. It's srange :) ######################## there are only 4 kind of needed coins in the sets => max answer is 4 and sets may be formed like 1 2 3 4 1 3 4 5 1 2 4 5 2 3 4 5 and so on any 4 sets are correct Edited by author 01.03.2009 22:29 Edited by author 01.03.2009 22:29 I'm sorry, my question wasn't clear :) What is your answers for yours tests? My program returned: 5 1 2 3 4 5 and 4 1 2 3 4 Is it right? Your tests are added. Problem will be rejudged soon. Edited by author 01.03.2009 16:40 My program returns wrong results on such a simple test 3 3 1 1 1 1 2 2 3 3 1 2 3 It returns result 2 coins and sets 1&3,instead of 3 1 2 3,but it still got AC yesterday. Edited by author 05.03.2009 19:54 when the shopkeeper made the set, did she include more than one boxes of same type in it? |
|
|