問題一覧 > 通常問題

No.1651 Removing Cards

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 73
作問者 : chocorusk / テスター : hos.lyric
お気に入りにしたユーザー ProblemId : 2877 / 自分の提出
問題文最終更新日: 2021-08-20 18:44:56
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 310 (順位表) の他の問題:

Problem Statement

Cards with $1, 2, \ldots , N$ written on them, $1$ card for each number, are lined up in a row in this order from left to right. Rusk repeats the following operation until $1$ card remains.

  1. Among the remaining cards, mark every card that is the $K x + 1$-th from the left ($x$ is a non-negative integer).
  2. Remove all marked cards.
What is the number written on the last remaining card?

Find the answer for each of the cases where the value of $N$ is $N_1, N_2, \ldots, N_Q$.

Input

$K\ Q$
$N_1$
$N_2$
$\vdots$
$N_Q$

  • $2\leq K\leq 10^4$
  • $1\leq Q\leq 10^5$
  • $1\leq N_i\leq 10^{18}$
  • All input values are integers.

Output

Print $Q$ lines. On the $i$-th line ($1\leq i\leq Q$), print the number written on the last remaining card after repeating the operation in the case $N=N_i$.

Sample

Sample 1
Input
3 1
7
Output
5

  • Initially, the numbers written on the cards are, from left to right, $1, 2, 3, 4, 5, 6, 7$.
  • In the $1$-st operation, the $1, 4, 7$-th cards from the left are removed. The numbers written on the remaining cards are, from left to right, $2, 3, 5, 6$.
  • In the $2$-nd operation, the $1, 4$-th cards from the left are removed. The numbers written on the remaining cards are, from left to right, $3, 5$.
  • In the $3$-rd operation, the $1$-st card from the left is removed. The number written on the remaining card is $5$.

Sample 2
Input
5 3
3
34
334
Output
3
30
290

Sample 3
Input
3141 5
9265358979
3238462643
3832795028
8419716939
9375105820
Output
9263828525
3238177188
3832261774
8417162552
9373616394

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