POI Sum of one-sequence 連續串之和 解題報告
題目描述
我們定義連續串為一串整數，它的第一個元素為0，並且任兩個相鄰元素之差的絕對值為1。更精確的說，如果[a1, a2, …, an]為一個連續串，那麼有： 對於任意的1<=ka1=0
任務： 寫一個程序： 在文件SUM.IN中讀入連續串的長度和連續串中所有元素的和； 找出一個給定長度的連續串，使其所有元素的和與給定的和相等，或者指出這樣的連續串不存在。 將結果輸出到文件SUM.OUT中。
輸入格式： 在文本文件SUM.IN的第一行有一個整數n，滿足1n10000，表示連續串中元素的個數。第二行為一個整數S，滿足|S|<=50000000，表示連續串中所有元素之和。
輸出格式： 如果能夠找到滿足條件的連續串，你應當在文本文件SUM.OUT的前n行輸出n個整數（每行一個），表示連續串中的各個元素（第k個元素輸出在第k行）。否則，文件應該只包含一個單詞NIE（為波蘭語的「否」）。
樣例： 輸入（SUM.IN）： 8 4
輸出（SUM.OUT）： 0 1 2 1 0 -1 0 1
思路分析
本題採用構造法。時間複雜度O(n)，空間複雜度O(n)。先建立一個從0到n-1的數列，並求出要求的和與數列的和的差值。如果差值為奇數則無解，如 差值為偶數，則逐漸減小差值。比如將最後一位改為降序，則差值減小2，倒數第二位改為降序則差值減小4，以此類推。可以先從前面減，減到很小的時候（不能 再減）再從右面減。所謂減就是把這一位改為上一位減一，而保持後面的升序。
完整代碼
//By Ceeji
//Date: 2009-4-10
//Type: Gouzao
//HAOI test 1 - Problem 1 : sum (POI)
//State : Accepted
Program sum;
Const
inf='sum.in';
ouf='sum.out';
maxn=10000;
Var
n,s,i,j,l:longint;
x:longint;
q:qword;
b:array[1..maxn]of boolean;
begin
q:=1;
assign(input,inf); reset(input);
assign(output,ouf); rewrite(output);
fillchar(b,sizeof(b),0);
readln(n,s);
close(input);
x:=((n-1)*n div 2-s);
if odd(x) then begin writeln('NIE'); close(output); exit; end;
l:=2;
while x>=(n-l+1)<<1 do
begin
b[l]:=true;
dec(x,(n-l+1)<<1);
inc(l);
end;
l:=1;
b[n-(x>>1)+1]:=true;
j:=0;
writeln(j);
for i:=2 to n do
begin
if b[i] then dec(j) else inc(j);
inc(ans,j);
writeln(j);
end;
close(output);
end.
© 轉載需附帶本文連結，依 CC BY-NC-SA 4.0 釋出。