ACAC 题库 ac.isam.top
GitHub
第 007 场 AtCoder Regular Contest
B
迷路的 CD 盒
迷子のCDケース
AtCoder
⌀ 529
原题
← AC →

迷路的 CD 盒AI (CI翻译)

1

1AI (CI翻译)

3

3AI (CI翻译)

image 図 $1$:黄緑色のCD、オレンジ色のCDの順で聴いた場合のCDの動き

image 图 $1$：按黄绿色 CD、橙色 CD 的顺序播放时 CD 的移动AI (CI翻译)

N M
disk_{0}
disk_{1}
:
:
disk_{M-1}

N M
disk_{0}
disk_{1}
:
:
disk_{M-1}
AI (CI翻译)

  • 入力は $M+1$ 行ある。
  • $1$ 行目には、高橋君が所持するCDケースの個数を表す整数 $N(1≦N≦100)$と、今日聴いたCDの枚数 $M(0≦M≦100)$ が空白区切りで与えられる。
  • CDケースを $1$ つ無くしているので、高橋君は計 $N+1$ 枚のCDを所持している。
    • CDと対応するCDケースにはそれぞれ $0$ から $N$ までの数が番号付けられている。
    • 現在CDプレイヤーに入ってるCDとそれに対応する見当たらないCDケースは $0$ 番である。
  • $2$ 行目からの $M$ 行には今日聴いたCDの番号のリストが与えられる。
  • $i+2$ 行目の整数 $disk_{i}(0≦i≦M-1,$ $0≦disk_i≦N)$ は $i+1$ 番目に $disk_i$ 番のCDを聴いたことを表している。
  • 输入共有 $M+1$ 行。
  • 第 $1$ 行包含两个以空格分隔的整数 $N(1≦N≦100)$ 和 $M(0≦M≦100)$，分别表示高桥君拥有的 CD 盒数量，以及今天播放的 CD 数量。
  • 由于丢失了 1 个 CD 盒，高桥君总共拥有 $N+1$ 张 CD。
    • CD 以及与其对应的 CD 盒分别被编号为 $0$ 到 $N$。
    • 当前放入 CD 播放器中的 CD，以及与它对应的丢失的 CD 盒，编号均为 $0$。
  • 第 $2$ 行开始的 $M$ 行给出今天播放的 CD 编号列表。
  • 第 $i+2$ 行的整数 $disk_{i}(0≦i≦M-1,$ $0≦disk_i≦N)$ 表示第 $i+1$ 张播放的 CD 是编号为 $disk_i$ 的 CD。
AI (CI翻译)

1

1AI (CI翻译)

N

NAI (CI翻译)

1

1AI (CI翻译)

1

1AI (CI翻译)

5 6
2
3
5
0
1
3

5 6
2
3
5
0
1
3
AI (CI翻译)

0
5
2
4
1

0
5
2
4
1
AI (CI翻译)

  • まず $2$番のCDを聴くので、$0$ 番のCDは $2$ 番のCDケースに入れます。
  • 次に $3$番のCDを聴くので、$2$ 番のCDは $3$ 番のCDケースに入れます。
  • このように各CDを順に聴いては片付けるを繰り返すと、下図のようにCDの位置が入れ替わります。
  • 首先播放编号为 $2$ 的 CD，因此将编号为 $0$ 的 CD 放入编号为 $2$ 的 CD 盒中。
  • 接着播放编号为 $3$ 的 CD，因此将编号为 $2$ 的 CD 放入编号为 $3$ 的 CD 盒中。
  • 如此反复按顺序播放并收好每张 CD 后，CD 的位置就会如下面的图所示发生交换。
AI (CI翻译)

image

imageAI (CI翻译)

3 5
0
1
1
1
2

3 5
0
1
1
1
2
AI (CI翻译)

0
1
3

0
1
3
AI (CI翻译)

  • 同じCDを連続して聴いた場合もあります。
  • この場合は $1$ 枚目としてCDプレイヤーに入っている $0$ 番のCDを聴くので、CDケースに入っているCDは入れ替わりません。
  • $2$ 枚目としては $1$ 番のCDを聴くので、$1$ 番のCDケースに $0$ 番のCDが入ります。
  • $3$ 枚目と $4$ 枚目は $2$ 枚目でCDケースに入れた $1$ 番のCDを聴くので入れ替わりは起きません。
  • 最後に $2$ 番のCDを聴くので $2$ 番のCDケースに $3$ 番のCDが入ります。
  • 也可能连续播放同一张 CD。
  • 在这种情况下，第 1 张播放的是放在 CD 播放器中的编号为 $0$ 的 CD，因此放在 CD 盒中的 CD 不会交换。
  • 第 2 张播放的是编号为 $1$ 的 CD，因此编号为 $1$ 的 CD 盒中会放入编号为 $0$ 的 CD。
  • 第 3 张和第 4 张播放的都是第 2 张时放入 CD 盒中的编号为 $1$ 的 CD，因此不会发生交换。
  • 最后播放编号为 $2$ 的 CD，因此编号为 $2$ 的 CD 盒中会放入编号为 $3$ 的 CD。
AI (CI翻译)

5 0

5 0
AI (CI翻译)

1
2
3
4
5

1
2
3
4
5
AI (CI翻译)

  • 何もCDを聴かなかった場合は入れ替わりは起きません。
  • 如果没有播放任何 CD，则不会发生交换。
AI (CI翻译)

10 7
2
8
5
3
3
8
1

10 7
2
8
5
3
3
8
1
AI (CI翻译)

8
0
5
4
3
6
7
2
9
10

8
0
5
4
3
6
7
2
9
10
AI (CI翻译)

5 7
3
4
3
1
2
2
0

5 7
3
4
3
1
2
2
0
AI (CI翻译)

3
1
2
4
5

3
1
2
4
5
AI (CI翻译)

题目信息
题号
arc007_2
所属比赛
第 007 场 AtCoder Regular Contest
时间限制
2 s
内存限制
64 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。