問題一覧 > 通常問題

No.3266 Iwai Seijin Can't Help But Look

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 65
作問者 : Rice_tawara459 / テスター : ゆにたりー卿 DeltaStruct kazuppa 👑 loop0919 Andrew8128 bolero のらら elphe よには yimiya（いみや）
お気に入りにしたユーザー ProblemId : 12570 / 自分の提出
問題文最終更新日: 2025-09-06 12:01:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Div.2 (順位表) の他の問題:

Problem Statement

Iwai Seijin is always concerned about his rank during a contest. Therefore, even in the middle of solving a problem, Iwai Seijin cannot help but look at the standings.

This is important, so let me say it again. Iwai Seijin cannot help but look (at the standings).

Iwai Seijin is about to participate in a certain programming contest. In this contest, each participant has an integer value called the predicted new rating, and Iwai Seijin's predicted new rating at the start is $1200$. Note that in this contest, the predicted new rating can be any integer; in particular, it can also be negative.

You are given a string $S'$ of length $N$ consisting of 0 and 1. Let $S$ be the string obtained by repeating $S'$ $10^{100}$ times.

From now on, $10^{100}$ events will happen to Iwai Seijin in order. The $i$-th event is determined by the $i$-th character of $S$ as follows.

  • If the $i$-th character of $S$ is 0

    • Iwai Seijin's predicted new rating decreases by $1$.

  • If the $i$-th character of $S$ is 1

    • Iwai Seijin, who cannot help but look at the standings, checks his current predicted new rating on the standings.

    • If his current predicted new rating is $1199$ or less, he solves a problem desperately and gets AC. As a result, Iwai Seijin's predicted new rating increases by $1$.
    • If his current predicted new rating is $1200$ or more, he just shouts "What a waste of server costs!" and does nothing. Iwai Seijin's predicted new rating does not change.

At which event does Iwai Seijin, who cannot help but look at the standings, get his $A$-th AC?

Here, the contest has sufficiently many problems, and Iwai Seijin will never run out of problems to solve. Also, from the constraints, it is guaranteed that the answer is an integer not greater than $2 \times 10^{18}$.

Constraints

  • $2 \le N \le 2 \times 10^5$
  • $1 \le A \le 10^{12}$
  • $S'$ is a string consisting of 0 and 1
  • $|S'|=N$
  • $S'$ contains at least $1$ each of 0 and 1
  • $N,A$ are integers

Input

The input is given from standard input in the following format.

$N\ A$
$S'$

Output

Output the answer.

Sample

Sample 1
Input
5 3
10100
Output
8

The following events happen to Iwai Seijin.

  • Character 1 of $S$ is 1. Iwai Seijin's current predicted new rating is $1200$, so the predicted new rating does not change.
  • Character 2 of $S$ is 0. Iwai Seijin's current predicted new rating is $1200$, so the predicted new rating decreases by $1$ to $1199$.
  • Character 3 of $S$ is 1. Iwai Seijin's current predicted new rating is $1199$, so he gets AC on a problem, and the predicted new rating increases by $1$ to $1200$.
  • Character 4 of $S$ is 0. Iwai Seijin's current predicted new rating is $1200$, so the predicted new rating decreases by $1$ to $1199$.
  • Character 5 of $S$ is 0. Iwai Seijin's current predicted new rating is $1199$, so the predicted new rating decreases by $1$ to $1198$.
  • Character 6 of $S$ is 1. Iwai Seijin's current predicted new rating is $1198$, so he gets AC on a problem, and the predicted new rating increases by $1$ to $1199$.
  • Character 7 of $S$ is 0. Iwai Seijin's current predicted new rating is $1199$, so the predicted new rating decreases by $1$ to $1198$.
  • Character 8 of $S$ is 1. Iwai Seijin's current predicted new rating is $1198$, so he gets AC on a problem, and the predicted new rating increases by $1$ to $1199$.
He gets the $3$rd AC at the $8$th event, so output $8$.

Sample 2
Input
7 1
1000001
Output
7

Sample 3
Input
2 20
10
Output
41

Sample 4
Input
10 81181819
1011010011
Output
202954549

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。