Time Limit: 2 sec / Memory Limit: 256 MB
問題文
しかしある時のこと、大学で怪しげな連中に突然「あなたは素数の光を信じますか？」と話しかけられてから様子がおかしい。
俺は数学がそこまでできるわけではないが、素数ぐらいは知っている。1 とその数自身でしか割り切れない正の整数のことだ。
ただし 1 が素数じゃないってことだって知ってる。でも素数の光っていうのは何だかよく分からなかった。
奴らの話を聞いてからなんだか変だ。頭の中にはいつだって片隅に素数がいるし、素数を見るとなぜかたまらなく嬉しくなるようになった。
これまで毎回欠かさず参加していた ARC も、素数回のときでないと、なんだかうまくいかない気がして見送ってしまう。
そういえば、今もちょうど ARC が始まったところらしい。今回の ARC には、俺は無事に出られるのだろうか。
入力
入力は以下の形式で標準入力から与えられる。
N
- N (17 \leq N \leq 1,000,000) は、ARC が何回目の開催であるかを表す整数である。
出力
YES、そうでないときは NO と一行に出力せよ。
入力例１
17
出力例１
YES今回の ARC017 は、17 が素数である(2 から 16 までのいずれの整数でも割り切れない)ため参加することができる。
入力例２
18
出力例２
NO次回の ARC018 は、18 がたとえば 2 や 3 で割り切れるため参加することができない。
入力例３
999983
出力例３
YESARC999983 はいつ頃開催されることになるのでしょうか。
入力例４
672263
出力例４
NO672263 は 1 とそれ自身以外に、547 と 1229 で割り切ることができる。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
大変なことになってしまった！！
なんと、我が社の次の決算報告会の発表者に僕が選ばれてしまったのだ！我が社のイメージのためにも、そして社内での僕の地位のためにも、なんとしても好印象を与える発表をせねばならない。
我が社の直近の業績は N 個の数からなる数列で表される。これを発表したいところだけれど……、あいにく、我が社の業績はそこまで良いとは言えないのが実情だ。一体どうすればいいんだろうか……。
途方に暮れた僕は、とりあえず発表会場の設備を調査した。なんと、これが僕の生まれ持った強運か、プロジェクターの解像度がとても低く、画面には一度に K 個の数を表示するのが限界であることがわかった。業績の数列のうちの連続する K 個をうまく選べれば、我が社の業績がうなぎのぼりであるように見せかけられるのではないだろうか？
これは最高のアイデアだと思ったが、聴衆から「それって業績の一部ですよね？他の部分も見せて頂けませんか？」と言われたらジ・エンドだ。そこで用意周到な僕は、業績の数列のうち、プロジェクターで映したときに業績が常に上昇しているように見せられるような箇所がいくつあるのか、事前に調べておくことにした。
常に成長を続ける企業であるとアピールするためには、ある値はその前の値より真に大きくなくてはいけない。つまり 100, 200, 300 という列は常に上昇していると考えるが、 100, 200, 200 という列は常に上昇しているとは考えない。
※この問題文はフィクションです。業績はきちんと発表しましょう。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 : A_N
- 1 行目には、業績を表す数列の要素数 N (1 \leq N \leq 300,000)、プロジェクターで一度に表示できる数の個数 K (1 \leq K \leq N) が半角空白区切りで与えられる。
- 2 行目から N 行では、業績を表す数列が与えられる。このうち i 行目が i 番目の業績を表す整数 A_i (1 \leq A_i \leq 300,000) である。
注意: この問題では最大で 300,000 行ほどの入力を読み込む必要がある。ほとんどの言語では問題ないが、Python 2.x で input() を使うと時間制限に間に合わないおそれがあるので、かわりに整数を読み込む際には int(raw_input()) を使うこと。
出力
入力例１
10 4 100 300 600 700 800 400 500 800 900 900
出力例１
3業績を表す 10 個の数列から、連続する 4 個を抜き出してみると、
- (100,\, 300,\, 600,\, 700) は常に上昇しているように見える
- (300,\, 600,\, 700,\, 800) は常に上昇しているように見える
- (600,\, 700,\, 800,\, 400) は常に上昇しているように見えない
- (700,\, 800,\, 400,\, 500) は常に上昇しているように見えない
- (800,\, 400,\, 500,\, 800) は常に上昇しているように見えない
- (400,\, 500,\, 800,\, 900) は常に上昇しているように見える
- (500,\, 800,\, 900,\, 900) は常に上昇しているように見えない
入力例２
10 3 10 40 50 80 90 30 20 40 90 95
出力例２
5この場合、常に上昇しているように見える箇所は以下の画像に矢印で示された 5 箇所となる。
入力例３
8 4 1 2 3 4 5 6 7 8
出力例３
5元々の業績が常に上昇しているので、どこをプロジェクターに映しても大丈夫である。
入力例４
8 2 100000 90000 50000 30000 10000 4000 200 1
出力例４
0元々の業績があまりに良くない場合、どこを映しても業績を右肩上がりに見せかけられないことがある。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
世の中にはナップサック問題というものがあり、決まった大きさのナップサックにできるだけ価値が高くなるよう品物を詰めることを考えるらしいが、そんなことを考えても無駄である。
価値がいくら高くなったところで、ナップサックに無駄なスペースができてしまうのは許せない。私は無駄なものが嫌いなのだ。
さて、今ここに大きさ X のナップサックと N 個の品物がある。
i 番目の品物の大きさは w_i である。品物の価値については、考えても無駄なので無視する。
ナップサックに無駄なスペースができないよう品物を詰める方法は何通りあるだろうか？
つまり、N 個の品物から、大きさの総和が無駄なくぴったり X となる選び方が何通りあるか、ということだ。
私ははじめ手でこの問題を解こうとしたが、無駄が多い手段であると分かったので君に頼むことにした。
無駄な計算時間のないプログラムを書いてこの問題を解き、私の無駄な時間を省くのを手伝ってもらいたい。
入力
入力は以下の形式で標準入力から与えられる。
N X w_1 w_2 : w_N
- 1 行目には、品物の個数を表す整数 N (1 \leq N \leq 32) とナップサックの大きさを表す整数 X (1 \leq X \leq 10^9) が半角空白区切りで与えられる。
- 2 行目から N 行では、品物の大きさが与えられる。このうち i (1 \leq i \leq N) 行目には、i 番目の品物の大きさを表す整数 w_i (1 \leq w_i \leq 5 \times 10^7) が書かれている。
出力
入力例１
5 5 1 1 2 3 4
出力例１
4無駄のない品物の選び方は次の 4 通りである。
- 品物 1, 品物 2, 品物 4 を選ぶ: 1 + 1 + 3 = 5
- 品物 1, 品物 5 を選ぶ: 1 + 4 = 5
- 品物 2, 品物 5 を選ぶ: 1 + 4 = 5
- 品物 3, 品物 4 を選ぶ: 2 + 3 = 5
入力例２
8 21 10 4 2 30 22 20 8 14
出力例２
0どのように品物を選んでも、その大きさの和がぴったり 21 になるようにはできない。
入力例３
20 100000000 35576749 38866484 6624951 39706038 11133516 25490903 14701702 17888322 14423251 32111678 24509097 43375049 35298298 21158709 30489274 37977301 19510726 28841291 10293962 12022699
出力例３
45
入力例４
16 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例４
12870
Time Limit: 2 sec / Memory Limit: 256 MB
私はとあるクッキー工場に勤めている。
この工場では「ARCたんクッキー」というかわいいクッキーを作っている。
この工場には N 個のARCたんクッキー製造機があり、製造機には 1 から N まで番号がついている。製造機ごとに異なるフレーバーが設定されているため、異なる製造機から作られたクッキー同士は区別される。また製造機ごとに一度に生成するクッキーの量が設定されている。製造機は指定された製造数のクッキーを一度に全て生成する。
この度、私が勤めている工場では、M 日間、工場見学ツアーを実施することになった。それぞれの日には次のいずれかの作業が実行される。
- 見学ツアーを実施する。ツアーではそれぞれの日ごとに定められた、ある連続した番号の製造機をちょうど 1 回ずつ稼働させ、それらの製造機が生成したクッキー全てをお土産としてツアー参加者に配る予定である。
- メンテナンスを実施し、それぞれの日ごとに定められた、ある連続した番号の製造機の製造数を一定数増減させる。
工場はとても広く迷子になりやすいので、それぞれのツアー実施日内ではツアー客の定員を固定することになっている。
ここの工場長は割り切れないことを好まず、どの製造機から作られたクッキーもその日参加した全てのツアー客に同数ずつ配らなければ気が済まない。また、ARCたんクッキーの一部を配らない、砕くなどかわいそうなことはしてはならない。つまり、作ったクッキーは全てツアー客に平等に配らなければならない。一方でこの工場の宣伝のため、このような条件を満たしつつできるだけ多くのツアー客を受け入れたいと考えている。
立案者である私は、それぞれのツアー実施日において、1 回あたりのツアーに参加できるツアー客の最大値を求めることになった。しかしながら私は新しいフレーバー開発に忙しい。そこであなたに是非ともこの問題を解いてもらいたい。
入力
N a_1 a_2 … a_N M t_1 l_1 r_1 t_2 l_2 r_2 : t_M l_M r_M
- 1 行目には製造機の個数を表す整数 N (1≦N≦100,000) が与えられる。
- 2 行目には N 個の整数が空白を区切りとして与えられる。
- 整数 a_i (1≦a_i≦10^9) は製造機 i (1≦i≦N) が初期状態で製造するクッキーの個数を表す。
- 3 行目にはツアー及びメンテナンスをする日数を表す整数 M (1≦M≦100,000) が与えられる。
- 4 行目から M 回、ツアー及びメンテナンスの工程を表す 3 つの整数が空白を区切りとして与えられる。
- 整数 t_i (-10^9＜t_i＜10^9) は通算 i (1≦i≦M) 日目にする作業を表す。
- t_i=0 ならその日はツアーを実施する日であること表す。
- t_i≠0 ならその日はメンテナンスを実施する日であること表す。
- 少なくとも 1 回はツアーを実施する日がある。
- 整数 l_i,r_i (1≦l_i≦r_i≦N) は通算 i 日目にする作業の詳細に関する情報を表す。
- その日がツアーを実施する日なら、番号 l_i , l_i+1, ... , r_i の製造機をツアー実施時に使用することを表す。
- その日がメンテナンスを実施する日なら、番号 l_i , l_i+1, ... , r_i の製造機に対し、メンテナンスを実施することを表す。t_i が正ならそれぞれの製造機の製造数を t_i ずつ増やし、t_i が負なら製造数を -t_i ずつ減らす処理をメンテナンス時に行う。
- 全てのメンテナンスを実施する日において、メンテナンス実施後、どの製造機も製造するクッキーの枚数が 1 枚以上 10^9 枚以下である。
部分点
- 下記の条件を満たすテストケースのみで構成された、30 点分のセットがある。
- 全ての整数 i (1≦i≦M) において、t_i≠0 なら l_i=r_i が成立する。
- 上記のセットを含む全てのテストケースに正解することで、残りの 70 点を得られる。
出力
ツアーを行う回数を T とする。このとき出力は T 行だけ出力せよ。i 行目には、初日から数えて i 回目のツアー実施日において、観光客を呼べる人数の最大値を出力せよ。
なお、出力の最後には改行を入れること。
入力例 1
4 6 3 38 49 7 0 1 3 -2 3 3 0 1 3 9 2 2 0 1 2 6 3 3 0 3 4
出力例 1
1 3 6 7
- 初期状態における製造機ごとのクッキー製造数は、1 番の製造機から順に 6,3,38,49 となっている。
- 1 日目はツアーを実施する。
- ツアーでは製造機 1,2,3 を用いるので、製造されるクッキーの個数は順に 6,3,38 となる。
- この場合、観光客は 1 人しか受け入れられない。
- 2 日目はメンテナンスを実施する。
- 製造機 3 の製造数を 2 だけ減らす。メンテナンス後のクッキー製造数は、1 番の製造機から順に 6,3,36,49 となる。
- 3 日目はツアーを実施する。
- ツアーでは製造機 1,2,3 を用いるので、製造されるクッキーの個数は順に 6,3,36 となる。
- この場合、観光客は最大で 3 人受け入れられる。
- 4 日目はメンテナンスを実施する。
- 製造機 2 の製造数を 9 だけ増やす。メンテナンス後のクッキー製造数は、1 番の製造機から順に 6,12,36,49 となる。
- 5 日目はツアーを実施する。
- ツアーでは製造機 1,2 を用いるので、製造されるクッキーの個数は順に 6,12 となる。
- この場合、観光客は最大で 6 人受け入れられる。
- 6 日目はメンテナンスを実施する。
- 製造機 3 の製造数を 6 だけ増やす。メンテナンス後のクッキー製造数は、1 番の製造機から順に 6,12,42,49 となる。
- 7 日目はツアーを実施する。
- ツアーでは製造機 3,4 を用いるので、製造されるクッキーの個数は順に 42,49 となる。
- この場合、観光客は最大で 7 人受け入れられる。
入力例 2
3 1 3 17 6 16 1 1 8 2 2 0 1 2 0 2 2 6 2 2 0 1 3
出力例 2
1 11 17
- このテストケース内の 4 日目のように、ツアー実施日に稼働させる製造機が 1 つだけのこともある。