|
|
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! 7 1 2 3 4 5 6 22 answer is 44 2 1 3 answer is 2 Try tist test: 5 1 2 4 8 16 Right answer is 32 )))) 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 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 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 # 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! Yeah... I almost wrote DP :))) it's waaaay easier. Thanks! :) 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. 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). Cool !!! 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 :) The answer is 180002??? 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 Does it means that first bancknot must be 1? or if doesn't is 1 correct answer when first(d[1]) isn't 1? Does that mean I cann't use same banknote more than once (ie. to make 2 I can/cann't use twice banknote 1?)? |
|
|