Xmas Contest 2010
Problems

Xmas Contest 20102Problem A : Christmas Trees
TL: 1 sec ML: 64 MB

うさぎたちの住む街には, とてもとても長い直線状の大通りがある. 今年の冬は, この大通りにたくさんのクリスマスツリーが植えられた. 大通りの端から端まで, 間隔が a Metr, b Metr, a Metr, b Metr, a Metr, bMetr, · · · となるようにクリスマスツリーがある (Metr は長さの単位である).
うさぎの友達のねこ, くま, きつねの家は大通り沿い, 同じ側で, 異なる場所にある. うさぎは, ねこの家からくまの家までは c Metr であり, ねこの家からきつねの家までは d Metr であることを知っている. くまの家からきつねの家までには, 大通りに何本のクリスマスツリーがありうるだろうか. 最小値と最大値を求めよう.
ただし, くまの家やきつねの家ちょうどのところにあるクリスマスツリーも数えるものとする. また, 家やクリスマスツリーは十分に小さいものとする.

Input
各入力は 1 個以上 100 個以下のテストケースからなる.
各テストケースは, 整数 a, b, c, d (1 ≤ a ≤ 1 000 000 000, 1 ≤ b ≤ 1 000 000 000, 1 ≤ c ≤ 1 000 000 000,

1 ≤ d ≤ 1 000 000 000) を含む 1 行からなる.
最後のテストケースの次の行には, 4 つの 0 が書かれている.

Output
各テストケースに対して, 求める最小値と最大値をこの順に 1 つの空白で区切って 1 行に出力せよ.

Grading
採点用データのうち配点の 40% 分については, a ≤ 100, b ≤ 100 を満たす.
採点用データのうち配点の 20% 分については, a ≤ 100, b ≤ 100, c ≤ 100, d ≤ 100 を満たす.

SampleSample Input2 5 6 12
2 5 15 8
5 2 2 175 2 75 72
3 3 44 55
0 0 0 0Sample Output
1 6

Xmas Contest 2010
2 84 60 43
3 34Hint

サンプル入力の 1 個目のテストケースについて, 必要ならば上の図を参考にせよ.

3

Xmas Contest 2010

4





Problem B : Simple Parsing
TL: 1 sec ML: 64 MB



どこかの国のプログラミングコンテストでは, 行列が複雑に出てくる数式を調べさせる問題が出題されたらしい. うさぎの国のプログラミングコンテストはもっと平和である.
そんなわけで, これは単純な数式を調べる問題である. 数式は, 整数, 加算 +, 減算・符号反転 −, 括弧 () のみからなる.
参考までに, BNF を用いて数式の正確な定義を表すと以下のようになる.

• <expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>• <term> ::= <integer> | "-" <term> | "(" <expression> ")"• <integer> ::= <digit> | <integer> <digit>• <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
以下の点に注意せよ.

• 数式は空白を含まない.
• 加算 + と減算 − は, 通常の計算と同様に, 括弧がない限りは左から行う.
• 符号反転の − が重なることがある. これは右に結合する.
• 整数の先頭には余計な 0 が付いていることがある. それらは無視すること.
• 実は, 答えることが要求されているのは, 計算結果が偶数か奇数かだけである.

Input
各入力は 1 個以上 10 個以下のテストケースからなる.
各テストケースは, 上記で定義された数式 <expression> が 1 つ書かれた 1 行からなる. 与えられる数式は10 000 文字以下である.
最後のテストケースの次の行には, 1 つの # が書かれている.

Output
計算結果が偶数ならば EVEN, 奇数ならば ODD と 1 行に出力せよ.

Grading
採点用データのうち配点の 40% 分については, 与えられる数式は 100 文字以下である.

SampleSample Input
2010-(12+25)

Xmas Contest 2010
-55+1+2+3+4+5+6+7+8+9+10-----(0+123456789)+(3+-2+((((000001)))))#Sample Output
ODD
EVENODD5

Xmas Contest 20106Problem C : Connect The Decoration
TL: 2 sec ML: 64 MBありすは, クリスマスツリーのかざりつけを楽しんでいます. きらきらのアクセサリーやふわふわのマスコットたちをどのように並べるか, それはとても重要な問題なのです. おねえさんの読んでいた本に出てくるような難しい言葉で言えば, 「えぬぴぃこんなん」とか言うんでしたっけ. 「絵がない本なんかで, かざりつけ問題が解けるわけないじゃない」とありす. とにかく, かざりつけは難しいのです.
さてさて, ありすはお気に入りのアクセサリーやマスコットを机の上にでたらめに並べてみました. 「たくさんありすぎて, よくわかんない」ですって. そう, アクセサリーやマスコットがあまりに多くて, いちばんいい並べ方を見つけるのは, まさに「えぬぴぃこんなん」なのでした.
とりあえず, ありすはいくつかのアクセサリーとマスコットをビーズのチェーンや糸でつなげてみて, 試しにツリーにかざってみよう, ということにしました. しかし, つなげてみてはかざりつけを試し, つなげてみてはかざりつけを試し, を何回もやっていると日が暮れてしまいます. なんとかして, うまくいきそうなつなぎかたを見つけないといけません.
アクセサリーやマスコットをつなげるときは, 色の組み合わせ, 形の組み合わせ, 動物の相性といったいろいろなことをありすは考えます. つなげる部分が多いとみばえがあまりよくならない気がしたありすは, 「この子とこの子を直接つなげたときの＜みばえわるさ＞はいくつ」という数をどんどんつけていきました. 相性がわるすぎて, つなげるのはもってのほか！ というような組み合わせのことはしっかりと忘れました.
ところで, ありすにはいくつかの「すごくお気に入りのアクセサリー」や「すごくお気に入りのマスコット」があります. ツリーにかざろうと試すときにはつなげたアクセサリーやマスコットを持ち上げますが, そのときに, 「すごくお気に入り」なものたちをぜんぶ持ち上げなきゃ, とありすは決めました. 「すごくお気に入り」ではないもののいくつかは離れていて机の上に残ってもかまいませんが, 「すごくお気に入り」なものた
ちはぜんぶがひとかたまりにつながっていなければなりません.
ありすは, ＜みばえわるさ＞の合計がいちばん小さくなるようなつなげかたを試すことにしました. いったい, ＜みばえわるさ＞はいちばん小さくなるといくつになるのでしょうか？

Input
各入力は 1 個以上 10 個以下のテストケースからなる.
各テストケースは, 以下のような形式である. 入力の値はすべて正の整数である.

NM

s1..
.
sN
a1..
.

b1

c1

aM

bM

cM

Xmas Contest 20107

アクセサリーとマスコットは合わせて N 個あり (2 ≤ N ≤ 100), 直接つなげる可能性があるアクセサリーやマスコットのペアは M 組ある (1 ≤ M ≤ 1000).
アクセサリーやマスコットには 1 番から N 番までの通し番号がついている. i 番のアクセサリーまたはマスコットが「すごくお気に入り」であるとき si = 0 であり, そうでないとき si = 1 である. 各テストケースにおいて, si の総和は 10 以下である.

aj bj cj という行は, aj 番と bj 番のアクセサリーやマスコットをつなげる可能性があり, その＜みばえわるさ＞が cj であることを表す (1 ≤ aj < bj ≤ N , 1 ≤ cj ≤ 1 000 000). 異なる j, k に対して (aj , bj ) = (ak , bk )となることはない.

M 組のつなげる候補すべてをつなげると, N 個のアクセサリーとマスコットはすべてつながって, 一気に持ち上げられるようになることが保証されている. また, 「すごくお気に入り」のアクセサリーまたはマスコッ
トは少なくとも 2 個あることが保証されている.
最後のテストケースの次の行には, 2 つの 0 が書かれている.

Output
各テストケースごとに, ＜みばえわるさ＞の合計の最小値を 1 行で出力せよ.

Grading
採点用データのうち配点の 40% 分については, N ≤ 10 を満たす.

SampleSample Input
4 600111 2 10
1 3 1
1 4 1
2 3 1
2 4 1
3 4 10
5 70
101

Xmas Contest 2010
0
3 5 8
1 2 5
1 3 122 3 6
3 4 134 5 7
2 4 200 0
Sample Output
2198

Xmas Contest 20109Problem D : Presents
TL: 2 sec ML: 64 MB

うさぎたちの住む街には, とてもとても長い直線状の大通りがある. 大通り上, 駅からうさぎの家までの間にはたくさんのお店があるが, クリスマスというこの一大イベントに合わせてセールを行っている. どのお店も,「クリスマスプレゼント」の販売をしているが, 具体的に何を売っているかはもちろんお店によって異なる.
ある日, うさぎは駅からの帰り道にお店でたくさんプレゼントを買っていくことにした. もちろん, たくさんのプレゼントを買うと嬉しいが, あまり大荷物で歩くのも疲れてしまう. 以下の条件の下で, うまいプレゼントの買い方を探そう.

• 駅からうさぎの家までの距離は D Metr である (Metr は長さの単位である).
• お店は N 軒あり, 駅から近い順に 1 から N までの番号がついている.
• 駅からお店 i までの距離は di Metr である.
• お店 i で x 個のプレゼントを買うと, ai x + bi 円かかる.
• すべてのお店に寄る必要はない.
• 1 つのお店で買えるプレゼントの数に制限はない.
• うさぎは, プレゼント x 個を持って y Metr 進むと, 「疲れ度」が x2 y たまってしまう.
• うさぎは, 合計で少なくとも P 個のプレゼントを買うことにした.
• うさぎは, (かかった金額) + (たまった疲れ度) − Q × (買ったプレゼントの個数) を最小化したい.

Input
各入力は 1 個以上 10 個以下のテストケースからなる.
各テストケースは, 以下のような形式である. 入力の値はすべて正の整数である. 各文字の意味は問題文中の通りである.

NPQ

d1..
.

a1

b1

dN

aNbN

D1 ≤ N ≤ 1 000, 1 ≤ P ≤ 1 000, 1 ≤ Q ≤ 100 000, 0 < d1 < · · · < dN < D ≤ 100 000, 1 ≤ ai ≤ 100 000,1 ≤ bi ≤ 100 000 を満たす.
最後のテストケースの次の行には, 4 つの 0 が書かれている.

Output
各テストケースに対して, (かかった金額) + (たまった疲れ度) − Q × (買ったプレゼントの個数) の最小値を1 行に出力せよ.

Xmas Contest 2010

10Grading
採点用データのうち配点の 30% 分については, N ≤ 100, P ≤ 100, Q ≤ 100, D ≤ 100 を満たす.

SampleSample Input
1 1 22 10
7 3 22 3 5 10
1 1 202 2 202 2 50 10
4 10 1
6 18 10 0 0 0Sample Output-2883-70Hint
サンプル入力の 1 個目のテストケースにおいては, 店 1 でプレゼントを 3 個買うのが最適である. 11 円かかり, 疲れ度は 27 となる.
サンプル入力の 2 個目のテストケースにおいては, 店 1 には寄らず, 店 2 でプレゼントを 3 個買うのが最適である. 26 円かかり, 疲れ度は 72 となる.

Xmas Contest 2010

11





Problem E : Donuts
TL: 1 sec ML: 64 MB

ありすはお菓子が大好き. ここはありすの夢の中の世界, N 個のドーナツが空中に浮かんでいるようです.
各ドーナツは 4 数 a, b, t, k で表されます. これは, そのドーナツを xy 平面に正射影すると, 楕円 x2 /a2 +y 2 /b2 = 1 を正の向きに t 度回転させたものと, それを原点中心に k % に縮小したものとで挟まれた領域となることを示します. と言われてもありすにはぴんとこないので, これを処理するのはあなたの役目なのです.

xy 平面に垂直な方向から見たとき, ドーナツがすべて重なっている部分の面積を求めてください.

Input
各入力は 1 個以上 20 個以下のテストケースからなる.
各テストケースの 1 行目には, ドーナツの個数を表す整数 N (1 ≤ N ≤ 10) が書かれている.
続く N 行には, 各ドーナツを表す 4 つの整数 a, b, t, k (0 < a ≤ 100, 0 < b ≤ 100, 0 ≤ t < 180,0 < k < 100) が書かれている.
最後のテストケースの次の行には, 1 つの 0 が書かれている.

Output
ドーナツがすべて重なっている部分の面積を 1 行で出力せよ. 正解との絶対誤差は 10−3 以下であること.

Grading
採点用データのうち配点の 30% 分については, N ≤ 2 を満たす.

SampleSample Input
14 2 60 50
24 2 0 50
4 2 60 50
24 2 0 50
4 3 70 80
0Sample Output
18.849556

Xmas Contest 2010
7.328815
3.996436

Hint

サンプル入力の各テストケースについて, 必要ならば上の図を参考にせよ.

12

Xmas Contest 201013Problem F : Christmas Magic
TL: 5 sec ML: 64 MB――12 月 25 日.
世間はクリスマスで賑わっているようだが, 私はとてもそれどころではない. うさぎの生態に関する論文の締め切りが, 刻一刻と迫ってきているのだ.
文章はだいたい書き上げたが, 今はデータの加工で苦労している. 例えば, こんな表についてである.
白うさぎ

黒うさぎ

その他

合計

♂

45312♀

74718

合計

1191030

これから, データの合計の値, ここでは 30 を, 別の値, たとえば 100 になるように変換することになっている. つまりこの例では表の各値を 10/3 倍すればいい. しかし同時に, 表の各マスに現れる数は整数でなければならないので, 適切に丸める必要がある.
「普通に四捨五入すればいいじゃない」だって？ 試しにやってみようか.
白うさぎ

黒うさぎ

その他

合計

♂

13171040♀

23132360

合計

373033100

これは気に入らない. なぜなら, ♀の行や白うさぎの列の合計の値が各データの単純な和とずれているからだ.
♀白うさぎの項目を 23 から 24 に修正すれば, この問題は解決する.
白うさぎ

黒うさぎ

その他

合計

♂

13171040♀

24132360

合計373033100

最初の表では同じ 7 であった 2 つの値が, 24 と 23 という異なる値に変換されてしまったが, 別に構わない.
そんなに厳密に書かなければならない論文でもないし, そもそももともとのデータに多少の誤差が伴うからだ.
こういう表はまだまだたくさんある. とても人の手でやってられる量じゃない. サンタさんでもやってきて魔法でどうにかしてくれればいいのに. ちょっと遅いけれど.
ところで, 修正方法はでたらめではいけない. 実数 x を整数 y に丸めるときは, x − 1 < y < x + 1 でなければならない. さらに, 「ずれ」として (x − y)2 を考えて, 表の各マスに対してこの値を足そう. もちろん, 各行の合計や各列の合計についてもである. 上の表では, 「ずれ」の和は (40/3 − 13)2 + (50/3 − 17)2 + (10 −10)2 + (40 − 40)2 + (70/3 − 24)2 + (40/3 − 13)2 + (70/3 − 23)2 + (60 − 60)2 + (110/3 − 37)2 + (30 − 30)2 +(100/3 − 33)2 + (100 − 100)2 = 10/9 となる. 私は「ずれ」の和が最小になるような表を作りたい.

Xmas Contest 2010

14

「ずれ」の和が最小になるような表が複数考えられるなら, もうどれでも構わない. もし万が一条件を満たす表が見つからないなら, ……どうしようかな.

Input
各入力は 1 個以上 10 個以下のテストケースからなる.
各テストケースの 1 行目には, 整数 M, N, K (1 ≤ M ≤ 40, 1 ≤ N ≤ 40, 1 ≤ K ≤ 1 000 000 000) が書かれている. これは, 表のデータが M 行 N 列であること, 合計の値が K になるように変換しようとしていることを表す.
続く M 行の各行には N 個の非負整数が書かれており, 順番に表の内容を表す. これら M N 個の非負整数の和は 1 以上 1 000 000 000 以下である.
表の各行の合計や各列の合計の部分は, M, N の値やその後の入力には含まれないことに注意せよ. 例えば,問題文中の表の場合は M = 2, N = 3 である.
各テストケースの後には空行が 1 つ含まれる.
最後のテストケースの次の行には, 3 つの 0 が書かれている.

Output条件を満たす表が存在する場合, 「ずれ」の和が最小になる表を 1 つ出力せよ. 表は入力と同様に M 行からなり, 各行は空白で区切られた N 個の整数からなる. が複数ある場合は, そのうちどれを出力してもよい.
条件を満たす表が存在しない場合は, 表の代わりに Merry Christmas! という 1 行を出力せよ.
各テストケースに対する出力の後には空行を 1 つ出力すること.

Grading
採点用データのうち配点の 10% 分については, M ≤ 2 を満たす.
採点用データのうち配点の 10% 分については, M N ≤ 16 を満たす.

SampleSample Input
2 3 100
4 5 3
7 4 7
1 6 101 1 1 1 1 10 0 0
Sample Output

Xmas Contest 201013 17 1024 13 23
1 1 2 2 2 2Hint
サンプル入力の 2 個目のテストケースにおいては, 出力は一意ではないことに注意せよ.

Warning
採点に時間がかかる場合がありますのでご了承ください.

15Xmas Contest 2010

16





Problem G : Strange Sequence
TL: 2 sec ML: 64 MB

くろうさ 「昨日, 夢で不思議な数列の話を見たんだ. 」
しろうさ 「あなたはいつも変わった夢を見るのね. どんな数列？」
くろうさ 「確か, N 個の整数が並んでいて, 連続するどの A 項の和も正で, 連続するどの B 項の和も負, とかだったなあ. 確か, 数列の端と端は連続しているとは考えなかった. 」
しろうさ 「なにそれー. そんな数列本当にあるの？」
くろうさ 「それがわからないんだ. あ, そういえば, 数列中の任意の連続する範囲の和の絶対値はいずれも 1以上 M 以下だ, って条件がさらについてたんだった. 連続する範囲, ってのは 1 項のみや数列全体も含むよ. 」
しろうさ 「そんなの無理に決まってるじゃない……自信ないけど. 」
くろうさ 「そうだよねえ. 」

Input
各入力は 1 個以上 20 個以下のテストケースからなる.
各テストケースは, 整数 N, M, A, B (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, 1 ≤ A ≤ N , 1 ≤ B ≤ N ) を含む 1 行からなる.
最後のテストケースの次の行には, 4 つの 0 が書かれている.

Output
各テストケースに対して, 条件を満たす数列として考えられるものの個数を 1 000 000 009 で割った余りを 1行で出力せよ.

SampleSample Input
2 4 1 15 3 3 25 3 3 519 22 6 70 0 0 0
Sample Output
0000

Xmas Contest 201017Problem H : Read Me
TL: 2 sec ML: 64 MB


どの問題の入力であるかを答えるだけの簡単なお仕事です.

Input
各入力は 1 個以上 10 個以下のテストケースからなる. 入力は 500 KB を超えない.
各テストケースは, 「Xmas Contest 2010」の問題 A, B, C, D, E, F, G のいずれかの入力データの要件を満たす.
各テストケースの次の行には, @@@@@@@@@@ (アットマーク 10 個) が書かれている. さらに, 入力の最後の行には, @@@@@@@@@@@@@@@@@@@@ (アットマーク 20 個) が書かれている.

Output
各テストケースに対応する問題のアルファベット大文字 (A, B, C, D, E, F, G のいずれか) を 1 行に出力せよ. 2 つ以上の問題の入力データとしてあり得る場合は, 代わりに ? (半角疑問符) を出力せよ.

SampleSample Input
2 5 6 122 5 15 8
5 2 2 175 2 75 72
3 3 44 55
0 0 0 0@@@@@@@@@@
2010-(12+25)-55+1+2+3+4+5+6+7+8+9+10-----(0+123456789)+(3+-2+((((000001)))))#@@@@@@@@@@
4 60011
1 2 10Xmas Contest 2010
1 3 1
1 4 1
2 3 1
2 4 1
3 4 105 7010103 5 8
1 2 5
1 3 122 3 6
3 4 134 5 7
2 4 200 0@@@@@@@@@@
1 1 22 10
7 3 2
2 3 5 10
1 1 202 2 202 2 50 10
4 10 1
6 18 10 0 0 0@@@@@@@@@@
14 2 60 50
24 2 0 50
4 2 60 500@@@@@@@@@@
2 3 100
4 5 3
7 4 718

Xmas Contest 2010

1 6 101 1 1 1 1 10 0 0@@@@@@@@@@
2 4 1 15 3 3 25 3 3 519 22 6 70 0 0 0@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Sample Output
AB
CDEF?

19