Time Limit: 2 sec / Memory Limit: 256 MB
問題文
幼稚園の先生であるけんしょう先生は，持っている a 個のお菓子を b 人の児童に同じ数ずつ配りたいと思っています．けんしょう先生は持っているお菓子を全て配りきりたいと思っていますが，a と b の組によっては全員に同じ数ずつ配りきれないことがあることに気づきました． そこで，けんしょう先生は必要最低限のお菓子を買い足すことにしました．たとえば，7 つのお菓子を 3 人に配るシチュエーションを考えてみましょう．今のままでは同じ数配りきれないので，2 個のお菓子を買い足せばお菓子の数は 9 個となり，3 人に 3 個ずつ配ることが出来ます．
さて，天才プログラマ児童たかはし君であるあなたは，いくつのお菓子を買い足せば良いかを先生に教えてあげるために，プログラムを作ることにしました．
入力
入力は以下の形式で標準入力から与えられる．
a b
- 1 行目には，けんしょう先生が最初に持っているお菓子の数を表す整数 a (1 ≦ a ≦ 100) が与えられる．
- 2 行目には，児童の数を表す整数 b (1 ≦ b ≦ 100) が与えられる．
出力
けんしょう先生が買い足さなければならないお菓子の個数を 1 行に出力せよ．出力の末尾に改行をいれること．
入力例1
7 3
出力例1
2
問題文中で説明したケースです．7を3で割った余りは1なので，もう2 個買い足すことで3つになり，全員に同じ数のお菓子を配りきることができます．
入力例2
5 5
出力例2
0
買い足さなくても，5 人の児童にちょうど 1 つずつ配ることができます．
入力例3
1 100
出力例3
99
1 つのお菓子しかないので，99 個買い足して全員に 1 個ずつ配ります．
入力例4
25 12
出力例4
11
11 個買い足すことで，お菓子は合計 36個となり， 12人に 3 個ずつ配ることができます．
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたは買い物をしていて，商品リストからいくつかの商品を選んだ．そして今，その商品の価格を合計しようとしている．
ところで，とある集合の任意の部分集合を 2 進数を用いて表す方法が存在し，forループで全ての部分集合(組み合わせ)を列挙する際などに用いることができる．
- n 個の商品があり， 商品0,商品1,..,商品n-1 があるとする．添字が0から始まることに注意せよ．
- 部分集合を表す 10 進整数を X とし，その 2 進 n 桁表現をb_{n-1}b_{n-2}...b_1b_0とする．b_0 が最下位ビットで b_{n-1} が最上位ビットである．先頭の0 を許す表現であることに注意せよ．
そして，この整数 X の 2 進表現を用いて，ある部分集合を以下のように定義する．
- b_0=1 ならば集合は商品0 を含み，b_0=0 ならば集合は商品 0 を含まない．
- b_1=1 ならば集合は商品1 を含み，b_1=0 ならば集合は商品 1 を含まない．
- ...
- b_{n-1}=1 ならば集合は商品 n-1 を含み，b_{n-1}=0 ならば集合は商品 n-1 を含まない．
例えば，n=4,X=5 のとき， b=0101 であり，部分集合は \{商品0,商品2\} である． 簡単にいえば，Xの 2 進表現において，k(0 ≦ k ≦ n-1) 番目のビットが立っていれば k 番目のアイテムを含むということである．あるビットが立っているかどうかは，多くのプログラミング言語で容易に判定できるので，各自調べられたい．
あなたの仕事は，商品の数，それぞれの商品の価格，そして部分集合を表す 10 進整数 X が与えられるので，部分集合に含まれる商品の価格を合計することである．
※今回の問題には直接関係は無いが，部分集合を上記のように表現することで，大きさ n の集合の全ての部分集合(空集合を含む)を0 ～ 2^n-1 の連続した整数で表現できるので，全列挙を行う際には応用するとよい．
入力
入力は以下の形式で標準入力から与えられる。
n X
a_0 a_1 a_2 ... a_{n-1}
- 1 行目には，商品の数 n (1 ≦ n ≦ 20) と，商品の部分集合を表す 10 進整数 X (0 ≦ X ≦ 2^{n}-1) が空白区切りで与えられる．
- 2 行目には，商品 0 ～ n-1 の商品の価格 a_0,a_1,...,a_{n-1}(0 ≦ a_0,a_1,...,a_{n-1} ≦ 1,000) が順番に空白区切りで与えられる．
出力
- 部分集合に含まれる商品の価格を合計したものを 1 行に出力せよ．出力の末尾に改行をいれること．
入力例1
4 5 1 10 100 1000
出力例1
101
n と X は問題文中の説明で用いた値である．部分集合は\{商品0,商品2\}であるので，1+100=101となる．
入力例2
20 1048575 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
出力例2
210
X の 2 進表現は11111111111111111111(20個の1が並んでいる)であるので，部分集合は全商品を含んでいる．
入力例3
4 0 1000 1000 1000 1000
出力例3
0
部分集合が空集合であることもある．
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
AtColor社は，0 から 1,000,000 まで 1,000,001 通りの濃さがある灰色の絵の具を販売することにしました．0 が最も黒く，1,000,000 が最も白い絵の具です．
しかし，途方も無い数の濃さのバリエーションがある一方，消費者には細かい違いが分からないということが判明しました．これを知ったAtColor社は，売れない濃さの絵の具を生産するのはやめて，最も人気のある濃さの色の絵の具1つだけを販売することにしました．
AtColor社は上記を達成するために，最も人気な絵の具がどのくらい売れるかをアンケート調査で調べることにしました． AtColor社がどの範囲の濃さの絵の具なら購入したいかというアンケートを消費者に対して行ったところ， 「a ≦ x ≦ b を満たす濃さ x の絵の具ならば購入する」という形式の情報が n 件得られました．
あなたの仕事は，これらの情報から，最も多くの消費者に購入される濃さの絵の具について，その絵の具を購入する消費者の数を出力するプログラムを作ることです．
入力
入力は以下の形式で標準入力から与えられる．
n
a_{1}\ b_{1}
a_{2}\ b_{2}
:
a_{n}\ b_{n}
- 1 行目には，アンケート情報の数 n (1 ≦ n ≦ 100,000) が与えられる．
- 続く 2 行目から n行は，各アンケート情報を表す． a_i,b_i(0≦a_i≦b_i≦1,000,000) はそれぞれ i 番目のアンケート情報における濃さの下限と上限(端を含む)を表す整数で，空白区切りで与えられる．
部分点
この問題には2つのデータセットがあり，データセット毎に部分点が設定されている．
- 1≦n≦2,000 を満たすデータセット 1 に正解した場合は 30 点が与えられる．
- 追加制約のないデータセット 2 に正解した場合は，上記のデータセットとは別に 70 点が与えられる．
出力
最も多くの消費者に購入される濃さの絵の具について，それを購入する消費者の数を 1 行に出力せよ．出力の末尾に改行を入れること．
入力例1
4 0 2 2 3 2 4 5 6
出力例1
3
- 濃さ 0,1,4,5,6 の絵の具は，1人の消費者によって購入してもらえます．
- 濃さ 2 の絵の具は，3人の消費者によって購入してもらえます．
- 濃さ 3 の絵の具は，2人の消費者によって購入してもらえます．
- 他の濃さの絵の具は誰にも購入してもらえません．
よって，3 を出力します．
入力例2
4 1000000 1000000 1000000 1000000 0 1000000 1 1000000
出力例2
4
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
n 個の頂点と n-1 本の辺からなる連結な無向グラフが与えられます．それぞれの頂点には 1 から n までの番号が順番にふられています．
グラフ理論において，このような条件を満たすグラフは木と呼ばれ，閉路を含まないという性質があります． このグラフに対し，元のグラフに含まれない追加辺 (a,b) を1つ追加したグラフについて考えてみると，このグラフはちょうど1つの閉路を含みます． あなたの仕事は，そのようなグラフについて，閉路の長さ(閉路に含まれる辺の数)を出力することです．ただ，追加辺の候補はいくつかあり，Q 個与えられるので，それら全ての候補について答えを出力してください．
入力
入力は以下の形式で標準入力から与えられる．
N
x_1\ y_1
x_2\ y_2
：
x_{N-1}\ y_{N-1}
Q
a_1\ b_1
a_2\ b_2
：
a_{Q}\ b_{Q}
- 1 行目には，グラフの頂点数を表す整数 N (1≦N≦100,000) が与えられる．
- 続く2 行目からN-1行は，グラフの辺情報を表す．i番目の行には，辺が結ぶ頂点 x_i と y_iが空白区切りで与えられる．
- 続く1+N 行目には，辺(a,b)の候補の数を表す整数 Q (1≦Q≦100,000) が与えられる．
- 続く2+N 行目からQ行は，i番目の追加辺候補の情報を表す．i 番目の行には，追加辺が結ぶ頂点 a_i と b_iが空白区切りで与えられる．
- 与えられる辺は全て，存在する頂点を結んでいる．
- グラフは自己辺を含まない．つまり，任意のiについて，x_i≠y_iが成り立つ．
- グラフは多重辺を含まない．つまり，任意のi,j(i≠j)について，x_i≠x_jもしくはy_i≠y_jが成り立つ．
- 追加辺は，元のグラフに含まれない辺であり自己辺でないことが保障されている．
部分点
この問題には2つのデータセットがあり，データセット毎に部分点が設定されている．
- Q=1 を満たすデータセット 1 に正解した場合は 30 点が与えられる．
- 追加制約のないデータセット 2 に正解した場合は，上記のデータセットとは別に 70 点が与えられる．
出力
全ての追加辺候補について，それを元のグラフに追加したときにできる閉路の長さを，1 行目から Q 行順番に出力せよ．出力の末尾に改行を入れること．
入力例1
5 1 2 1 3 1 4 4 5 3 2 3 2 5 2 4
出力例1
3 4 3
図は以下の通りです．
入力例2
6 1 2 2 3 3 4 4 5 5 6 4 1 3 1 4 1 5 1 6
出力例2
3 4 5 6
入力例3
7 3 1 2 1 2 4 2 5 3 6 3 7 5 4 5 1 6 5 6 4 7 5 3
出力例3
3 3 5 5 4