実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 100 点
問題文
E869120 君は, CODE FESTIVAL 予選に参加するか迷った. 迷いに迷った末, 彼は「魔法のサイコロ」で参加するかどうかを決めることにした.
魔法のサイコロは, 1 以上 100 以下の整数が等確率で出るように設計されている.
彼はサイコロを 1 回振り, 出た整数が N の倍数であればコンテストに参加しない. そうでない場合, 彼はコンテストに参加する.
彼がコンテストに参加する確率は何パーセントか?
制約
- N は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N
出力
E869120 君が CODE FESTIVAL 予選に参加する確率は何パーセントか, 整数で出力しなさい.
入力例 1
3
出力例 1
67
サイコロの目が 3, 6, 9, 12, 15, 18, 21, ..., 96, 99 の場合コンテストに参加しない. そうでない場合参加する.
よって彼がコンテストに参加しない確率は 33 %, 参加する確率は 67 %である.
入力例 2
17
出力例 2
95
サイコロの目が 17, 34, 51, 68, 85 の場合コンテストに参加しない. そうでない場合参加する.
よって彼がコンテストに参加しない確率は 5 %, 参加する確率は 95 %である.
入力例 3
57
出力例 3
99
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 200 点
問題文
CODE FESTIVAL 2015 本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた.
そこで, CODE FESTIVAL 2018 本戦参加者の N 人全員が同じ行動をして, 集合写真を撮ることにした.
それぞれの人は「字の綺麗さ」「顔の面白さ」の 2 つの値を持ち, i 番目の人の「字の綺麗さ」は a_i, 「顔の面白さ」は b_i である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる.
本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が 1 回トレーニングをすると, この人の「字の綺麗さ」は 1 上がる.
全ての人のトレーニング回数の合計を X 回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.
制約
- N は 1 以上 100 以下の整数
- X は 0 以上 100 以下の整数
- a_i, b_i \ (1 \leq i \leq N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N X a_1 b_1 a_2 b_2 a_3 b_3 : : a_N b_N
出力
写真の好感度の最大値を出力しなさい.
入力例 1
3 1 12 10 24 20 36 5
出力例 1
800
X=1 なので, トレーニングできる回数は 1 回までである. したがって, 次の 4 通りの方法が考えられる.
- 誰もトレーニングしない場合:写真の好感度は 12 \times 10 + 24 \times 20 + 36 \times 5 = 780
- 1 番目の人が 1 回トレーニングする場合:写真の好感度は 13 \times 10 + 24 \times 20 + 36 \times 5 = 790
- 2 番目の人が 1 回トレーニングする場合:写真の好感度は 12 \times 10 + 25 \times 20 + 36 \times 5 = 800
- 3 番目の人が 1 回トレーニングする場合:写真の好感度は 12 \times 10 + 24 \times 20 + 37 \times 5 = 785
よって, 写真の好感度の最大値は 800 である.
入力例 2
3 0 25 20 17 30 9 50
出力例 2
1460
X=0 なので, 誰もトレーニングできない. したがって, 写真の好感度は 25 \times 20 + 17 \times 30 + 9 \times 50 = 1460 となる.
入力例 3
3 3 3 25 5 12 7 25
出力例 3
385
例えば, 1 番目の人が 2 回, 3 番目の人が 1 回トレーニングすると, 写真の好感度 385 が達成できる.
また, 写真の好感度を 385 より大きくすることはできない.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 500 点
問題文
AtCoder 社長の chokudai さんは, CODE FESTIVAL 2018 本戦で参加者に配る直方体のケーキを用意した.
このケーキは, 地面と垂直方向に, 縦に N 分割, 横に N 分割され, 合計 N^2 個のピースに分けられている.
chokudai さんの飼い犬のリチャードは, CODE FESTIVAL 2018 予選に参加したが, ギリギリ通過できなかった.
そこでリチャードは, 本戦で配られるケーキのいくつかのピースにスプレーをかけることで, すべてのピースを食べられなくしようと思った.
あるピースにスプレーがかけられると, このピースとこれに隣り合っているピースすべてが食べられなくなる.
ただし、隣り合っているとは、面で接していることを指すものとする.
リチャードが目標を達成できるようなスプレーのかけ方を 1 つ求めなさい. また, スプレーをかけるのに長く時間を使うと chokudai さんに見つかってしまうので, スプレーをかけるピースの個数を 201 \ 800 個以内にしなければならない.
制約
- N は 1 以上 1 \ 000 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N
出力
1 行目から N 行目までに, それぞれ長さ N の文字列を出力しなさい. ただし, この N \times N の文字列はケーキを上から見た図 (各文字は 1 ピース) に対応しており, そのピースにスプレーをかける場合 X
, かけない場合 .
を出力する. X
の個数は 201 \ 800 個以下でなければならない.
この問題の制約下で, 目標を達成するスプレーのかけ方が必ず存在することが示せる. そのようなスプレーのかけ方が複数存在する場合, そのうちのどれを出力してもよい.
入力例 1
3
出力例 1
X.. ..X X..
入力例 2
6
出力例 2
X.X..X ..X.X. X..X.. .X...X X..X.. .X..X.
入力例 3
21
出力例 3
XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX X....X....X....X....X X.XXXX.XX.XX.X.X.XXXX X.XXXX.XX.XX.X.X....X X.XXXX.XX.XX.X.X.XXXX X....X....X....X....X XXXXXXXXXXXXXXXXXXXXX X....X....XX...X....X X.XXXX.XXXX.XXXXXX.XX X....X....XX..XXXX.XX X.XXXX.XXXXXXX.XXX.XX X.XXXX....X...XXXX.XX XXXXXXXXXXXXXXXXXXXXX XXX.XX.XX.X....X.XXXX XXX.XX.XX.X.XX.X.XXXX XXX.XX.XX.X....X.XXXX XXX.XXX..XX.XX.X.XXXX XXX.XXXX.XX.XX.X....X XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点: 700 点
問題文
CODE FESTIVAL 2018 本戦の参加者は N 人である. これから, 彼らは夕食で寿司を食べる.
それぞれの参加者は 空腹度 という整数の値を持つ. この値は, それぞれの参加者について独立に, 以下のように定まる.
- 確率 \frac{p_1}{q} で空腹度 x_1, 確率 \frac{p_2}{q} で空腹度 x_2, ... , 確率 \frac{p_M}{q} で空腹度 x_M.
あなたは寿司職人である. 厨房に N 枚の皿があり, あなたはそれぞれの皿に寿司を 1 個以上乗せる. 皿に乗せられる寿司の数に制限はなく, 皿ごとに異なる個数の寿司を乗せてもよい.
そして, これら N 枚の皿が参加者たちの座るテーブルに運ばれ, 彼らは皿をそれぞれ 1 枚取る.
空腹度 x の参加者が y 個の寿司の乗った皿を取ると, その参加者の 不満度 は |x - y| となる.
参加者たちは彼ら自身の空腹度を把握しており, 彼らは全員の不満度の合計が最小となるように皿を取る. このときの全員の不満度の合計を 不適合度 と呼ぶ.
あなたは, 不適合度の期待値が最小となるように皿に寿司を乗せたい. このように皿に寿司を乗せたときの不適合度の期待値を求めよ.
制約
- N は 1 以上 2 \ 000 以下の整数
- M は 1 以上 2 \ 000 以下の整数
- 1 \leq x_1 < x_2 < x_3 < ... < x_M \leq 1 \ 000 \ 000.
- p_i \ (1 \leq i \leq M) は, 1 以上 1 \ 000 \ 000 以下の整数
- q は 1 以上 1 \ 000 \ 000 以下の整数
- p_1 + p_2 + p_3 + ... + p_M = q.
入力
入力は以下の形式で標準入力から与えられる.
N M q x_1 p_1 x_2 p_2 x_3 p_3 : : x_M p_M
出力
不適合度の期待値の達成可能な最小値を出力しなさい.
ジャッジの解からの絶対誤差または相対誤差が \pm 0.0001 以内であれば正解とみなされる.
入力例 1
1 3 100 1 30 3 20 9 50
出力例 1
3.6000000000
この場合, 参加者は 1 人であり, 彼の空腹度は確率 30/100 = 0.3 で 1, 確率 20/100 = 0.2 で 3, 確率 50/100 = 0.5 で 9 となる.
1 枚の皿に 6 個の寿司を乗せることを考える. 唯一の参加者がこの皿を取り, 不適合度の期待値, すなわちこの参加者の不満度の期待値は |1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6 となる.
これが達成可能な最小値である.
入力例 2
2 3 10 1 3 3 2 9 5
出力例 2
4.1600000000
この場合, 参加者は 2 人であり, 彼らを A, B と呼ぶことにする. 彼らの空腹度の確率分布はそれぞれ入力例 1 での参加者のそれと同じである. また, 2 枚の皿を皿 1, 皿 2 と呼ぶことにする.
皿 1 に 9 個, 皿 2 に 1 個の寿司を置くことを考える.
例えば, 確率 30/100 × 20/100 で A, B の空腹度がそれぞれ 1, 3 となる。このとき, A が皿 2, B が皿 1 を取ることで二人の不満度の合計が |1-1| + |3-9| = 6 となって最小化されるため, 不適合度は 6 である.
その他の場合についても同様に計算することで, 寿司をこのように置いたときの不適合度の期待値が 4.16 であることがわかる.
これが達成可能な最小値である.
入力例 3
3 2 2 111111 1 999999 1
出力例 3
666665.9999999997
1 枚目の皿に 111 \ 111 個, 2 枚目の皿に 999 \ 999 個, 3 枚目の皿に 555 \ 555 個の寿司を置くと, 不適合度の期待値は 666 \ 666 となり, これが達成可能な最小値である.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点: 800 点
問題文
CODE FESTIVAL 本選で良い成績を取るために, いろはちゃんは 12 年前から毎日修行をしている.
今日は, 「足し引きゲーム」で修行を行うことにした. このゲームは以下のようなものである.
- 電光掲示板に数 G が書かれている. 最初, G = 0 である.
- プレイヤーは以下の操作を 320 回以内行うことができる : 1 以上 N 以下の整数 x を選び, G に 1/x を足す, または G から 1/x を引く. ただし, G を負にしてはならない.
- G を, このゲームにおいて G が取り得る値のうち 0 を除いて最小の値にすると, ゲームクリアである.
いろはちゃんは早くゲームクリアしたい. 彼女を助けるために, ゲームクリアする方法を一つ出力せよ.
制約
- N は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N
出力
出力は, 以下のような形式で行うこと.
Q op_1 x_1 op_2 x_2 op_3 x_3 ... op_Q x_Q
- Q は, あなたが行う操作の回数である. Q の値は, 320 以下でなければならない.
- op_i は, i 回目に行う操作の種類である.
+
のとき「1/{x_i} を足す」,-
のとき「1/{x_i} を引く」という操作を行うことを意味する.
入力例 1
2
出力例 1
3 + 2 + 2 - 2
G が取り得る値のうち 0 以外で最小のものは, 1/2 である.
以下の出力において, G の値は以下のように変化する.
- 最初, G = 0 である.
- 次に, G に 1/2 を足す. G の値は 1/2 に変化する.
- 次に, G に 1/2 を足す. G の値は 1 に変化する.
- 最後に, G から 1/2 を引く. G の値は 1/2 に変化する.
入力例 2
3
出力例 2
3 + 3 + 3 - 2
G が取り得る値のうち 0 以外で最小のものは, 1/6 である.
以下の出力において, G の値は以下のように変化する.
- 最初, G = 0 である.
- 次に, G に 1/3 を足す. G の値は 1/3 に変化する.
- 次に, G に 1/3 を足す. G の値は 2/3 に変化する.
- 最後に, G から 1/2 を引く. G の値は 1/6 に変化する.
入力例 3
4
出力例 3
5 + 3 + 3 - 2 + 4 - 3
G が取り得る値のうち 0 以外で最小のものは, 1/12 である.
以下の出力において, G の値は以下のように変化する.
- 最初, G = 0 である.
- 次に, G に 1/3 を足す. G の値は 1/3 に変化する.
- 次に, G に 1/3 を足す. G の値は 2/3 に変化する.
- 次に, G から 1/2 を引く. G の値は 1/6 に変化する.
- 次に, G に 1/4 を足す. G の値は 5/12 に変化する.
- 最後に, G から 1/3 を引く. G の値は 1/12 に変化する.
入力例 4
7
出力例 4
10 + 1 - 3 - 7 - 7 + 2 - 4 - 7 - 5 - 7 - 7