acm International Collegiate Programming Contest

Links

A B C D E F G H I

Problem A

部員の変遷

春は別れと出会いの季節.今年もまた,伝統ある芸楽部の歴史に新たな名前を刻むときが来た.

部活日誌には,この部活の n 年分の部員の推移が記録されている.記録によれば,初年度より前の部員数はもちろん 0 人であり,毎年部員は 4 月に新入生のみが入部しており,3 年後の 3 月に卒業するタイミングでのみ退部しているようだ.

部の変遷を紐解くために,n 年間の各年の新入部員の数のデータから在籍する部員の数が最大になった年度の部員数を調べてみよう.

Input

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

n a1 a2 an

n は新入部員の数が記録されている年数を表す,3 以上 1000 以下の整数である.続く行は各年度の新入部員の数を表す n 個の整数からなり,i 年目の新入部員の数 ai はそれぞれ 0 ≤ ai ≤ 108 を満たす.

入力の終わりは,ゼロ 1 つだけからなる行で表される.

Output

各データセットについて,在籍する部員の数が最大になった年度の部員数を 1 行に出力せよ.

Sample Input

8
5 2 3 4 8 2 1 6
3
2 1 7
5
0 1 3 3 3
5
0 0 0 0 0
0

Sample Output

15
10
9
0
(End of Problem A) A B C D E F G H I

Problem B

シンプルなエディタ

あなたはコンピュータの中で働く妖精である.あなたの今日の仕事はキーボードからの入力を元にエディタを操作することである.

しかし,あなたは寝坊してしまった! 急いで仕事場に向かうとすでにキーボードからの入力が処理されずに溜まっている.今あなたがすべきことは,とにかく今溜まっている入力を全て順に処理した後の文字列を画面に表示することである.

状況を整理しよう.最初エディタには文字列が何も書かれておらず,文字の挿入位置を示す縦線(カーソル)が 1 つあるだけである.

キーボードからの入力には大きく分けて以下の 3 種類が存在する.

  • INSERT c
    • このとき,あなたはカーソルの左に文字 c を挿入する.
      • より正確には,カーソルの左隣に文字が存在しない場合はカーソルの左隣に,カーソルの左隣に文字が存在する場合はその文字とカーソルとの間に文字 c を挿入する.
  • LEFT _
    • このとき,あなたはカーソルを 1 文字分左に動かす.ただし,カーソルの左に文字が存在しない場合は何もしない.
    • _” は入力形式を合わせるためのダミーである.
  • RIGHT _
    • このとき,あなたはカーソルを 1 文字分右に動かす.ただし,カーソルの右に文字が存在しない場合は何もしない.
    • _” は入力形式を合わせるためのダミーである.

いま溜まっているキーボードからの入力を全て順に処理した後の文字列を求め,出力せよ.カーソルを出力する必要はない.

Input

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

N a1  ⋮ aN

1 行目にはキーボードからの入力の数を表す整数 N が与えられる.N1 ≤ N ≤ 1000 を満たす.

続く N 行にはキーボードからの入力 ai が順に与えられる.ai は以下の 3 つのいずれかの形式を満たす.

  • INSERT c
    • c は英小文字 1 文字である
  • LEFT _
  • RIGHT _

INSERT c という形式の入力が 1 つ以上存在することが保証される.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットについて,キーボードからの入力を全て順に処理した後の文字列を一行に出力せよ.

Sample Input

5
INSERT a
INSERT g
LEFT _
LEFT _
INSERT j
19
INSERT z
INSERT y
LEFT _
LEFT _
LEFT _
INSERT a
RIGHT _
RIGHT _
INSERT a
RIGHT _
INSERT n
LEFT _
LEFT _
RIGHT _
LEFT _
LEFT _
INSERT n
LEFT _
INSERT u
0

Sample Output

jag
azunyan
(End of Problem B) A B C D E F G H I

Problem C

星間広告計画

20XX 年,民間人の宇宙旅行が当たり前となった時代のことである.旅行会社の社長であるあなたは新たに小星団 X を発見した.小星団 X は N 個の小さな星からなり,星 i は 3 次元 xyz 直交座標系における (xi, yi, zi) の位置に存在している.

さて,あなたは星団 X 内に自分の会社の看板を建てようと計画している.具体的には,星団 X 内から同一平面上に存在する 4 つの相異なる星を選択し,それらの星を頂点とする正の面積を持つ長方形の看板を建てたいと考えている.ただし星の大きさは無視でき,長方形領域の周上や内部に別の星が存在しても問題ないとする.

看板の頂点となりうる 4 つの星の組の総数を求めよ.

Input

入力は 30 個以下のデータセットからなる.各データセットは次の形式で表される.

N x1 y1 z1  ⋮ xN yN zN

1 行目には整数 N が与えられる.N は星団 X に含まれる星の個数であり,4 ≤ N ≤ 1500 を満たす.

続く N 行には,星団 X に含まれる各星の座標が与えられる.このうち i 番目の行には整数 xi, yi, zi が与えられ,i 番目の星が 3 次元座標 (xi, yi, zi) の位置に存在していることを表す.|xi|, |yi|, |zi| ≤ 108 を満たすことが保証される.N 個の座標はすべて相異なる.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットについて,看板の頂点となりうる 4 つの星の組の総数を1 行で出力せよ.

Sample Input

8
0 0 1
0 1 1
1 0 1
1 1 1
6 0 1
7 1 1
9 -1 1
8 -2 1
8
0 0 0
0 1 0
1 0 0
1 1 0
0 0 2
0 1 2
1 0 2
1 1 2
20
-2 -2 1
-2 -1 -2
-2 -1 1
-2 0 -2
-1 -2 -1
-1 1 -2
-1 1 1
-1 1 2
0 -2 -2
0 -2 -1
0 -2 1
0 1 2
0 2 -1
1 0 -2
1 0 -1
1 1 2
1 2 -1
1 2 0
2 1 -2
2 2 0
0

Sample Output

2
12
15
(End of Problem C) A B C D E F G H I

Problem D

過去問の共有

JAG 大学 ICPC 学科には N 人の学生が在籍しており,それぞれの学生には 1 から N までの番号がついている.また,学生の交友関係が M 個存在する.i 番目の交友関係は,学生 aibi が友達であり,互いに連絡できることを表す.

学科の期末試験では,N 教科の試験が行われる予定である.はじめ,学生 i は教科 i の過去問を持っている.
あなたは学生 1 である.友達同士で過去問を共有することを繰り返したとき,あなたが過去問の情報を何教科得られるかが気になった.そこで,友達同士で行われる過去問の共有が K 回行われたときの期待値を調べることにした.

次のイベントが順に K 回独立に発生することを考える.

  • M 個の交友関係のうち一つがランダムに選ばれ,その学生二人が連絡を取りあう.このとき,それぞれが持つ過去問情報をすべて共有しあう.
    • 言い換えると,片方が持つ過去問の教科の集合を X,もう片方を Y とすると,そのイベントの後,持っている過去問の教科の集合は双方とも X ∪ Y になる.

K 回のイベントの終了後,学生 1 であるあなたが持っている過去問の教科数の期待値を mod 998244353 で求めよ.

なお,この問題において,求める期待値は必ず有理数になることが証明できる.また,この問題の制約のもとでは,その値を既約分数 P/Q で表したとき,Q ≢ 0 (mod 998244353) となることも証明できる.よって,R × Q ≡ P (mod 998244353), 0 ≤ R < 998244353 を満たす整数 R が一意に定まる.この R が,期待値 mod 998244353 である.ここで,998244353 = 223 × 7 × 17 + 1 は素数である.

Input

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

N M K a1 b1  ⋮ aM bM

1 行目には NM および K が与えられる.N は学生の人数であり,2 以上 10 以下の整数である.M は交友関係の個数であり,1 以上 N(N-1)/2 以下の整数である.K はイベントが発生する回数であり,1 以上 50 以下の整数である.

続く M 行には,交友関係の情報が与えられる.このうち i 番目の行には ai および bi が与えられ,それぞれ 1 以上 N 以下の整数である.自分自身に交友関係があるような入力は与えられない.すなわち,すべての 1 ≤ i ≤ M について ai ≠ bi を満たす.また,同じ交友関係が複数与えられることはない.すなわち,すべての 1 ≤ i, j ≤ M について,i ≠ j ならば { ai, bi } ≠ { aj, bj } を満たす.

入力の終わりは 3 つのゼロからなる行で表される.

Output

各データセットについて,答えを 1 行で出力せよ.

Sample Input

4 3 2
1 2
1 4
3 4
4 3 9
2 3
2 4
3 4
10 20 30
3 5
6 4
1 6
1 8
7 2
9 3
2 3
6 10
1 9
3 10
2 8
4 10
5 1
7 3
10 8
4 9
3 8
10 1
5 9
4 5
0 0 0

Sample Output

887328316
1
369808863
(End of Problem D) A B C D E F G H I

Problem E

ジェットコースター 2

JAG (Japan Amusement Group) は,観光客が多く訪れる国内有数の遊園地である.中でもジェットコースターは大人気アトラクションである.

今日も JAG は大盛況であり,ジェットコースター前には多数の団体客が列を作って待機している.アトラクションのスタッフであるあなたが確認したところ,待機列には現在 N グループの団体客が並んでおり,列の先頭から i 番目の団体は ai 人からなるようである.

ジェットコースターには一度の運行で M 人まで搭乗可能であり,あなたはアトラクションの各運行ごとに以下のルールに従って客を座席へ案内する.これを待機列から客がいなくなるまで繰り返す.

  1. 待機列が空になった場合,もしくは待機列先頭に並んでいる団体客の人数がジェットコースターの空席数より多い場合,ジェットコースターを発進させて現在の運行を終える.
  2. 1 の条件に当てはまらない場合,待機列先頭の団体客全員をジェットコースターの空席へ案内する.
  3. 1 に戻る.

閉園時間が近いことに気づいたあなたは,一組以下の隣接する団体客に待機順を入れ替わってもらうことで,アトラクション運行回数を削減できないかと考えた.具体的には以下の操作を 1 回以下行うことを考えている.

  • 1 ≤ i ≤ N-1 を満たす整数 i を一つ選び,現在待機列先頭から i 番目に並んでいる団体客と i+1 番目に並んでいる団体客の待機順を入れ替える

最適に操作を行った場合,待機列を空にするまでに必要なアトラクション運行回数は最小で何回にできるだろうか?ただし,今後新規の客が待機列に追加されることも,待機中の客が列から離脱することもないものとする.

Input

入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.

N M a1 a2 aN

一行目には整数 N, M が与えられる.N は待機中の団体客グループの数であり,2 ≤ N ≤ 2 × 105 を満たす.M は一度の運行でジェットコースターに搭乗できる最大人数であり,1 ≤ M ≤ 109 を満たす.

二行目には N 個の整数 a1, a2, ... , aN が与えられる.ai は待機列先頭から i 番目に並んでいる団体客の人数であり,1 ≤ ai ≤ M を満たす.

また,すべてのデータセットに対する N の合計は 2 × 106 を超えない.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットについて,最適な操作を行った場合に必要なアトラクション運行回数を1 行で出力せよ.

Sample Input

9 5
3 3 2 2 3 3 2 2 2
6 20
9 15 7 18 5 6
0 0

Sample Output

5
4
(End of Problem E) A B C D E F G H I

Problem F

スライムの合成

JAG 王国ではスライムの異常発生が深刻な問題になっている.魔法使いであるあなたは,スライムの数を減らすために「スライム合成魔法」を開発した.

JAG 王国のスライムには非負整数で表される「レベル」がついており,スライム合成魔法ではこのレベルが重要な意味合いを持つ.スライム合成魔法を発動すると,同じレベル X である二匹のスライムを合成して,レベル X+1 のスライム一匹にすることができるのだ.

これによってスライムの数を減らすことができることを確信したあなたはスライム異常発生の現場へと急行した.

現場では,n 匹のスライムが一列に並べられている.はじめ,左から i 番目のスライムのレベルは Li である.スライム合成魔法は列で隣り合う同じレベルの二匹のスライムにしか発動出来ず,条件を満たすスライムのペアが存在しない場合には発動することも出来ない.スライム合成魔法によって合成されたスライムは,元の二体のスライムの位置の中間に生まれる.スライムが勝手に移動することはなく,移動させることもできない.

たとえば,スライムのレベルの列が (1, 1, 1, 1) の場合,左から 2 番目のスライムと 3 番目のスライムにスライム合成魔法を発動すると,発動後のスライムのレベルの列は (1, 2, 1) になり,これ以上スライム合成魔法を発動することはできない.

スライム合成魔法は発動直前に条件を満たしていれば,どのスライムのペアにも発動することができる.最適な順序でスライム合成魔法を発動した場合,あなたは最大何匹のスライムを減らすことができるか,つまり最大何回スライム合成魔法を発動できるかを求めよ.

入力で与えられるスライムのレベルは 0 から 9 までであるが,スライム合成魔法によってレベル 10 以上のスライムを生成することが可能であることに注意せよ.

Input

入力は複数のデータセットからなる.データセットの個数は 40 を超えない.各データセットは次の形式で表される.

n L

1 行目には整数 n が与えられ,1 ≤ n ≤ 2 × 105 を満たす.2 行目には数字列 L が与えられ,その長さが n である.この数字列の i 番目の数字 Li は,左から i 番目のスライムのレベルであり,0 以上 9 以下であることが保証される.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットについて,最適な順序でスライム合成魔法を発動したとき最大何回発動できるかを答えよ.

Sample Input

4
1111
5
31132
10
3331124331
0

Sample Output

3
1
8
(End of Problem F) A B C D E F G H I

Problem G

数列の分割

長さ n の整数列 A = (a1, ...,an) が与えられる.m 個の整数列 B1, ..., Bm (m ≥ 1) が以下の条件をともに満たすとき,(B1, ..., Bm)A の分割と呼ぶことにする.

  • いずれの Bi (1 ≤ i ≤ m) も,長さが 1 以上の整数列である.
  • B1, ..., Bm をこの順につなげたものは A に等しい.

たとえば,((3, 1, 4, 1, 5)) や ((3), (1, 4), (1, 5)) などはいずれも (3, 1, 4, 1, 5) の分割である.

また,整数列 B に対し,B の要素の総和の 2 乗を f(B) とする.さらに,A の分割 (B1, ..., Bm) に対し,f(B1) + … + f(Bm) を,この分割のスコアと呼ぶことにする.たとえば,((3), (1, 4), (1, 5)) のスコアは 32 + (1+4)2 + (1+5)2 = 70 である.

A の分割はちょうど 2n-1 個存在する.A のすべての分割に対するスコアを降順に並べたとき,k 番目となる値を求めよ.

たとえば,Sample Input の 2 つ目のデータセットでは,A の分割のスコアを降順に並べると 196, 130, 116, 110, 106, 100, 90, 70, 70, 68, 66, 62, 60, 60, 58, 52 となるため,6 番目の値は 100 である.

Input

入力は複数のデータセットからなる.データセットの個数は 30 を超えない.各データセットは次の形式で表される.

n k a1 a2 an

n および k はいずれも整数であり,1 ≤ n ≤ 1000 および 1 ≤ k ≤ min{2n-1, 2000} を満たす.各 ai は数列 Ai 番目の要素となる整数であり,-106 ≤ ai ≤ 106 を満たす.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットについて,A のすべての分割のスコアのうち k 番目に大きい値を,1 行に出力せよ.

Sample Input

5 1
3 1 4 1 5
5 6
3 1 4 1 5
14 255
2024 6 29 14 0 -17 0 2024 7 5 16 30 -19 30
0 0

Sample Output

196
100
8484005
(End of Problem G) A B C D E F G H I

Problem H

物理実験

ウェーブマシンは,波のふるまいを観察するための物理実験装置である.この装置上では横波を発生させることができ,発生した波は一定の速さで進行し,装置の両端で反射する.

この問題で考える波は,波長の極めて短い 1 周期の波のみであり,その位置は点とみなせるものとする.いま,任意の実数 x ≥ 0 について,ウェーブマシンの左端から右に x 離れた位置の座標を x と定義する.また,ウェーブマシンの右端の座標を m としよう.ウェーブマシンの左端で波を発生させたとき,はじめ,波はある速さ v で右方向に進行する.波が座標 m に到達したとき,波は反射し,同じ速さのまま進行方向は左向きとなる.同様に,波が座標 0 に到達したとき,波の進行方向は右向きとなる.また,ウェーブマシンの両端以外の場所で波が反射することはない.したがって,一度発生した波は,長さ m のウェーブマシン上を,一定の速さ v で往復し続けることになる.

あなたは,物理の実験で,ウェーブマシン上に波を発生させ,その座標と進行方向を記録し続けることになった.はじめ,あなたはウェーブマシンの左端で波を発生させ,しばらく待機した.そして,あなたが観測を開始した時刻 0 において,この波はある座標 x0 に位置し,そのときの波の進行方向は右向きであった.その後あなたは,この波の座標と進行方向を,1 単位時間ごとに計 t 回記録した.

記録も終わり,さあ,あとは実験レポートを書くだけだ!とあなたは意気込んでいるところかもしれないが,ちょっと待ってほしい.うっかり者のあなたは,時刻 0 での波の位置の座標 x0 および速さ v を記録し忘れてしまっていた.加えて,t 個の記録をバラバラに並べ替えてしまい,どの記録がどの時刻のものかわからなくなってしまった.なんとしても再実験を避けたいあなたは,残された記録に矛盾しない x0 および v の値を用いて,実験レポートを書くことにした.

入力として,ウェーブマシンの長さ m および t 個の記録が与えられる.各記録は波の座標 yi および進行方向 di からなり,これは時刻 1, ... , t のうちのいずれかのものである.なお,座標 0 における波の進行方向は常に右向き,座標 m における波の進行方向は常に左向きとする.あなたの目的は,以下のすべての条件を満たす x0 および v の値を 1 組求めることである.なお,複数の解が存在するならば,そのうちどれを出力してもよい.

  • 時刻 0 における波の進行方向は右向きである.
  • 時刻 0 における波の位置の座標 x0 は,0 以上 m-1 以下の整数である.すなわち,座標 x0 はウェーブマシンの右端ではない.
  • 波の速さ v は,1 以上 2m 以下の整数である.
  • (1, ..., t) の順列 (p1, ..., pt) が存在し,任意の整数 j (1 ≤ j ≤ t) について,時刻 pj における波の座標は yj,進行方向は dj である.

Input

入力は複数のデータセットからなる.データセットの個数は 50 を超えない.各データセットは次の形式で表される.

m t y1 d1  ⋮ yt dt

m はウェーブマシンの長さを表す整数であり,1 ≤ m ≤ 109 を満たす.t は記録の数を表す整数であり,2 ≤ t ≤ 105 を満たす.yi はある時刻における波の位置の座標を表す整数であり,0 ≤ y ≤ m を満たす.di は L または R であり,L であればその時刻における波の進行方向が左向きであることを,R であれば右向きであることを表す.ここで,yi = 0 であれば di は R であり,yi = m であれば di は L であることが保証される.

与えられる入力に対して,答えが少なくとも 1 つ存在することが保証される.

また,すべてのデータセットに対する t の合計は 106 を超えない.

入力の終わりは 2 つのゼロからなる行で表される.

Output

条件を満たす x0 および v の値を,空白区切りで 1 行に出力せよ.条件を満たす解が複数存在するならば,そのうちどれを出力してもよい.

Sample Input

10 6
8 R
8 L
6 L
0 R
6 R
2 L
1 5
1 L
1 L
0 R
0 R
1 L
0 0

Sample Output

4 14
0 1
(End of Problem H) A B C D E F G H I

Problem I

橋の建造計画 2

N 個の小島からなる国があり,国民はそれらの島に住んでいる.島から島へ渡るにはフェリーを使うしかなく,多くの国民は不便に感じている.そこで国王は国民の意見を聞いて橋を架けることにした.

国王のもとに,国民から「島 u と島 v の間を直接結ぶ双方向に渡れる橋を架けてほしい.」という形の意見が全部で M 個届いた.資金は潤沢にあるので,これらちょうど M 本の橋を架ける計画を立てることにした.

あとはそれぞれの橋について建造を担当する建設会社を決定するだけだが,ここで一つ問題があった.この国には数多くの建設会社が存在するが,その中には,橋の耐久性に問題がある,納期を超過する,などの様々な問題を抱える会社があるらしい.残念ながら問題を抱える会社の特定はできなかったので,リスク分散と各会社との連絡コストとを天秤にかけ,以下の条件を満たすような建設会社の割り当てを考えることにした.

  • 条件
    • 各建設会社について,その会社が建造を担当する全ての橋が通れない状態でも,それ以外の橋を使いすべての島を互いに行き来することができる.
    • その上で,仕事を依頼する(1 本以上の橋の建造を担当する)建設会社の数が最小である.

あなたの仕事は,上の条件を満たすような建設会社の割り当てを実際に求めることである.

Input

入力は 40 個以下のデータセットからなる.各データセットは次の形式で表される.

N M u1 v1  ⋮ uM vM

1 行目には 2 つの整数 N および M が与えられる.N はこの国の島の数であり,2 ≤ N ≤ 150 を満たす.M は国民からの意見の総数であり,N-1 ≤ M ≤ 1500 を満たす.

続く M 行には,M 個の国民からの意見の情報が与えられる.このうち i 番目の行には整数 ui, vi が与えられ,i 番目の意見が「島 ui と島 vi の間を直接結ぶ双方向に渡れる橋を架けてほしい.」というものであることを表す.1 ≤ ui ≤ N および 1 ≤ vi ≤ N および ui ≠ vi を満たすことが保証される.また,i ≠ j ならば { ui, vi } ≠ { uj, vj } を満たすことが保証される.また,M 個の国民からの意見を叶えるように M 本の橋を架けた際,それらの橋を使用してすべての島を互いに行き来することが可能なことが保証される.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットに対し,もし条件を満たすような建設会社の割り当て方法がない場合,-1 と一行に出力せよ.そうでない場合の出力は 2 行となる.まず 1 行目に仕事を依頼する(1 本以上の橋の建造を担当する)建設会社の数 K を出力せよ.そして 2 行目に M 個の整数を空白区切りで出力せよ.そのうち i 番目の整数は,i 番目の意見に対応する橋 (ui, vi) の建造を担当する建設会社の番号であり,1 以上 K 以下の整数である必要がある.

条件を満たす解が複数存在するならば,そのうちどれを出力してもよい.

Sample Input

3 3
1 2
2 3
1 3
3 2
1 2
1 3
4 5
1 2
2 3
3 4
4 1
1 3
0 0

Sample Output

3
2 3 1
-1
3
2 3 2 1 1
(End of Problem I) A B C D E F G H I