以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。






可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Bookshelf
本棚(Bookshelf)
20XX 年,IOI がJOI 君の住む国で開催されることになった.このニュースを聞いたJOI 君は友人に知ら
せるために部屋を飛び出そうとした.しかし,あまりにも急いでいたため部屋の本棚にぶつかってしまい,
本は本棚から全て落ちてしまった.とにかく急いでいたJOI 君は,落ちた本を順番を全く考慮せず全て本棚
に入れて家を出た.帰宅後,JOI 君は滅茶苦茶な順番に並んだ本を本来の順番に戻す作業が必要になった.
JOI 君の部屋の本棚は幅N センチメートルであり,本棚には幅1 センチメートルの本がN 冊入っている.
本には1 からN までの番号がふられており,本来は本棚には左から1, . . . , N の順番で本が並べられていた.
また,本i の重さはAi グラムである.
JOI 君は疲れていて本を同時にたくさん持ちたくなかったので,次のような操作を行うことで本棚を整
理することにした:
• 本棚に入っている本を1 つ選び,取り出す.
• 次に,本を取り出してできた隙間に隣接している本を動かすことを何度か行う.
• 次に,取り出した本を本棚の隙間に戻す.
本を本棚から同時に2 冊以上取り出すことはできない.
例えば,本が左から5, 3, 4, 1, 2 の順で並んでいるとき,本1 を取り出し,本4 と本3 を順に右に動かし,
本1 を本棚に戻すことで,本棚の本を左から5, 1, 3, 4, 2 の順にすることができる.(下図)
5 3 4 1 2
↓
5 3 4 2
↓
5 3 4 2
↓
5 3 4 2
↓
5 1 3 4 2
この操作で,JOI 君が重さw グラムの本を本棚から取り出すとき,JOI 君はちょうどw カロリーを消費
する.また,JOI 君が重さw グラムの本を本棚に戻すときも,JOI 君はちょうどw カロリーを消費する.ま
た,本棚はなめらかな素材でできているので,JOI 君が本棚の中で本を動かすときにはJOI 君はカロリー
を消費しないとしてよい.
JOI 君は疲れていたので,なるべくカロリーを消費しないようにして本棚の本を本来の順番に戻すこと
にした.
本棚– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Bookshelf
課題
本の数と,それぞれの本の重さ,現在の本棚の本の並び順が与えられたとき,JOI 君が本棚の本を本来
の順番に並び替えるために消費するカロリーの合計の最小値を求めるプログラムを作成せよ.
制限
1 ≦N ≦100 000 本の数
1 ≦Ai ≦1 000 000 000 本i の重さ(グラム)
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.
• 続くN 行には本の重さの情報が書かれている.i + 1 行目(1 ≦i ≦N) には,本i の重さを表す整数Ai
が書かれている.
• 続くN 行には現在の本棚の本の並び順の情報が書かれている.j + N + 1 行目(1 ≦j ≦N) には,現
在左からj 番目にある本の番号を表す整数が書かれている.
出力
標準出力に,JOI 君が消費するカロリーの合計の最小値を表す整数を1 行で出力せよ.
採点基準
採点用データのうち,配点の30%分については,N ≦5 000 を満たす.
採点用データのうち,配点の30%分については,1 ≦i ≦N なる全てのi に対しAi = 1 を満たす.
採点用データのうち,配点の20%分については,これら2 つの条件の両方を満たす.
採点用データのうち,配点の40%分については,これら2 つの条件の少なくとも一方を満たす.
本棚– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – Bookshelf
入出力の例
入力例 出力例
4 14
1
6
4
3
3
4
2
1
この入力例では,最初本は左から3, 4, 2, 1 の順に並んでおり,本1, 2, 3, 4 の重さはそれぞれ1, 6, 4, 3 グラ
ムである.
JOI 君は,まず以下の操作を順番に行う:
• 本1 を取り出す.
• 本2,本4,本3 を順に右に動かす.
• 本1 を隙間に戻す.
本棚の本は左から1, 3, 4, 2 の順になる.本1 の重さは1 グラムなのでJOI 君は1 × 2 = 2 カロリーを消費
する.
次に,以下の操作を順番に行う:
• 本2 を取り出す.
• 本4,本3 を順に右に動かす.
• 本2 を隙間に戻す.
本棚の本は左から1, 2, 3, 4 の順になる.本2 の重さは6 グラムなのでJOI 君は6 × 2 = 12 カロリーを消費
する.
よってJOI 君は合計14 カロリーの消費で本を左から1, 2, 3, 4 の順にできる.また,JOI 君が消費するカ
ロリーをこれより少なくすることは不可能である.
本棚– 3 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – IOI
国際情報オリンピック(IOI)
20XX 年,ついにJOI 国で行われることになったIOI にはK 人の選手が参加した.選手には1, 2, . . . , K と
番号が付けられている.問題は全部でN 問出題され,各選手は各問題について0 以上100 以下の整数の点
数を付けられる.
選手にはN 問の合計点に応じてメダルが与えられる.メダルの与えられる詳しい条件は,たとえば金メ
ダルについては次のように決まっている:
G を,N 問の合計点がG 点以上の選手の人数が全体の1 以上となるような最大の値とする.こ 12
のとき,金メダルが与えられる条件は,N 問の合計点がG 点以上であることである.
すでに競技が終了している問題がM 問あり,点数が確定している.IOI のウェブサイトで各選手の現在ま
での合計点を見ていたあなたは,金メダルを与えられることが確実な選手や金メダルを与えられる可能性
のある選手がそれぞれどれだけいるのかが知りたくなった.
課題
各選手の現在までの合計点が与えられたとき,金メダルを与えられることが確実な選手,および,金メ
ダルを与えられる可能性のある選手をそれぞれ番号順に出力するプログラムを作成せよ.
制限
1 ≦K ≦100 000 選手の人数
1 ≦N ≦10 000 000 全体の問題数
0 ≦M ≦N すでに終了した問題数
0 ≦Pi ≦100 × M 番号i の選手の現在までの合計点
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数K, N, M が空白を区切りとして書かれており,選手の人数がK 人であること,全体の
問題数がN 問であること,そのうちすでに終了した問題がM 問あることを表す.
• 続くK 行には各選手の得点が書かれている.i + 1 行目(1 ≦i ≦K) には,番号i の選手の現在までの
合計点を表す整数Pi が書かれている.
国際情報オリンピック– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – IOI
出力
標準出力に以下の内容を出力せよ.
• 初めのa 行は,金メダルを与えられることが確実な選手の番号を,1 行に1 つずつ,小さい順に列挙
していなければならない.ただしa は金メダルを与えられることが確実な選手の人数である.
• 続く1 行には文字列-------- (ハイフンが8 個) を出力せよ.
• 続くb 行は,金メダルを与えられる可能性のある選手の番号を,1 行に1 つずつ,小さい順に列挙し
ていなければならない.ただしb は金メダルを与えられる可能性のある選手の人数である.
採点基準
採点用データのうち,配点の20%分については,K ≦3 000 を満たす.
国際情報オリンピック– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 4 – IOI
入出力の例
入力例1 出力例1
15 3 2 12
0 --------
30 4
50 6
100 9
0 11
190 12
10 14
50
100
80
90
200
50
100
0
入力例2 出力例2
5 4 2 --------
0 1
50 2
100 3
150 4
200 5
国際情報オリンピック– 3 / 3