/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
正整数 A,B,C,L,R が与えられます。
ただし、L \leq R です。
f(n)=n^3+An^2+Bn+C
と定義します。
\mathtt{+} と \mathtt{-} からなる空でない文字列 S に対して
g(S) = \sum_{i=1}^{|S|} \begin{cases} f(i) & (S_i = \mathtt{+}) \\ -f(i) & (S_i = \mathtt{-}) \end{cases}
と定義します。
ただし、S_i は S の i 文字目を表します。
g(S')=k となるような S の空でない部分文字列 S' が存在するとき、k は S から生成可能であるということにします。
以下の条件を満たすような文字列 S を一つ構成してください。
- 1 \leq |S| \leq 2 \times 10^6
- S は \mathtt{+} と \mathtt{-} からなる文字列である。
- 上の 2 条件を満たすもののうち、S から生成可能な L 以上 R 以下の整数の個数が最大である。
さらに、構成した文字列を S として、k=L,L+1,\dots,R について、以下の条件を満たすような 2 整数 l,r が存在するかを判定して、存在するならば 1 つ求めてください。
- 1 \leq l \leq r \leq |S|
- S の l 文字目から r 文字目までを S' とすると、g(S')=k
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、AB は ABC の部分文字列ですが、AC は ABC の部分文字列ではありません。
制約
- 1 \leq A,B,C \leq 10^5
- 1 \leq L \leq R \leq \min(L+10^5,10^{14})
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B C L R
出力
答えを以下の形式で出力せよ。
S
\mathrm{output}_{L}
\mathrm{output}_{L+1}
\vdots
\mathrm{output}_{R}
ここで、\mathrm{output}_i は k=i についての出力を表す。
条件を満たす 2 整数 l,r が存在するならば以下の形式で出力せよ。
l r
存在しないならば -1 を出力せよ。
解が複数ある場合、どれを出力してもよい。
入力例 1
2 2 3 22 23
出力例 1
+---+--+ 2 5 6 8
f(n)=n^3+2n^2+2n+3
f(1)=8,\; f(2)=23,\; f(3)=54,\; f(4)=107
です。
g(\mathtt{---+})=-f(1)-f(2)-f(3)+f(4)=-8-23-54+107=22
g(\mathtt{--+})=-f(1)-f(2)+f(3)=-8-23+54=23
なので、22 も 23 も \mathtt{---+} から生成可能です。
入力例 2
1 2 2 5 7
出力例 2
++ -1 2 2 -1
Score : 900 points
Problem Statement
You are given positive integers A,B,C,L,R.
Here, L \leq R.
Define
f(n)=n^3+An^2+Bn+C.
For a non-empty string S consisting of \mathtt{+} and \mathtt{-}, define
g(S) = \sum_{i=1}^{|S|} \begin{cases} f(i) & (S_i = \mathtt{+}) \\ -f(i) & (S_i = \mathtt{-}) \end{cases}.
Here, S_i denotes the i-th character of S.
An integer k is said to be generable from S if there exists a non-empty substring S' of S such that g(S')=k.
Construct a string S that satisfies the following conditions.
- 1 \leq |S| \leq 2 \times 10^6
- S is a string consisting of \mathtt{+} and \mathtt{-}.
- Among the strings satisfying the two conditions above, S maximizes the number of integers between L and R, inclusive, that are generable from S.
Furthermore, for the constructed string S and each k=L,L+1,\dots,R, determine whether there exist two integers l,r satisfying the following conditions, and if they exist, find one such pair.
- 1 \leq l \leq r \leq |S|
- Letting S' be the string formed by the l-th through r-th characters of S, we have g(S')=k.
What is a substring?
A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, AB is a substring of ABC, but AC is not a substring of ABC.
Constraints
- 1 \leq A,B,C \leq 10^5
- 1 \leq L \leq R \leq \min(L+10^5,10^{14})
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B C L R
Output
Print a solution in the following format:
S
\mathrm{output}_{L}
\mathrm{output}_{L+1}
\vdots
\mathrm{output}_{R}
Here, \mathrm{output}_i denotes the output for k=i.
If there exist two integers l,r satisfying the conditions, print them in the following format:
l r
If they do not exist, print -1.
If there are multiple solutions, you may print any of them.
Sample Input 1
2 2 3 22 23
Sample Output 1
+---+--+ 2 5 6 8
We have
f(n)=n^3+2n^2+2n+3 and
f(1)=8,\; f(2)=23,\; f(3)=54,\; f(4)=107.
Since
g(\mathtt{---+})=-f(1)-f(2)-f(3)+f(4)=-8-23-54+107=22 and
g(\mathtt{--+})=-f(1)-f(2)+f(3)=-8-23+54=23,
both 22 and 23 are generable from \mathtt{---+}.
Sample Input 2
1 2 2 5 7
Sample Output 2
++ -1 2 2 -1