Let's sequence S(n) = {s[1], s[2], ..., s[n]} is optimal sequence for the first n steps. L[i] is max number when we can get one space using S(n) for any number in range [1..L[i]]: firstly, we apply s[n], then s[n-1] and etc.
Now let's get next s[n+1]. Suppose we found s[n+1] and want get L[n+1]. Always L[n+1] + 1 = q*s[n+1] + r, 0<=r<s[n+1]. L[n+1] is max number => for L[n+1] + 1 we need at least n+2 steps => q + r >= L[n] + 1. But L[n+1] + 1 is min number when using S(n+1) we can't get one space => r->max, q->min =>
r = s[n+1] - 1, q = L[n] + 1 - r =>
L[n+1] + 1 = q * s[n+1] + r =>
L[n+1] = (L[n] - s[n+1] + 2) * s[n+1] + s[n+1] - 2 -> max (where arg is s[n+1])
=> s[n+1] = (L[n] + 1) / 2
But using symmetry we can give s[n+1] = floor(L[n] / 2) + 1 (we choice bigger number because s[2] > 1).
=> L[n+1] = q * s[n+1] + r - 1, q = L[n] + 1 - r, r = s[n+1] - 1.



Edited by author 26.02.2022 01:27

Edited by author 26.02.2022 01:27

I'd like to thank authors for this problem - it became one of my favorite on Timus!
Thanks again for very interesting problem!
:-)

Nice problem.
Playing out with small numbers and sample could help in sequence instantiation.

My solution is only 30 lines of c++ code O(L) though.

Hint: imagine we have sequence which can replace up to L spaces afterall. Then to enlarge our sequence we insert L/2 + 1 in the beginning. Maximum L could be computed via straightforward iteration starting from lax max_L
Example:

seq: 2
max_L: 2

seq: 2, 2/2 + 1 = 2, 2
max_L: 2, 4

seq: 2, 2, 4/2 + 1 = 2, 2, 3
max_L: 2, 4, 10

seq: 2, 2, 3, 10/2 + 1 = 2, 2, 3, 6
max_L: 2, 4, 10, 40

Etc.
GL.

In the statement it is said, that

"If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces sequences of up to K spaces (K ≥ L) for a maximal possible K."

So for the sample right answer would be

4
11
5
3
2

and maximum possible k = 110

Where I was wrong, people? :)

Hi Experts,
  Can you suggest how to approach solving such problems. I am getting no clues at all. Moreover we know nothing about total  number of spaces in the text.

regards
Anupam

I think that checker is not correct. Admins, please, check test7.

Here is my program:program Space;
  var L, R, I, J, K : longint;
      s : array [1.. 1000] of longint;
  begin
    readln (L);
    if L < 2 then R := 0;
    for I := 1 to 1000 do s [I] := 0;
    if L > 1 then
      begin
        I := 2;
        J := 2;
        s [1] := 2;
        R := 1;
        repeat
          if L > J then
            begin
              inc (R);
              s [R] := I;
              if R > 3 then inc (s [R]);
              I := J + 1;
              J := (I + 2 - s [R]) * s [R] - 2;
            end;
        until L <= J;
      end;
    writeln (R);
    for I := R downto 1 do writeln (s [I]);
  end.

Petrov should use F7 instead of ctrl+F7 :)

А тут еще жюри подсунуло текст отформатированный какой-то противным DOSовским текстовым редактором
->
А тут ещё жюри подсунуло текст, отформатированный каким-то противным DOSовским текстовым редактором

370
371
199999

I haven't found equivalent of this in it:

If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces sequences of up to K spaces (K >= L) for a maximal possible K. If there are several optimal schemes, you may give any one of them.

if L=11
Why it WRONG?
4
5
4
3
2

the answer is:
4
11
5
3
2

Is it right?who can help me?