Hide

Problem B
Spam Filter

/problems/spam/file/statement/en/img-0001.jpg
Photo by AJ Cann

Goo is working in a well-known Slovak antivirus company which unfortunately cannot be named. In addition to antivirus software, they are developing a spam filter. Recently, Goo has made a few improvements to the filter and he wants to demonstrate his progress to his boss. As you can imagine, demonstrating low-level ideas of your implementation is not a good way to impress your boss, so Goo instead decided to make a presentation with plenty of graphs showing filtering results. The company has a huge database of e-mails and each e-mail is marked as a spam or ham (i.e. not spam). These e-mails were all correctly marked by people – every time someone in the company receives an e-mail, he marks it as either spam or ham and adds it to the database.

The success of Goo’s program can be measured in a simple way. Goo ran his program on all e-mails in the database. For each message he noted if his program correctly decided whether the message was spam or ham. The messages were processed in order from the oldest to the newest one. To impress the boss, Goo wants to select e-mails from a period of time and calculate the success rate only for this period. Of course, a period containing only one e-mail won’t impress anyone, so Goo wants to choose a period which is long enough.

Task

You are given a sequence of test results and a number $k$. Your task is to find a continuous subsequence of length at least $k$ which has the highest possible success rate among all such subsequences. The success rate of a subsequence is defined as the number of successfully classified e-mails divided by the length of the subsequence.

Input description

On the first line there is an integer $k$ ($1\le k \le 100$) denoting the minimal subsequence length. The second line contains a string consisting of characters 0 and 1, denoting answers of the program for each e-mail in the database. Number 1 indicates that Goo’s program gave a correct answer and 0 that it failed. The length of the string will be at least $k$ and at most $100\, 000$ characters.

Output description

The first and only line of output should consist of two integers $f$ and $\ell $, separated by a single space. The integer $f$ is the 1-based index of the first element of subsequence with the best success rate and $\ell $ is its length. If there are multiple optimal solutions, you can output any one of them.

Sample Input 1 Sample Output 1
1
01
2 1
Sample Input 2 Sample Output 2
4
0110011
2 6

Please log in to submit a solution to this problem

Log in