program de; var a,b:array[-1400..1400] of integer; a1,b1:array[1..2800] of integer; i,j,n,max_a,max_b:integer; ch:char; procedure diog; begin if ch='s' then begin b[i-j]:=0; inc(a[i-j]); if a[i-j]>max_a then max_a:=a[i-j]; end else begin a[i-j]:=0; inc(b[i-j]); if b[i-j]>max_b then max_b:=b[i-j]; end; end; procedure diogobrat; begin if ch='s' then begin b1[i+j]:=0; inc(a1[i+j]); if a1[i+j]>max_a then max_a:=a1[i+j]; end else begin a1[i+j]:=0; inc(b1[i+j]); if b1[i+j]>max_b then max_b:=b1[i+j]; end; end; procedure vivod; begin if max_a=max_b then begin writeln('?'); writeln(max_a); end else if max_a<max_b then begin writeln('S'); writeln(max_b); end else begin writeln('s'); writeln(max_a); end; end; begin { assign(input,'c:\test.txt'); reset(input); } readln(n); for i:=1 to n do begin for j:=1 to n do begin read(ch); diog; diogobrat; end; readln; end; vivod; end. There is test where your program wrongs: 5 sSSSS SSsss ssSSS sSSss sSSSS Your program outputs ? 3 but real answer is obvious S 4 Good luck! I thought what to consider it is necessary only on a diagonal. Thanks, now I have AC. Exactly! Do NOT forget to consider vertical and horizontal arrays. Thank you for this test and thanks to my friend Agabek. I got AC now. Maybe you are using expressions like (n-j) for j=0...n-i-1 and 0-indexing when checking diagonals. So, (n-j) results in WA #8. Correct expression is (n-1-j) Really dont know what the mistake??? int main() { char src[1405][1405]; int n; cin >> n; for(int i = 0; i < n; i++) { for(int z = 0; z < n; z++) { cin >> src[i][z]; } } int s = 0, S = 0; for(int i = 0; i < n; i++) { int tmps = 0, tmpS = 0; for(int z = 0; z < n; z++) { if(src[i][z] == 's') { tmps++; s = max(s, tmps); tmpS = 0; } else { tmpS++; S = max(S, tmpS); tmps = 0; } } } for(int i = 0; i < n; i++) { int tmps = 0, tmpS = 0; for(int z = 0; z < n; z++) { if(src[z][i] == 's') { tmps++; s = max(s, tmps); tmpS = 0; } else { tmpS++; S = max(S, tmpS); tmps = 0; } } } for(int i = 0; i < n; i++) { int tmps = 0, tmpS = 0; for(int z = 0; z <= i; z++) { if(src[i - z][z] == 's') { tmps++; s = max(s, tmps); tmpS = 0; } else { tmpS++; S = max(S, tmpS); tmps = 0; } } } for(int i = 0; i < n; i++) { int tmps = 0, tmpS = 0; for(int z = i; z < n; z++) { if(src[z][z - i] == 's') { tmps++; s = max(s, tmps); tmpS = 0; } else { tmpS++; S = max(S, tmpS); tmps = 0; } } } if(s > S) { cout << "s\n" << s; } else if(s < S) { cout << "S\n" << S; } else { cout << "?\n" << s; } } I don't see any dynamic programming in this problem... can someone please explain the problem, specially the part "(parallel to the north-south or east-west directions or at the angle 45° to them)" and the first sample input-output. At last I have understood the problem (thanks to Fahim and Sadia). You have to consider either north-south, or east-west or diagonal straight lines; consider which yields highest amount of crop of a kind instead of all of them together. More clearly, for first test, SsS sSs SsS my confusion was _s_ s_s _s_ we can get a ring of 4 's' ... so the ans should be s 4 but later my friends explained consider only one straight line,which ever produces most as S__ _S_ __S or _s_ s__ ___ or ___ __s _s_ Hope my problem helps other. 4 SSsS sssS SSsS Ssss output s 4 Try also: 4 ssSs SSSs ssSs sSsS output ? 3 I used only ~2MB in C#, but want to know how to improve it. Thx. The problem can be solved in O(N) memory. Just read line-by-line and calculate something =) I did a little bit different: I saved NxN matrix using BitArray and after that used 2xN array to culc answers, but I see that its even possible to solve this problem without saving all matrix at all, just 2xN array. [code deleted] sorry.stupid mistake.AC Edited by author 20.07.2010 18:09 Make a macro for "for" #define F(i,n) for(int i = 0; i < n; ++i) macros for start/process/stop of each line #define START int c0 = 0, ... #define P(x) if(x == 's'){ ... #define STOP mc0 = max(mc0, c0); ... vertical/horizontal lines are simple: F(i,n){ START; F(j,n) P(s[i][j]); STOP; } F(i,n){ START; F(j,n) P(s[j][i]); STOP; } The simplest diagonal is F(i,n) { START; F(j,i+1) P(s[ i-j ][ j ]); STOP; } with a macro for symmetry #define I(ind) n-1-(ind) the other lines simply invert some of coordinates: F(i,n) { START; F(j,i+1) P(s[I(i-j)][ j ]); STOP; } F(i,n-1){ START; F(j,i+1) P(s[ i-j ][I(j)]); STOP; } F(i,n-1){ START; F(j,i+1) P(s[I(i-j)][I(j)]); STOP; } If you use Java pay attention to size of arrays, that you used. I used 2 arrays for saving current line and prev line of input(every has o(n) elements), and 2 arrays for saving result of calculating in prev Line, and for saving result of calculation in current line (every has o(n) elements). Edited by author 21.02.2010 15:56 This problem is not so memory consuming. Java solution using variable char field[][] = new char[1 + n + 1][1 + n + 1]; gets AC. So it is possible to store whole input in memory, but it is impossible to store significant amount of data for each cell. For example 4 arrays NxN of 16-bit ints need extra 16 Mb of memory while total ML is 16 Mb. program Ural1287; var map:array[0..1401,0..1401]of boolean; ans,i,j,n,k:longint; c:char; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure dm(i,j:longint); begin if ans=k then if map[i,j]xor(c='S') then c:='?'; if ans<k then begin ans:=k; if map[i,j] then c:='S' else c:='s'; end; k:=1; end; begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(c); map[i,j]:=c='S'; end; readln; end; c:=' '; for i:=1 to n do begin k:=1; for j:=2 to n do begin if map[i,j]=map[i,j-1] then inc(k) else dm(i,j-1); end; dm(i,n); end; for i:=1 to n do begin k:=1; for j:=2 to n do begin if map[j,i]=map[j-1,i] then inc(k) else dm(j-1,i); end; dm(n,i); end; for i:=1 to n do begin k:=1; for j:=i+1 to n do begin if map[j-i+1,j]=map[j-i,j-1] then inc(k) else dm(j-i,j-1); end; dm(j-i+1,n); k:=1; for j:=i+1 to n do begin if map[j,j-i+1]=map[j-i,j-1] then inc(k) else dm(j-1,j-i); end; dm(n,j-i+1); end; for i:=1 to n do begin k:=1; for j:=2 to i do begin if map[i-j+1,j]=map[i-j+2,j-1] then inc(k) else dm(i-j+2,j-1); end; dm(i,1); k:=1; for j:=2 to i do begin if map[j,i-j+1]=map[j-1,i-j+2] then inc(k) else dm(j-1,i-j+2); end; dm(1,i); end; writeln(c); writeln(ans); end. Wa#11 Who can help me??? I keep getting WA on testcase 4, but I'm sure my program is correct. Can someone give me this test or send me AC program or just tell me what is the trick in this testcase? I sent you a mail... Send me too,pleeeeeeeeeeeeeeeeeeeeese The only problem is that it was 3 years ago :))) sSSSS sSsSs SsSss ssSsS sssSs output S 4 I'm curious how some people coped with so less memory, probably they've read char by char and not knowing the whole map but I don't know how to do it :( I got TL and ML consequently :( I think that following two input routines are the same: #1, gets AC ------------------------- ReadLn(N); For I := 1 To N Do begin For J := 1 To N Do begin Read(Ch); <work> end; ReadLn; end; ---------------------- #2, gets WA on test 4 ---------------------- Read(N); Read(Ch); For I := 1 To N Do For J := 1 To N Do begin While Not((Ch = 's')Or(Ch = 'S')) Do Read(Ch); <work> Read(Ch); end; ----------------------------- Where am I mistake? in windows - end of string is a 2 symbols: ord (ch)=13 and ord (ch)=10 Please send me our sourse code. J get WA on test#4 :~)) I got accepted with simple algorithm. There is no incorrect tests. to Gheorghe Stefan:I didn't say that it's impossible to get AC. I got it too. I ask you are input routines the same. I think they are. Profound parts of this two programs are the same too, so why don't they give the same result? to JUDGES: can you give any comments? Tests were corrected. Problem was rejudged. Thank you. |
|