10049 - Self-describing Sequence

[andmej]

i didn't use formula but just a double for loop to generate the points where the sequence changes (so I store the values 1,2,4,6,9,12,16,20,24, ....). My program runs in 0.1 seconds using 3MB of memory. I think I can improve the running time a bit, but don't know about the memory. I was wondering how people can solving this problem in 0.000 seconds using only 64k of memory.

What would be the algorithm to generate this change-points with a double for loop? I've only been able to generate them recursively and I get Time Limit Exceeded.

[ergysr]

I am new to the judge and have a lot of trouble with my submissions. I get WA on every problem

Please somebody look my source code for this problem, compile it, run it and test it. I think my output is correct but so should be something else with the judging system. I use Pascal. Please heeeeelp me

Code: Select all

{#10049 Self-Describing Sequence}

program sequence;
const n=673365;
var t:array[1..n] of longint;
 i,j,k,pos:longint;


begin
t[1]:=1;
t[2]:=3;
i:=3;
j:=3;
pos:=1;
repeat

for k:=pos to n do if i<=t[k+1] then begin

                                          t[j]:=t[j-1]+k+1;
                                          pos:=k;
                                          break;                       
                                     end;
inc(i);
inc(j);

until i>n;


repeat
readln(k);
for i:=1 to n do if t[i]>=k then begin
writeln(i);
break;
end;
until k=0;


end.

[ergysr]

I get WA on every problem i submit in pascal.

Please somebody look my source code for this problem
{#10049 Self-Describing Sequence}, compile it, run it and test it. I think my output is correct. Please heeeeelp me

Code: Select all

{#10049 Self-Describing Sequence}

program sequence;
const n=673365;
var t:array[1..n] of longint;
 i,j,k,pos:longint;


begin
t[1]:=1;
t[2]:=3;
i:=3;
j:=3;
pos:=1;
repeat

for k:=pos to n do if i<=t[k+1] then begin

                                          t[j]:=t[j-1]+k+1;
                                          pos:=k;
                                          break;                       
                                     end;
inc(i);
inc(j);

until i>n;


repeat
readln(k);
for i:=1 to n do if t[i]>=k then begin
writeln(i);
break;
end;
until k=0;


end.

[ergysr]

Need immediate help, on every problem i submit on the judge, I GET WA. I submit in pascal.
Look at my source for this problem. Please someone pm me and help me.

Code: Select all

{#10049 Self-Describing Sequence}

program sequence;
const n=673365;
var t:array[1..n] of longint;
 i,j,k,pos:longint;


begin
t[1]:=1;
t[2]:=3;
i:=3;
j:=3;
pos:=1;
repeat

for k:=pos to n do if i<=t[k+1] then begin

                                          t[j]:=t[j-1]+k+1;
                                          pos:=k;
                                          break;                       
                                     end;
inc(i);
inc(j);

until i>n;


repeat
readln(k);
for i:=1 to n do if t[i]>=k then begin
writeln(i);
break;
end;
until k=0;


end.