問題一覧 > 通常問題

No.2037 NAND Pyramid

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 98
作問者 : milkcoffee / テスター : nok0 riano
お気に入りにしたユーザー ProblemId : 8225 / 自分の提出
問題文最終更新日: 2022-08-12 21:57:36
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
yukicoder contest 356 (順位表) の他の問題:

Problem Statement

$N$ blocks are arranged in a row, and each has the digit 0 or 1 written on it.
This information is given as a string $S$ of length $N$: the digit written on the $i$-th block from the left matches the $i$-th character of $S$.

Starting from this state, we stack blocks with the digit 0 or 1 written on them to form a pyramid with $N$ levels.
Blocks are placed $1$ at a time, from the bottom up, according to the following rules.

  • If both of the $2$ blocks directly below have 1 written on them, place a block with 0 written on it.
  • Otherwise, place a block with 1 written on it.
Below is an example of a pyramid with $5$ levels, where the blocks on level $1$ are 01011.

On the $K$-th level from the top, $K$ blocks are placed in a row. What digits are written on them?

Input

$N$ $K$
$S$

  • $2 \leq N \leq 4 \times 10^5$
  • $1 \leq K \leq N-1$
  • $N,K$ are integers.
  • $S$ is a string of length $N$ consisting of 0 and 1.

Output

Output a string of length $K$ consisting of 0 and 1, whose $i$-th character is the digit written on the $i$-th block from the left on the $K$-th level from the top.

Sample

Sample 1
Input
5 3
01011
Output
001

This is the same as the example in the problem statement. The blocks on the $3$-rd level from the top have 0, 0, 1 written on them from the left, so the correct output is 001.

Sample 2
Input
2 1
11
Output
0

Sample 3
Input
16 6
0110010100111011
Output
000001

Sample 4
Input
20 3
01001101011001011011
Output
101

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