|
|
sol.push_back(ceil((double)n/2)) (sol is vector in c++) If you solved it using such code, please explain why it works. Basically, it's a greedy algorithm: the maximum length you can fold is CURRENT_LENGTH / 2. So, you just fold it in half until it's of length 1. Why are not correct 12 4 6 3 1 1 not correct first sample! 12 4 5 3 2 1 correct: 12 4 6 3 2 1 Yes. Because 5 3 2 1 is a bit confusing... Better, if it will 6 3 2 1 :) Edited by author 01.12.2013 03:16 Edited by author 17.07.2010 00:34 Possible answer in first test is: 6 3 1 1 Now try to think whats the best way to make minimal "cuts" :) And when n=1000000000 the answer is: 30 500000000 250000000 125000000 62500000 31250000 15625000 7812500 3906250 1953125 976562 488281 244141 122070 61035 30518 15259 7629 3815 1907 954 477 238 119 60 30 15 7 4 2 1 Edited by author 17.07.2010 12:55 IF N=1 MY PROGRAM OUTPUT 0 0 ???????????????????? My program Wa3 This is my program: program Ural683; var a,m,n:longint; k:array[0..50]of longint; begin readln(n); m:=1; k[0]:=n; while k[m-1]<>0 do begin k[m]:=k[m-1]shr 1; inc(m); end; m:=0; a:=1; while a<n do begin inc(m);a:=a shl 1; end; writeln(m); for a:=1 to m do if k[a]=0 then write(1,' ') else write(k[a],' '); end. Who can help me? Edited by author 02.04.2009 14:18 Now I am AC!!! program Ural683; var a,m,n:longint; k:array[0..50]of longint; begin readln(n); m:=0; while n<>1 do begin inc(m); n:=n-n shr 1; k[m]:=n; end; writeln(m); for a:=1 to m do write(k[a],' '); end. Give me tests... 24 5 11 6 3 2 1 48 6 23 12 6 3 2 1 correct? My AC Solution: 24 5 12 6 3 1 1 ---- 48 6 24 12 6 3 1 1 ---- 1024 10 512 256 128 64 32 16 8 4 2 1 Good luck. Edited by author 30.03.2009 22:54 I`m interesed too, is it correct answer for this example: ***input*** 12 ***output*** 4 6 3 1 1 as in exanple answer is a little different, it is 4 5 3 2 1 |
|
|