Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
りんごが 5 個あり、みかんが N 個あります。
整数 N が与えられるので、りんごとみかんを合わせて何個あるかを出力するプログラムを作成してください。
制約
- 1 \leq N \leq 100
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
りんごとみかんを合わせた個数を出力してください。
入力例 1
2
出力例 1
7
このテストケースでは、りんごが 5 個、みかんが 2 個あります。
合計個数は 5+2=7 個です。
入力例 2
4
出力例 2
9
このテストケースでは、りんごが 5 個、みかんが 4 個あります。
合計個数は 5+4=9 個です。
入力例 3
8
出力例 3
13
このテストケースでは、りんごが 5 個、みかんが 8 個あります。
合計個数は 5+8=13 個です。
Source Name
「アルゴリズム×数学」が基礎からしっかり身につく本 2.1.3項Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
3 つの整数 A_1, A_2, A_3 が与えられます。
A_1 + A_2 + A_3 を出力してください。
制約
- 1 \leq A_1, A_2, A_3 \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
A_1 A_2 A_3
出力
答えを出力してください。
入力例 1
10 20 50
出力例 1
80
10+20+50=80 なので、80 と出力すれば正解となります。
入力例 2
1 1 1
出力例 2
3
1+1+1=3 なので、3 と出力すれば正解となります。
入力例 3
100 100 100
出力例 3
300
100+100+100=300 なので、300 と出力すれば正解となります。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数 N と N 個の整数 A_1, A_2, \cdots, A_N が与えられます。（入力の形式は「入力」セクションを参照）
A_1 + A_2 + \cdots + A_N を出力してください。
制約
- 1 \leq N \leq 50
- 1 \leq A_i \leq 100 (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 A_3 \cdots A_N
出力
答えを出力してください。
入力例 1
5 3 1 4 1 5
出力例 1
14
3+1+4+1+5=14 なので、14 と出力すれば正解となります。
入力例 2
3 10 20 50
出力例 2
80
10+20+50=80 なので、80 と出力すれば正解となります。
入力例 3
10 1 2 3 4 5 6 7 8 9 10
出力例 3
55
1+2+3+4+5+6+7+8+9+10=55 なので、55 と出力すれば正解となります。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
3 つの整数 A_1, A_2, A_3 が与えられます。
A_1 A_2 A_3 を出力するプログラムを作成してください。
制約
- 1 \leq A_1, A_2, A_3 \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
A_1 A_2 A_3
出力
答えを出力してください。
入力例 1
2 8 8
出力例 1
128
2 \times 8 \times 8 = 128 なので 128 と出力すれば正解となります。
入力例 2
7 7 25
出力例 2
1225
7 \times 7 \times 25 = 1225 なので 1225 と出力すれば正解となります。
入力例 3
100 100 100
出力例 3
1000000
100 \times 100 \times 100 = 1000000 なので 1000000 と出力すれば正解となります。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の整数 a_1, a_2, \cdots, a_N が与えられます。
(a_1 + a_2 + \cdots + a_N) \bmod 100 の値を出力してください。
制約
- 1 \leq N \leq 50
- 1 \leq a_i \leq 100 (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N a_1 a_2 a_3 \cdots a_N
出力
答えを出力してください。
入力例 1
3 30 50 70
出力例 1
50
30+50+70=150 なので、これを 100 で割った余り 50 を出力すれば正解となります。
入力例 2
10 1 2 3 4 5 6 7 8 9 10
出力例 2
55
1+2+3+4+5+6+7+8+9+10=55 なので、これを 100 で割った余り 55 を出力すれば正解となります。
入力例 3
5 60 60 60 60 60
出力例 3
0
答えが 0 になる場合もあることに注意してください。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数 N が与えられます。2N+3 の値を出力してください。
制約
- 1 \leq N \leq 100
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
100
出力例 1
203
N=100 のとき 2N+3=203 です。
入力例 2
27
出力例 2
57
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 以下の正の整数の中で、X の倍数または Y の倍数であるものの個数はいくつありますか？
制約
- 1 \leq N \leq 10^6
- 1 \leq X < Y \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X Y
出力
答えを出力してください。
入力例 1
15 3 5
出力例 1
7
15 以下の正の整数の中で 3 または 5 の倍数であるものは 3,5,6,9,10,12,15 の 7 個であるため、7 と出力すれば正解です。
入力例 2
1000000 11 13
出力例 2
160839
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
赤・青のカードが各 1 枚ずつあり、あなたはそれぞれのカードに 1 以上 N 以下の整数を 1 つ書き込みます。
カードに書かれた整数の合計が S 以下となる書き方は、いくつありますか？
制約
- 1 \leq N \leq 1000
- 1 \leq S \leq 2000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N S
出力
答えを出力してください。
入力例 1
3 4
出力例 1
6
合計が 4 以下となる書き込み方は、以下の 6 通りです。
- 赤のカードに 1 を書き込み、青のカードに 1 を書き込む
- 赤のカードに 1 を書き込み、青のカードに 2 を書き込む
- 赤のカードに 1 を書き込み、青のカードに 3 を書き込む
- 赤のカードに 2 を書き込み、青のカードに 1 を書き込む
- 赤のカードに 2 を書き込み、青のカードに 2 を書き込む
- 赤のカードに 3 を書き込み、青のカードに 1 を書き込む
入力例 2
869 120
出力例 2
7140
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
注意
この問題は 2.4 節（計算量と全探索）と 3.7 節（動的計画法）両方で扱います。
全探索で解いても 1000 点中 500 点しか得られず、満点（AC）にならないことに注意してください。（本に記されている通り、一部の大きいケースでは現実的な時間で答えが求まらないからです）
問題文
N 枚のカードが横一列に並べられています。左から i 番目 (1 \leq i \leq N) のカードには整数 A_i が書かれています。
カードの中からいくつかを選んで、合計がちょうど S となるようにする方法はありますか。
制約
- 1 \leq N \leq 60
- 1 \leq A_i \leq 10000
- 1 \leq S \leq 10000
- 入力はすべて整数
部分点
- 1 \leq N \leq 20 について解けると、500 点が獲得できます。
入力
入力は以下の形式で標準入力から与えられます。
N S A_1 A_2 A_3 \dots A_N
出力
合計を S となるようにする方法が存在する場合は Yes、そうでない場合は No と出力してください。
入力例 1
3 11 2 5 9
出力例 1
Yes
カード 1, 3 を選べば合計が 11 になるので答えは Yes です。
入力例 2
4 11 3 1 4 5
出力例 2
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N! の値を求めてください。
制約
- 1 \leq N \leq 20
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
5
出力例 1
120
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 以下の素数を、小さい順に出力してください。
制約
- 2 \leq N \leq 3000
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
N 以下の素数を、小さい順に空白区切りで出力してください。最後の改行を忘れないようにしましょう。
入力例 1
10
出力例 1
2 3 5 7
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N が素数であるかどうかを判定してください。
制約
- 2 \leq N \leq 10^{13}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
Nが素数である場合は Yes を、素数でない場合は No を出力してください。
入力例 1
53
出力例 1
Yes
53 は素数です。
よって、Yes と出力すれば正解となります。
入力例 2
77
出力例 2
No
77 は 7 で割り切れるため、素数ではありません。
よって、No と出力すれば正解となります。
入力例 3
472249589291
出力例 3
Yes
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数Nが与えられます。 Nの約数を列挙してください。
制約
- 1 \leq N \leq 10^{13}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
Nの約数を改行区切りで出力してください。 出力する順番は任意ですが、同じ数が 2 回以上出力されてはいけません。
入力例 1
12
出力例 1
1 2 3 4 6 12
12の約数は1、2、3、4、6、12の 6 個あります。
入力例 2
827847039317
出力例 2
909863 1 909859 827847039317
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
自然数 N を素因数分解するプログラムを作成してください。
なお、任意の自然数の素因数分解は一意となることが知られています。
制約
- 2 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
N の素因数を、小さい順に空白区切りで出力してください。
ただし、同じ素因数で N を複数回割ることができる場合は、その素因数は回数分出力してください。
入力例 1
10
出力例 1
2 5
10 = 2 \times 5 です。
入力例 2
36
出力例 2
2 2 3 3
36 = 2 \times 2 \times 3 \times 3 です。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
A と B の最大公約数を求めてください。
制約
- 1 \leq A, B \leq 10^9
- A, B は整数
入力
入力は以下の形式で標準入力から与えられます。
A B
出力
A と B の最大公約数を出力してください。
入力例 1
33 88
出力例 1
11
33 と 88の最大公約数は 11 です。
よって、11 と出力すれば正解となります。
入力例 2
123 777
出力例 2
3
123 と 777 の最大公約数は 3 です。
よって、3 と出力すれば正解となります。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の正の整数 A_1, A_2, \dots, A_N の最大公約数を求めてください。
制約
- 2 \leq N \leq 10^5
- 2 \leq A_i \leq 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
3 12 18 24
出力例 1
6
12, 18, 24 の最大公約数は 6 です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の正の整数 A_1, A_2, \dots, A_N の最小公倍数を求めてください。
制約
- 2 \leq N \leq 10^5
- 2 \leq A_i \leq 10^{18}
- 入力はすべて整数
- 問題の答えは 10^{18} 以下である
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
3 12 18 14
出力例 1
252
12, 18, 14 の最小公倍数は 252 です。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
コンビニには N 個の品物が売られており、i 番目（1 \leq i \leq N）の商品の値段は A_i 円です。 異なる 2 つの品物を買う方法のうち、合計金額が 500 円となるものは何通りありますか。
制約
- 2 \leq N \leq 200000
- A_i は 100,200,300,400 のいずれか
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
5 100 300 400 400 200
出力例 1
3
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 枚のカードがあり、左から i 番目（1 \leq i \leq N）のカードの色は A_i です。 A_i=1 のとき赤色、A_i=2 のとき黄色、A_i=3 のとき青色です。同じ色のカードを 2 枚選ぶ方法は何通りありますか。
制約
- 2 \leq N \leq 500000
- 1 \leq A_i \leq 3
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
6 1 3 2 1 1 2
出力例 1
4
以下の 4 通りの方法があります。
- 左から 1 番目のカードと、左から 4 番目のカードを選ぶ。
- 左から 1 番目のカードと、左から 5 番目のカードを選ぶ。
- 左から 4 番目のカードと、左から 5 番目のカードを選ぶ。
- 左から 3 番目のカードと、左から 6 番目のカードを選ぶ。
Time Limit: 5 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 枚のカードがあり、左から i 番目のカードには整数 A_i が書かれています。
カードを 5 枚選ぶ方法のうち、選んだカードに書かれた整数の和がちょうど 1000 となるものは何通りありますか。
制約
- 5 \leq N \leq 100
- 1 \leq A_i \leq 1000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N
A_1 A_2 … A_{N}
出力
答えを出力してください。
入力例 1
5 100 150 200 250 300
出力例 1
1
左から 1, 2, 3, 4, 5 番目のカードを選ぶと、整数の和はちょうど 1000 になります。
これ以外の選び方は存在しないので、1 と出力すれば正解となります。
入力例 2
13 243 156 104 280 142 286 196 132 128 195 265 300 130
出力例 2
4
整数の和が 1000 となる選び方として、以下の 4 通りがあります。
- 左から 1, 8, 10, 12, 13 番目のカードを選ぶ
- 左から 2, 3, 4, 10, 11 番目のカードを選ぶ
- 左から 2, 6, 9, 12, 13 番目のカードを選ぶ
- 左から 4, 8, 9, 10, 11 番目のカードを選ぶ
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数 n, r が与えられます。{}_n\mathrm{C}_r を出力するプログラムを作成してください。
制約
- 1 \leq r \leq n \leq 20
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
n r
出力
答えを出力してください。
入力例 1
6 2
出力例 1
15
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 枚のカードがあり、左から i 番目のカードには整数 A_i が書かれています。 和が 100000 となる 2 枚のカードの選び方は何通りあるかを求めるプログラムを作成してください。
制約
- 2 \leq N \leq 200000
- 1 \leq A_i \leq 99999
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
6 40000 50000 20000 80000 50000 30000
出力例 1
2
和が 100000 となる選び方として、以下の 2 通りがあります。
- 左から 2 番目のカードと、左から 5 番目のカードを選ぶ。
- 左から 3 番目のカードと、左から 4 番目のカードを選ぶ。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
青・赤 2 つの N 面体サイコロがあります。各サイコロの出目は以下の通りです。
- 青のサイコロ: B_1, B_2, \dots, B_N が等確率で出る
- 赤のサイコロ: R_1, R_2, \dots, R_N が等確率で出る
あなたは 2 つのサイコロを同時に振り、出目の合計だけ賞金がもらえます。もらえる賞金の期待値を計算してください。
制約
- 2 \leq N \leq 100000
- 0 \leq B_i, R_i \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N
B_1 B_2 \dots B_{N}
R_1 R_2 \dots R_{N}
出力
もらえる賞金の期待値を計算してください。 なお、想定解答との絶対誤差または相対誤差が 10^{－6} 以下であれば正解として扱われます。
入力例 1
3 1 2 3 10 20 30
出力例 1
22.000000000000
もらえる賞金の期待値は 22 であり、これを出力すれば正解となります。
なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば、小数点以下何桁出力しても構いません。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
ある国語のテストの問題は N 問からなり、すべて選択式問題です。
i 問目 (1 \leq i \leq N) は P_i 個の選択肢から 1 つの正解を選ぶ形式であり、配点は Q_i 点です。
太郎君はまったく手がかりがつかめなかったので、全部の問題をランダムに回答することにしました。太郎君が得られる点数の期待値を計算してください。
制約
- 1 \leq N \leq 50
- 2 \leq P_i \leq 9
- 1 \leq Q_i \leq 200
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N P_1 Q_1 P_2 Q_2 : P_N Q_N
出力
太郎君が得られる点数の期待値を出力してください。 なお、想定解答との絶対誤差または相対誤差が 10^{－6} 以下であれば正解として扱われます。
入力例 1
2 2 50 4 100
出力例 1
50.000000000000
太郎君が得られる点数の期待値は 50 であり、これを出力すれば正解となります。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
次郎君の夏休みは N 日間あります。 彼は i 日目（1 \leq i \leq N）日目の勉強時間を以下の手順で決めます。
- 1 日の最初にサイコロを振る
- サイコロを振って 1,2 が出た場合: A_i 時間勉強する
- サイコロを振って 3,4,5,6 が出た場合: B_i 時間勉強する
彼の夏休みの合計勉強時間の期待値を求めるプログラムを作成してください。
制約
- 2 \leq N \leq 200000
- 0 \leq A_i, B_i \leq 24
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
答えを出力してください。 なお、想定解答との絶対誤差または相対誤差が 10^{－3} 以下であれば正解として扱われます。
入力例 1
5 3 1 4 1 5 9 2 6 5 3
出力例 1
21.333333333333
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
1 ドル払うと、N 種類のコインのうち 1 つが等確率で出現する機械があります。 全種類のコインを集めるまでに支払う金額の期待値を計算するプログラムを作成してください。
制約
- 2 \leq N \leq 10^6
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。 なお、想定解答との絶対誤差または相対誤差が 10^{－6} 以下であれば正解として扱われます。
入力例 1
5
出力例 1
11.416666666667
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
長さ N の配列 [A_1, A_2, \cdots, A_N] が与えられます。
書籍に記されている「マージソートを行う未完成のプログラム」を元に、配列を昇順に並び替えるプログラムを作成してください。
制約
smallと名前がついているテストケースを正答することで、満点の 50 \% を得ることができます。
smallのテストケースは以下の制約を満たします。
- 2 \leq N \leq 2000
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
さらに以下の制約を満たすテストケースを正答することで、満点を得ることができます。
- 2 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N
A_1 A_2 … A_{N}
出力
与えられた配列を昇順に並び替えて出力してください。
入力例 1
3 3 1 2
出力例 1
1 2 3
入力例 2
10 658 299 47 507 122 969 449 68 513 800
出力例 2
47 68 122 299 449 507 513 658 800 969
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N 個の足場があります。 足場には 1, 2, \ldots, N と番号が振られています。 各 i (1 \leq i \leq N) について、足場 i の高さは h_i です。
最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
- 足場 i にいるとき、足場 i + 1 または i + 2 へジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |h_i - h_j| を支払う。
カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。
制約
- 入力はすべて整数である。
- 2 \leq N \leq 10^5
- 1 \leq h_i \leq 10^4
入力
入力は以下の形式で標準入力から与えられる。
N h_1 h_2 \ldots h_N
出力
カエルが支払うコストの総和の最小値を出力せよ。
入力例 1
4 10 30 40 20
出力例 1
30
足場 1 → 2 → 4 と移動すると、コストの総和は |10 - 30| + |30 - 20| = 30 となります。
入力例 2
2 10 10
出力例 2
0
足場 1 → 2 と移動すると、コストの総和は |10 - 10| = 0 となります。
入力例 3
6 30 10 60 10 60 50
出力例 3
40
足場 1 → 3 → 5 → 6 と移動すると、コストの総和は |30 - 60| + |60 - 60| + |60 - 50| = 40 となります。
Score : 100 points
Problem Statement
There are N stones, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), the height of Stone i is h_i.
There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:
- If the frog is currently on Stone i, jump to Stone i + 1 or Stone i + 2. Here, a cost of |h_i - h_j| is incurred, where j is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone N.
Constraints
- All values in input are integers.
- 2 \leq N \leq 10^5
- 1 \leq h_i \leq 10^4
Input
Input is given from Standard Input in the following format:
N h_1 h_2 \ldots h_N
Output
Print the minimum possible total cost incurred.
Sample Input 1
4 10 30 40 20
Sample Output 1
30
If we follow the path 1 → 2 → 4, the total cost incurred would be |10 - 30| + |30 - 20| = 30.
Sample Input 2
2 10 10
Sample Output 2
0
If we follow the path 1 → 2, the total cost incurred would be |10 - 10| = 0.
Sample Input 3
6 30 10 60 10 60 50
Sample Output 3
40
If we follow the path 1 → 3 → 5 → 6, the total cost incurred would be |30 - 60| + |60 - 60| + |60 - 50| = 40.
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
太郎君は N 段の階段を上ろうとしています。彼は一歩で 1 段か 2 段上ることができます。
0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを計算してください。
制約
- 1 \leq N \leq 45
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
4
出力例 1
5
0 段目から 4 段目まで移動する方法は以下の 5 通りがあります。
- 0 段目 → 1 段目 → 2 段目 → 3 段目 → 4 段目
- 0 段目 → 1 段目 → 2 段目 → 4 段目
- 0 段目 → 1 段目 → 3 段目 → 4 段目
- 0 段目 → 2 段目 → 3 段目 → 4 段目
- 0 段目 → 2 段目 → 4 段目
よって、5 と出力すれば正解となります。
入力例 2
45
出力例 2
1836311903
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N 個の品物があります。 品物には 1, 2, \ldots, N と番号が振られています。 各 i (1 \leq i \leq N) について、品物 i の重さは w_i で、価値は v_i です。
太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 100
- 1 \leq W \leq 10^5
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N W w_1 v_1 w_2 v_2 : w_N v_N
出力
太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。
入力例 1
3 8 3 30 4 50 5 60
出力例 1
90
品物 1, 3 を選べばよいです。 すると、重さの総和は 3 + 5 = 8 となり、価値の総和は 30 + 60 = 90 となります。
入力例 2
5 5 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
出力例 2
5000000000
答えは 32-bit 整数型に収まらない場合があります。
入力例 3
6 15 6 5 5 6 6 4 6 6 3 5 7 2
出力例 3
17
品物 2, 4, 5 を選べばよいです。 すると、重さの総和は 5 + 6 + 3 = 14 となり、価値の総和は 6 + 6 + 5 = 17 となります。
Score : 100 points
Problem Statement
There are N items, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.
Taro has decided to choose some of the N items and carry them home in a knapsack. The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.
Find the maximum possible sum of the values of items that Taro takes home.
Constraints
- All values in input are integers.
- 1 \leq N \leq 100
- 1 \leq W \leq 10^5
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N W w_1 v_1 w_2 v_2 : w_N v_N
Output
Print the maximum possible sum of the values of items that Taro takes home.
Sample Input 1
3 8 3 30 4 50 5 60
Sample Output 1
90
Items 1 and 3 should be taken. Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.
Sample Input 2
5 5 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
Sample Output 2
5000000000
The answer may not fit into a 32-bit integer type.
Sample Input 3
6 15 6 5 5 6 6 4 6 6 3 5 7 2
Sample Output 3
17
Items 2, 4 and 5 should be taken. Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
太郎君の夏休みは N 日間あり、i 日目に勉強すると A_i だけ実力が上がることが知られています。
しかし、彼は 2 日連続で勉強したくありません。太郎君が夏休みの間に実力をどれだけ上げられるか、その最大値を求めるプログラムを作成してください。
制約
- 2 \leq N \leq 500000
- 0 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
5 2 5 3 3 1
出力例 1
8
2 日目、4 日目に勉強すると、実力が 5+3=8 上がります。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
長さ N の配列 A = [A_1, \cdots, A_N] と 1 個の質問（クエリ）が与えられます。 質問の内容は以下の通りです。
- 質問: 要素 X は配列 A の中にありますか？
与えられた質問について、答えを出力するプログラムを作成してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq X \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X
A_1 A_2 … A_{N}
出力
配列 A に要素 X が存在する場合はYesを、存在しない場合はNoを出力してください。
入力例 1
7 3 1 2 3 4 5 6 7
出力例 1
Yes
入力例 2
7 9 1 2 3 4 5 6 7
出力例 2
No
入力例 3
7 1 2 3 4 5 6 7 8
出力例 3
No
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
2 次元平面上に点 A, B, C があります。点 A の座標は (a_x,a_y)、点 B の座標は (b_x,b_y) 、点 C の座標は (c_x,c_y) です。
点 A と線分 BC 上の点の最短距離を求めてください。
制約
- -10^9 \le a_x,a_y,b_x,b_y,c_x,c_y \le 10^9
- 入力はすべて整数
- 点 A,B,C の位置は相異なる
入力
入力は以下の形式で標準入力から与えられます。
a_x a_y b_x b_y c_x c_y
出力
答えを出力してください。なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解と判定されます。
入力例 1
0 5 1 1 3 0
出力例 1
4.123105625618
入力例 2
-40 -30 -50 -10 -20 -20
出力例 2
15.811388300842
入力例 3
1000000000 1000000000 -1000000000 -1000000000 0 -1000000000
出力例 3
2236067977.499789714813
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
2 次元平面上に N 個の点があり、i 番目の点 (1 \leq i \leq N) の座標は (x_i, y_i) です。
最も近い 2 つの点の距離を求めてください。
制約
- 2 \leq N \leq 2000
- 0 \leq x_i, y_i \leq 10^6 (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N x_1 y_1 \vdots x_N y_N
出力
答えを出力してください。正しい値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解とみなされます。
入力例 1
4 0 1 2 0 2 3 3 1
出力例 1
1.4142135623730950488016887242
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
二次元平面上に、以下の 2 つの円があります。
- 1 つ目の円の中心座標は (x_1, y_1)、半径は r_1
- 2 つ目の円の中心座標は (x_2, y_2)、半径は r_2
さて、2 つの円の位置関係は以下の 5 通りのいずれかです。
[1] 一方の円が他方の円を完全に含み、2 つの円は接していない
[2] 一方の円が他方の円を完全に含み、2 つの円は接している
[3] 2 つの円が互いに交差する
[4] 2 つの円の内部に共通部分は存在しないが、2 つの円は接している
[5] 2 つの円の内部に共通部分は存在せず、2 つの円は接していない
与えられた 2 つの円に当てはまる位置関係の番号を出力してください。
制約
- 0 \leq x_1, x_2, y_1, y_2 \leq 10^6
- 1 \leq r_1, r_2 \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
x_1 y_1 r_1 x_2 y_2 r_2
出力
当てはまる位置関係の番号を出力してください。
入力例 1
4 1 2 1 5 3
出力例 1
4
入力例 2
1 1 6 3 3 2
出力例 2
1
入力例 3
6 6 6 6 6 6
出力例 3
2
2 つの円がぴったり一致する場合も、2 番の位置関係とみなします。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
時針と分針の長さがそれぞれ A センチメートル、B センチメートルであるアナログ時計を考えます。
時針と分針それぞれの片方の端点は同じ定点に固定されており、この点を中心としてそれぞれの針は一定の角速度で時計回りに回転します。時針は 12 時間で、分針は 1 時間で 1 周します。
0 時ちょうどに時針と分針は重なっていました。ちょうど H 時 M 分になったとき、2 本の針の固定されていない方の端点は何センチメートル離れているでしょうか。
制約
- 入力はすべて整数
- 1 \leq A, B \leq 1000
- 0 \leq H \leq 11
- 0 \leq M \leq 59
入力
入力は以下の形式で標準入力から与えられる。
A B H M
出力
答えを、単位を除いて出力せよ。正しい値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解とみなされる。
入力例 1
3 4 9 0
出力例 1
5.00000000000000000000
2 本の針は図のようになるので、答えは 5 センチメートルです。
入力例 2
3 4 10 40
出力例 2
4.56425719433005567605
2 本の針は図のようになります。各針は常に一定の角速度で回ることに注意してください。
Score: 300 points
Problem Statement
Consider an analog clock whose hour and minute hands are A and B centimeters long, respectively.
An endpoint of the hour hand and an endpoint of the minute hand are fixed at the same point, around which each hand rotates clockwise at constant angular velocity. It takes the hour and minute hands 12 hours and 1 hour to make one full rotation, respectively.
At 0 o'clock, the two hands overlap each other. H hours and M minutes later, what is the distance in centimeters between the unfixed endpoints of the hands?
Constraints
- All values in input are integers.
- 1 \leq A, B \leq 1000
- 0 \leq H \leq 11
- 0 \leq M \leq 59
Input
Input is given from Standard Input in the following format:
A B H M
Output
Print the answer without units. Your output will be accepted when its absolute or relative error from the correct value is at most 10^{-9}.
Sample Input 1
3 4 9 0
Sample Output 1
5.00000000000000000000
The two hands will be in the positions shown in the figure below, so the answer is 5 centimeters.
Sample Input 2
3 4 10 40
Sample Output 2
4.56425719433005567605
The two hands will be in the positions shown in the figure below. Note that each hand always rotates at constant angular velocity.
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
2 次元平面上に 2 つの線分があります。1 つ目の線分は座標 (x_1, y_1) と 座標 (x_2, y_2) を結んでいます。2 つ目の線分は座標 (x_3, y_3) と 座標 (x_4, y_4) を結んでいます。
この 2 つの線分が交差するならば Yes を、交差しないならば No を出力してください。
ここで、2 つの線分が交差しているとは、両方に共通して含まれる点が存在することを言います。
制約
- 0 \leq x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4 \leq 10^9
- (x_1, y_1) \neq (x_2, y_2)
- (x_3, y_3) \neq (x_4, y_4)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
x_1 y_1 x_2 y_2 x_3 y_3 x_4 y_4
出力
2 つの線分が交差するならば Yes を、交差しないならば No を出力してください。
入力例 1
1 1 2 2 1 2 2 1
出力例 1
Yes
入力例 2
1 2 2 2 1 1 1 3
出力例 2
Yes
入力例 3
100000001 200000000 200000000 200000000 100000000 100000000 100000000 300000000
出力例 3
No
入力例 4
1 1 3 3 2 2 4 4
出力例 4
Yes
入力例 5
4 1 3 2 2 3 1 4
出力例 5
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
遊園地「ALGO-RESORT」では N 日間にわたるイベントが開催され、 i 日目 (1 \leq i \leq N) には A_i 人が来場しました。
以下の合計 Q 個の質問に答えるプログラムを作成してください。
- 1 個目の質問：L_1 日目から R_1 日目までの合計来場者数は？
- 2 個目の質問：L_2 日目から R_2 日目までの合計来場者数は？
- :
- Q 個目の質問：L_Q 日目から R_Q 日目までの合計来場者数は？
制約
- 1 \le N,Q \le 10^5
- 1 \le A_i \le 10000
- 1 \le L_i \le R_i \le N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N Q A_1 A_2 \cdots A_N L_1 R_1 L_2 R_2 : L_Q R_Q
出力
全体で Q 行出力してください。
i 行目 (1 \leq i \leq Q) には、i 個目の質問への答えを整数で出力してください。
入力例 1
10 5 8 6 9 1 2 1 10 100 1000 10000 2 3 1 4 3 9 6 8 1 10
出力例 1
15 24 1123 111 11137
この入力には 5 個の質問が含まれています。
- 1 個目の質問は 2 日目から 3 日目までの合計来場者数を尋ねるもので、これに対する答えは 6+9=15 です。
- 2 個目の質問は 1 日目から 4 日目までの合計来場者数を尋ねるもので、これに対する答えは 8+6+9+1=24 です。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
注意
書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。
書籍内のコードの訂正点
誤:
// 答えの出力
for (int i = 1; i <= N - 1; i++) {
正:
// 答えの出力
for (int i = 2; i <= N; i++) {
問題文
ALGO 国は N 個の区画に分かれており、西から順に 1 から N までの番号が付けられています。
最初はどの区画にも雪が積もっていませんが、これから Q 日間にわたって雪が降り続け、 i 日目 (1 \leq i \leq Q) には区画 L_i, L_{i+1}, \dots, R_i の積雪が X_i \text{cm} 増加することが予想されています。
予想通りに雪が降り終わった後の積雪の大小関係を表す、 N－1 文字の文字列を出力するプログラムを作成してください。i 文字目は以下のようにしてください。
- (区画 i の積雪) > (区画 i + 1 の積雪) の場合：
> - (区画 i の積雪) = (区画 i + 1 の積雪) の場合：
= - (区画 i の積雪) < (区画 i + 1 の積雪) の場合：
<
たとえば積雪が区画 1 から順に [3 \text{cm}, 8 \text{cm}, 5 \text{cm}, 5 \text{cm}, 4 \text{cm}] である場合、 <>=> という出力が正解です。
制約
- 2 \le N \le 10^5
- 1 \le Q \le 10^5
- 1 \le L_i \le R_i \le N
- 1 \le X_i \le 10000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N Q L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_Q R_Q X_Q
出力
問題文中の指示通り出力してください。
入力例 1
5 3 1 2 3 2 5 4 2 4 1
出力例 1
<>=>
このケースでは、積雪は次のように変化します。
- 最初、積雪は区間 1 から順に [0,0,0,0,0] です。
- 1 日目を終え、区間 1 から 2 の積雪が 3 増加しました。積雪は区間 1 から順に [3,3,0,0,0] です。
- 2 日目を終え、区間 2 から 5 の積雪が 4 増加しました。積雪は区間 1 から順に [3,7,4,4,4] です。
- 3 日目を終え、区間 2 から 4 の積雪が 1 増加しました。積雪は区間 1 から順に [3,8,5,5,4] です。
このとき、出力すべき文字列は <>=> となります。
入力例 2
10 10 1 1 1 6 7 28 3 5 4096 6 10 2000 1 10 10000 2 8 2 10 10 2 1 2 8000 6 7 20 6 8 2048
出力例 2
<>====>><
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
ALGO 鉄道の情報線には N 個の駅があり、西から順に 1 から N までの番号が付けられています。駅 i と駅 i+1 (1 \leq i \leq N-1) は双方向につながっており、距離は A_i キロメートルです。
太郎君は、駅 B_1 から出発し、駅 B_2, B_3, \dots, B_{M-1} をその順に経由し、駅 B_M で旅を終える計画を立てました。彼が旅全体で何メートル移動することになるかを求めてください。
制約
- 2 \leq N \leq 200\,000
- 2 \leq M \leq 200\,000
- 1 \leq A_i \leq 10^7 (1 \leq i \leq N-1)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- B_{j} \neq B_{j+1} (1 \leq j \leq M-1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N
A_1 \dots A_{N-1}
M
B_1
\vdots
B_M
出力
彼が旅全体で何メートル移動することになるかを、単位（メートル）を省いて出力してください。
入力例 1
4 8 6 9 6 2 1 3 2 3 4
出力例 1
43
太郎君は駅 2 から出発し、次のように移動します。
- 駅 2 から 駅 1 に行く。このとき移動する距離は 8 メートル。
- 駅 1 から 駅 3 に行く。このとき移動する距離は 14 メートル。
- 駅 3 から 駅 2 に行く。このとき移動する距離は 6 メートル。
- 駅 2 から 駅 3 に行く。このとき移動する距離は 6 メートル。
- 駅 3 から 駅 4 に行く。このとき移動する距離は 9 メートル。
したがって、太郎君の移動距離は合計で 43 メートルです。
Time Limit: 6 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
あるコンビニは時刻 0 に開店し、時刻 T に閉店します。このコンビニには N 人の従業員が働いており、i 番目 (1 \leq i \leq N) の従業員は時刻 L_i に出勤し、時刻 R_i に退勤します。
t = 0, 1, 2, \dots, T-1 それぞれについて、時刻 t+0.5 にコンビニにいる従業員の数を出力するプログラムを作成してください。
制約
- 1 \leq T \leq 500\,000
- 1 \leq N \leq 500\,000
- 0 \leq L_i < R_i \leq T (1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
T N L_1 R_1 \vdots L_N R_N
出力
全体で T 行出力してください。
t + 1 行目 (0 \leq t \leq T-1) には、時刻 t+0.5 にコンビニにいる従業員の数を出力してください。
入力例 1
10 7 0 3 2 4 1 3 0 3 5 6 5 6 5 6
出力例 1
2 3 4 1 0 3 0 0 0 0
このコンビニは時刻 0 に開店し、時刻 10 に閉店します。従業員の出退勤の様子を図に表すと以下のようになります。
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数 X に対し、X の正の約数の個数を f(X) とします。
正整数 N が与えられるので、\sum_{K=1}^N K\times f(K) を求めてください。
制約
- 1 \leq N \leq 10^7
入力
入力は以下の形式で標準入力から与えられる。
N
出力
値 \sum_{K=1}^N K\times f(K) を出力せよ。
入力例 1
4
出力例 1
23
f(1)=1, f(2)=2, f(3)=2, f(4)=3 なので、答えは 1\times 1 + 2\times 2 + 3\times 2 + 4\times 3 =23 となります。
入力例 2
100
出力例 2
26879
入力例 3
10000000
出力例 3
838627288460105
オーバーフローに注意してください。
Score : 400 points
Problem Statement
For a positive integer X, let f(X) be the number of positive divisors of X.
Given a positive integer N, find \sum_{K=1}^N K\times f(K).
Constraints
- 1 \leq N \leq 10^7
Input
Input is given from Standard Input in the following format:
N
Output
Print the value \sum_{K=1}^N K\times f(K).
Sample Input 1
4
Sample Output 1
23
We have f(1)=1, f(2)=2, f(3)=2, and f(4)=3, so the answer is 1\times 1 + 2\times 2 + 3\times 2 + 4\times 3 =23.
Sample Input 2
100
Sample Output 2
26879
Sample Input 3
10000000
Sample Output 3
838627288460105
Watch out for overflows.
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
各頂点に 1,2,\dots,N の番号がついた、 N 頂点 M 辺の無向グラフが与えられます。
i 番目の辺は頂点 A_i と頂点 B_i とを結んでいます。
このグラフ全体が連結であるかどうか判定して以下のように出力してください。
- もしグラフ全体が連結であれば、
The graph is connected.と出力する - そうでなければ、
The graph is not connected.と出力する
制約
- 入力はすべて整数
- 1 \le N \le 10^5
- 0 \le M \le \min(10^5,\frac{N(N-1)}{2})
- 1 \le A_i < B_i \le N
- グラフに多重辺や自己ループは存在しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
問題文中の指示通り出力せよ。
入力例 1
3 2 1 3 2 3
出力例 1
The graph is connected.
与えられたグラフは連結です。
入力例 2
6 6 1 4 2 3 3 4 5 6 1 2 2 4
出力例 2
The graph is not connected.
与えられたグラフは連結ではありません。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 頂点 M 辺の無向グラフが与えられます。各頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。
1 以上 N 以下の全ての整数 k について、以下の問いに答えてください。
頂点 1 から頂点 k まで、辺を何本かたどって移動することを考えるとき、たどるべき辺の本数の最小値を出力せよ。ただし、移動不可能な場合は -1 を出力せよ。
制約
- 入力はすべて整数
- 1 \le N \le 10^5
- 0 \le M \le \min(10^5,\frac{N(N-1)}{2})
- 1 \le A_i < B_i \le N
- グラフに多重辺や自己ループは存在しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
全体で N 行出力してください。
i 行目には、 k=i の場合の答えを出力してください。
入力例 1
3 2 1 3 2 3
出力例 1
0 2 1
- 頂点 1 から頂点 1 には、 0 本の辺を辿って移動可能であるとします。
- 頂点 1 から頂点 2 に移動する際、 1 \rightarrow 3 \rightarrow 2 と移動すると辿る辺の数が最小になります。
- 頂点 1 から頂点 3 に移動する際、 1 \rightarrow 3 と移動すると辿る辺の数が最小になります。
入力例 2
6 6 1 4 2 3 3 4 5 6 1 2 2 4
出力例 2
0 1 2 1 -1 -1
与えられるグラフが連結であるとは限りません。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点：2 点
問題文
N 頂点 M 辺の連結な単純無向グラフが与えられます。グラフの頂点には、それぞれ 1 から N までの番号が振られています。 i 番目の辺は、頂点 a_i と b_i を双方向に結んでいます。
以下の条件を満たす頂点の個数はいくつあるか出力してください。
- 自分自身より頂点番号が小さい隣接頂点がちょうど 1 つ存在する
制約
- 2 \leq N \leq 100000
- N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 100000)
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは単純グラフである
- 与えられるグラフは連結である
- 入力はすべて整数で与えられる
入力
入力は以下の形式で標準入力から与えられます。
N M
a_1 b_1
\vdots
a_{M} b_{M}
出力
条件を満たす頂点の個数を一行に出力してください。
入力例 1
5 5 1 2 1 3 3 2 5 2 4 2
出力例 1
3
条件を満たす頂点は、2, 4, 5 の 3 つです。
- 頂点 2 は、自分自身より頂点番号が小さい隣接頂点として、頂点 1 のみをもつ
- 頂点 4 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ
- 頂点 5 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ
入力例 2
2 1 1 2
出力例 2
1
条件を満たす頂点は 2 のみです。
入力例 3
7 18 7 2 1 6 5 2 1 3 7 6 5 3 5 6 5 4 1 7 2 6 3 4 5 1 4 7 4 6 5 7 3 2 4 2 1 4
出力例 3
0
Source Name
「競プロ典型90問」78日目Time Limit: 2 sec / Memory Limit: 256 MB
問題文
たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
- まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
- 次に、それぞれのマスが通行可能な空きマス(
.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。幅優先探索というのは以下の手法です。
- スタート地点から近い(たどり着くための最短手数が少ない)マスから順番に、たどり着く手数を以下のように確定していく。説明の例として図1の迷路を利用する。
- 最初に、スタート地点は、スタート地点から手数0でたどり着ける(当然)ので、最短手数0で確定させる(図2)。
- 次に、スタート地点の四近傍(上下左右)の空きマスについて、手数1で確定させる(図3)。
- 次に、手数1で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数2で確定させる(図4)。
- 次に、手数2で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数3で確定させる(図5)。
- 次に、手数3で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数4で確定させる(図6)。
- 上記の手順を確定の更新が無くなるまで繰り返すと、スタート地点からたどり着ける全ての空きマスについて最短手数が確定する(図7)。スタートとゴールは必ず空きマスを辿ってたどり着けるという制約があるので、ゴール地点への最短手数も分かる。
さて、この処理をスマートに実装するためには、先入れ先出し(FIFO)のキュー(Queue)というデータ構造を用いると良いことが知られています。もちろん、使わなくても解くことは可能です。今回、よく分からなければ思いついた方法で解くことをおすすめします。先入れ先出しのキューとは以下のような機能を持つデータ構造です。
- 追加(Push): キューの末尾にデータを追加する。
- 取り出し(Pop): キューの先頭のデータを取り出す。
このデータ構造を使うと、先ほどの幅優先探索の説明における「マスの最短手数の確定」のタイミングでその確定マスをキューに追加し、追加操作が終わればPopを行い、取り出したマスの4近傍を調べるということを繰り返せば(つまり先に追加されたものから順番に処理していけば)、簡潔に処理ができることが分かります。
入力
入力は以下の形式で標準入力から与えられる。
R\ C
sy\ sx
gy\ gx
c_{(1,1)}c_{(1,2)}\ …\ c_{(1,C)}
c_{(2,1)}c_{(2,2)}\ …\ c_{(2,C)}
:
c_{(R,1)}c_{(R,2)}\ …\ c_{(R,C)}
- 1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
- 2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R かつ 1≦sx≦C である。
- 3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
- 4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は
.もしくは#のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が.なら、マス (i,j) が空きマスであり、#なら、マス (i,j) が壁マスであることをあらわす。 - 盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c_{(i,j)} は
#である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。
出力
- スタート地点からゴール地点に移動する最小手数を 1 行に出力せよ。最後に改行を忘れないこと。
入力例1
7 8 2 2 4 5 ######## #......# #.###### #..#...# #..##..# ##.....# ########
出力例1
11
問題文中の例です。
入力例2
5 8 2 2 2 4 ######## #.#....# #.###..# #......# ########
出力例2
10
図8のように進めば 10 手でたどり着くことが進むことができます(※Sはスタート、Gはゴールをあらわす)。
入力例3
50 50 2 2 49 49 ################################################## #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# ##################################################
出力例3
94
もはやただの広い空間であり、迷路と呼んで良いのかは分からないがこの問題でこのような盤面も迷路として扱う。兎にも角にも、スタートからゴールへの最短手数は 94 である。
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
頂点数が N、辺の数が M のグラフが与えられます。各頂点には 1 から N までの番号が付けられており、i 番目の辺 (1 \leq i \leq M) は頂点 A_i と頂点 B_i を双方向に結んでいます。
このグラフが二部グラフであれば Yes を、二部グラフでなければ No を出力してください。
制約
- 1 \leq N, M \leq 200\,000
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 B_1 \vdots A_M B_M
出力
与えられたグラフが二部グラフであれば Yes を、二部グラフでなければ No を出力してください。
入力例 1
8 7 1 5 1 6 2 7 3 7 4 6 5 8 6 8
出力例 1
Yes
入力例 2
6 7 1 6 2 6 3 6 2 4 3 5 1 3 1 4
出力例 2
No
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください。
制約
- 2 \leq K \leq 10^5
- K は整数である
入力
入力は以下の形式で標準入力から与えられる。
K
出力
K の倍数の 10 進法での各桁の和としてありうる最小の値を出力せよ。
入力例 1
6
出力例 1
3
12=6×2 が最小値を達成します。
入力例 2
41
出力例 2
5
11111=41×271 が最小値を達成します。
入力例 3
79992
出力例 3
36
Score : 700 points
Problem Statement
Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.
Constraints
- 2 \leq K \leq 10^5
- K is an integer.
Input
Input is given from Standard Input in the following format:
K
Output
Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K.
Sample Input 1
6
Sample Output 1
3
12=6×2 yields the smallest sum.
Sample Input 2
41
Sample Output 2
5
11111=41×271 yields the smallest sum.
Sample Input 3
79992
Sample Output 3
36
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
以下の漸化式で定められるフィボナッチ数列の第 N 項 a_N を 1000000007 (=10^9+7) で割った余りを求めてください。
- a_1 = 1, a_2 = 1
- a_n = a_{n-1} + a_{n-2} (n \geq 3)
制約
- 3 \le N \le 10^7
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを整数で出力してください。
入力例 1
6
出力例 1
8
a=(1,1,2,3,5,8,\dots) です。
N=6 なので、第 6 項 である 8 を出力してください。
入力例 2
8691200
出力例 2
922041576
1000000007 で割った余りを求めることに注意してください。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
a^b を 1000000007 (=10^9+7) で割った余りを計算してください。
制約
- 1 \le a \le 100
- 1 \le b \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
a b
出力
答えを整数として出力してください。
入力例 1
5 23
出力例 1
871631629
5^{23}=11920928955078125 ですが、これを 10^9+7 で割った余りである 871631629 を出力してください。
入力例 2
97 998244353
出力例 2
934801994
b の値は大きくなることがあります。
Source Name
AOJ NTL_ 1 _B - PowerTime Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
無限に大きいマス目があり、各マスは 2 つの整数を用いてマス (a, b) という形で表されます。すべてのマス (a, b) に対して、右隣のマスは (a+1, b) であり、真上のマスは (a, b+1) です。
マス (0, 0) から出発し、上か右に隣り合うマスへの移動を繰り返すことでマス (X, Y) にたどり着く方法は何通りありますか。答えを 1000000007（素数）で割った余りを求めてください。
制約
- 1 \le X,Y \le 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
X Y
出力
答えを出力してください。
入力例 1
1 2
出力例 1
3
(0,0) から (1,2) にたどり着く方法は、以下の 3 通りです。
- (0,0) \rightarrow (0,1) \rightarrow (0,2) \rightarrow (1,2)
- (0,0) \rightarrow (0,1) \rightarrow (1,1) \rightarrow (1,2)
- (0,0) \rightarrow (1,0) \rightarrow (1,1) \rightarrow (1,2)
入力例 2
869 120
出力例 2
445891023
1000000007 (=10^9+7) で割った余りを求めることに注意してください。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
二次元グリッドの原点 (0,0) にチェスのナイトの駒があります。
ナイトの駒はマス (i,j) にあるとき (i+1,j+2) か (i+2, j+1) のどちらかのマスにのみ動かすことができます。
ナイトの駒をマス (X,Y) まで移動させる方法は何通りありますか？
10^9+7 で割った余りを求めてください。
制約
- 1 \leq X \leq 10^6
- 1 \leq Y \leq 10^6
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
ナイトの駒を (0,0) から (X,Y) まで移動させる方法の数を、10^9+7 で割った余りを出力せよ。
入力例 1
3 3
出力例 1
2
(0,0) \to (1,2) \to (3,3) と (0,0) \to (2,1) \to (3,3) の 2 通りが考えられます。
入力例 2
2 2
出力例 2
0
(2,2) にナイトの駒を移動させることはできません。
入力例 3
999999 999999
出力例 3
151840682
方法の数を 10^9+7 で割った余りを出力してください。
Score : 400 points
Problem Statement
There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.
When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).
In how many ways can the knight reach the square (X, Y)?
Find the number of ways modulo 10^9 + 7.
Constraints
- 1 \leq X \leq 10^6
- 1 \leq Y \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X Y
Output
Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.
Sample Input 1
3 3
Sample Output 1
2
There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).
Sample Input 2
2 2
Sample Output 2
0
The knight cannot reach (2,2).
Sample Input 3
999999 999999
Sample Output 3
151840682
Print the number of ways modulo 10^9 + 7.
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
正の整数 N が与えられるので、4^0 + 4^1 + \dots + 4^N を 1\,000\,000\,007 で割った余りを出力してください。
制約
- 1 \leq N \leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
4^0 + 4^1 + \dots + 4^N を 1\,000\,000\,007 で割った余りを出力してください。
入力例 1
3
出力例 1
85
4^0 + 4^1 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85 なので、85 を出力します。
入力例 2
45
出力例 2
414031736
4^0 + 4^1 + \dots + 4^{45} = 1650586719047173699865498965 なので、1650586719047173699865498965 を 1\,000\,000\,007 で割った余り 414031736 を出力します。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
以下の漸化式で定められるフィボナッチ数列の第 N 項 a_N を 10^9 で割った余りを出力してください。
- a_1 = 1, a_2 = 1
- a_n = a_{n-1} + a_{n-2} (n \geq 3)
なお、書籍の問題文中では「下 9 桁」となっていますが、桁のはじめのゼロは取って出力してください。例えば a_N = 1012345678 の場合、012345678 ではなく 12345678 という出力が正解となります。
制約
- 3 \le N \le 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
10
出力例 1
55
フィボナッチ数列は a=(1,1,2,3,5,8,13,21,34,55,\dots) であり、第 10 項は 55 です。
入力例 2
876543210987654321
出力例 2
942619746
10^9 で割った余りを求めることに注意してください。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
以下の漸化式で定められる数列の第 N 項 a_N を 1000000007(=10^9+7) で割った余りを求めてください。
- a_1 = 1, a_2 = 1
- a_n = 2a_{n－1} + a_{n－2} (n \ge 3)
制約
- 3 \le N \le 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
10
出力例 1
1393
a=(1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, ...) であり、第 10 項は 1393 です。
入力例 2
876543210987654321
出力例 2
841102483
10^9+7 で割った余りを求めることに注意してください。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
以下の漸化式で定められる数列の第 N 項 a_N を 1000000007 (=10^9+7) で割った余りを求めてください。
- a_1 = 1, a_2 = 1, a_3 = 2
- a_n = a_{n－1} + a_{n－2} + a_{n-3} (n \ge 4)
なお、このような数列 (a_1, a_2, a_3, \cdots) をトリボナッチ数列といいます。
制約
- 4 \le N \le 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
10
出力例 1
149
a=(1, 1, 2, 4, 7, 13, 24, 44, 81, 149) であり、第 10 項は 149 です。
入力例 2
876543210987654321
出力例 2
639479200
10^9+7 で割った余りを求めることに注意してください。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
K \times N の長方形のマス目を、1 \times 2 または 2 \times 1 の長方形のタイルで完全に敷き詰める方法の数を 1000000007 (=10^9+7) で割った余りを求めてください。ただし、以下の条件を満たす敷き詰め方を正しい敷き詰めであるとします。
- タイルはマス目からはみ出してはならず、また異なるタイル同士が重なってはならない。
- 全てのタイルは、マス目のちょうど 2 マスを完全に覆う。
また、回転や裏返しによって一致する敷き詰め方も、異なるものとして数えます。
制約
- 2 \le K \le 4
- 5 \le N \le 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
K N
出力
答えを出力してください。
部分点
この問題では、初期得点を 0 点として、以下の条件で得点が加算されます。
- K=2 を満たすケース全てに正答した場合、 2 点が加算される。
- K=3 を満たすケース全てに正答した場合、 30 点が加算される。
- K=4 を満たすケース全てに正答した場合、 400 点が加算される。
- 全てのケースに正答した場合、 568 点が加算される。
- これにより、最終的な満点は 1000 点となる。
入力例 1
2 6
出力例 1
13
入力例 2
3 8
出力例 2
153
入力例 3
4 7
出力例 3
781
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
下記のような無限に広がるマス目に、一つのコマが置かれています。あなたはこれから、「駒を上下左右に隣り合うマスに動かすという操作を ちょうど N 回 行わなければなりません。
最初にコマが置かれたマスから右に a 個分動かした後、上に b 個分動かした場所をマス (a,b) とするとき、駒を最終的にマス (X,Y) に移動させることが可能か判定してください。
制約
- 1 \leq N \leq 10^9
- -10^9 \leq X \leq 10^9
- -10^9 \leq Y \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X Y
出力
マス (X,Y) にたどり着けるなら Yes、そうでないならば No を出力してください。
入力例 1
10 2 2
出力例 1
Yes
下図のような経路でコマを動かせば目的を達成できるため、答えは Yes です。
入力例 2
9 3 1
出力例 2
No
どのようにしても目的を達成できないことが証明できるため、答えは No です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
2^N の一の位を求めてください。
制約
- 1 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを出力してください。
入力例 1
10
出力例 1
4
2^{10}=1024 なので、一の位は 4 です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の石があり、プレイヤー 2 人が交互に石を取り合います。
各ターンでは 1 個以上 3 個以下の石を取る必要があり、初めて石を取れなくなった方が負けです。
整数 N が与えられるので、両者が最善を尽くしたとき、どちらが勝つかを求めてください。
制約
- 1 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
先手必勝の場合 First、後手必勝の場合 Second と出力してください。
入力例 1
4
出力例 1
Second
先手が石を 1 個取った場合は後手は 3 個、先手が 2 個取った場合は後手は 2 個、先手が 3 個取った場合は後手は 1 個取れば勝てるため、N=4 の場合は後手必勝です。
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N個の石があります。各ターンでは、今残っている石の数をa個とするとき、1個以上a/2個以下の石を取らなければなりません。また、初めて石を取れなくなったほうが負けです。両者が最善を尽くした時、先手と後手どちらが勝つかを求めるプログラムを作成してください。
制約
- 1 \leq N \leq 10^{18}
ただしsmallと名がつくテストケースについては、追加で以下の制約を満たします。
- 1 \leq N \leq 10^5
入力
入力は以下の形式で標準入力から与えられます。
N
出力
先手が勝つならばFirst、後手が勝つならばSecondと出力してください。
入力例 1
2
出力例 1
First
先手は必ず 1 個の石を取ります。
後手は石をこれ以上取ることができないため、先手が勝ちます。
入力例 2
3
出力例 2
Second
入力例 3
1000000000000000000
出力例 3
First
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
高橋王国には N 個の町があります。町は 1 から N まで番号が振られています。
それぞれの町にはテレポーターが 1 台ずつ設置されています。町 i (1 \leq i \leq N) のテレポーターの転送先は町 A_i です。
高橋王は正の整数 K が好きです。わがままな高橋王は、町 1 から出発してテレポーターをちょうど K 回使うと、どの町に到着するかが知りたいです。
高橋王のために、これを求めるプログラムを作成してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq K \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
町 1 から出発してテレポーターをちょうど K 回使ったとき到着する町の番号を出力せよ。
入力例 1
4 5 3 2 4 1
出力例 1
4
町 1 から出発してテレポーターを 5 回使うと、1 \to 3 \to 4 \to 1 \to 3 \to 4 と移動します。
入力例 2
6 727202214173249351 6 5 2 5 3 2
出力例 2
2
Score: 400 points
Problem Statement
The Kingdom of Takahashi has N towns, numbered 1 through N.
There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.
Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.
Help the king by writing a program that answers this question.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq K \leq 10^{18}
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.
Sample Input 1
4 5 3 2 4 1
Sample Output 1
4
If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.
Sample Input 2
6 727202214173249351 6 5 2 5 3 2
Sample Output 2
2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N \times N のマス目があります。
左上のマスから出発し、上下左右に隣り合うマスに移動することを繰り返しながら出発地点に戻る経路のうち、すべてのマスを（最初と最後を除き）ちょうど一回ずつ 通るものが存在するか、判定してください。
制約
- 2 \leq N \leq 10^{9}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
条件を満たすものが存在するならば Yes、存在しないならば No を出力してください。
入力例 1
2
出力例 1
Yes
上から i 番目、左から j 番目のマスを (i,j) と表す時、以下のように移動すれば条件を満たすため、Yes と出力すれば正解となります。
- (1, 1) \to (1, 2) \to (2, 1) \to (2, 2) \to (1, 1)
入力例 2
3
出力例 2
No
N=3 の場合は条件を満たす経路が存在しないため、No と出力すれば正解となります。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。あなたは数列に対して、以下の操作を ちょうど K 回行います。
- 1 以上 N 以下の整数 x を選び、A_x に +1 または -1 を加算する。
数列の要素を全てゼロにすることができるか、すなわち (A_1,A_2,\dots,A_N) = (0,0,\dots,0) にできるか判定してください。
制約
- 1 \leq N \leq 50
- 1 \leq K \leq 50
- 0 \leq A_i \leq 50
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K A_1 A_2 \cdots A_N
出力
数列の要素を全てゼロにできるならば Yes、そうでないならば No を出力してください。
入力例 1
3 3 2 0 1
出力例 1
Yes
例えば、以下のように操作すると目的を達成できます。よって Yes を出力すると正解です。
- A_1 に -1 を加算する。
- A_3 に -1 を加算する。
- A_1 に -1 を加算する。
入力例 2
5 2 1 0 0 0 0
出力例 2
No
どのようにしても全ての要素を 0 にすることはできません。ここで、ちょうど K 回操作するということに注意してください。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
縦 H マス、横 W マスの盤面があります。 この盤面の左上隅のマスに角行の駒が置かれています。 駒が 0 回以上の好きな回数の移動を繰り返して到達できるマス目は何個あるでしょうか？
ただし、角行の駒は斜めに動くものとします。 より厳密には、駒が上から r_1 番目、左から c_1 番目のマスから上から r_2 番目、左から c_2 番目のマス目に動ける条件は
- r_1 + c_1 = r_2 + c_2
- r_1 - c_1 = r_2 - c_2
のうちちょうど一方が成立することです。たとえば、駒が図の位置にあるとき、一回で移動できる場所は赤くなっているマスです。
制約
- 1 \leq H, W \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
H \ W
出力
駒が到達できるマス目の個数を出力せよ。
入力例 1
4 5
出力例 1
10
下図の水色のマスに到達可能です。
入力例 2
7 3
出力例 2
11
下図の水色のマスに到達可能です。
入力例 3
1000000000 1000000000
出力例 3
500000000000000000
Score : 200 points
Problem Statement
We have a board with H horizontal rows and W vertical columns of squares. There is a bishop at the top-left square on this board. How many squares can this bishop reach by zero or more movements?
Here the bishop can only move diagonally. More formally, the bishop can move from the square at the r_1-th row (from the top) and the c_1-th column (from the left) to the square at the r_2-th row and the c_2-th column if and only if exactly one of the following holds:
- r_1 + c_1 = r_2 + c_2
- r_1 - c_1 = r_2 - c_2
For example, in the following figure, the bishop can move to any of the red squares in one move:
Constraints
- 1 \leq H, W \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H \ W
Output
Print the number of squares the bishop can reach.
Sample Input 1
4 5
Sample Output 1
10
The bishop can reach the cyan squares in the following figure:
Sample Input 2
7 3
Sample Output 2
11
The bishop can reach the cyan squares in the following figure:
Sample Input 3
1000000000 1000000000
Sample Output 3
500000000000000000
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
黒色・白色・灰色のカードが 1 枚ずつあります。
以下の条件のうち一つ以上を満たすように、各カードに 1 以上 N 以下の整数を書き込む方法が何通りあるかを求めてください。
- 黒色と白色のカードに書かれている整数の差の絶対値は K 以上
- 黒色と灰色のカードに書かれている整数の差の絶対値は K 以上
- 灰色と白色のカードに書かれている整数の差の絶対値は K 以上
制約
- 1 \leq N \leq 100000
- 1 \leq K \leq \min(5,N-1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K
出力
答えを出力してください。
入力例 1
3 1
出力例 1
24
例えば、黒色・白色・灰色のカードにそれぞれ 2, 3, 2 を書いた場合、条件のうち一つ以上を満たします。
また、黒色・白色・灰色のカードにそれぞれ 1, 1, 1 を書いた場合、すべての条件を満たしません。
Time Limit: 5 sec / Memory Limit: 1024 MB
配点: 2 点
問題文
H 行 W 列のマス目があります。上から i\ (1 \leq i \leq H) 行目、左から j\ (1 \leq j \leq W) 列目にあるマス (i, j) には、整数 A_{i, j} が書かれています。 すべてのマス (i, j)\ (1 \leq i \leq H, 1 \leq j \leq W) について、以下の値を求めてください。
- マス (i, j) と同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値
制約
- 2 \leq H, W \leq 2000
- 1 \leq A_{i, j} \leq 99
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
出力
マス (i, j) と同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値を B_{i, j} として、以下の形式で出力してください。
B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}
入力例 1
3 3 1 1 1 1 1 1 1 1 1
出力例 1
5 5 5 5 5 5 5 5 5
入力例 2
4 4 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
出力例 2
28 28 25 26 39 33 40 34 38 38 36 31 41 41 39 43
マス (1, 1) と同じ行または同じ列にあるマスに書かれている整数の合計は次の通りです。
- 3+1+4+1+5+5+9=28
入力例 3
2 10 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 95 2 88 41 97
出力例 3
627 629 598 648 592 660 567 653 606 662 623 633 651 618 645 650 689 685 615 676
入力例 4
10 10 83 86 77 65 93 85 86 92 99 71 62 77 90 59 63 76 90 76 72 86 61 68 67 79 82 80 62 73 67 85 79 52 72 58 69 67 93 56 61 92 79 73 71 69 84 87 98 74 65 70 63 76 91 80 56 73 62 70 96 81 55 75 84 77 86 55 96 79 63 57 74 95 82 95 64 67 84 64 93 50 87 58 76 78 88 84 53 51 54 99 82 60 76 68 89 62 76 86 94 89
出力例 4
1479 1471 1546 1500 1518 1488 1551 1466 1502 1546 1414 1394 1447 1420 1462 1411 1461 1396 1443 1445 1388 1376 1443 1373 1416 1380 1462 1372 1421 1419 1345 1367 1413 1369 1404 1368 1406 1364 1402 1387 1416 1417 1485 1429 1460 1419 1472 1417 1469 1480 1410 1392 1443 1396 1466 1411 1486 1399 1416 1447 1397 1372 1429 1378 1415 1408 1431 1369 1428 1450 1419 1393 1472 1401 1478 1437 1484 1425 1439 1498 1366 1390 1438 1378 1414 1380 1475 1398 1438 1409 1425 1442 1492 1442 1467 1456 1506 1417 1452 1473
Source Name
「競プロ典型90問」4日目Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
1 以上 N 以下の整数の中で、V_1, V_2, \dots, V_K のいずれかの倍数であるものの個数を出力するプログラムを作成してください。
制約
- 1 \leq N \leq 10^{12}
- 1 \leq K \leq 10
- 1 \leq V_i \leq 50
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K V_1 V_2 \cdots V_K
出力
答えを出力してください。
入力例 1
100 3 2 3 5
出力例 1
74
入力例 2
100 3 2 4 6
出力例 2
50
入力例 3
10000000000000 10 13 17 19 23 29 31 37 41 43 47
出力例 3
3324865541894
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 a,b,c,d が与えられます。 a \leq x \leq b, c\leq y \leq d を満たす整数 x,y について、x \times y の最大値はいくつですか。
制約
- -10^9 \leq a \leq b \leq 10^9
- -10^9 \leq c \leq d \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d
出力
答えを出力せよ。
入力例 1
1 2 1 1
出力例 1
2
x=1,y=1 のとき x \times y=1、x=2,y=1 のとき x \times y=2 であるため、答えは 2 です。
入力例 2
3 5 -4 -2
出力例 2
-6
答えが負になることもあります。
入力例 3
-1000000000 0 -1000000000 0
出力例 3
1000000000000000000
Score : 200 points
Problem Statement
Given are integers a,b,c and d. If x and y are integers and a \leq x \leq b and c\leq y \leq d hold, what is the maximum possible value of x \times y?
Constraints
- -10^9 \leq a \leq b \leq 10^9
- -10^9 \leq c \leq d \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a b c d
Output
Print the answer.
Sample Input 1
1 2 1 1
Sample Output 1
2
If x = 1 and y = 1 then x \times y = 1. If x = 2 and y = 1 then x \times y = 2. Therefore, the answer is 2.
Sample Input 2
3 5 -4 -2
Sample Output 2
-6
The answer can be negative.
Sample Input 3
-1000000000 0 -1000000000 0
Sample Output 3
1000000000000000000
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
2次元座標上に N 個の点があります。
i(1≦i≦N) 番目の点の座標は (x_i,y_i) です。
長方形の内部に N 点のうち K 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。
制約
- 2≦K≦N≦50
- -10^9≦x_i,y_i≦10^9 (1≦i≦N)
- x_i≠x_j (1≦i<j≦N)
- y_i≠y_j (1≦i<j≦N)
- 入力値はすべて整数である。(21:50 追記)
入力
入力は以下の形式で標準入力から与えられる。
N K
x_1 y_1
:
x_{N} y_{N}
出力
条件を満たす長方形の中で最小面積となるような長方形の面積を出力せよ。
入力例 1
4 4 1 4 3 3 6 2 8 1
出力例 1
21
条件を満たす最小面積となる長方形の 1 つは (1,1),(8,1),(1,4),(8,4) の 4 つの頂点で構成されます。
その面積は (8-1) × (4-1) = 21 であるため、21 と出力します。
入力例 2
4 2 0 0 1 1 2 2 3 3
出力例 2
1
入力例 3
4 3 -1000000000 -1000000000 1000000000 1000000000 -999999999 999999999 999999999 -999999999
出力例 3
3999999996000000001
オーバーフローに注意してください。
Score : 400 points
Problem Statement
We have N points in a two-dimensional plane.
The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).
Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.
Here, points on the sides of the rectangle are considered to be in the interior.
Find the minimum possible area of such a rectangle.
Constraints
- 2 \leq K \leq N \leq 50
- -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)
- x_i≠x_j (1 \leq i<j \leq N)
- y_i≠y_j (1 \leq i<j \leq N)
- All input values are integers. (Added at 21:50 JST)
Input
Input is given from Standard Input in the following format:
N K
x_1 y_1
:
x_{N} y_{N}
Output
Print the minimum possible area of a rectangle that satisfies the condition.
Sample Input 1
4 4 1 4 3 3 6 2 8 1
Sample Output 1
21
One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).
Its area is (8-1) × (4-1) = 21.
Sample Input 2
4 2 0 0 1 1 2 2 3 3
Sample Output 2
1
Sample Input 3
4 3 -1000000000 -1000000000 1000000000 1000000000 -999999999 999999999 999999999 -999999999
Sample Output 3
3999999996000000001
Watch out for integer overflows.
Time Limit: 10 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
正の整数Nと正の整数の組(a_1,b_1,c_1),(a_2,b_2,c_2), ... , (a_N,b_N,c_N)が与えられます。 以下の条件式をすべて満たす実数の組(x,y)の中で、x+yの最大値を求めるプログラムを作成してください。
- a_1 x + b_1 y \leq c_1
- a_2 x + b_2 y \leq c_2
- (中略)
- a_N x + b_N y \leq c_N
制約
- 1 \leq N \leq 500
- 1 \leq a_i,b_i,c_i \leq 10^9
- x+yが最大となるとき、xとyは共に正の実数である
この制約は\mathcal{O}(N^3)時間で解くことを許容する制約です。
入力
入力は以下の形式で標準入力から与えられます。
N a_1 b_1 c_1 a_2 b_2 c_2 . . a_N b_N c_N
出力
x+yの最大値を出力してください。 なお、想定解答との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われます。
入力例 1
2 1 3 3 3 1 3
出力例 1
1.5
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 A, B が与えられます。整数 x, y を A ≤ x < y ≤ B となるように選ぶときの、\gcd(x, y) の最大値を求めてください。
なお、\gcd(x, y) は x と y の最大公約数を表します。
制約
- A, B は整数
- 1 ≤ A < B ≤ 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
2 4
出力例 1
2
A ≤ x < y ≤ B を満たす (x,y) の選び方は (2,3), (2,4), (3,4) の 3 つです。それぞれ最大公約数は 1, 2, 1 であるので、最大値は 2 です。
入力例 2
199999 200000
出力例 2
1
\gcd(199999, 200000) = 1 です。
入力例 3
101 139
出力例 3
34
Score : 300 points
Problem Statement
Given are integers A and B. Find the maximum possible value of \gcd(x, y) when we choose integers x and y so that A ≤ x < y ≤ B.
Here, \gcd(x, y) denotes the greatest common divisor of x and y.
Constraints
- A and B are integers.
- 1 ≤ A < B ≤ 2 \times 10^5
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
2 4
Sample Output 1
2
We have three ways to choose (x, y) such that A ≤ x < y ≤ B: (2,3), (2,4), (3,4), where the greatest common divisors are 1, 2, 1, respectively, so the maximum possible value is 2.
Sample Input 2
199999 200000
Sample Output 2
1
We have \gcd(199999, 200000) = 1.
Sample Input 3
101 139
Sample Output 3
34
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の整数 A_1, A_2, \cdots, A_N から 1 個以上を選ぶ方法は 2^N - 1 通りあります。
これらについて、「選んだ整数の最大値」をすべて足した値はいくつになりますか。答えを 1000000007 で割った余りを出力してください。
制約
- 1 \leq N \leq 300000
- 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
2 3 5
出力例 1
13
\{ 3 \}、\{ 5 \}、\{ 3, 5 \} の 3 通りの選び方があるため、答えは 3+5+5=13 です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の整数 A_1,A_2,\dots,A_N があります。ここで、A_1 < A_2 < \cdots < A_N を満たします。
\displaystyle \sum_{i=1}^{N} \sum_{j=i+1}^{N} (A_j-A_i) の値を計算してください。
制約
- 2 \leq N \leq 200000
- 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N
出力
答えを出力してください。
入力例 1
3 1 3 5
出力例 1
8
(A_2-A_1)+(A_3-A_1)+(A_3-A_2) = 2+4+2 = 8 であるため、8 と出力すれば正解です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
下図のような N 段のピラミッドがあり、最下段には左から順に整数 A_1, A_2, \dots, A_N が書かれています。
下の段から順に、「隣り合った 2 つの数を足した答えを上の段に書く」という操作を行ったとき、一番上に書かれる整数はいくつですか。
答えを 1000000007 (=10^9+7) で割った余りを出力してください。
制約
- 2 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \dots A_N
出力
一番上に書かれる整数を 1000000007 (=10^9+7) で割った余りを出力してください。
入力例 1
5 20 22 25 43 50
出力例 1
480
ピラミッドには以下のように整数が書かれます。よって、480 と出力すれば正解です。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の整数 A_1,\ldots,A_N が与えられます。
1\leq i < j \leq N を満たす全ての i,j の組についての |A_i-A_j| の和を求めてください。
すなわち、\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|} を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- |A_i|\leq 10^8
- A_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 5 1 2
出力例 1
8
|5-1|+|5-2|+|1-2|=8 です。
入力例 2
5 31 41 59 26 53
出力例 2
176
Score : 400 points
Problem Statement
Given are N integers A_1,\ldots,A_N.
Find the sum of |A_i-A_j| over all pairs i,j such that 1\leq i < j \leq N.
In other words, find \displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- |A_i|\leq 10^8
- A_i is an integer.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
3 5 1 2
Sample Output 1
8
We have |5-1|+|5-2|+|1-2|=8.
Sample Input 2
5 31 41 59 26 53
Sample Output 2
176
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
2 次元座標上にN個の点があります。i番目の点の座標は(X_i, Y_i)です。\mathcal{dist} (i, j) をi番目の点とj番目の点の間のマンハッタン距離とするとき、次式の値を求めるプログラムを作成してください。ただし、座標(x_1 , y_1)と座標(x_2,y_2)の間のマンハッタン距離は|x_1 − x_2| + |y_1 − y_2|で定義されます。
\sum_{i=1}^{N} \sum_{j=i+1}^{N} \mathcal{dist} (i,j)
制約
- 2 \leq N \leq 200000
- -10^5 \leq X_i , Y_i \leq 10^5
- X_i,Y_iは整数
入力
入力は以下の形式で標準入力から与えられます。
N X_1 Y_1 X_2 Y_2 : X_N Y_N
出力
式の値を出力してください。
入力例 1
2 1 2 10 20
出力例 1
27
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
注意
書籍の版によっては、書籍内の制約が正しくない場合があります。正誤表を参照してください。
書籍内の制約の訂正点
誤：1 \le A_i < B_i \le M正：1 \le A_i < B_i \le N
問題文
ALGO 家は N 人家族であり、各人には 1 から N までの番号が振られています。あなたは人 1 の年齢が 0 歳であり、その他の人の年齢も 0 以上 120 以下の整数であることを知っています。また、以下の M 個の条件を満たすことが分かっています。
- 人 A_1 と人 B_1 の年齢は 0 歳差または 1 歳差である。
- 人 A_2 と人 B_2 の年齢は 0 歳差または 1 歳差である。
- :
- 人 A_M と人 B_M の年齢は 0 歳差または 1 歳差である。
人 1,2,3,\dots,N の年齢として考えられる最大値を出力してください。
制約
- 2 \leq N \leq 100000
- 1 \leq M \leq 500000
- 1 \leq A_i < B_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 B_1 A_2 B_2 : A_M B_M
出力
N 行出力してください。
i 行目 (1 \leq i \leq N) には、人 i の年齢として考えられる最大値を出力してください。
入力例 1
6 7 1 2 1 3 2 4 2 5 3 4 4 6 5 6
出力例 1
0 1 1 2 2 3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数 N に対して、\{1, 2, ..., N\} を並べ替えた数列 \{P_1, P_2, ..., P_N\} を選びます。
そして、各 i=1,2,...,N について、i を P_i で割った余りを M_i とします。
M_1 + M_2 + \cdots + M_N の最大値を求めてください。
制約
- N は 1 \leq N \leq 10^9 を満たす整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
M_1 + M_2 + \cdots + M_N の最大値を出力せよ。
入力例 1
2
出力例 1
1
\{1, 2\} を並び替えた数列として \{P_1, P_2\} = \{2, 1\} を選ぶと、M_1 + M_2 = 1 + 0 = 1 となります。
入力例 2
13
出力例 2
78
入力例 3
1
出力例 3
0
Score : 400 points
Problem Statement
For an integer N, we will choose a permutation \{P_1, P_2, ..., P_N\} of \{1, 2, ..., N\}.
Then, for each i=1,2,...,N, let M_i be the remainder when i is divided by P_i.
Find the maximum possible value of M_1 + M_2 + \cdots + M_N.
Constraints
- N is an integer satisfying 1 \leq N \leq 10^9.
Input
Input is given from Standard Input in the following format:
N
Output
Print the maximum possible value of M_1 + M_2 + \cdots + M_N.
Sample Input 1
2
Sample Output 1
1
When the permutation \{P_1, P_2\} = \{2, 1\} is chosen, M_1 + M_2 = 1 + 0 = 1.
Sample Input 2
13
Sample Output 2
78
Sample Input 3
1
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数 x_1,x_2,\dots,x_N は以下の条件をすべて満たします。
- x_1=0 である。
- 1 \le i \le M について、|x_{A_i}-x_{B_i}| \le C_i を満たす。
x_N の値として考えられる最大値を求めるプログラムを作成してください。
制約
- 2 \leq N \leq 100000
- 0 \leq M \leq 500000
- 1 \leq A_i < B_i \leq N
- 0 \leq C_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N M A_1 B_1 C_1 A_2 B_2 C_2 : A_M B_M C_M
出力
x_N をいくらでも大きくできる場合は、-1 を出力してください。
そうでない場合は、x_N の最大値を出力してください。
入力例 1
4 4 1 2 3 1 3 4 3 4 1 2 4 10
出力例 1
5
x_1=0,x_2=3,x_3=4,x_4=5 の場合、x_4 は最大値 5 となります。
入力例 2
2 0
出力例 2
-1
x_2 はいくらでも大きくできるため、-1 を出力します。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
1000 円札、5000 円札、10000 円札を使って N 円を支払いたいです。最小何枚で支払うことが出来るか求めてください。
ただし、紙幣はどれも十分にあるものとします。
制約
- 1000 \le N \le 200000
- N は 1000 の倍数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
N 円払うための最小の枚数を出力してください。
入力例 1
29000
出力例 1
7
10000 円札 2 枚、5000 円札 1 枚、1000 円札 4 枚を使うと、7 枚の紙幣で支払うことができます。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
今日は N 本の映画が上映されます。i 番目の映画は時刻 L_i に開始し、時刻 R_i に終了します。
最大いくつの映画を最初から最後まで見ることができますか。
ただし、映画を見終わった直後に次の映画を見始めることはできますが、同時に複数の映画を見ることはできないものとします。
制約
- 1 \le N \le 300000
- 0 \le L_i < R_i \le 86400
- 入力はすべて整数
部分点
- N \leq 2000 を満たすケースで正解すると、500 点が得られます。
入力
入力は以下の形式で標準入力から与えられます。
N L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
最大いくつの映画を最初から最後まで見ることができるか出力してください。
入力例 1
3 123 86399 1 86400 86399 86400
出力例 1
2
以下のようにすると、2 個の映画を最初から最後まで見ることができます。
- まず、映画 1 を時刻 123 から時刻 86399 まで見る。
- 次に、映画 3 を時刻 86399 から時刻 86400 まで見る。
3 個すべての映画を最初から最後まで見る方法はありません。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 3 点
問題文
AGC 街道には N 人の小学生が住んでおり、小学生 i (1 \leq i \leq N) の家は位置 A_i にあります。
また、小学校は N 校建てられており、小学校 j (1 \leq j \leq N) は位置 B_j にあります。
AGC 街道に住む小学生は性格が悪く、どの人同士も険悪な関係になっているため、全員が別の学校に通うようにしたいです。
また、不便さは次のように定義されます。
- 小学生 i にとっての家から学校までの距離を E_i とするとき、不便さは距離の総和、すなわち E_1 + E_2 + ... + E_N である。
- ただし、位置 u から位置 v までの距離は |u-v|
どの生徒も別の学校に通うという条件下における、不便さとして考えられる最小値を求めてください。
制約
- 1 \leq N \leq 100000
- 0 \leq A_i \leq 10^9
- 0 \leq B_j \leq 10^9
- A_1, A_2, \dots, A_N は相異なる
- B_1, B_2, \dots, B_N は相異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
答えを出力してください。
入力例 1
1 869 120
出力例 1
749
小学生 1 の家と小学校 1 の距離は |869 - 120| = 749 です。
この入力では小学生 1 が必ず小学校 1 に通うことになるため、この値が不便さとして考えられる唯一の値であり、最小値です。
入力例 2
6 8 6 9 1 2 0 1 5 7 2 3 9
出力例 2
5
小学生 1,2,3,4,5,6 をそれぞれ小学校 3,2,6,4,5,1 に通わせることにすると、不便さは |8-7|+|6-5|+|9-9|+|1-2|+|2-3|+|0-1|=5 となります。
これ以上不便さを小さくすることはできないため、答えは 5 です。
入力例 3
10 31 41 59 26 53 58 97 93 23 84 17 32 5 8 7 56 88 77 29 35
出力例 3
211
入力例 4
20 804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735 35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041
出力例 4
2736647674
Source Name
「競プロ典型90問」14日目Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
\sqrt{a} + \sqrt{b} < \sqrt{c} ですか？
制約
- 1 \leq a, b, c \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
a \ b \ c
出力
\sqrt{a} + \sqrt{b} < \sqrt{c} ならば Yes、そうでないならば No と出力せよ。
入力例 1
2 3 9
出力例 1
No
\sqrt{2} + \sqrt{3} < \sqrt{9} ではありません。
入力例 2
2 3 10
出力例 2
Yes
\sqrt{2} + \sqrt{3} < \sqrt{10} です。
Score : 300 points
Problem Statement
Does \sqrt{a} + \sqrt{b} < \sqrt{c} hold?
Constraints
- 1 \leq a, b, c \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
a \ b \ c
Output
If \sqrt{a} + \sqrt{b} < \sqrt{c}, print Yes; otherwise, print No.
Sample Input 1
2 3 9
Sample Output 1
No
\sqrt{2} + \sqrt{3} < \sqrt{9} does not hold.
Sample Input 2
2 3 10
Sample Output 2
Yes
\sqrt{2} + \sqrt{3} < \sqrt{10} holds.
Time Limit: 5 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
1 以上 N 以下の整数の組 (a,b,c,d) であって、以下の条件両方を満たすものが存在するか、判定してください。
- a + b + c + d = X
- abcd = Y
制約
- 1 \le N \le 300
- 1 \le X \le 10^9
- 1 \le Y \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X Y
出力
条件を満たす整数の組 (a,b,c,d) が存在するなら Yes、そうでないならば No を出力してください。
入力例 1
6 11 30
出力例 1
Yes
例えば、(a, b, c, d) = (3, 2, 5, 1) が条件を満たします。
入力例 2
1 1000000000 1
出力例 2
No
条件を満たす整数の組 (a, b, c, d) は存在しません。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
長さ N の (,) からなるカッコ列 S が与えられるので、S が正しいカッコ列であるかどうかを判定してください。
ただし、正しいカッコ列とは次のうちいずれかの条件を満たすものを指します。
- 空文字列
- 空文字列でない正しいカッコ列 A,B が存在し、A, B をこの順に連結した文字列
- ある正しいカッコ列 A が存在し、
(,A,)をこの順に連結した文字列
たとえば、(()())() は正しいカッコ列ですが、))()(( は正しいカッコ列ではありません。
制約
- N は 1 以上 500000 以下の整数
- S は
(と)からなる N 文字の文字列
入力
入力は以下の形式で標準入力から与えられます。
N S
出力
S が正しいカッコ列ならば Yes 、そうでないならば No を出力してください。
入力例 1
8 (()())()
出力例 1
Yes
入力例 2
6 ))()((
出力例 2
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数 N が与えられます。
\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} ij
を 1000000007 (=10^9+7) で割った余りを求めてください。
制約
- 1 \le N \le 10^9
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
求めた値を 1000000007 (=10^9+7) で割った余りを出力してください。
入力例 1
2
出力例 1
9
(1 \times 1 )+(1 \times 2)+(2 \times 1)+(2 \times 2)=1+2+2+4=9 なので、9 と出力すれば正解です。
入力例 2
869120
出力例 2
497335961
1000000007 (=10^9+7) で割った余りを出力してください。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
3 つの正整数 A, B, C が与えられます。
\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc
を 998244353 で割った余りを求めてください。
制約
- 1 \leq A, B, C \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
求めた値を 998244353 で割った余りを出力せよ。
入力例 1
1 2 3
出力例 1
18
(1 \times 1 \times 1) + (1 \times 1 \times 2) + (1 \times 1 \times 3) + (1 \times 2 \times 1) + (1 \times 2 \times 2) + (1 \times 2 \times 3) = 1 + 2 + 3 + 2 + 4 + 6 = 18 となります。
入力例 2
1000000000 987654321 123456789
出力例 2
951633476
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given are three positive integers A, B, and C. Compute the following value modulo 998244353:
\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc
Constraints
- 1 \leq A, B, C \leq 10^9
Input
Input is given from standard input in the following format:
A B C
Output
Print the value modulo 998244353.
Sample Input 1
1 2 3
Sample Output 1
18
We have: (1 \times 1 \times 1) + (1 \times 1 \times 2) + (1 \times 1 \times 3) + (1 \times 2 \times 1) + (1 \times 2 \times 2) + (1 \times 2 \times 3) = 1 + 2 + 3 + 2 + 4 + 6 = 18.
Sample Input 2
1000000000 987654321 123456789
Sample Output 2
951633476
Be sure to compute the value modulo 998244353.
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
\log_2 a < b \log_2 c かどうか判定してください。
なお、この問題は 競プロ典型 90 問 020 - Log Inequality と同一のものですが、制約が変更されています。
制約
- 1 \leq a \leq 10^{18}
- 1 \leq b \leq 10^{18}
- 1 \leq c \leq 10^{18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
a b c
出力
\log_2 a < b \log_2 c であれば Yes、そうでなければ No と出力してください。
入力例 1
4 3 2
出力例 1
Yes
\log_2 4 = 2 である一方、3 \log_2 2 = 3 であるため、Yes と出力すれば正解となります。
入力例 2
16 3 2
出力例 2
No
\log_2 16 = 4 である一方、3 \log_2 2 = 3 であるため、No と出力すれば正解となります。
入力例 3
8 3 2
出力例 3
No
\log_2 a = b \log_2 c の場合も No と出力することに注意してください。
入力例 4
1000000000000000000 1000000000000000000 1000000000000000000
出力例 4
Yes
非常に大きい値が入力される場合があることに注意してください。
入力例 5
869120 5 15
出力例 5
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
関数 f(x) を次のように定義します。
- f(x)=(x の各位の数字の積)
例えば f(777)=343、f(8691)=432、f(869120)=0 です。
整数 N と B が与えられるので、 1 以上 N 以下の整数 m の中で m-f(m) = B となるものの個数を求めてください。
制約
- 1 \leq N \lt 10^{11}
- 1 \leq B \lt 10^{11}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N B
出力
答えを出力してください。
入力例 1
999 434
出力例 1
2
m=574 と m=777 の 2 つが条件を満たします。
入力例 2
255 15
出力例 2
2
入力例 3
9999999999 1
出力例 3
0
Source Name
「競プロ典型90問」25日目Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
整数の組 (a, b, c) であって、以下の条件をすべて満たすものの個数を求めてください。
- 1 \leq a < b < c \leq N
- a + b + c = X
制約
- 3 \leq N \leq 100
- 0 \leq X \leq 300
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X
出力
答えを整数で出力してください。
入力例 1
5 9
出力例 1
2
(a, b, c) = (1, 3, 5), (2, 3, 4) の 2 通りがあります。
入力例 2
8 16
出力例 2
5
(a, b, c) = (1, 7, 8), (2, 6, 8), (3, 5, 8), (3, 6, 7), (4, 5, 7) の 5 通りがあります。
入力例 3
3 20
出力例 3
0
条件を満たす (a, b, c) が存在しないケースもあることに注意してください。
入力例 4
29 47
出力例 4
97
入力例 5
100 160
出力例 5
1213
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
縦の長さと横の長さが整数である面積 N の長方形について、周の長さの最小値を求めてください。
制約
- 1 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
答えを整数で出力してください。
入力例 1
10
出力例 1
14
面積が 10 の長方形として、以下の 4 つが考えられます。
- 縦の長さが 1、横の長さが 10 の長方形（周の長さは 22）
- 縦の長さが 2、横の長さが 5 の長方形（周の長さは 14）
- 縦の長さが 5、横の長さが 2 の長方形（周の長さは 14）
- 縦の長さが 10、横の長さが 1 の長方形（周の長さは 22）
周の長さの最小値は 14 であるため、14 と出力すれば正解となります。
入力例 2
9
出力例 2
12
面積が 9 の長方形として、以下の 3 つが考えられます。
- 縦の長さが 1、横の長さが 9 の長方形（周の長さは 20）
- 縦の長さが 3、横の長さが 3 の長方形（周の長さは 12）
- 縦の長さが 9、横の長さが 1 の長方形（周の長さは 20）
周の長さの最小値は 12 であるため、12 と出力すれば正解となります。
入力例 3
160
出力例 3
52
周の長さが最小となる長方形として、10 \times 16（周の長さは 52）などが考えられます。
入力例 4
869120
出力例 4
3732
周の長さが最小となる長方形として、896 \times 970（周の長さは 3732）などが考えられます。
入力例 5
2147483647
出力例 5
4294967296
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 3 点
問題文
正整数 A, B が与えられます。A と B の最小公倍数を求めてください。ただし、答えが 10^{18} を超える場合は Large と出力してください。
制約
- 1 \leq A, B \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
A B
出力
A と B の最小公倍数を出力してください。答えが 10^{18} を超える場合は代わりに Large と出力してください。
入力例 1
4 6
出力例 1
12
4 と 6 の最小公倍数は 12 です。
答えが 10^{18} を超えないので、12 を出力してください。
入力例 2
1000000000000000000 3
出力例 2
Large
10^{18} と 3 の最小公倍数は 3 \times 10^{18} です。
答えが 10^{18} を超えるので、Large と出力してください。
入力例 3
1000000000000000000 1
出力例 3
1000000000000000000
答えがちょうど 10^{18} の場合、そのまま出力することに注意してください。
Source Name
「競プロ典型90問」38日目Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の値の分からない整数列 A があります。
長さ N-1 の整数列 B が与えられます。このとき、
B_i \geq \max(A_i, A_{i+1})
が成立することが分かっています。
A の要素の総和として考えられる値の最大値を求めてください。
制約
- 入力は全て整数
- 2 ≤ N ≤ 100
- 0 \leq B_i \leq 10^5
入力
入力は以下の形式で標準入力から与えられる。
N
B_1 B_2 ... B_{N-1}
出力
A の要素の総和として考えられる値の最大値を出力せよ。
入力例 1
3 2 5
出力例 1
9
A として、例えば A = ( 2 , 1 , 5 )や、 A = ( -1 , -2 , -3 ), A = ( 2 , 2 , 5 ) 等が考えられます。これらのうち A の要素の総和が最大となるものは、 A = ( 2 , 2 , 5 ) です。
入力例 2
2 3
出力例 2
6
入力例 3
6 0 153 10 10 23
出力例 3
53
Score : 300 points
Problem Statement
There is an integer sequence A of length N whose values are unknown.
Given is an integer sequence B of length N-1 which is known to satisfy the following:
B_i \geq \max(A_i, A_{i+1})
Find the maximum possible sum of the elements of A.
Constraints
- All values in input are integers.
- 2 \leq N \leq 100
- 0 \leq B_i \leq 10^5
Input
Input is given from Standard Input in the following format:
N
B_1 B_2 ... B_{N-1}
Output
Print the maximum possible sum of the elements of A.
Sample Input 1
3 2 5
Sample Output 1
9
A can be, for example, ( 2 , 1 , 5 ), ( -1 , -2 , -3 ), or ( 2 , 2 , 5 ). Among those candidates, A = ( 2 , 2 , 5 ) has the maximum possible sum.
Sample Input 2
2 3
Sample Output 2
6
Sample Input 3
6 0 153 10 10 23
Sample Output 3
53
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 2 点
問題文
ABC 大学には N 人の一年生が在籍しています。クラスは 2 つあり、学籍番号 i 番の生徒のクラスは C_i 組です。今日は期末試験が返却され、学籍番号 i 番の生徒の点数は P_i 点でした。
以下の形式の質問が Q 個与えられます。j = 1, 2, \dots, Q それぞれについて答えてください。
- 学籍番号 L_j \sim R_j 番の 1 組生徒における、期末試験点数の合計
- 学籍番号 L_j \sim R_j 番の 2 組生徒における、期末試験点数の合計
- これら 2 つの値をそれぞれ求めよ。
制約
- 1 \leq N \leq 100000
- 1 \leq C_i \leq 2
- 0 \leq P_i \leq 100
- 1 \leq Q \leq 100000
- 1 \leq L_j \leq R_j \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N C_1 P_1 C_2 P_2 \vdots C_N P_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
学籍番号 L_j \sim R_j 番の 1 組生徒における期末試験点数の合計を A_j、学籍番号 L_j \sim R_j 番の 2 組生徒における期末試験点数の合計を B_j として、以下の形式で出力してください。
A_1 B_1 A_2 B_2 \vdots A_Q B_Q
入力例 1
7 1 72 2 78 2 94 1 23 2 89 1 40 1 75 1 2 6
出力例 1
63 261
学籍番号 2 \sim 6 番の 1 組生徒における、期末試験合計点は 23+40=63 です。
また、学籍番号 2 \sim 6 番の 2 組生徒における、期末試験合計点は 78+94+89=261 です。
入力例 2
7 1 72 2 78 2 94 1 23 2 89 1 40 1 75 10 1 3 2 4 3 5 4 6 5 7 1 5 2 6 3 7 1 6 2 7
出力例 2
72 172 23 172 23 183 63 89 115 89 95 261 63 261 138 183 135 261 138 261
入力例 3
1 1 100 3 1 1 1 1 1 1
出力例 3
100 0 100 0 100 0
一方の組の生徒が存在しないケースもあります。
入力例 4
20 2 90 1 67 2 9 2 17 2 85 2 43 2 11 1 32 2 16 1 19 2 65 1 14 1 51 2 94 1 4 1 55 2 90 1 89 1 35 2 81 20 3 17 5 5 11 11 8 10 3 13 2 6 3 7 3 5 12 18 4 8 3 16 6 8 3 20 1 12 1 6 5 16 3 10 17 19 4 4 7 15
出力例 4
175 430 0 85 0 65 51 16 116 246 67 154 0 165 0 111 213 184 32 156 175 340 32 54 299 511 132 336 67 244 175 314 51 181 124 90 0 17 120 186
Source Name
「競プロ典型90問」10日目Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は料理 1 から N の N 品の料理を作ろうとしています。
料理 i はオーブンを連続した T_i 分間使うことで作れます。1 つのオーブンを 2 つ以上の料理のために同時に使うことはできません。
2 つのオーブンを使えるとき、N 品の料理を全て作るまでに最短で何分かかりますか？ なお、オーブンを使う時間以外は無視できるものとします。
制約
- 1 \leq N \leq 100
- 1 \leq T_i \leq 10^3
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N T_1 \ldots T_N
出力
答えを出力せよ。
入力例 1
5 8 3 7 2 5
出力例 1
13
例えば 2 つのオーブンを次のように使うことで、13 分で全ての料理を作ることができます。
- 1 つ目のオーブン：料理 5,1 を順に作る。
- 2 つ目のオーブン：料理 2,4,3 を順に作る。
入力例 2
2 1000 1
出力例 2
1000
入力例 3
9 3 14 15 9 26 5 35 89 79
出力例 3
138
Score : 400 points
Problem Statement
Takahashi is going to cook N dishes called Dish 1 through N.
Dish i can be cooked by using an oven for T_i consecutive minutes. An oven cannot be used for two or more dishes simultaneously.
If Takahashi has two ovens to use, what is the shortest number of minutes needed to cook all the N dishes? Assume that all processes other than using ovens take negligible time.
Constraints
- 1 \leq N \leq 100
- 1 \leq T_i \leq 10^3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N T_1 \ldots T_N
Output
Print the answer.
Sample Input 1
5 8 3 7 2 5
Sample Output 1
13
We can, for example, use the two ovens as follows to cook all the dishes in 13 minutes.
- The first oven: Cook Dishes 5 and 1 in this order.
- The second oven: Cook Dishes 2, 4, and 3 in this order.
Sample Input 2
2 1000 1
Sample Output 2
1000
Sample Input 3
9 3 14 15 9 26 5 35 89 79
Sample Output 3
138
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
L 以上 R 以下の素数の個数はいくつですか。
ただし、1 は素数ではない ものとします。
制約
- 1 \leq L \leq R \leq 10^{12}
- R - L \leq 500000
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
L R
出力
答えを整数で出力してください。
入力例 1
21 40
出力例 1
4
21 以上 40 以下の素数は、23、29、31、37 の 4 個です。
入力例 2
101 130
出力例 2
6
101 以上 130 以下の素数は、101、103、107、109、113、127 の 6 個です。
入力例 3
1 100
出力例 3
25
1 以上 100 以下の素数は、全部で 25 個あります。
入力例 4
217 217
出力例 4
0
217 は素数ではありません。
入力例 5
999999500000 1000000000000
出力例 5
18228
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
N 個の点 P_1, P_2, \dots, P_N を頂点とする多角形があります。点 P_i の座標は (X_i, Y_i) であり、P_i と P_{i+1} を結ぶ線分 (i = 1, 2, \dots, N-1) は多角形の辺です。また、P_N と P_1 を結ぶ線分も多角形の辺です。
座標 (A, B) が多角形の内部に含まれているかどうかを判定するプログラムを作成してください。
制約
- 3 \leq N \leq 100000
- -10^9 \leqq X_i \leqq 10^9
- -10^9 \leqq Y_i \leqq 10^9
- -10^9 \leqq A \leqq 10^9
- -10^9 \leqq B \leqq 10^9
- 点 (A, B) は多角形の辺上にはない
- 多角形の内角がちょうど 180^{\circ} になることはない
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N A B
出力
座標 (A, B) が多角形の内部に含まれるなら INSIDE、外部に含まれるなら OUTSIDE と出力してください。
部分点
この問題では、多角形が凸多角形であるケースにすべて正解すれば、部分点として 500 点を獲得します。
入力例 1
4 0 0 3 1 2 3 0 3 2 1
出力例 1
INSIDE
多角形は以下の図のようになり、座標 (2, 1) の点はその内部に含まれます。
入力例 2
4 3 1 0 0 0 3 2 3 3 2
出力例 2
OUTSIDE
多角形は以下の図のようになり、座標 (3, 2) の点はその外部にあります。
入力例 3
6 5 5 -1 -3 5 1 -3 -5 1 1 -5 -3 0 -1
出力例 3
INSIDE
多角形は以下の図のようになり、座標 (0, -1) の点はその内部に含まれます。
入力例 4
16 0 0 8 0 8 7 7 7 7 1 1 1 1 6 5 6 5 3 3 3 3 5 2 5 2 2 6 2 6 7 0 7 4 4
出力例 4
OUTSIDE
多角形は以下の図のようになり、座標 (4, 4) の点はその外部にあります。
入力例 5
3 0 0 1000000000 671903261 671903261 1000000000 520908341 350000013
出力例 5
OUTSIDE
この入力例では、点と多角形は非常に近く、距離 10^{-9} 程度しか離れていませんが、点は多角形の外部にあります。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点：5 点
問題文
N 頂点の木が与えられます。木の頂点にはそれぞれ 1 から N までの番号が振られています。
i 番目の辺は、頂点 a_i と頂点 b_i を双方向に結んでおり、長さは全て 1 です。
- {\displaystyle\sum_{u = 1}^{N - 1} \sum_{v = u + 1}^{N} \operatorname{dist}(u, v)}
の値を求めてください。
ただし、\operatorname{dist}(u,v) は、頂点 u から 頂点 v までの最短距離とします。
制約
- 2 \leq N \leq 100000
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは木である
- 入力は全て整数で与えられる
入力
入力は以下の形式で標準入力から与えられます。
N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
出力
答えを 1 行に出力してください。
入力例 1
2 1 2
出力例 1
1
\operatorname{dist}(1, 2) = 1 であるので、答えは 1 です。
入力例 2
4 1 2 1 3 1 4
出力例 2
9
- \operatorname{dist}(1, 2) = 1
- \operatorname{dist}(1, 3) = 1
- \operatorname{dist}(1, 4) = 1
- \operatorname{dist}(2, 3) = 2
- \operatorname{dist}(2, 4) = 2
- \operatorname{dist}(3, 4) = 2
であるので、これらを足し合わせた 9 が答えになります。
入力例 3
12 1 2 3 1 4 2 2 5 3 6 3 7 8 4 4 9 10 5 11 7 7 12
出力例 3
211
Source Name
「競プロ典型90問」39日目Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
i = 1, 2, \dots, Q に対して、以下の問題を解いてください。
試験管に 3 種類の物質 A, B, C がそれぞれ a, b, c グラム入っているとき、次の 1 秒間で以下のような変化が起こります。
- 物質 A のうち aX_i グラムが物質 C に変化する
- 物質 B のうち bY_i グラムが物質 A に変化する
- 物質 C のうち cZ_i グラムが物質 B に変化する
すなわち、1 秒後の物質 A, B, C の量は、それぞれ a(1-X_i) + bY_i, b(1-Y_i) + cZ_i, c(1-Z_i) + aX_i グラムになります。
最初、試験管に物質 A, B, C が 1 グラムずつ入っています。T_i 秒後の物質 A, B, C の量がそれぞれ何グラムになるかを求めるプログラムを作成してください。
制約
- 1 \leqq Q \leqq 10^4
- 0 \leqq X_i, Y_i, Z_i \leqq 1
- 1 \leqq T_i \leqq 10^7
- X, Y, Z は実数で、最大で小数点以下 7 桁まで与えられる
- T は整数
入力
入力は以下の形式で標準入力から与えられます。
Q X_1 Y_1 Z_1 T_1 X_2 Y_2 Z_2 T_2 \vdots X_Q Y_Q Z_Q T_Q
出力
i \ (1 \leqq i \leqq Q) 番目の問題における、T_i 秒後の物質 A, B, C の量を a'_i, b'_i, c'_i とするとき、次の形式で出力してください。
a'_1 b'_1 c'_1 a'_2 b'_2 c'_2 \vdots a'_Q b'_Q c'_Q
ただし、正解との絶対誤差が 10^{-7} 以下であるような答えを出力すれば、正答とみなされます。
入力例 1
5 0.10 0.20 0.30 2 0.02 0.03 0.01 3 0.50 0.00 0.00 16 0.20 0.70 0.60 12345 1.00 1.00 1.00 10000000
出力例 1
1.210000000000000 1.120000000000000 0.670000000000000 1.027637000000000 0.942080000000000 1.030283000000000 0.000015258789062 1.000000000000000 1.999984741210938 1.852941176470589 0.529411764705882 0.617647058823530 1.000000000000000 1.000000000000000 1.000000000000000
まず、1 番目の問題 (X = 0.1, Y = 0.2, Z = 0.3, T = 2) では、次のように物質の量が変化していきます。
- 最初、物質 A, B, C の量はそれぞれ 1, 1, 1 グラム
- 1 秒後、物質 A, B, C の量はそれぞれ 1.1, 1.1, 0.8 グラムになる
- 2 秒後、物質 A, B, C の量はそれぞれ 1.21, 1.12, 0.67 グラムになる
次に、2 番目の問題 (X = 0.01, Y = 0.02, Z = 0.03, T = 3) では、次のように物質の量が変化していきます。
- 最初、物質 A, B, C の量はそれぞれ 1, 1, 1 グラム
- 1 秒後、物質 A, B, C の量はそれぞれ 1.01, 0.98, 1.01 グラムになる
- 2 秒後、物質 A, B, C の量はそれぞれ 1.0192, 0.9607, 1.0201 グラムになる
- 3 秒後、物質 A, B, C の量はそれぞれ 1.027637, 0.942080, 1.030283 グラムになる
残りの 3, 4, 5 番目の問題についても答えれば、正解となります。ただし、3 番目の物質 A の量を 1.525879e-5 といった指数形式で出力しないようにしてください。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 6 点
問題文
1 から N までの整数が書かれた、N 個のボールがあります。 k = 1, 2, 3, ..., N それぞれについて、以下の質問に答えてください。
- これら N 個のボールから 1 個以上のボールを選ぶ方法は 2^N-1 通り存在するが、その中で次の条件を満たす選び方は何通りあるか。
- どの選んだ 2 つのボールについても、書かれている整数の差が k 以上である。
- ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力すること。
制約
- 1 \leq N \leq 10^5
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
出力は N 行からなります。
i\ (1\leq i \leq N) 行目には、k = i のときの答えを 10^9+7 で割った余りを出力してください。
入力例 1
1
出力例 1
1
ボール 1 を選ぶ 1 通りのみが存在します。
入力例 2
2
出力例 2
3 2
k=1 のとき、選んだボールの集合として、\{1\}、\{2\}、\{1,2\} の 3 通りが存在します。
k=2 のとき、\{1\}、\{2\} の 2 通りが存在します。
入力例 3
3
出力例 3
7 4 3
入力例 4
4
出力例 4
15 7 5 4
入力例 5
7
出力例 5
127 33 18 13 10 8 7
入力例 6
20
出力例 6
1048575 17710 2744 906 430 250 167 118 90 75 65 56 48 41 35 30 26 23 21 20
入力例 7
50
出力例 7
898961330 951279874 262271567 14341526 1985602 466851 153365 63191 30623 16687 9987 6453 4354 3070 2290 1790 1427 1138 910 735 605 512 448 405 375 350 326 303 281 260 240 221 203 186 170 155 141 128 116 105 95 86 78 71 65 60 56 53 51 50
10^9+7 で割った余りを出力してください。
Source Name
「競プロ典型90問」15日目Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
N 個のブロックが横一列に並んでおり、それぞれのブロックは青・白・赤のうちいずれかで塗られています。
左から i 番目 (1 \leq i \leq N) のブロックの色は文字 c_i で表され、B は青、W は白、R は赤に対応しています。
この状態から青・白・赤のブロックを積み上げ、N 段のピラミッドの形にします。以下の図がその一例です。
ここでは、ブロックを下から順に、以下の規則で 1 個ずつ置いていきます。
- 直下にある 2 個のブロックの色が同じ場合、それと同じ色のブロックを置く
- 直下にある 2 個のブロックの色が異なる場合、そのどちらでもない色のブロックを置く
このとき、一番上のブロックはどの色になるでしょうか？
制約
- N は 2 \leq N \leq 400000 を満たす整数
- c_1, c_2, \dots, c_N はそれぞれ
B，W，Rのいずれか
入力
入力は以下の形式で標準入力から与えられます。
N c_1c_2\cdotsc_N
出力
一番上のブロックの色が青ならば B、白ならば W、赤ならば R を出力してください。
入力例 1
3 BWR
出力例 1
W
この入力例では、ブロックを以下のように積み上げることになります。
- 一番下の段の左から 1, 2 番目のブロックはそれぞれ青色・白色なので、その上に赤色のブロックを置く。
- 一番下の段の左から 2, 3 番目のブロックはそれぞれ白色・赤色なので、その上に青色のブロックを置く。
- 下から 2 段目のブロックはそれぞれ赤色・青色なので，その上に白色のブロックを置く。
一番上のブロックの色は白となるため、W を出力します。
入力例 2
4 RRBB
出力例 2
W
この入力例では、ブロックを以下のように積み上げることになります。
- 一番下の段の左から 1, 2 番目のブロックはそれぞれ赤色・赤色なので、その上に赤色のブロックを置く。
- 一番下の段の左から 2, 3 番目のブロックはそれぞれ赤色・青色なので、その上に白色のブロックを置く。
- 一番下の段の左から 3, 4 番目のブロックはそれぞれ青色・青色なので、その上に青色のブロックを置く。
- 下から 2 段目の左から 1, 2 番目のブロックはそれぞれ赤色・白色なので、その上に青色のブロックを置く。
- 下から 2 段目の左から 2, 3 番目のブロックはそれぞれ白色・青色なので、その上に赤色のブロックを置く。
- 下から 3 段目のブロックはそれぞれ青色・赤色なので、その上に白色のブロックを置く。
一番上のブロックの色は白となるため、W を出力します。
入力例 3
6 BWWRBW
出力例 3
B
最終的なブロックの並びは、以下の図のように表されます。一番上のブロックの色は青となるため、B を出力します。
なお、これは問題文中に例示したケースと同じものになっています。
入力例 4
8 WWBRBBWB
出力例 4
R
最終的なブロックの並びは、以下の図のように表されます。一番上のブロックの色は赤となるため、R を出力します。
入力例 5
21 BWBRRBBRWBRBBBRRBWWWR
出力例 5
B
Score : 600 points
Problem Statement
We have N blocks arranged in a row, where each block is painted blue, white, or red.
The color of the i-th block from the left (1 \leq i \leq N) is represented by a character c_i; B, W, and R stand for blue, white, and red, respectively.
From this situation, we will pile up blue, white, and red blocks to make a pyramid with N steps. The following figure shows an example of this:
Here, we place blocks one by one from bottom to top as follows:
- if the two blocks immediately below a position have the same color, we will place there a block of the same color;
- if the two blocks immediately below a position have different colors, we will place there a block of the color different from those two colors.
What will be the color of the block at the top?
Constraints
- N is an integer satisfying 2 \leq N \leq 400000.
- Each of c_1, c_2, \dots, c_N is
B,W, orR.
Input
Input is given from Standard Input in the following format:
N c_1c_2\cdotsc_N
Output
If the topmost block will be blue, print B; if it will be white, print W; if it will be red, print R.
Sample Input 1
3 BWR
Sample Output 1
W
In this case, we will pile up blocks as follows:
- the 1-st and 2-nd blocks from the left in the bottom row are respectively blue and white, so we place a red block on top of it;
- the 2-nd and 3-rd blocks from the left in the bottom row are respectively white and red, so we place a blue block on top of it;
- the blocks in the 2-nd row from the bottom are respectively red and blue, so we place a white block on top of it.
Thus, the block at the top will be white; we should print W.
Sample Input 2
4 RRBB
Sample Output 2
W
In this case, we will pile up blocks as follows:
- the 1-st and 2-nd blocks from the left in the bottom row are both red, so we place a red block on top of it;
- the 2-nd and 3-rd blocks from the left in the bottom row are respectively red and blue, so we place a white block on top of it;
- the 3-rd and 4-th blocks from the left in the bottom row are both blue, so we place a blue block on top of it;
- the 1-st and 2-nd blocks from the left in the 2-nd row from the bottom are respectively red and white, so we place a blue block on top of it;
- the 2-nd and 3-rd blocks from the left in the 2-nd row from the bottom are respectively white and blue, so we place a red block on top of it;
- the blocks in the 3-rd row from the bottom are respectively blue and red, so we place a white block on top of it.
Thus, the block at the top will be white; we should print W.
Sample Input 3
6 BWWRBW
Sample Output 3
B
The figure below shows the final arrangement of blocks. The block at the top will be blue; we should print B.
Note that this is the case shown as an example in Problem Statement.
Sample Input 4
8 WWBRBBWB
Sample Output 4
R
The figure below shows the final arrangement of blocks. The block at the top will be red; we should print R.
Sample Input 5
21 BWBRRBBRWBRBBBRRBWWWR
Sample Output 5
B
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 10000 点
問題文
中心座標が (0, 0) である半径 1 の円に、等しい半径の円を 100 個敷き詰める方法のうち、円の半径ができるだけ大きいものを求めてください。
なお、記録は 21 世紀になってからも塗り替えられており、いまだ解決されていない難問です。
入力形式
この問題では入力が与えられません。
出力形式
i 個目の円の中心座標を (x_i, y_i) とします。100 行にわたって以下の形式で出力してください。
x_1 y_1
x_2 y_2
\vdots
x_{100} y_{100}
なお、円の中心座標がすべて決まれば、円の半径は円同士が重ならないギリギリの値に自動的に設定されるので、半径を出力する必要はありません。
出力する実数 x_i, y_i は、1.23456e-03 のような指数表記で出力せず、すべて 0.00123456 のような形式で出力してください。
得点計算
この問題では、配置する円の大きさができるだけ大きいほど高得点が得られるようになっています。
まず、以下の条件を 1 つでも満たした場合は、不正解 (WA) となります。
- 出力形式が指定されたフォーマットに沿っていない（指数表記で出力している場合も含む）
- いずれかの i \ (1 \leq i \leq 100) に対して、\sqrt{{x_i}^2 + {y_i}^2} \gt 1 である（円の中心座標が半径 1 の円の内部に入っていない）
それ以外の場合は正解 (AC) と判定されます。100 個の円の中心座標から計算された円の半径 R に応じて、以下のように得点が決まります。
- 以下の 9 個の点を基準にして、R の 1 次関数的に（折れ線グラフのように）得点が増加していきます。
| R | 0.00 | 0.07 | 0.08 | 0.085 | 0.088 | 0.089 | 0.0895 | 0.0900 | 0.090235 |
|---|---|---|---|---|---|---|---|---|---|
| 得点 | 0 | 350 | 750 | 1250 | 1700 | 2000 | 2700 | 4000 | 8700 |
- R \gt 0.090235 のとき、R が 10^{-9} 増えるごとに 1 点上がるペースで得点が増加していきます。
- ただし、得点は小数点以下を四捨五入して整数に丸められます。
出力例
-0.63 -0.63 -0.63 -0.49 -0.63 -0.35 -0.63 -0.21 -0.63 -0.07 -0.63 0.07 -0.63 0.21 -0.63 0.35 -0.63 0.49 -0.63 0.63 -0.49 -0.63 -0.49 -0.49 -0.49 -0.35 -0.49 -0.21 -0.49 -0.07 -0.49 0.07 -0.49 0.21 -0.49 0.35 -0.49 0.49 -0.49 0.63 -0.35 -0.63 -0.35 -0.49 -0.35 -0.35 -0.35 -0.21 -0.35 -0.07 -0.35 0.07 -0.35 0.21 -0.35 0.35 -0.35 0.49 -0.35 0.63 -0.21 -0.63 -0.21 -0.49 -0.21 -0.35 -0.21 -0.21 -0.21 -0.07 -0.21 0.07 -0.21 0.21 -0.21 0.35 -0.21 0.49 -0.21 0.63 -0.07 -0.63 -0.07 -0.49 -0.07 -0.35 -0.07 -0.21 -0.07 -0.07 -0.07 0.07 -0.07 0.21 -0.07 0.35 -0.07 0.49 -0.07 0.63 0.07 -0.63 0.07 -0.49 0.07 -0.35 0.07 -0.21 0.07 -0.07 0.07 0.07 0.07 0.21 0.07 0.35 0.07 0.49 0.07 0.63 0.21 -0.63 0.21 -0.49 0.21 -0.35 0.21 -0.21 0.21 -0.07 0.21 0.07 0.21 0.21 0.21 0.35 0.21 0.49 0.21 0.63 0.35 -0.63 0.35 -0.49 0.35 -0.35 0.35 -0.21 0.35 -0.07 0.35 0.07 0.35 0.21 0.35 0.35 0.35 0.49 0.35 0.63 0.49 -0.63 0.49 -0.49 0.49 -0.35 0.49 -0.21 0.49 -0.07 0.49 0.07 0.49 0.21 0.49 0.35 0.49 0.49 0.49 0.63 0.63 -0.63 0.63 -0.49 0.63 -0.35 0.63 -0.21 0.63 -0.07 0.63 0.07 0.63 0.21 0.63 0.35 0.63 0.49 0.63 0.63
この出力は、以下の図のように円を配置することに相当します。
円の半径は 0.07 となるので、あなたは 350 点を獲得します。
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 10000 点
問題文
以下の条件をすべて満たす重みなし無向グラフを 1 つ構成してください。
- 多重辺や自己ループは存在しない。
- すべての頂点の次数が 4 以下である。
- すべての 2 頂点間の最短経路長が 4 以下である。
頂点数が多いほど、高い得点が得られます。
入力
この問題に入力はありません。
出力
以下の形式で答えを出力してください。
N M A_1 B_1 A_2 B_2 : A_M B_M
ただし、それぞれの変数は以下の情報を表します。ここで、1 \leq A_i, B_i \leq N を満たす必要があります。
このグラフには頂点が N 個あり、1 から N までの番号が付けられています。
また、辺が M 本あり、i 番目の辺は頂点 A_i と B_i を双方向に結んでいます。
得点
正しい形式で出力されていない場合、あるいは出力が条件を満たさない場合は 0 点となります。
出力が条件を満たす場合は、100 \times N 点が得られます。
入力例 1
(No Input)
出力例 1
9 12 1 2 2 3 4 5 5 6 7 8 8 9 1 4 4 7 2 5 5 8 3 6 6 9
この出力例は、以下のグラフに対応します。
頂点は 9 個あるので、100 \times 9 = 900 点が得られます。
なお、たとえば以下のような出力をすると、不正解となります。
なぜなら、頂点 1 と 8 の間の最短経路長が 7 であり、問題文の条件を満たさないからです。
8 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8