|
|
вернуться в форумМоя программа ЗДАЛАСЬ за O(n) Послано OSPU 10 мар 2003 21:06 program a1032; var mas,a:array[0..10001] of integer; i,j,n:integer; s:longint; begin for i:=0 to 10001 do mas[i]:=0; readln(n); s:=0; for i:=1 to n do begin readln(a[i]); s:=(s+a[i]) mod n; if s=0 then begin writeln(i); for j:=1 to i do writeln(a[j]); halt; end; if mas[s]<>0 then begin writeln(i-j-1); for j:=mas[s]+1 to i do writeln(a[j]); halt; end; mas[s]:=i; end; writeln(0); end. plz write just English.. Послано Pasha 10 мар 2003 21:51 ? As you know i can prove that there is 1<=i<j<=n that: ( a[i]+a[i+1]+...+a[j-1]+a[j] ) mod n =0 because as box-principle(or pigeonhole) if we define b[i]:=a[i] mod n and b[0]:=0; we see b[x] es should be in range [0..n-1] but they are n+1 b(b[0] to b[n]) and it means there is two b (like (b[i],b[j]) that hey are equal b[i]=b[j] so we see: P1=a[1]+a[2]+a[3]+..a[j]=l*n+b[j] and P2=a[1]+a[2]+a[3]+..a[i]=k*n+b[i] so if we calculate p1-p2 we see: P3=a[j]+a[j-1]+a[j-2]+..a[i+2]+a[i+1]= (l-k)*n+b[j]-b[i] and we knew b[i]=b[j] so P3=(l-k)*n ----> p3 mod n =0!!!! so we should calcualte all b(s) and find I and J so: (with this algorithm we dont need to read all numbers!) here is my code: Var n,i,k :integer; a :array[0..10000] of integer; m :array[0.. 9999] of integer; begin readln(n); fillchar(m,sizeof(m),-1); m[0]:=0; k:=0; repeat inc(a[0]); readln(a[a[0]]); k:=(k+a[a[0]]) mod n; if m[k]=-1 then m[k]:=a[0] else begin writeln(a[0]-m[k]); for i:=m[k]+1 to a[0] do writeln(a[i]); break; end; until false; end. ~~~~~~~~~~~~~~~~~~~~~~ Please tell me if you dont understand it at all. and your notice about it Sincerely Aidin_n7@hotmail.com OSPU stated: my program's ACCEPTED with O(n) complexity (-) |
|
|