Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 227 A 問題 Last Card

AtCoder ABC ABC227 A問題 100 pts

問題

提出解答

解法1 (シミュレーション)

解法2 (計算)

問題の概要

$N$ 人に $K$ 枚のカードを配る. ただし, 配り方は以下である.

人 $A, A+1, A+2, \dots, N-1,N,1,2,\dots$ の順に $1$ 枚ずつ配る.

$K$ 枚目のカードは誰に配られるか?

制約

$1 \leq N,K \leq 1000$
$1 \leq A \leq N$

解法1 (シミュレーション)

カードの枚数が高々 $1000$ 枚なので, 愚直にシミュレーションすることで, 最後に誰に配られるかがわかる (計算量 $O(N)$ ).

解法2 (計算)

順々に配られるので, $K$ 枚目のカードが配られる人の番号 $X$ は,

$A+K-1$ が $N$ の倍数ならば, $X=N$ .
$A+K-1$ が $N$ の倍数でないならば, $X=(A+K-1) \mod N$ .

である (計算量 $O(1)$ .