ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1061. Buffer Manager

WA#3
Posted by Duzhy Igor 13 Mar 2007 12:15
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
Re: WA#3
Posted by Smilodon_am 28 Apr 2010 11:26
If you have WA#3 try to use this simple test:
1 1
9
Right answer is "1", of course.