Show all threads Hide all threads Show all messages Hide all messages |
Cool problem! My method. | jagatsastry | 1515. Cashmaster | 9 Nov 2023 13:53 | 5 |
Wow. This problem is really cool. Try using the naive method and you're sure to get TLE#26. Well, my solution(AC 0.234) goes this way: if the first term is not 1 then the ans is 1. if the first i terms are 1<<0, 1<<1, 1<<2, ... 1<<(i-1) then all numbers from 1 to (1<<i) - 1 can be expressed as a sum of some of the above terms. Thus if a number k is present all numbers from k to k+((1<<i) - 1) can be skipped. Proceed using this approach. By the way 1<<i represents pow(2, i). And how do you plan to proceed with this approach? :) how is your algorithm working on this test: 6 1 2 3 6 9 18 My brain burned in notebook on that algorithm! |
easy | 👑TIMOFEY👑 | 1515. Cashmaster | 16 Oct 2022 10:35 | 1 |
easy 👑TIMOFEY👑 16 Oct 2022 10:35 |
Couple of test cases which helped me | Smog | 1515. Cashmaster | 26 Oct 2021 00:20 | 1 |
7 1 2 3 4 5 6 22 answer is 44 2 1 3 answer is 2 |
If you have WA3 | Kirom `Ekexity [SESC17]💻 | 1515. Cashmaster | 6 Dec 2020 02:31 | 2 |
Try tist test: 5 1 2 4 8 16 Right answer is 32 )))) |
Weak tests 1515 Cashmaster | Васильев Константин | 1515. Cashmaster | 2 Apr 2013 23:39 | 2 |
i've got test for this program 3 3 5 9 if answer of my program is "4" site accept my program. But the right answer is "1"!!! is it right? Edited by moderator 03.04.2013 12:40 Test is added. 66 authors have lost AC Edited by author 03.04.2013 12:40 |
What is the test 2??? | Dark Cleaner | 1515. Cashmaster | 29 Jan 2013 23:44 | 1 |
My first program gives right answers for all the extremal tests, that I think out for my AC program, but it can not pass this test with diagnosis "Crash (access violation)". Why? What checks this test? Edited by author 30.01.2013 01:45 |
Please help me.Whats wrong?WA 3. | GrL | 1515. Cashmaster | 3 Oct 2009 17:58 | 3 |
I have AC Edited by author 10.11.2007 01:29 what algo did you use? I also get WA#3 but I can't find my mistake. What did you fix in your code? Edited by author 03.10.2009 18:37 |
COOL Solution | Mihran Hovsepyan {2 kurs of <RAU>} | 1515. Cashmaster | 18 Oct 2008 16:52 | 2 |
COOL Solution Mihran Hovsepyan {2 kurs of <RAU>} 17 Oct 2008 22:15 # include <iostream> using namespace std; main() { int n,b[100]; int i,max=0; cin>>n; for(i=0;i<n;i++) cin>>b[i]; for(i=0;i<n;i++) { if(b[i]>max+1) {cout<<max+1;return 0;} else max+=b[i]; } cout<<max+1; return 0; } Edited by author 22.10.2008 22:13 Hey,pal,why do you sort the array? It is already sorted! |
Analysis of this problem is on my site!!! | [SSAU_#617]snipious_#0 aka Pimenov Sergey Nikolaevich | 1515. Cashmaster | 18 Jul 2008 16:14 | 2 |
Yeah... I almost wrote DP :))) it's waaaay easier. Thanks! :) |
Help pls | Madhav | 1515. Cashmaster | 18 Jul 2008 16:08 | 2 |
Can any one tell me how to solve this problem using greedy approach pls..? Initially values till max=0 are reachable. If next coin is higher than max+1, then the answer is max+1. Otherwise max is boosted by its value (that is, values 0...max+ai are reachable). Proceed until you find a hole or you run out of coins. |
test16 | bakhtin | 1515. Cashmaster | 20 Mar 2008 18:05 | 1 |
test16 bakhtin 20 Mar 2008 18:05 |
good test case | Giorgi Saghinadze (Tbilisi SU) | 1515. Cashmaster | 13 Sep 2007 09:43 | 9 |
56 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 100000 131072 200000 262144 300000 400000 500000 524288 600000 700000 800000 900000 900001 900002 900003 900004 900005 900006 900007 900008 900009 900010 900011 900012 900013 900014 900015 900016 999000 999001 999002 999003 999004 999005 999006 999007 999008 999009 1000000 admin please add this test case. many programs (for example mine) can't paass it. Thank you! Test of such structure was added, 37 submits lost AC verdict (submits from online contest were not rejudged). I used greedy, but getting wrong answer? doesn't it a greedy problem? plz, let me know if i am wrong or right. Edited by author 28.12.2006 18:51 Edited by author 28.12.2006 18:52 you are right. It's very greedy :) Re: good test case [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich 29 Jan 2007 16:42 Re: good test case [SSAU_#617]snipious_#1 aka Pimenov Sergey Nikolaevich 29 Jan 2007 18:10 Now... The true answer is 29038772!!! 29,038,772 is a combination too. you can see that the first 17 numbers are 2^0, 2^1... 2^16. with that all numbers between 1 and 131,071 are generated. if you rest the summatory of the numbers of the list from 524,288 to the end to the number that you say, is obtained 124,303 and it's lower than 131,071, so can be generated. the solution is 30 938 756 that is higher than the summatory of all numbers in the list |
first bancknot | levanivar | 1515. Cashmaster | 16 Dec 2006 14:35 | 2 |
Does it means that first bancknot must be 1? or if doesn't is 1 correct answer when first(d[1]) isn't 1? Yes (-) Dmitry 'Diman_YES' Kovalioff 16 Dec 2006 14:35 |
Use some banknote more than once | opaka_cetvorka | 1515. Cashmaster | 16 Dec 2006 13:15 | 2 |
Does that mean I cann't use same banknote more than once (ie. to make 2 I can/cann't use twice banknote 1?)? |