Time Limit: 1 sec / Memory Limit: 64 MB
問題文
E869120鉄道では毎日たくさんの列車が運行されています。
うさぎは, 何本の列車が運行されているのだろうと思ったので, 観察をすることにした。
うさぎはA地点で調査をして次のような結果が出た。
- A地点に電車が1回目に通ったのは5時ちょうどで, 最後に通ったのは23時ちょうどだった。
- 電車はA地点をN回, K分ごとに通過した。
Nが分かっているとき, Kの値を求めなさい。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、整数 N が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
Kの値を1行に出力せよ。ただし, 10-6以下の誤差は許容する。
制約
- 2≦N≦1,000,000
入力例1
9
出力例1
135.000000000000
列車はA地点を5:00, 7:15, 9:30, 11:45, 14:00, 16:15, 18:30, 20:45, 23:00の9回,135分ごとに通過した。
入力例2
1001
出力例2
1.08000000000064.8秒ごとに通過する電車は東京都心にあるかもしれません。
入力例3
114514
出力例3
0.009431243614
Time Limit: 1 sec / Memory Limit: 64 MB
問題文
E869120は, H \times Wのケーキを作った。square1001はE869120と分けるためにケーキを分割することになった。
ケーキは長方形であり, 4頂点の座標は(0, 0), (0, H), (W, 0), (W, H)である。
square1001は, 座標(0, 0)から(i, H) (1≦i≦W)または(W, i) (1≦i≦H)に向かって切る。しかし, 次の条件を満たさなければならない。
- ケーキの上にはイチゴがN個あり, それを均等に分けなければならない。
- ナイフがイチゴの上にくるように切るとイチゴは消えてしまうので, イチゴを1個も消滅させないように切らなければならない。
- 整数座標に向かって切らなければならない。
そのとき, square1001が(0,0)からPに向かって切るようなPをすべて求めなさい。ただし, そのようなことができないときは-1と出力しなさい。
ただし、イチゴの面積は考えないものとします。
入力
入力は, 以下の形式で与えられる。
H W N X_1 Y_1 X_2 Y_2 : : X_N Y_N
(X_i, Y_i)は, i番目のイチゴの座標である。H, W, Nについては, 問題文中に記載されている。
出力
下の出力例にしたがって辞書順で出力しなさい。解がない場合は-1と出力しなさい。ただし, 出力には余計な空白や改行を入れないこと。
制約
1≦H, W, N≦10
1≦X_i＜W, 1≦Y_i＜H
i≠j⇒(X_i,Y_i)≠(X_j,Y_j)
入力例1
5 5 2 1 3 4 2
出力例1
(2,5) (3,5) (4,5) (5,3) (5,4) (5,5)
下のように切ることができる。
辞書式順序に従って出力する。
入力例2
5 5 5 1 1 1 3 3 3 3 4 4 3
出力例2
-1
イチゴは奇数個なので等しく分けることはできない。
入力例3
5 5 2 3 2 4 3
出力例3
-1
整数座標に向かって切ることしかできない。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
うさぎは、お金が大好きである。
うさぎは、ある都市を散策することにした。ただし、時間の関係上 同じ街を2度通ってはいけないが、どこの町から出発してもよい。
街 i にはお金が D_i 円あり、 うさぎはお金をできるだけ取りたい。
取ることができるお金の最大値を求めなさい。
ただし、街は N 個、道路は K 個あり、 道路 i は街 X_iと Y_iを結んでいます。また, 道路は双方向に通行可能です。
入力
入力は以下の形式で標準入力から与えられる。
N K D_1 D_2 ： D_N X_1 Y_1 X_2 Y_2 : : X_K Y_K
- 1 行目には、整数 N と Kが与えられる。
- 次の N 行には、街i にあるお金 D_i が与えられる。
- その次の K 行には、X_i とY_iが与えられる。
出力
出力は以下の形式で標準出力に行うこと。
うさぎが得られるお金の最大値を1行に出力しなさい。
ただし、答えは 32 ビット整数型に収まらない可能性があります。
制約
- 1≦N≦50
- 1≦K≦50
- 1≦D_i≦1,000,000,000
- 1≦X_i, Y_i≦N
- X_i≠Y_i
- 同一の道路は存在しないことが保証されている
- 可能な散策経路は2,000,000通り以下である。
部分点
この問題には、部分点が設定されている。
1≦N,K≦10を満たすテストケースすべてに正解した場合は、50点が与えられる。
残りのデータセットすべてに正解した場合は、50点が与えられる。
入力例1
6 6 1 2 3 4 5 7 1 2 1 3 1 6 2 4 3 4 4 5
出力例1
20
街 6 から出発し、6→1→3→4→5 の順に行くと 7+1+3+4+5=20円が得られる。
入力例2
4 2 1 10 5 6 1 2 3 4
出力例2
11
入力例3
5 4 2 3 5 6 7 1 3 1 4 2 4 4 5
出力例3
20
問題文担当者：E869120
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
square1001は、毎日歩いて中学校まで通っている。
彼は、左下の交差点 (1,1) に住んでおり、 右上の交差点 (W,H)にある学校まで行く。
ただし、次のような条件がある。
- 彼は時間短縮のために右か上にしか進まない。
- 彼はその日、K 個のマスに用事があった。 左下 が(X_i,Y_i) で, 右上が(X_i+1,Y_i+1) のマスである。
そのため、用事のあるマスそれぞれについて、その周りの交差点４つのうち少なくとも１つは通る必要があった。
それらの条件を満たす行き方は何通りあるか。 mod 1,000,000,007で求めよ。
入力
入力は以下の形式で標準入力から与えられる。
H W K X_1 Y_1 X_2 Y_2 ： ： X_K Y_K
- 1 行目には、整数 H (1≦H≦1,000) , W(1≦W≦1,000) , K(1≦K≦200)が空白区切りで与えられる。
- 次のK 行には、整数 X_i (1≦X_i＜W) , 整数 Y_i (1≦Y_i＜H)が空白区切りで与えられる。
出力
条件を満たす行き方を1行に出力しなさい。
入力例1
4 4 1 2 2
出力例1
18
(1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)→(4,4)という行き方と、
(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)→(4,4)という行き方はできない。
よって, 20-2=18を出力する。
※図の左上数が抜けていてすみません。
入力例2
9 9 3 3 2 4 5 7 7
出力例2
4380
Time Limit: 3 sec / Memory Limit: 128 MB
問題文
E869120王国では, N個の街があり, 街i-1と街iは道路で結ばれている。
また, 街i (1≦i≦N)には整数a_iが書かれており, 道路の長さは次の規則に従って定められる。
- 街i-1と街iを結ぶ道路の長さはa_{i-1}a_iである。
E869120王国に住むsquare1001は, 散歩をすることにした。
square1001は街1に住んでいて, 1->c_1->c_2-> ... ->c_Q->1というように散歩することになっている。
しかし, square1001はとんでもない距離を歩くかもしれないので, あなたはsquare1001のために歩く距離を教えてほしい。
square1001の歩く距離をmod 1,000,000,007で求めなさい。
入力
入力は以下の形式で与えられる。
N Q a_1 a_2 ... a_N c_1 c_2 ... c_Q
- 1行目には街の数N, 経由地の数Qが空白区切りで与えられる。
- 2行目には街に書かれている整数a_1,a_2,...a_Nが空白区切りで与えられる。
- 3行目にはsquare1001の散歩する経路を表す整数c_1,c_2,...c_Qが空白区切りで与えられる。
出力
出力は以下の形式に従うこと。
1行目に, square1001が歩く距離を1,000,000,007で割った余りを出力しなさい。ただし, 出力の末尾には改行を入れること。
制約
- 2≦N≦120,000
- 1≦Q≦120,000
- 0≦a_i≦1,000,000,000
- 1≦c_i≦N
- c_{i-1}≠c_i
- a_i=0⇒a_{i+1}≠0
部分点
「1≦N≦1,000かつ1≦Q≦1,000かつ1≦a_i≦1,000」を満たすテストケースに正答した場合は部分点として15点が与えられる。
「1≦N≦1,000かつ1≦Q≦1,000」を満たすテストケースに正答した場合は部分点として50点が与えられる。
すべてのテストケースに正答した場合は100点が与えられる。
入力例1
4 3 5 3 1 2 3 2 4
出力例1
264
- 1回目に, 街1->街3まで行くので, 5^3+3^1=128歩く。
- 2回目に, 街3->街2まで行くので, 3^1=3歩く。
- 3回目に, 街2->街4まで行くので, 3^1+1^2=4歩く。
- 4回目に, 街4->街1まで行くので, 1^2+3^1+5^3=129歩く。
- よって, square1001は合計で264歩くことになる。
入力例2
3 2 23 12 9 2 3
出力例2
876796540
square1001は43,829,259,183,601,346歩くことになるので, それを1,000,000,007で割った余りである876,796,540を出力する。
入力例3
2 1 1000000000 1000000000 2
出力例3
625113690
square1001はどのくらい歩けばよいのでしょうか???
Time Limit: 4 sec / Memory Limit: 256 MB
リジャッジをしました。申し訳ございません。(01/24 22:16:18追記)
部分点のケースはあっていますが、sub2-3.txtが間違っていることが判明しました。消去し次第リジャッジを行います。(01/24 22:12:49追記)
問題文
square1001の部分文字列である「1001」は回文数である。
すなわち、その名前を付けた彼も回文数が好きであった。
ということで、E869120は彼に次のような問題を出した。
「a以上b以下の数がある。 その中で、cの倍数かつ各位の数字の和が dである回文数はいくつあるか。」
square1001は、普通に全探索して求めようとしたが、 a , bが相当大きいためできなかった。
その問題の答えをmod 10000で求めよ。
入力
入力は以下の形式で標準入力から与えられる。
a b c d
正整数a,b,c,dが 1 行に入力される。
出力
条件を満たす回文数の個数を1行に出力せよ。
制約
- a＜b
- 2≦|a|=|b|≦80 かつ |a|, |b|は2の倍数
- 1≦c≦50
- 1≦d≦720
- a,bは回文数
ここで, |a|はaの桁数を表す。
部分点
1≦a,b≦10,000,000,000を満たすデータセットすべてに正解した場合は、 20点が与えられる。
残りのデータセットすべてに正解した場合、80点が与えられる。
入力例1
1001 9999 9 36
出力例1
1
「9999」が条件を満たす。
入力例2
1001 4004 49 20
出力例2
1
「3773」が条件を満たす。
入力例3
1000000001 9999999999 50 50
出力例3
0
「0」で終わる回文数は存在しない。
問題文担当者：E869120
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
E869120は, セールスマンである。だから, すべての建物を1度ずつ通って店に戻ってこなければならない。
E869120の住む街には, 建物がN個あり, 道路がM本ある。建物の番号は1-indexedでつけられており, 店は建物1とする。
また, 道路 i は建物s_iと建物t_iを結んでいて, 距離はd_iである。
しかし, その街は不審者対策として一定の時間を過ぎると道路を閉鎖する。
道路 iは, E869120が出発してから時間 time_i 経つと道路が閉鎖される。
だから, その道路を通る際, 時間 time_i 以内に道路を通り終えなければならない。
そのとき, E869120は次のようなことを考えた。
「最短時間で戻ってくる方法の総数はどのくらいあるのだろう？」
そこで, 優秀なプログラマーであるあなたにプログラムを作ってもらうことになりました。
最短経路と, 最短時間で戻ってくる方法の総数を求めなさい。ただし, E869120は時間 1 につき距離 1 進む。また, 道路は双方向に移動可能である。
入力
入力は以下の形式で標準入力から与えられる。
N M s_1 t_1 d_1 time_1 s_2 t_2 d_2 time_2 ：： ： ： s_M t_M d_M time_M
・1行目には、整数N , M が与えられる。
・次のM行には、整数s_i , t_i , d_i , time_i
が空白区切りで与えられる。
出力
出力は以下の形式で標準出力に行うこと。
最短経路と, 最短時間で戻ってくる方法の総数を空白で区切って出力しなさい。
ただし, そのような経路が存在しない場合 "IMPOSSIBLE"と出力しなさい。
また,出力の末尾には改行を入れること。
制約
- 1≦N≦16
- 1≦s_i＜t_i≦N ※入力例ではそうとは限りません
- 1≦d_i≦1,000,000,000,000
- 1≦time_i≦1,000,000,000,000
- 任意のi,jに対し, (s_i,t_i)≠(s_j,t_j)
部分点
2≦N≦8を満たすデータセットすべてに正解した場合は、15点が与えられる。
残りのデータセットすべてに正解した場合は、85点が与えられる。
入力例1
3 3 1 2 1 6 2 3 2 6 3 1 3 6
出力例1
6 2
1->2->3->1 または 1->3->2->1 と行くと, 時間6で行くことができる。これが最短経路である。
入力例2
3 3 1 2 1 1 2 3 1 3 3 1 1 3
出力例2
3 1
道路1が時間1経つと閉鎖されるため, 1->3->2->1と行くことができない。
入力例3
3 3 1 2 1 1 2 3 1 1 3 1 1 1
出力例3
IMPOSSIBLE
1->2->3->1 , 1->3->2->1と行くことはできないため, E869120は役目を果たすことができない。
入力例4
3 2 1 2 3 20 2 3 2 20
出力例4
IMPOSSIBLE
Time Limit: 7 sec / Memory Limit: 600 MB
問題文
ある家には、square1001,E869120,うさぎの3人がいるが、その3人は昼食の値段の 差がああだこうだ、といってけんかが起きてしまう。
そこで、square1001は次のように言った。
「square1001とE869120の合計値段の差、square1001とうさぎの合計値段の差が 両方D以下になるようにしたいです。」
→2人は賛成した。
N個の食品があり、それらの値段はA_iである。また、E個までなら食品を残してもよい。
条件を満たす食品の分け方は何通りあるか。
入力
入力は以下の形式で標準入力から与えられる。
N D E A_1 A_2 ： A_N
- 1 行目には、整数 N, D, Eが空白区切りで与えられる。
- 次のN 行には、整数 A_i が与えられる。
出力
食品の分け方の通り数を1行に出力せよ。
制約
- 2≦N≦20
- 0≦D≦1,000,000,000
- 0≦E≦2
- 1≦A_i≦1,000,000,000
部分点
この問題には、部分点が設定されている。
・2≦N≦10を満たすケースすべてに正解した場合は、20点が与えられる。
・11≦N≦20かつ条件を満たす食品の分け方が1000通り以下であるデータセットに正解した場合は、50点が与えられる。
・残りのデータセットすべてに正解した場合は、30点が与えられる。入力例1
3 2 1 2 4 6
出力例1
4
square1001をA, E869120をB, うさぎをCとすると, 以下のように分けることができます。
| 食品1 | 食品2 | 食品3 | |
| 方法1 | A | B | × |
| 方法2 | A | C | × |
| 方法3 | B | A | C |
| 方法4 | C | A | B |
入力例2
4 1 1 1 2 3 4
出力例2
10
問題文担当者：E869120