| ENG RUS | Timus Online Judge |
Discussion of Problem 1126. Magnetic StormsPage 1 Ted It can be solve in O(N+M) [8] // Problem 1126. Magnetic Storms 7 May 2004 13:08 Vlad Veselov Can you tell more about this solution? [4] // Problem 1126. Magnetic Storms 7 May 2004 18:39 Ted Re: Can you tell more about this solution? [3] // Problem 1126. Magnetic Storms 7 May 2004 20:29 I'm not good at English. A[I] is the Ith number. First,try to count a array F. F[I] means the nearest number A[F[I]]: A[F[I]]>A[I] and F[I]>I. You can count F in O(N). Find largest number in [L,R],just find a min I,F[I]>R. So you can solve the problem in O(N+M). And this problem is RMQ problem, also have a very hard standard solution in O(N+M). Edited by author 07.05.2004 20:31 bug27 Re: Can you tell more about this solution? // Problem 1126. Magnetic Storms 30 Mar 2005 18:37 strong! St.Max [UPML KNU] Re: Can you tell more about this solution? // Problem 1126. Magnetic Storms 3 May 2006 21:56 Good idea. But I had to be very carefully solving it. Edited by author 04.05.2006 20:00 c_pp Re: Can you tell more about this solution? // Problem 1126. Magnetic Storms 8 Jan 2017 01:27 Thanks, @Ted. Your idea is brilliant. I count F[] array with O(N) , used stack. + buffered i/o ==> result is very good: AC. 0.001s Partisan [UPML KNU] Re: It can be solve in O(N+M) [2] // Problem 1126. Magnetic Storms 20 May 2006 19:48 There is an interesting situation here: when I declared arrays a and f with size 1..25000, I got WA#2. When I changed them to 1..25001, I got AC... BlindButcher Re: It can be solve in O(N+M) [1] // Problem 1126. Magnetic Storms 22 Oct 2008 17:47 I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Mewtwo Re: It can be solve in O(N+M) // Problem 1126. Magnetic Storms 20 Mar 2016 18:58 BlindButcher wrote 22 October 2008 17:47 I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Thanks for sharing the idea... :) Vlad Veselov My solution is O(N * 17) but it fits in memory only on C++. Can anyone give me better solution? My mailbox is vlad_veselov@mail.ru. [3] // Problem 1126. Magnetic Storms 20 Apr 2004 21:08 Oberon (Yura Znovyak) Re: My solution is O(N * 17) but it fits in memory only on C++. Can anyone give me better solution? My mailbox is vlad_veselov@mail.ru. [2] // Problem 1126. Magnetic Storms 21 Apr 2004 00:01 It is solvable in PASCAL too. AC in 0.046s with 489 KB of memory. But here is Delphi report: " Mine is on Borland Delphi Version 15.0 Copyright (c) 1983,2002 Borland Software Corporation MAGNSTOR.PAS(1) MAGNSTOR.PAS(1) MAGNSTOR.PAS(1) MAGNSTOR.PAS(137) 138 lines, 0.02 seconds, 11564 bytes code, 113813 bytes data. " It uses only 113813 bytes of memory. If I am not mistaken (I have solved it a long time ago) my solution is O(N log N). Romanchik Vitaly Re: My solution is O(N * 17) but it fits in memory only on C++. Can anyone give me better solution? My mailbox is vlad_veselov@mail.ru. [1] // Problem 1126. Magnetic Storms 14 Jul 2004 05:32 Use Hash-table to store the results !!!! Romanchik Vitaly Re: My solution is O(N * 17) but it fits in memory only on C++. Can anyone give me better solution? My mailbox is vlad_veselov@mail.ru. // Problem 1126. Magnetic Storms 14 Jul 2004 05:34 There is O(n) algorithm !!!!! If you want to know more mail me VRomanchik@Tut.by Ksenya What does that mean: "If the intensity was low within the last 6 hours..." [1] // Problem 1126. Magnetic Storms 21 Aug 2003 22:46 I have WA. But I just found all maximum values in 1..m, 2..m+1, 3..m+2 etc. And I thought that it is what I must to do. But what does that mean: "If the intensity was low within the last 6 hours the magnetic field was regarded to be quiet; the children were let outdoors and played all the prescript time. Otherwise new peaks were probable and the children spent their time indoors." What should I do with 6 hours? Or maybe it is just an example? GvPlankid Re: What does that mean: "If the intensity was low within the last 6 hours..." // Problem 1126. Magnetic Storms 26 Sep 2004 22:37 Don't mind. it 's just the background, It is nothing with the problem. noname why i got WA. I've compared my sol with others, they nearly the same!! // Problem 1126. Magnetic Storms 16 Jun 2003 21:09 Here's my code. my email: klux_13@sina.com program magnetic_storms; var n,m:integer; a:array[1..25000] of longint; h:array[0..100000] of integer; procedure init; var d:longint; begin fillchar(a,sizeof(a),0); readln(m); n:=0; readln(d); while d<>-1 do begin inc(n); a[n]:=d; readln(d); end; end; procedure work; var i,max:longint; begin fillchar(h,sizeof(h),0); h[0]:=1; max:=0; for i:=1 to m do begin inc(h[a[i]]); if a[i]>max then max:=a[i]; end; writeln(max); for i:=m+1 to n do begin inc(h[a[i]]); dec(h[a[i-m]]); if a[i]>max then max:=a[i] else if h[max]=0 then begin while h[max]=0 do dec(max); end; writeln(max); end; end; begin assign(input,'1126.in'); reset(input); init; work; end. Alex[LSD] Help! I am quite sure this should work but it gets WA. WHY?!!! [2] // Problem 1126. Magnetic Storms 6 Jun 2003 10:38 My Email : caa@baga.ac.net.ru =-=-=-=-= Program acm_1126; Var A : array [1..25000] of longint; G : array [0..400,0..299] of longint; Nums : array [0..400] of longint; i,j,k : longint; M,N : longint; Begin FillChar(G,sizeOf(G),0); FillChar(Nums,sizeOf(Nums),0); Read(M); i:=0; N:=0; While i<>-1 do BegiN Read(i); If i<>-1 then Begin Inc(N); A[N]:=i; End; End; For i:=1 to N do Begin j:=A[i] div 300; k:=A[i] mod 300; Inc(G[j,k]); Inc(Nums[j]); If i>M then Begin j:=A[i-M] div 300; k:=A[i-M] mod 300; Dec(G[j,k]); Dec(Nums[j]); End; If i>=M then Begin k:=400; While Nums[k]=0 do Dec(k); j:=299; While G[k,j]=0 do Dec(j); writeln(300*k+j); End; End; End. Tony Re: Help! I am quite sure this should work but it gets WA. WHY?!!! [1] // Problem 1126. Magnetic Storms 6 Jun 2003 15:46 Read this program more clear again! Alex[LSD] Oh believe me I ve read it tens of times. And I just cant figure out how it doesnt get AC... 8-( [HEEEEEELP!!!] // Problem 1126. Magnetic Storms 10 Jun 2003 10:49 Tony I only use search with structure Hash and it got AC.I faint. // Problem 1126. Magnetic Storms 4 Jun 2003 10:00 If someone need help,sent to my E-mail. coma Is there a solution can solve the problem faster than a o(m*n^0.5) algorithm) [2] // Problem 1126. Magnetic Storms 3 Jun 2003 11:15 Nick Permyakov Re: Is there a solution can solve the problem faster than a o(m*n^0.5) algorithm) // Problem 1126. Magnetic Storms 16 Aug 2003 18:34 There is an O(n) solution for this problem. WinTokk Re: Is there a solution can solve the problem faster than a o(m*n^0.5) algorithm) // Problem 1126. Magnetic Storms 15 Apr 2004 18:00 Mine is O(M*logM). Edited by author 15.04.2004 18:02 Koala I use the algorithm of binary search, but still get WA. // Problem 1126. Magnetic Storms 13 Feb 2003 10:53 {This is my program. I really appreciate your help.} program p1126; const maxn=25000; var a,c:array [1..maxn] of longint; m,n,k,tail,i,j:longint; procedure insert(x:longint); var low,high,mid:longint; begin low:=1; high:=tail; while low<high do begin mid:=(low+high) shr 1; if x>=c[mid] then low:=mid+1 else high:=mid; end; move(c[low],c[low+1],sizeof(longint)*(tail-low+1)); inc(tail); c[low]:=x; end; procedure delete(x:longint); var low,high,mid:longint; begin low:=1; high:=tail; mid:=0; while low<high do begin mid:=(low+high) shr 1; if x=c[mid] then break; if x<c[mid] then high:=mid-1 else low:=mid+1; end; move(c[mid+1],c[mid],sizeof(longint)*(tail-mid)); dec(tail); end; begin read(m); n:=0; read(k); while k<>-1 do begin inc(n); a[n]:=k; read(k); end; c[1]:=-maxlongint; c[2]:=maxlongint; tail:=2; for j:=1 to m do insert(a[j]); writeln(c[tail-1]); i:=0; for j:=m+1 to n do begin inc(i); delete(a[i]); insert(a[j]); writeln(c[tail-1]); end; end. Andrey Popyk (popyk@ief.tup.km.ua) Why this program WA? Gime me a test, please. [1] // Problem 1126. Magnetic Storms 25 Sep 2002 16:36 CONST DimQ = 25007; TYPE Elem = record Num:longint; Time:integer; end; VAR Queue:Array[1..DimQ] of Elem; LenQ:integer; MyEl:Elem; PROCEDURE Add(El:Elem); var T:integer; begin inc(LenQ); T:=LenQ; while (T<>1) and (Queue[T div 2].Num < El.Num) do begin Queue[T]:=Queue[T div 2]; T:=T div 2; end; Queue[T]:=El; end; PROCEDURE DelTop; var El:Elem; T:integer; begin El:=Queue[LenQ]; dec(LenQ); T:=1; while (2*T+1<=LenQ) and (Queue[2*T+1].Num > El.Num) or (2*T<=LenQ) and (Queue[2*T].Num > El.Num) do begin if (2*T+1<=LenQ) and (Queue[2*T+1].Num > Queue[2*T].Num) then begin Queue[T]:=Queue[2*T+1]; T:=2*T+1 end else begin Queue[T]:=Queue[2*T]; T:=2*T end; end; Queue[T]:=El; end; PROCEDURE Solve; var All,M:integer; begin All:=0; readln(M); repeat readln(MyEl.Num); if MyEl.Num = -1 then break; inc(All); MyEl.Time:=All; Add(MyEl); if All>=M then begin while Queue[1].Time<=All-M do DelTop; writeln(Queue[1].Num); end; until false; end; BEGIN { assign(INPUT,'1126.dat'); reset(INPUT);} Solve; END. Andrey Popyk (popyk@ief.tup.km.ua) And why this program CRASH??? // Problem 1126. Magnetic Storms 25 Sep 2002 16:39 VAR A:Array[1..25007] of longint; M,Max,K,i,j:longint; BEGIN readln(M); repeat inc(K); readln(A[K]); if A[k]=-1 then break; until false; dec(K); for i:=1 to K-M+1 do begin Max:=i; for j:=i to i+M-1 do if A[j]>A[Max] then Max:=j; writeln(A[Max]); end; END. Marko Tintor (marko@pkj.co.yu) Why Time Limit? complexity (n-m)*log(m) // Problem 1126. Magnetic Storms 20 Jul 2002 17:55 Idea: Using pointer connected heap and queue. Heap for maximum element. Queue to find element what needs to be extracted from heap. #include <fstream.h> ifstream fin("magnetic.dat"); //#define fin cin const int max=14001; short m, value[max], queue[max], heap[max+1], s,c,a; void heap_swap(short a, short b) { short x; x=heap[a]; heap[a]=heap[b]; heap[b]=x; x=queue[heap[a]]; queue[heap[a]]=queue[heap[b]]; queue[heap[b]]=x; } void push() { short e=(s+c)%max; value[e]=a; queue[e]=++c; heap[c]=e; short k=c; while(k>1 && value[heap[k>>1]]<value[heap[k]]) { heap_swap(k>>1,k); k=k>>1; } } void pop() { cout << value[heap[1]] << endl; short k=queue[s]; s++; s%=max; heap_swap(k,c--); while(k>1 && value[heap[k>>1]]<value[heap[k]]) { heap_swap(k>>1,k); k=k>>1; } short l=k<<1, m; while(l<=c) { m=k; if(value[heap[l]]>value[heap[m]]) m=l; if(l+1<=c && value[heap[l+1]]>value[heap[m]]) m=l+1; if(m==k) break; heap_swap(m,k); k=m; l=k<<1; } } void main() { fin >> m; for(int i=0; i<m; i++) {fin >> a; push();} while(1) { pop(); fin >> a; if(a==-1) break; push(); } } raxtinhac Magnetic storm : Please help, I tried many tests but it get WA // Problem 1126. Magnetic Storms 30 May 2002 19:30 Here is my program : const max = 15000; fi = ‘magnetic.inp’; var a,tt,cs :array[1..max] of longint; m,n,x :longint; procedure doicho(r,c :longint); var tam :longint; begin tam := a[r]; a[r] := a[c]; a[c] := tam; cs[ tt[r] ] := c; cs[ tt[c] ] := r; tam := tt[r]; tt[r] := tt[c]; tt[c] := tam; end; procedure downheap(r :longint); var c :longint; begin while r*2 <= n do begin c := r*2; if c < n then if a[c] < a[c+1] then inc(c); if a[r] < a[c] then doicho(r,c) else exit; r := c; end; end; procedure upheap( r :longint); var c :longint; begin while r > 1 do begin c := r div 2; if a[c] < a[r] then doicho(r,c) else exit; r := c; end; end; {--------------------------------------------------------------------- ------} procedure them; var t :longint; begin inc(m); if m > n then m := 1; t := cs[m]; a[t] := x; upheap(t); downheap(t); end; {--------------------------------------------------------------------- ------} begin assign(f, fi); reset(f); readln(f, m); for n := 1 to m do begin readln(f, a[n]); tt[n] := n; cs[n] := n; if a[n] = -1 then halt; upheap(n); end; repeat writeln(a[1]); readln(f, x); if x = -1 then break; them; until false; close(f); end. qwt Why I got WAЈїЈїЈїЈїЈїЈїЈї [1] // Problem 1126. Magnetic Storms 25 Apr 2002 18:49 var a:array[0..14000] of longint; b:array[-1..200000] of longint; n,i,j,k,max:longint; begin read(n); fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); b[- 1]:=10000;max:=-1; for i:=0 to n-2 do begin read(a[i]); if a[i]=-1 then begin writeln(max);halt;end; inc(b[a[i]]); if a[i]>max then max:=a[i]; end; read(j); while j>=0 do begin inc(i); i:=i mod n; dec(b[a[i]]);a[i]:=j; inc(b[j]); if j>max then max:=j; while b[max]<=0 do dec(max); writeln(max); read(j); end; end. SOM (Sokolov Maxim_NN_Liceum165) Re: Why I got WAЈїЈїЈїЈїЈїЈїЈї // Problem 1126. Magnetic Storms 17 Oct 2010 00:31 Because first chislo is m (don't n) Edited by author 17.10.2010 00:31 Edited by author 17.10.2010 00:31 qwt Why I got WA? Who can help me,and give me some hints? [2] // Problem 1126. Magnetic Storms 6 Apr 2002 19:25 var a:array[0..14000] of integer; b:array[0..32767] of integer; n,i,j,k,max:integer; begin readln(n); fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); b[0]:=1;max:=0; for i:=0 to n-2 do begin readln(a[i]); if a[i]=-1 then begin writeln(max);halt;end; inc(b[a[i]]); if a[i]>max then max:=a[i]; end; readln(j); while j>=0 do begin inc(i); i:=i mod n; dec(b[a[i]]);a[i]:=j; inc(b[j]); if j>max then max:=j; k:=max; if b[max]=0 then for max:=k-1 downto 0 do if b[max]>0 then break; writeln(max); readln(j); end; end. MadPsyentist/Sam Re: Why I got WA? Who can help me,and give me some hints? [1] // Problem 1126. Magnetic Storms 8 Apr 2002 01:50 If you explain the idea of your solution, I might be able to give a hint. Anyway, I compiled your program under FreePascal and it produces nothing for this little case. Is it the same on your side? 1 38197 11776 80610 -1 Koala But M>1 // Problem 1126. Magnetic Storms 13 Feb 2003 10:54 > If you explain the idea of your solution, I might be able to give a hint. > > Anyway, I compiled your program under FreePascal and it produces > nothing for this little case. Is it the same on your side? > 1 > 38197 > 11776 > 80610 > -1 blue dog Why I get WA?Here is my program. // Problem 1126. Magnetic Storms 4 Apr 2002 19:07 #include<stdio.h> #include<stdlib.h> #include<string> #include<assert.h> FILE *inp,*outp; long a[14101]; long b[14101]; long g[25101]; long m,i; void Change(long t1,long t2){ long k=a[t1];a[t1]=a[t2];a[t2]=k; k=b[t1];b[t1]=b[t2];b[t2]=k; g[b[t1]]=t1;g[b[t2]]=t2; } void Move(long i){ if (i>1&&a[i]>a[i/2]){ Change(i,i/2); Move(i/2); return; }else if (i*2<=m) if (a[i]<a[i*2]||a[i]<a[i*2+1]) if (a[i*2]>a[i*2+1]){ Change(i,i*2); Move(i*2); }else{ Change(i,i*2+1); Move(i*2+1); }; } main(){ inp=fopen("input.004","r");assert(inp); outp=fopen("output.004","w");assert(outp); memset(a,255,sizeof(a)); fscanf(inp,"%ld",&m); for (i=1;i<=m;i++){ fscanf(inp,"%ld",&a[i]); if (a[i]==-1){ fprintf(outp,"%ld\n",a[1]); exit(-1); }; g[i]=i;b[g[i]]=i; Move(i); } i=m; while(true){ fprintf(outp,"%ld\n",a[1]); i++;fscanf(inp,"%ld",&a[g[i-m]]); if (a[g[i-m]]==-1) exit(-1); g[i]=g[i-m];b[g[i]]=i; Move(g[i]); } fclose(outp); } qwt can anyone give me some tests? [5] // Problem 1126. Magnetic Storms 3 Apr 2002 20:00 var a:array[0..14000] of integer; b:array[0..25000] of integer; n,i,j,k,max:integer; begin readln(n); fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); b[0]:=1;max:=0; for i:=0 to n-2 do begin readln(a[i]); if a[i]=-1 then begin writeln(max);halt;end; inc(b[a[i]]); if a[i]>max then max:=a[i]; end; readln(j); while j>=0 do begin inc(i); i:=i mod n; dec(b[a[i]]);a[i]:=j; inc(b[j]); if j>max then max:=j; k:=max; if b[max]=0 then for max:=k-1 downto 0 do if b[max]>0 then break; writeln(max); readln(j); end; end. Calin Ciutu (ciutu@go.ro) Re: can anyone give me some tests? [4] // Problem 1126. Magnetic Storms 4 Apr 2002 01:36 for 3: 108900 and for 4: 598950 Calin Ciutu (ciutu@go.ro) Re: can anyone give me some tests? [3] // Problem 1126. Magnetic Storms 4 Apr 2002 01:48 Excuse me !! This are some tests for 1206 . --------------------------------------------- Here is a "good" test for 1126 : Input : 5 0 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 10 11 12 0 0 0 0 0 1 2 10 2 -1 Output : 4 5 6 7 8 9 10 10 10 10 10 10 9 8 7 6 5 10 11 12 12 12 12 12 0 1 2 10 10 qwt I got the right answer in your test,but still WA [2] // Problem 1126. Magnetic Storms 6 Apr 2002 19:22 > Excuse me !! This are some tests for 1206 . > > --------------------------------------------- > > Here is a "good" test for 1126 : > > Input : > > 5 > 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9 > 10 > 10 > 9 > 8 > 7 > 6 > 5 > 4 > 3 > 2 > 1 > 10 > 11 > 12 > 0 > 0 > 0 > 0 > 0 > 1 > 2 > 10 > 2 > -1 > > > Output : > > 4 > 5 > 6 > 7 > 8 > 9 > 10 > 10 > 10 > 10 > 10 > 10 > 9 > 8 > 7 > 6 > 5 > 10 > 11 > 12 > 12 > 12 > 12 > 12 > 0 > 1 > 2 > 10 > 10 Vlad Ionescu Re: I got the right answer in your test,but still WA [1] // Problem 1126. Magnetic Storms 8 Jun 2003 02:33 Your problem is in the array constraints: b:array[0..25000] of integer; The problem states that the values are between 0 and 100000, so b [100000] does not exist... Vlad Ionescu Re: I got the right answer in your test,but still WA // Problem 1126. Magnetic Storms 8 Jun 2003 02:36 > Your problem is in the array constraints: > b:array[0..25000] of integer; > The problem states that the values are between 0 and 100000, so b > [100000] does not exist... Got AC with this... var a:array[0..14000] of longint; b:array[0..100000] of longint; n,i,j,k,max:longint; begin {The rest is the same} end. Got AC with this... qwt Why I got 'Wrang answer'? [3] // Problem 1126. Magnetic Storms 3 Apr 2002 16:07 var a:array[0..14000] of integer; b:array[0..25000] of integer; n,i,j,k,max:integer; begin readln(n); fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); b[0]:=1; for i:=0 to n-2 do begin readln(a[i]); inc(b[a[i]]); if a[i]>max then max:=a[i]; end; readln(j); while j>=0 do begin inc(i); i:=i mod n; dec(b[a[i]]);a[i]:=j; inc(b[j]); if j>max then max:=j; k:=max; if b[max]=0 then for max:=k-1 downto 0 do if b[max]>0 then break; writeln(max); readln(j); end; end. MadPsyentist/Sam Re: Why I got 'Wrang answer'? [2] // Problem 1126. Magnetic Storms 4 Apr 2002 12:06 I don't know your logic truely but I test your program (compiled under DevPascal (FreePascal), Windows98SE) and found your program get Runtime Error and Wrong Answer many time when the value of measure is high. It didn't crash but the error message was redirected to the output instead , I don't know why. I randomly generate the test data and this is a case your program make wrong output, but no Runtime Error Input: 6 29261 440 1757 22684 2247 11022 25134 22643 6002 3108 16056 12612 29390 25192 6271 26467 7802 23059 1921 -1 My AC program output: 29261 25134 25134 25134 25134 25134 25134 29390 29390 29390 29390 29390 29390 26467 Your output: 29261 27029 27029 27029 27029 27029 27029 29390 29390 29390 29390 29390 29390 27029 If you edit your program and pass this test data but still get WA, you can ask me for me test. My e-mail address is piyawut@se-ed.net. MadPsyentist/Sam I mean "more test" ,not "me test" [1] // Problem 1126. Magnetic Storms 4 Apr 2002 12:08 > I don't know your logic truely but I test your program (compiled under > DevPascal (FreePascal), Windows98SE) and found your program get > Runtime Error and Wrong Answer many time when the value of > measure is high. It didn't crash but the error message was redirected to > the output instead , I don't know why. > > I randomly generate the test data and this is a case your program make > wrong output, but no Runtime Error > Input: > 6 > 29261 > 440 > 1757 > 22684 > 2247 > 11022 > 25134 > 22643 > 6002 > 3108 > 16056 > 12612 > 29390 > 25192 > 6271 > 26467 > 7802 > 23059 > 1921 > -1 > > My AC program output: > 29261 > 25134 > 25134 > 25134 > 25134 > 25134 > 25134 > 29390 > 29390 > 29390 > 29390 > 29390 > 29390 > 26467 > > Your output: > 29261 > 27029 > 27029 > 27029 > 27029 > 27029 > 27029 > 29390 > 29390 > 29390 > 29390 > 29390 > 29390 > 27029 > > If you edit your program and pass this test data but still get WA, you can > ask me for me test. My e-mail address is piyawut@se-ed.net. acmkx Re: I mean "more test" ,not "me test" // Problem 1126. Magnetic Storms 22 May 2005 14:57 MY Program's answer is the same as yours But I still get WA Here is my source: var a:array[1..14000]of longint; remax:array[1..140]of longint; temp,m,i,count,block,max:longint; procedure findmax; var i:longint; begin max:=0; for i:=1 to 140 do if(remax[i]>max)then max:=remax[i]; end; begin readln(m); fillchar(remax,sizeof(remax),0); max:=0; for I:=1 to m-1 do begin readln(a[i]); if a[i]>max then max:=a[i]; block:=i div 100; if a[i]>remax[block+1] then remax[block+1]:=a[i]; end; readln(a[m]); count:=m; while(a[count]<>-1)do begin if a[count]>max then max:=a[count]; writeln(max); block:=count div 100; if(a[count]>remax[block+1])then remax[block+1]:=a[count]; count:=count+1; if count=m+1 then count:=1; temp:=a[count]; a[count]:=0; block:=count div 100; if(temp=remax[block+1])then begin remax[block+1]:=0; for i:=block*100+1 to (block+1)*100 do if a[i]>remax[block+1]then remax[block+1]:=a[i]; end; if(temp=max)then findmax; readln(a[count]); end; end. Avanesov Please, give me a hint. My program gets Time Limit. [3] // Problem 1126. Magnetic Storms 23 Mar 2002 15:48 program p1126; var a : array[1..14000] of integer; i, m : integer; x : integer; max: integer; function findmax : integer; var k : integer; res : integer; begin res:=0; for k:=1 to m do if res<a[k] then res:=a[k]; findmax:=res; end; begin readln(m); read(x); max:=0; i:=1; while (x<>-1) and (i<=m) do begin if max< x then max:=x; a[i]:=x; inc(i); read(x); end; Writeln(max); i:=1; while x<>-1 do begin if a[i]= max then begin a[i]:=x; max:=findmax; end else begin a[i]:=x; if a[i]>max then max:=a[i]; end; Writeln(max); i:=i mod m +1 ; read(x); end; end. MadPsyentist/Sam use suitable data structure (-) [2] // Problem 1126. Magnetic Storms 25 Mar 2002 10:20 Junjie Liang Re: use suitable data structure (-) [1] // Problem 1126. Magnetic Storms 25 Mar 2002 16:45 The first time I read this problem, I thought of using a heap. However, I could not implement it properly. How do you know which number to delete off the heap each time? I only know how to delete the max/min number (depending on min/max heap). Any hints/tips/help/aids will be appreciated. :) MadPsyentist/Sam Re: use suitable data structure (-) // Problem 1126. Magnetic Storms 26 Mar 2002 14:42 look at the sample input 3 10 11 10 0 , delete 10 becase it's not in the period to consider anymore 0 , delete 11 0 , delete 10 1 , delete 0 so on... that is ,if you use heap (like me) , your heap must be able to delete not only the optimal data in the constrain of this problem (i don't know if it's bigger) , you can do the deletion in O(lg N) if still have no idea, feel free to mail to piyawut@se-ed.net Alex[LSD] Why WA? // Problem 1126. Magnetic Storms 22 Mar 2002 22:49 I know I'd probably get Time Limit. But can anyone explain why I m getting WA in this source... Please email : swin@mail2000.ru =-=-=-=-=-=-=-=-=-=-==-=-=-=-=-= Program acm_1126; const maxx=25000; Var A,B :array [1..maxx] of longint; M,N :Integer; i,j,k :Longint; Begin Readln(M); i:=0; k:=0; While i<>-1 do Begin Read(i); If i<>-1 Then Begin Inc(k); A[k]:=i; End; End; N:=k; For i:=1 to N do B[i]:=A[i]; For i:=1 to N do Begin k:=i+1; While (A[i]>A[k])and(k-i<M)and(k<=n) do Begin If A[i]>B[k] then B[k]:=A[i]; Inc(k); End; End; For i:=M to N do Writeln(B[i]); End. raxtinhac Why compilation error? Please help me ! [1] // Problem 1126. Magnetic Storms 14 Mar 2002 18:02 Here is my program : const max = 15000; var a,pos,cs :array[0..max] of word; n,m :word; x :longint; procedure doi(u,v :word); var tam :word; begin tam := a[u]; a[u] := a[v]; a[v] := tam; pos[ cs[u] ] := v; pos[ cs[v] ] := u; tam := cs[u]; cs[u] := cs[v]; cs[v] := tam; end; procedure upheap(k :word); var v :word; begin v := a[k]; a[0] := maxint; while a[k div 2] <= v do begin doi( k, k div 2); k := k div 2; end; end; procedure downheap( k :word); var j :integer; begin while k <= m div 2 do begin j := 2*k; if j < m then if a[j] < a[j+1] then inc(j); if a[k] >= a[j] then exit ; doi(k, j); k := j; end; end; procedure ghi_max; begin writeln( a[1] ); end; procedure xoa; var k :word; begin inc(n); if n = m+1 then n := 1; k := pos[n]; doi(k,m); dec(m); if k > m then exit; upheap(k); downheap(k); end; procedure them; begin inc(m); a[m] := x; cs[m] := n; pos[n] := m; upheap(m); end; begin readln( m); for n := 1 to m do begin read( a[n]); pos[n] := n; cs[n] := n; upheap(n); end; repeat ghi_max; xoa; read( x); if x = -1 then exit; them; until false; end. Bedny Yuri (bedny@rain.ifmo.ru) Re: Why compilation error? Please help me ! // Problem 1126. Magnetic Storms 20 Mar 2002 00:10 > Here is my program : > > const max = 15000; > > var a,pos,cs :array[0..max] of word; > > n,m :word; > x :longint; > > > procedure doi(u,v :word); > var tam :word; > begin > tam := a[u]; a[u] := a[v]; a[v] := tam; > pos[ cs[u] ] := v; pos[ cs[v] ] := u; > tam := cs[u]; cs[u] := cs[v]; cs[v] := tam; > end; > > > procedure upheap(k :word); > var v :word; > begin > v := a[k]; a[0] := maxint; > while a[k div 2] <= v do > begin > doi( k, k div 2); > k := k div 2; > end; > end; > > > procedure downheap( k :word); > var j :integer; > begin > while k <= m div 2 do > begin > j := 2*k; > if j < m then if a[j] < a[j+1] then inc(j); > if a[k] >= a[j] then exit ; > doi(k, j); > k := j; > end; > end; > > > procedure ghi_max; > begin > writeln( a[1] ); > end; > > > procedure xoa; > var k :word; > begin > inc(n); if n = m+1 then n := 1; > k := pos[n]; > > doi(k,m); dec(m); > if k > m then exit; > > upheap(k); > downheap(k); > end; > > > procedure them; > begin > inc(m); > a[m] := x; > cs[m] := n; > pos[n] := m; > upheap(m); > end; > > > begin > readln( m); > > for n := 1 to m do > begin read( a[n]); > pos[n] := n; cs[n] := n; > upheap(n); > end; > > repeat > ghi_max; > xoa; > > read( x); > if x = -1 then exit; > them; > until false; > end. > Hello! First of all, I sorry for my bad English. And now: programs on Timus are compiled in Delphi. type Integer range in Delphi is –2147483648..2147483647, type Word range in Delphi is 0..65535, hence arices error='constant expression violates subrange bounds', when you write 'a[0] := maxint' in procedure 'upheap'. If you write a[0]:=65535 I think that all will be ok! :) Bedny Yuri (bedny@rain.ifmo.ru) Please, help me to solve this problem! [2] // Problem 1126. Magnetic Storms 16 Feb 2002 22:30 First of all, I sorry for my bad English. Please help me to solve this problem. I wrote solution, but my program works very slow(>0.5). I think that idea of my solution is bad. Please help me! Miguel Angel You may use(+) [1] // Problem 1126. Magnetic Storms 17 Feb 2002 02:49 Well my solution isn't the fastest but is quick. Maybe is something complicated, but as you may see the data are ordered like a queue and you want to determine of all the data in the queue which one is the greatest, print it, and then throw the first, add the later and do the operation again. Hint: There's a Data Structure which does exactly this :). Doubts?: miguelangelhdz@hotmail.com Junjie Liang Re: You may use(+) // Problem 1126. Magnetic Storms 21 Mar 2002 16:52 Are you referring to a heap? Because that's was the first things that came to my mind (and nothing else so far)... If you are referring to a heap, could you explain how you decide which one to "throw away"? I can't seem to fit the idea of a queue and heap together...
|