I got WA at #1 and I use line tree. Now I've accepted! Edited by author 07.03.2013 19:40 Try to change compiler to Microsoft Studio. Worked for me [code deleted] Edited by moderator 02.09.2020 19:58 Do not post Accepted solution to the forum! it may help: line = Console.ReadLine(); while (line.Length < N) { line += Console.ReadLine(); } I got wrong 13 times because I ignored this sentence: Those characters are situated on the consecutive lines grouped by 80 characters per line without any spaces. Edited by author 03.05.2015 13:31 Input should be similar to this : for i:=1 to n do read(ch); If eoln then readln; What's wrong with my program??? #include <iostream> using namespace std; pair<int,int> FindAnswer(const char *arr, const int &N, const int K); int main(void) { // Inputs data int N, K; (cin >> N >> K).get(); // Creates an extra array char *arr=new char[N]; int length=0; int pos=-1; pair<int,int> res(-1,-1); char ch[1]; while(pos!=N-1) { while(pos!=N-1 && cin.read(ch, 1) && cin) { // Reads the next character if(ch[0]=='\n') continue; ++pos; // Inserts the digit to the array if(ch[0]!='*') arr[length++]=ch[0]; // Resets the array and finds the result else { if(length>=K) { pair<int,int> tmp=FindAnswer((const char *)arr, length, K); if(tmp.first<res.first) { res.first=tmp.first; res.second=pos-length+tmp.second; } } length=0; } } } // Outputs the result if(res.second==-1) cout << 0 << endl; else cout << res.second+1 << endl; return 0; } // Function determines the result pair<int,int> FindAnswer(const char *arr, const int &N, const int K) { int best=0; int res=0; int i; for(i=0; i<K; ++i) best+=arr[i]-'0'; int prev=best; for(i; i<N; ++i) { int tmp=prev-arr[i-K]+arr[i]; if(tmp<best) { best=tmp; res=i-K+1; } prev=tmp; } return make_pair(best, res); } Edited by author 14.03.2007 16:08 If you have WA#3 try to use this simple test: 1 1 9 Right answer is "1", of course. i got WA because of it for 3 times! You guys pay attention to it! yeah... I had some problems with it... =( I think I have the same problem, so what is the input format? Any examples ? I don't really know. I use JAVA, and when I changed Scanner and StreamTokenizer to just BufferedReader and in.readLine()s I got AC. Give me some tests. This My Code: int min =Integer.MAX_VALUE; while((x = in.read())!=-1) { if(x!=10 && x!=13){ um++; if((char)x!='*') { k = Integer.parseInt((char)x+""); a[++count] = k; } if((char)x=='*'){ for (int i = 1; i <= count-m+1 ; i++) { sum = 0; for (int j = i; j <= i+m-1 ; j++) { sum = sum + a[j]; } if(sum <= min) { min = sum; ind = um - count + i; if(um<n) ind--; }} count = 0; Arrays.fill(a,0); } } } for (int i = 1; i <= count-m+1 ; i++) { sum = 0; for (int j = i; j <= i+m-1 ; j++) { sum = sum + a[j]; } if(sum <= min) { min = sum; ind = um - count + i ; } } if(ind == 0)System.out.println("0"); else System.out.println(ind); } } My Answers: /* 40 5 12368145698754*11111*21*111*00001000000 ans = 35 40 5 12368145698754*11111*21*111*0000100*0000 ans = 31 40 5 00001000*0000*12368145698754*11111*21*111 ans = 4 */ I give many tests to your programm, all answer is true. But I don't now why WA. These answers are wrong. In the first test Ans=34 In the second test Ans=29 In the third test Ans=1 There is sentence in the problem statement: "If there are more than one such value for L, then write the smallest one." And at last: 1. N and K are situated on the single (first) line 2. In some of your tests real number of symbols doesn't correspond the number N: somewhere it is less, somewhere it is more. I got Crash#11 But when I wrote "if (k > n) k = n;" I got WA#7 And when "int[] a = new int[110000];" (not 100000) I got AC :) WHY?????????? If you have WA6 try this test: 40 5 12368145698754*11111*21*111*000010000000 ans = 34 This test helped me to pass Test 6, but then I got WA 10. Special thanks to <A HREF=" http://acm.timus.ru/author.aspx?id=69418">Bunyodbek Bobodjanov (TATU UF)</A>. This test was suggested by him but it was contained some mistake. Edited by author 08.01.2010 17:58 Edited by author 17.05.2009 16:56 Can someone provide me atleast 5 testcases rigourous ones so that i can validate my code var c:char; a:array[1..100000] of integer; cyc1,cyc2,n,k,m,s,sm,i:longint; begin readln(n,m); cyc1:=0; while (not eof(input))and(cyc1<=n) do begin while (not eoln(input))and(cyc1<=n) do begin read(c); inc(cyc1); if c='*' then a[cyc1]:=-1 else a[cyc1]:=ord(c)-ord('0'); end; readln; end; k:=0; s:=0; i:=0; sm:=100000; for cyc1:= 1 to n do begin if a[cyc1]=-1 then begin s:=0;k:=0; end else begin if k<m then begin inc(k); s:=s+a[cyc1]; if k=m then begin if sm>s then begin sm:=s; i:=cyc1-m+1;end; end; end else begin s:=s+a[cyc1]-a[cyc1-m]; if sm>s then begin sm:=s;i:=cyc1-m+1;end; end; end; end; writeln(i); end. try using an array only for the last K elements 0.031 242 KB Program Buffer_Manager; Var A:array[0..10000] of integer; bj:boolean; N,K,c,s,i,mi,t,b:Longint; min:longint; ch:char; Begin Readln(n,k); min:=1000000; while (b<n)and(not(eof(input))) do begin while (b<n)and (not(eoln(input))) do begin Read(ch);inc(b);inc(i); if i>k then i:=1; t:=a[i]; if ch='*' then A[i]:=-1 Else A[i]:=ord(ch)-48; if a[i]=-1 then begin c:=0;s:=0; End Else if c=k then begin S:=s-t+a[i]; if s<min then begin min:=s;mi:=b-k+1; End; End Else begin inc(c);s:=s+a[i]; if c=k then if s<min then begin min:=s;mi:=b-k+1;End; End; End; Readln; End; writeln(mi); End. Just one feeling, Always found that most guys are very smart, but the code they write/post are quite terrible(I mean hard to read). I would recommend writing readable code with clear structure and comments as that's the rule in real world( long code with clean structure and readability is much better than urgly code with small size). Edited by author 05.08.2008 13:41 Edited by author 05.08.2008 13:41 [code deleted] Edited by moderator 06.03.2006 18:47 just try to solve it using only last k elements. It's much easier! I need help with this problem. I wrote a few versions of code but every time I get WA! Give me a tip how to do this. You can use an algorithm with complexity O(n) : D[i] := A[1] -> A[i] ! => Sum (i,i+K-1) = D[i+k-1] - D[i-1] ; Is it enough ? #include <stdio.h> long n, z, s, poz, min = 10000000; int k; char sir[100009]; //FILE *f; int main () { long i, j; //f = fopen("buffer.in","r"); scanf("%ld %d",&n,&k); if((long)k > n) printf("0\n"); else { scanf("%c",&sir[0]); for(i=1; i<=n; i++) { scanf("%c",&sir[i]); if(sir[i] == '\n') i--; } for(i=1; i<=k; i++) { z--; if(sir[i] == '*') { s += 10; z = k; } else s += sir[i] - '0'; } if(z <= 0 && s < min) { min = s; poz = i-k; } for(; i<=n; i++) { if(sir[i-k] == '*') s -= 10; else s -= sir[i-k] - '0'; z--; if(sir[i] == '*') { s += 10; z = k; } else s += sir[i] - '0'; if(z <= 0 && s < min) { min = s; poz = i-k+1; } } } printf("%ld\n",poz); return 0; } const max = 100000; var can , find : boolean; ch : char; o , bh : array [0..max] of longint; min , n , k , i , j , rec : longint; begin fillchar(o,sizeof(o),0); fillchar(bh,sizeof(bh),0); i := 0; j := 1; can := true; readln(n,k); if k > n then begin writeln(0); halt; end; while not eof(input) do begin while not eoln(input) do begin read(ch); if ch in ['0'..'9','*'] then begin inc(i); if can and (ch = '*' ) then begin can := false; inc(j); end; if ch in ['0'..'9'] then begin o[i] := o[i-1] + ord(ch) - ord('0'); can := true; bh[i] := j; end else o[i] := 0; end; end; readln; end; min := maxlongint; find := false; for i := 1 to n do if (bh[i] <> 0) and (bh[i] = bh[i+k-1]) and ((o[i+k-1] - o[i-1]) < min) then begin min := o[i+k-1] - o[i-1]; find := true; rec := i; end; if find then writeln(rec) else writeln(0); end. |
|