Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.
ContestId |
Name |
Phase |
Frozen |
Duration (Seconds) |
Relative Time |
Start Time |
|---|---|---|---|---|---|---|
| 725 | Canada Cup 2016 | FINISHED | False | 9000 | 299256923 | Oct. 22, 2016, 3:05 p.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 708 ) | E | Too Much Money | PROGRAMMING | brute force greedy | 2500 |
Alfred wants to buy a toy moose that costs c dollars. The store doesn’t give change, so he must give the store exactly c dollars, no more and no less. He has n coins. To make c dollars from his coins, he follows the following algorithm: let S be the set of coins being used. S is initially empty. Alfred repeatedly adds to S the highest-valued coin he has such that the total value of the coins in S after adding the coin doesn’t exceed c . If there is no such coin, and the value of the coins in S is still less than c , he gives up and goes home. Note that Alfred never removes a coin from S after adding it. As a programmer, you might be aware that Alfred’s algorithm can fail even when there is a set of coins with value exactly c . For example, if Alfred has one coin worth $3, one coin worth $4, and two coins worth $5, and the moose costs $12, then Alfred will add both of the $5 coins to S and then give up, since adding any other coin would cause the value of the coins in S to exceed $12. Of course, Alfred could instead combine one $3 coin, one $4 coin, and one $5 coin to reach the total. Bob tried to convince Alfred that his algorithm was flawed, but Alfred didn’t believe him. Now Bob wants to give Alfred some coins (in addition to those that Alfred already has) such that Alfred’s algorithm fails. Bob can give Alfred any number of coins of any denomination (subject to the constraint that each coin must be worth a positive integer number of dollars). There can be multiple coins of a single denomination. He would like to minimize the total value of the coins he gives Alfred. Please find this minimum value. If there is no solution, print " Greed is good ". You can assume that the answer, if it exists, is positive. In other words, Alfred's algorithm will work if Bob doesn't give him any coins. The first line contains c ( 1 ≤ c ≤ 200 000 ) — the price Alfred wants to pay. The second line contains n ( 1 ≤ n ≤ 200 000 ) — the number of coins Alfred initially has. The |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 21766937 | MintGreen | E | Oct. 25, 2016, 8:56 a.m. | OK | FPC | TESTS | 35 | 62 | 2457600 | 2500 | |
| 21689792 | s34vv1nd | E | Oct. 22, 2016, 5:34 p.m. | OK | FPC | TESTS | 35 | 62 | 3379200 | 2500 | |
| 24263425 | Gray_58 | E | Jan. 30, 2017, 9:46 a.m. | OK | FPC | TESTS | 35 | 62 | 3686400 | 2500 | |
| 31101600 | vjudge1 | E | Oct. 7, 2017, 6:16 a.m. | OK | GNU C++ | TESTS | 35 | 15 | 1433600 | 2500 | |
| 21697062 | Minology | E | Oct. 23, 2016, 2:57 a.m. | OK | GNU C++ | TESTS | 35 | 15 | 1638400 | 2500 | |
| 31099434 | vjudge5 | E | Oct. 7, 2017, 4:47 a.m. | OK | GNU C++ | TESTS | 35 | 15 | 3174400 | 2500 | |
| 26532673 | jiyutian | E | April 21, 2017, 7:38 a.m. | OK | GNU C++ | TESTS | 35 | 15 | 3481600 | 2500 | |
| 23372982 | Ali.Pi | E | Dec. 28, 2016, 7:53 a.m. | OK | GNU C++ | TESTS | 35 | 15 | 3686400 | 2500 | |
| 31096048 | vjudge5 | E | Oct. 7, 2017, 1:15 a.m. | OK | GNU C++ | TESTS | 35 | 30 | 2252800 | 2500 | |
| 22884081 | dmlocdmloc | E | Dec. 11, 2016, 4:01 p.m. | OK | GNU C++ | TESTS | 35 | 30 | 2457600 | 2500 | |
| 21740604 | ShallWe | E | Oct. 24, 2016, 12:16 p.m. | OK | GNU C++ | TESTS | 35 | 30 | 2457600 | 2500 | |
| 31099283 | nn020701 | E | Oct. 7, 2017, 4:40 a.m. | OK | GNU C++ | TESTS | 35 | 30 | 3174400 | 2500 | |
| 31102227 | vjudge1 | E | Oct. 7, 2017, 6:37 a.m. | OK | GNU C++ | TESTS | 35 | 30 | 12390400 | 2500 | |
| 21695121 | Chortos-2 | E | Oct. 22, 2016, 10:34 p.m. | OK | GNU C11 | TESTS | 35 | 15 | 1638400 | 2500 | |
| 21694977 | Chortos-2 | E | Oct. 22, 2016, 10:16 p.m. | OK | GNU C11 | TESTS | 35 | 31 | 2355200 | 2500 | |
| 69429201 | rainboy | E | Jan. 23, 2020, 4:46 p.m. | OK | GNU C11 | TESTS | 35 | 46 | 1638400 | 2500 | |
| 21698764 | King_George | E | Oct. 23, 2016, 5:51 a.m. | OK | GNU C++11 | TESTS | 35 | 30 | 1638400 | 2500 | |
| 22184972 | savinov | E | Nov. 12, 2016, 9:49 p.m. | OK | GNU C++11 | TESTS | 35 | 30 | 2355200 | 2500 | |
| 21973844 | nguyenchanhdai | E | Nov. 1, 2016, 4:51 p.m. | OK | GNU C++11 | TESTS | 35 | 31 | 1024000 | 2500 | |
| 21839769 | bnguyenltt | E | Oct. 28, 2016, 5:45 a.m. | OK | GNU C++11 | TESTS | 35 | 31 | 1024000 | 2500 | |
| 45155517 | luogu_bot4 | E | Nov. 1, 2018, 12:46 a.m. | OK | GNU C++11 | TESTS | 35 | 31 | 1433600 | 2500 | |
| 45173931 | luogu_bot1 | E | Nov. 1, 2018, 1:54 p.m. | OK | GNU C++11 | TESTS | 35 | 31 | 1433600 | 2500 | |
| 22931264 | -XraY- | E | Dec. 13, 2016, 4:49 p.m. | OK | GNU C++11 | TESTS | 35 | 31 | 1638400 | 2500 | |
| 21797497 | EsTer | E | Oct. 26, 2016, 2:44 p.m. | OK | GNU C++11 | TESTS | 35 | 31 | 2457600 | 2500 | |
| 21696651 | FailedSystemTest | E | Oct. 23, 2016, 2:07 a.m. | OK | GNU C++11 | TESTS | 35 | 31 | 2457600 | 2500 | |
| 45083577 | jambow | E | Oct. 30, 2018, 5:33 a.m. | OK | GNU C++11 | TESTS | 35 | 31 | 3174400 | 2500 | |
| 31102223 | q234rty | E | Oct. 7, 2017, 6:37 a.m. | OK | GNU C++14 | TESTS | 35 | 15 | 12390400 | 2500 | |
| 31102161 | q234rty | E | Oct. 7, 2017, 6:35 a.m. | OK | GNU C++14 | TESTS | 35 | 30 | 32460800 | 2500 | |
| 22408355 | thjchph4trjnh | E | Nov. 22, 2016, 5:24 p.m. | OK | GNU C++14 | TESTS | 35 | 46 | 1638400 | 2500 | |
| 43069795 | nickluo | E | Sept. 19, 2018, 8:23 a.m. | OK | GNU C++14 | TESTS | 35 | 46 | 3276800 | 2500 | |
| 23686571 | pimenta | E | Jan. 10, 2017, 6:54 p.m. | OK | GNU C++14 | TESTS | 35 | 46 | 3481600 | 2500 | |
| 23685312 | pimenta | E | Jan. 10, 2017, 5:22 p.m. | OK | GNU C++14 | TESTS | 35 | 46 | 3481600 | 2500 | |
| 25059478 | DXHPeter | E | Feb. 26, 2017, 4:06 p.m. | OK | GNU C++14 | TESTS | 35 | 46 | 4608000 | 2500 | |
| 68107088 | Jeffrey | E | Jan. 3, 2020, 7:41 a.m. | OK | GNU C++14 | TESTS | 35 | 61 | 1536000 | 2500 | |
| 22003674 | ErdemKirez | E | Nov. 2, 2016, 11:43 p.m. | OK | GNU C++14 | TESTS | 35 | 61 | 1638400 | 2500 | |
| 51473825 | KATATONIA | E | March 19, 2019, 8:14 a.m. | OK | GNU C++14 | TESTS | 35 | 61 | 1638400 | 2500 | |
| 52568927 | Osama_Alkhodairy | E | April 10, 2019, 1:29 p.m. | OK | GNU C++17 | TESTS | 35 | 46 | 1638400 | 2500 | |
| 64907865 | Phortox | E | Nov. 15, 2019, 12:07 a.m. | OK | GNU C++17 | TESTS | 35 | 62 | 1638400 | 2500 | |
| 65465667 | 0x000000_hole | E | Nov. 21, 2019, 5:44 a.m. | OK | GNU C++17 | TESTS | 35 | 62 | 2355200 | 2500 | |
| 45069672 | fedoseev.timofey | E | Oct. 29, 2018, 6:59 p.m. | OK | GNU C++17 | TESTS | 35 | 62 | 2662400 | 2500 | |
| 65823780 | vjudge2 | E | Nov. 27, 2019, 11:43 a.m. | OK | GNU C++17 | TESTS | 35 | 62 | 3174400 | 2500 | |
| 68437473 | A_Fan_of_the_AK_King--lk | E | Jan. 9, 2020, 9:32 a.m. | OK | GNU C++17 | TESTS | 35 | 62 | 3993600 | 2500 | |
| 65483552 | vjudge1 | E | Nov. 21, 2019, 12:29 p.m. | OK | GNU C++17 | TESTS | 35 | 77 | 1638400 | 2500 | |
| 65465676 | vjudge3 | E | Nov. 21, 2019, 5:44 a.m. | OK | GNU C++17 | TESTS | 35 | 77 | 2457600 | 2500 | |
| 65433992 | egekabas | E | Nov. 20, 2019, 12:52 p.m. | OK | GNU C++17 | TESTS | 35 | 92 | 1638400 | 2500 | |
| 51437851 | chinmay0906 | E | March 18, 2019, 7:54 a.m. | OK | GNU C++17 | TESTS | 35 | 92 | 4812800 | 2500 | |
| 69429200 | Dukkha | E | Jan. 23, 2020, 4:46 p.m. | OK | Java 11 | TESTS | 35 | 390 | 0 | 2500 | |
| 25068537 | megaspazz | E | Feb. 27, 2017, 3:56 a.m. | OK | Java 8 | TESTS | 35 | 109 | 20480000 | 2500 | |
| 25068529 | megaspazz | E | Feb. 27, 2017, 3:55 a.m. | OK | Java 8 | TESTS | 35 | 109 | 20480000 | 2500 | |
| 31590761 | keiii | E | Oct. 22, 2017, 3:22 a.m. | OK | Java 8 | TESTS | 35 | 124 | 20582400 | 2500 | |
| 21759711 | fnch | E | Oct. 24, 2016, 9:18 p.m. | OK | Java 8 | TESTS | 35 | 155 | 0 | 2500 | |
| 26130940 | mikcorer | E | April 4, 2017, 7:37 p.m. | OK | Java 8 | TESTS | 35 | 155 | 28672000 | 2500 | |
| 21694533 | uwi | E | Oct. 22, 2016, 9:29 p.m. | OK | Java 8 | TESTS | 35 | 171 | 0 | 2500 | |
| 21685932 | eatmore | E | Oct. 22, 2016, 5:02 p.m. | OK | Java 8 | TESTS | 35 | 186 | 0 | 2500 | |
| 21691461 | Lewin | E | Oct. 22, 2016, 6:53 p.m. | OK | Java 8 | TESTS | 35 | 264 | 7884800 | 2500 | |
| 41602458 | BaZ_ | E | Aug. 14, 2018, 9:28 p.m. | OK | Java 8 | TESTS | 35 | 295 | 4300800 | 2500 | |
| 21739671 | uwi | E | Oct. 24, 2016, 11:32 a.m. | OK | Java 8 | TESTS | 35 | 374 | 0 | 2500 | |
| 21694908 | dyukha | E | Oct. 22, 2016, 10:07 p.m. | OK | Kotlin | TESTS | 35 | 452 | 8499200 | 2500 | |
| 22049370 | Joker456 | E | Nov. 5, 2016, 6:20 a.m. | OK | Mono C# | TESTS | 35 | 108 | 4505600 | 2500 | |
| 21881883 | erik99 | E | Oct. 29, 2016, 7:45 p.m. | OK | MS C# | TESTS | 35 | 124 | 4505600 | 2500 | |
| 21698235 | LLI_E_P_JI_O_K | E | Oct. 23, 2016, 5:06 a.m. | OK | MS C++ | TESTS | 35 | 62 | 28057600 | 2500 | |
| 21690966 | KhaustovPavel | E | Oct. 22, 2016, 6:41 p.m. | OK | MS C++ | TESTS | 35 | 77 | 3276800 | 2500 | |
| 21690790 | Oleg_Smirnov | E | Oct. 22, 2016, 6:37 p.m. | OK | MS C++ | TESTS | 35 | 78 | 3379200 | 2500 | |
| 21690789 | Taube | E | Oct. 22, 2016, 6:37 p.m. | OK | MS C++ | TESTS | 35 | 124 | 7270400 | 2500 | |
| 22393330 | TheConfessor | E | Nov. 21, 2016, 10:32 p.m. | OK | MS C++ | TESTS | 35 | 202 | 3174400 | 2500 | |
| 21695633 | goodhope | E | Oct. 22, 2016, 11:39 p.m. | OK | MS C++ | TESTS | 35 | 295 | 4096000 | 2500 | |
| 21788554 | dantasse | E | Oct. 26, 2016, 7:06 a.m. | OK | Python 2 | TESTS | 35 | 561 | 9318400 | 2500 |
Back to search problems