Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 500 点
問題文
ニコニコテレビちゃんは、頭の体操として簡単な計算をすることにしました。 ところでニコニコテレビちゃんは人間ではないので、逆ポーランド記法で計算をします。
具体的には、0 ~ 9, -, + からなる文字列 S について、以下の規則に従い計算をします。
- まず、最初の時点では空の、無限に長いスタックを 1 つ持っていると考える。そして、S の文字を前から見ていく。
- もし
0~9が出てきたら、そのままスタックへ積む。 - もし
+が出てきたら、スタックから1個取り出し a、もう1個取り出し b とする。そして b+a をスタックへ積む。 - もし
-が出てきたら、スタックから1個取り出し a、もう1個取り出し b とする。そして b-a をスタックへ積む。 - 最後に、スタックの中身が 1 個ならばそれが答えである
- もし 1 個ではなかったり、途中で取り出そうとしたがスタックが空だったりした場合は S は正しい式ではない。
ニコニコテレビちゃんは、適当に文字列 S を書きました。 これに対してただ計算するだけではつまらないので、以下の問題を解くことにしました。
- この文字列を K 文字まで書き換えて、正しい式にできるか？また、出来るならば正しい式のうち、計算した答えの最大値はいくつか？
しかしこれは難しすぎたので、あなたが代わりに解いて助けてあげてください。
制約
- S は、
0~9、-、+からなる文字列である - 1 ≦ |S| ≦ 52
- 0 ≦ K ≦ |S|
入力
入力は以下の形式で標準入力から与えられる。
K S
出力
もし正しい式に出来ないならば NG と出力してください。
出来るならば OK と出力し、更に次の行に計算した答えの最大値を出力してください。
入力例 1
0 21+
出力例 1
OK 3
この式は、普通の記法で表すと2+1となります
入力例 2
1 21+
出力例 2
OK 11
29+に書き換えると、答えが最大になります
入力例 3
1 21-
出力例 3
OK 8
91-に書き換えると、答えが最大になります
入力例 4
0 1+1
出力例 4
NG
このような式は、逆ポーランド記法としては正しい式ではありません
入力例 5
3 1234567
出力例 5
OK 13
12+4+6+と書き換えると、答えが最大になります
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 1100 点
問題文
ニワンゴくんは、正の整数からなる数列 x_1,\ x_2,\ ...,\ x_N を持っています。次の Q 個のクエリに順に答えてください。
- クエリ: 1 ≦ l_i ≦ r_i ≦ N が与えられるので、x_{l_i},\ x_{l_i+1},\ ...,\ x_{r_i} の積 x_{l_i}x_{l_i+1}...x_{r_i} の約数の個数を 10^9 + 7 で割ったあまりを求めよ。
制約
- 1 ≦ N, Q ≦ 10^5
- 1 ≦ x_i ≦ 10^5 (1 ≦ i ≦ N)
- 1 ≦ l_i ≦ r_i ≦ N (1 ≦ i ≦ Q)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q x_1 : x_N l_1 r_1 : l_Q r_Q
出力
クエリ毎に、整数 x_{l_i}x_{l_i+1}...x_{r_i} の約数の個数を 10^9 + 7 で割ったあまりを一行に出力せよ。
入力例 1
6 5 2 6 5 18 4 15 1 6 2 4 1 3 2 6 4 4
出力例 1
90 24 12 75 6
最初のクエリにおいて、x_1x_2x_3x_4x_5x_6=64800 の約数の個数は 90 個なので、90 を出力します。
入力例 2
10 6 3003 57600 4320 100000 3456 2197 2187 65536 90090 8128 1 10 2 5 3 7 1 4 3 6 7 10
出力例 2
1005480 2106 7056 9576 3528 7680
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点：1200 点
問題文
スマホゲームが大好きなタカシくんは最近、大人気のスマホゲーム「ドワンGo」にはまっています。
ドワンGoは、地図上の一点に隠れるキャラクター「テレビちゃん」を捕獲していくゲームです。
テレビちゃんは地図上に一体だけ存在しており、テレビちゃんの位置(x_t, y_t)は0 \leq x_t \leq L, 0 \leq y_t \leq Lを満たす整数座標であることが知られています。
タカシくんにテレビちゃんの正確な位置はわかりませんが、そのかわり、タカシくんは指定した座標にアイテム「テレボール」を投げることができます。
テレビちゃんにテレボールが当たると、タカシくんはテレビちゃんを捕獲することができます。
テレボールは非常に小さいため、テレビちゃんの位置をぴったり指定しないと、タカシくんはテレビちゃんを捕獲できません。
しかし、テレビちゃんは臆病なので、テレボールを投げた位置がテレビちゃんに近いと（つまり、テレビちゃんの位置からテレボールを投げた位置までのユークリッド距離がR以下である（Rぴったりを含む）と）、
テレビちゃんの驚く声が聞こえます。
いま、タカシくんはテレボールをN個持っています。
タカシくんはこれ以上テレボールの数を増やす課金をしたくないため、
N個のテレボールで確実にテレビちゃんを捕獲したいと考え、あなたに助けを求めてきました。
タカシくんを支援するプログラムを作成してください。
入出力形式
あなたはタカシくんにテレボールを投げる位置を実数で指示することができます。
例えば、C/C++でタカシくんにテレボールを位置(x,y)に投げてもらうよう指示するには、
printf("%.9f %.9f\n", x, y); fflush(stdout);
とします。
Lより大きい値や負数の指定も可能ですが、xとyは文字列として20文字以下でなくてはなりません。また、指数表記での指定は不可能です。
これらの条件を破った場合は誤答（Wrong Answer）となります。
次に、
scanf("%s", &result);
とすると、タカシくんがテレボールを投げた結果に応じて以下のように返事を得られます。
- テレビちゃんを捕獲した時（つまり(x_t,y_t)=(x,y)の時）、"found"が得られる
- テレビちゃんを捕獲できなかったが、テレビちゃんが声を発した時（つまり0 < \sqrt{(x_t-x)^2+(y_t-y)^2} \leq Rの時）、"close"が得られる
- テレビちゃんを捕獲できなかった上、テレビちゃんが声を発しなかった時（つまりR < \sqrt{(x_t-x)^2+(y_t-y)^2}の時）、"far"が得られる
- タカシくんがN個のボールを投げ切ってしまったか、あなたが指示した座標が不正であった時、"kill"が得られる
タカシくんが"found"もしくは"kill"を返すまで、あなたはタカシくんにテレボールを投げる指示をすることができますが、
"found"もしくは"kill"の返事が得られた時は、直ちにプログラムを終了してください。
制約
- L = 1,000,000
- R = 100,000
- 0 \leq x_t \leq L
- 0 \leq y_t \leq L
- x_t,y_tは整数
- テレボールはN = 200回まで投げることができる。それを超えると誤答（Query Limit Exceeded）となる
部分点
以下を満たすデータセットに正解した場合は、25点が与えられる。
- 0 \leq x_t \leq 10
- 0 \leq y_t \leq 10
入出力例
| プログラムの入力 | プログラムの出力 |
|---|---|
| 1000001.000000000000 1000000.000000000000 | |
| far | |
| -25252.525252525252 52525.252525252525 | |
| close | |
| 100000.000000000000 -0.000000000001 | |
| far | |
| -100000.000000000000 0.000000000000 | |
| close | |
| 0 0 | |
| found |
プログラムはタカシくんに(1000001, 1000000)の位置にテレボールを投げる指示を出し、
テレビちゃんが声を発していない（半径R = 100,000の範囲にテレビちゃんがいない）という情報を得ています。
その後何度かテレボールを投げる指示を出し、
最終的に(0, 0)にテレボールを投げる指示を出したところで、テレビちゃんを捕獲した。
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 1300 点
問題文
ニコニコテレビちゃんは、dwango主催のプログラミングコンテストである、 「ドワンゴからの挑戦状」の問題を準備していました。その問題は以下のような問題です。
- 長さ N の数列 a_1,\ a_2,\ ...,\ a_N が与えられる、これに対して Q 個クエリを処理する
- i 個目のクエリでは l_i,\ r_i,\ x_i が与えられ、以下の処理を行う
- a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i} にそれぞれ x_i を足す。そしてそのあと、a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i} の最大値を出力する。
コンテスト前日、ニコニコテレビちゃんはしっかり準備を終わらせ就寝しました。 当日の朝起きると、あら大変、パソコンが完全に壊れていました。
ニコニコテレビちゃんは頑張ってデータを復元したのですが、 数列の初期値 a_1,\ a_2,\ ...,\ a_N だけ復元することが出来ませんでした。
しかしニコニコテレビちゃんは、この逆境を逆手に取り、新たな問題を生み出すことに成功しました。 それは、この数列 a_1,\ a_2,\ ...,\ a_N を復元する、という問題です。
ここからが今回の問題です。
N と Q と クエリの内容 l_i,\ r_i,\ x_i、そしてその出力 y_i が与えられます。
あなたは、元の数列 a_1,\ a_2,\ ...,\ a_N としてあり得るものが存在するかを判定し、存在する場合はそれを 1 つ出力してください。
ただし、ニコニコテレビちゃんは a_1,\ a_2,\ ...,\ a_N は全て整数で、かつ絶対値が 10^{18} 以下であったことを覚えています。 なので、出力するものはこの制約を満たすようにしてください。
なお、今回与えられるすべてのテストケースについて、この a_1,\ a_2,\ ...,\ a_N の値の制約があってもなくても、 元の数列としてあり得るものが存在するかどうかは変わらないことが保証されます。
制約
- 入力は全て整数
- 1 ≦ N ≦ 200,000
- 1 ≦ Q ≦ 200,000
- 1 ≦ l_i ≦ r_i ≦ N
- |x_i| ≦ 10^9
- |y_i| ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N Q l_1 r_1 x_1 y_1 l_2 r_2 x_2 y_2 : l_q r_q x_q y_q
出力
もし条件を満たす数列 a_i が存在しないならば NG と出力してください。
存在するならば OK と出力し、次の行に a_1, a_2, ..., a_N を空白区切りで順に出力してください。
入力例 1
3 1 1 3 100 300
出力例 1
OK 200 200 200
100 を足した後の a_1, a_2, a_3 の最大値が 300 ということなので、例えば 200, 200, 200 が条件を満たします。
入力例 2
3 2 1 3 0 100 1 3 0 101
出力例 2
NG
このケースでは、 1 つ目のクエリでは a_1, a_2, a_3 の最大値を 100 と出力して、 2 つ目のクエリでは a_1, a_2, a_3 の最大値を 101 と出力しています。
これは明らかに矛盾しているため、NG と出力します。
入力例 3
3 2 1 1 0 11 3 3 0 1
出力例 3
OK 11 1000000000000000000 1
今回の入力ならば、2 つ目の値は制約を満たしていればなんでもよいです。
入力例 4
3 4 1 1 1 11 2 2 2 12 3 3 3 13 1 3 4 12345
出力例 4
NG
入力例 5
5 6 1 3 4 7 3 5 7 14 2 4 -10 4 2 4 3 7 1 2 1 6 4 5 -10 2
出力例 5
OK 1 3 3 7 5