以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 4 – Chinese
中華料理(Chinese)
K 理事長を含む情報オリンピック日本委員会のN 人全員で中華料理店にやってきた.
中華料理店のテーブルは円卓で,N 個の座席が等間隔に並んでいる.また,中央には料理が置かれる回転
台が乗っている.N 人の委員はN 個の座席に座り,K 理事長を1 として,そこから反時計回りに2, 3, · · · N
と委員に番号がつけられた.委員会はN 種類の料理を1 個ずつ注文し,それらの料理が回転台の上に置か
れた.料理は委員の目の前に置かれており,委員i の目の前に置かれた料理は料理i (1 ≦i ≦N) である.K
理事長以外の委員にはそれぞれ食べたい料理が1 つ決まっており,委員i (2 ≦i ≦N) が食べたい料理はAi
である.
回転台は(360/N) 度単位で時計回り・反時計回りのどちらの向きにも回転させることができる.
例えば,回転台を反時計回りに1 単位回転させると,K 理事長の目の前には料理N が,委員i (2 ≦i ≦N)
の目の前には料理i −1 が来る.
ある委員がある料理を食べるには,その料理がその委員の目の前に来るように回転台を回さなければな
らない.
情報オリンピック日本委員会ではK 理事長はとても尊敬されているため,最初にK 理事長が回転台を回
し,料理k (1 ≦k ≦N) が目の前に来るようにしてその料理を食べる.
K 理事長が料理を食べた後,K 理事長以外の委員たちはそれぞれ自分の食べたい料理が目の前に来るよ
うに回転台を回し,その料理を食べる.ただし,K 理事長以外の委員たちが回転台を回す順番はどのよう
な順番でも良い.
また,それぞれの料理は量が十分にあり,食べて無くなることは無いものとする.
K 理事長が何を食べても対応できるよう,全員が料理を食べられ,かつ回転台を回す量の合計が最小に
なるように,K 理事長以外の委員が回転台を回す順番と回し方を各k について前もって決めておきたい.
課題
各委員i (2 ≦i ≦N) が食べたい料理Ai が与えられたとき,K 理事長が食べる料理k (1 ≦k ≦N) のそれぞ
れについて,回転台を回す量の合計の最小値を(360/N) 度を1 単位として求めよ.
制限
2 ≦N ≦100 000 情報オリンピック日本委員会の人数
1 ≦Ai ≦N 委員i が食べたい料理
中華料理– 1 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 4 – Chinese
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれており,情報オリンピック日本委員会の人数を表す.
• 続くN −1 行には,各委員の食べたい料理の情報が与えられる.i (2 ≦i ≦N) 行目には整数Ai が書
かれている.これは委員i の食べたい料理がAi であることを表す.
出力
出力はN 行からなる.k 行目(1 ≦k ≦N) に,K 理事長が料理k を食べるときの,回転台を回す量の合計
の最小値を表す整数を出力せよ.ただし,回転台を回す量は,(360/N) 度を1 単位とする.
採点基準
採点用データのうち,配点の10%分についてはN ≦10 を満たす.
採点用データのうち,配点の40%分についてはN ≦1 000 を満たす.
中華料理– 2 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 4 – Chinese
入出力の例
入力例1 出力例1
5 4
3 4
5 5
3 6
2 4
この場合,円卓には5 人の委員が図のように座っている.
例えば,k = 3 の場合(K 理事長が料理3 を食べる場合) を考えると,回転台を回す量の合計が最小になる
ような回し方は以下の通りである.
• K 理事長(委員1) が回転台を時計回りに2 単位回し,料理3 を食べる.
• 委員3 が回転台を回さずに料理5 を食べる.
• 委員5 が回転台を回さずに料理2 を食べる.
• 委員2 が回転台を反時計回りに1 単位回し,料理3 を食べる.
• 委員4 が回転台を反時計回りに2 単位回し,料理3 を食べる.
この時,回転台を回す量の合計は2 + 1 + 2 = 5 単位となるので,出力の3 行目には5 を出力する.
中華料理– 3 / 3