AtCoder Regular Contest 020

A - 石を滑らせるゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

アリの Ant さんと Bug くんが石を滑らせるゲームで遊んでいます。このゲームには、まっすぐな細長い氷の板と 2 つの小さな石を使います。氷の板には 1 ミリメートルごとに -1,000 から 1,000 までの目盛りが順番についています。

はじめ 2 匹のプレイヤーは 1 つずつ石を持っています。2 匹のプレイヤーは交互に板の端から石を滑らせます。そして、最終的に滑らせた石がより 0 の目盛りに近かった方のプレイヤーがこのゲームの勝者となります。また、2 つの石の 0 の目盛りからの距離が同じ場合は引き分けとなります。

Ant さんと Bug くんのために、2 つの石のある場所の目盛りがそれぞれ与えられた時に勝敗を判定するプログラムを作ってあげて下さい。

入力

入力は以下の形式で標準入力から与えられる。

A B

1 行目には、Ant さんの石がある場所の目盛りを表す整数 A (-1,000 ≦ A ≦ 1,000) と Bug くんの石がある場所の目盛りを表す整数 B (-1,000 ≦ B ≦ 1,000) が空白区切りで与えられる。

部分点

この問題には部分点が設定されている。

0 ≦ A かつ 0 ≦ B を満たすテストケースすべてに正解した場合は 50 点が与えられる。

出力

勝者が Ant さんである場合は Ant、勝者が Bug くんである場合は Bug、引き分けである場合は Draw と 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

2 3

出力例1

Ant

Ant さんの石は 2 の目盛りの場所にあり、Bug くんの石は 3 の目盛りの場所にある。Ant さんの石の方が 0 の目盛りに近いため、勝者は Ant さんとなる。

入力例2

1 0

出力例2

Bug

入力例3

-100 100

出力例3

Draw

2 つの石のある場所の目盛りは異なるが、0 の目盛りからの距離は同じであるため、引き分けとなる。

B - 縞模様

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

小学生の高橋君は、縞模様が大好きです。今、高橋君は、左から右に一直線上に並んだ n 枚の色画用紙を眺めています。高橋君は縞模様がとても好きなので、いくつかの画用紙を絵の具で新しい色に塗り替えることで、全体に見て縞模様になっているようにしたいと思っています。

全体的に見て縞模様であるとは、全体で使用される色がちょうど 2 つであって、全ての画用紙についてそれと隣り合う画用紙との色が異なっている状態のことを指します。

あなたの仕事は、既に配置されている画用紙の枚数 n と、1 枚の画用紙を別の色に塗り替えるためにかかる絵の具の費用 c が与えられるので、縞模様の達成に必要な合計費用の最小値を出力するプログラムを作ってあげることです。この問題では便宜上、それぞれの色が 1 ～ 10 の 10 種類の数として与えられます。塗り替えるために使える絵の具の色もこの 10 種類のみです。

入力

入力は以下の形式で標準入力から与えられる。

n　c
a_1
a_2
:
a_n

1 行目には、画用紙の枚数を表す整数 n (2 ≦ n ≦ 100) と、画用紙を 1 枚塗り替えるために必要な絵の具の費用 c (1 ≦ c ≦ 1000) が与えられる。
2 行目から n 行では、既に配置された画用紙の色がそれぞれ与えられる。このうち i 行目では一直線上に並んだ画用紙のうち左から i 番目の色をそれぞれ表す整数 a_i (1 ≦ a_i ≦ 10) が与えられる。

出力

縞模様を達成するのに必要な合計費用の最小値を 1 行に出力せよ。出力の末尾にも改行をいれること。

入力例1

出力例1

塗られている色は、左から順番に 3,2,1 である。1 番目の「3」を「1」に塗り替えれば 1,2,1　となる。また、3 番目の「1」を「3」に塗り替えれば 3,2,3 となる。

これらはどちらも縞模様を達成していて、かつどちらの場合も 1 枚の画用紙を塗り替える必要があり、合計費用は 10 である。従って 10 を出力すればよい。

入力例2

出力例2

入力例3

出力例3

C - A mod B Problem

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君が高校生の頃参加していたコンテストでは、2 つの整数の和を求める問題が出題されたことがありました。あんなものは最強最速の手に掛かればお茶の子さいさいでした。

大学生になった高橋君は、現在あなたと大学生向けのコンテストに参加している真っ最中です。しかし、得意な言語を使う際に必要な統合開発環境が壊れていて、問題を解くどころではないらしいのです。そこで、チームメイトであるあなたは、統合開発環境の問題が審判団によって対応されるまでに、彼の代わりに以下の問題を解いておくことにしました。

整数 A と B が与えられる。 A を B で割った余りを出力しなさい。ただし、整数 A と整数 B について以下のような特徴があります。

整数 A, B はどちらも 10 進数である。
整数 B は 100 点中 99 点分のテストケースで B=1000000007(10^9+7)　を満たしている。
整数 A は非常に大きく、かつ部分的に周期性を持ち、以下のような形式で与えられる。

N と a_1,a_2,..,a_N と L_1,L_2,..,L_N が与えられる。これは、整数 A が上の桁から a_1 が L_1 回、a_2 が L_2 回、..、a_N が L_N 回と繰り返された形であることを意味する。

例えば、 N=3,a=\{123,4,56\},L=\{2,2,1\},B=1000000007のとき、A=1231234456であり、A を B で割った余りは 231234449 です。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1\ L_1
a_2\ L_2
:
a_N\ L_N
B

1 行目には、後に続く整数 A の情報の長さを表す整数 N (1 ≦ N ≦ 10,000) が与えられる。
2 行目から N 行では、整数 A の情報が与えられる。このうち i 行目では問題文中の a_i (1 ≦ a_i ≦ 10^9) と L_i (1 ≦ L_i ≦ 10^9) が半角スペース区切りで与えられる。
N+2 行目では、整数 B (1 ≦ B ≦ 1,000,000,007)　が与えられる。

部分点

この問題には3つのデータセットがあり、データセット毎に部分点が設定されている。

L_1+L_2+..+L_N ≦ 100,000 かつ、B=1000000007 を満たすデータセット 1 に正解した場合は 20 点が与えられる。
B=1000000007 を満たすデータセット 2 に正解した場合は、上記のデータセットとは別に 79 点が与えられる。
追加制約のないデータセット 3 に正解した場合は、上記のデータセットとは別に 1 点が与えられる。

出力

A を B で割った余りを 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

出力例1

231234449

問題文中の例です。

入力例2

1
123 3
1000000007

出力例2

123123123

A=123123123 です。

入力例3

1
123456789 10000
1000000007

出力例3

372735614

このテストケースはデータセット 1,2,3 の制約を満たしています。

入力例4

4
810143056 100000000
81671422 99999999
1639053 99999998
1657560 99999997
1000000007

出力例4

476685993

このテストケースはデータセット 2,3 の制約を満たしています。

入力例5

出力例5

このテストケースはデータセット 3 の制約を満たしています。

D - お菓子の国の旅行

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

お菓子の国はとても細長い国です。お菓子の国には N 個の町があり、それらの町は一直線上に並んでいて、端から順番に 1 から N までの番号がついています。隣り合う町の間には道があり、町 i と町 i+1 どうしを繋ぐ道の長さは D_i です。お菓子の国での移動手段はこれらの道しか存在しないため、町 a, b (a < b) について、町 a から町 b への移動距離と町 b から町 a の移動距離はいずれも D_a + D_{a+1} + ... + D_{b-1} となります。それぞれの町には砂糖専門店が 1 つずつあり、それぞれの砂糖専門店では他の町のものとは異なる砂糖を 1 種類売っています。ある町を訪れた際には、必ずその町の砂糖専門店で売っている砂糖を買わなければなりません。

アリ王国に住んでいるアリの Ant さんは、甘いものと数字の M が大好きです。Ant さんは今、お菓子の国へ旅行に行ってちょうど K 種類の砂糖を買いたいと考えています。Ant さんは、どの町の砂糖専門店をどの順番で訪れるのかを決めるために、まずはお菓子の国での移動距離の総和が M の倍数である町の訪れ方が何通りあるのかを計算してみることにしました。ただし、町の間の移動は遠回りをしないこととします。また、最初に訪れる町と最後に訪れる町はどこでも良いものとします。同じ町に2度訪れることはありません。町間の移動途中である町を通過したとして、その町を訪れたことにはならないことに注意してください。

Ant さんのために、お菓子の国での移動距離の総和が M の倍数となる町の訪れ方の個数を求めるプログラムを作ってあげて下さい。ただし、答えは非常に大きな数になることがあるため、1000000007(10^9+7) で割った余りを出力して下さい。

入力

入力は以下の形式で標準入力から与えられる。

N M K
D_1
D_2
:
D_{N-1}

1 行目には、お菓子の国にある町の個数を表す整数 N (2 ≦ N ≦ 100) と Ant さんが大好きな数を表す整数 M (1 ≦ M ≦ 30) と Ant さんが買おうと考えている砂糖の種類の数を表す整数 K (2 ≦ K ≦ 10 かつ K ≦ N) が空白区切りで与えられる。
2 行目から N-1 行では、隣り合う町どうしを繋ぐ道の長さが与えられる。このうち i 行目には、町 i と町 i+1 を繋ぐ道の長さを表す整数 D_i (1 ≦ D_i ≦ M) が与えられる。

部分点

この問題には部分点が設定されている。

N ≦ 12 を満たすテストケースすべてに正解した場合は 30 点が与えられる。

出力

答えを 1000000007(10^9+7) で割った余りを 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

出力例1

以下の 6 つの方法がある。

町 1 → 町 3 → 町 2 の順で砂糖専門店に訪れる。
町 2 → 町 3 → 町 1 の順で砂糖専門店に訪れる。
町 2 → 町 1 → 町 4 の順で砂糖専門店に訪れる。
町 4 → 町 1 → 町 2 の順で砂糖専門店に訪れる。
町 2 → 町 3 → 町 4 の順で砂糖専門店に訪れる。
町 4 → 町 3 → 町 2 の順で砂糖専門店に訪れる。

入力例2

出力例2

897286330

答えは非常に大きな数になることもあるため、1000000007(10^9+7) で割った余りを計算することを忘れてはならない。