入力

この問題では入力は与えられない。

出力

この問題に使用できる言語は Text (cat) のみである。

B 問題の制約を満たす入力 V, E, K, a_i, b_i と、その入力に対して正答となる出力 c_i を以下の形式で出力せよ。

以下の制約を満たすB問題の入力 V, E, K, a_i, b_i と、その入力に対して正答となる出力 c_i を以下の形式で出力せよ。

V ( 1 \leq V \leq 100 ), E ( 0 \leq E \leq 4950 ), K ( 1 \leq K \leq V )
※これは本戦参加者用のB問題の制約です。

V E K
a_1 b_1
a_2 b_2
:
a_E b_E
c_1
c_2
:
c_K

配点

この問題の得点は、コンテスト開催時間終了後に以下の操作が行われて確定する。
コンテスト開催時間中に Text (cat) において AC となったあなたの A 問題の提出のうち、最後の提出を、あなたの A 問題の本提出とする。
コンテスト開催時間中に AC となった他の本戦参加者の B 問題の提出のうち、各参加者の最後の提出を、その参加者の B 問題の本提出とする。
A 問題の本提出を行うと、10 点が与えられる。
コンテスト開催時間終了後、あなたの A 問題の本提出の入力部分が、他の各本戦参加者の B 問題の本提出に入力として与えられる。
他の本戦参加者 n 人の B 問題の本提出があなたの A 問題の本提出の入力部分に対して誤答し、
他の本戦参加者 m 人の B 問題の本提出がなかった場合、あなたに上記とは別に 2(n+m) 点が与えられる。

この問題には部分点は設定されていない。正解した場合は、10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

V E K
a_1 b_1
a_2 b_2
:
a_E b_E

• 1 行目には与えられるグラフの頂点の数 V ( 1 \leq V \leq 100 ) と辺の数 E ( 0 \leq E \leq 4950 ) と K ( 1 \leq K \leq V ) が空白区切りで与えられる。
• 1 行目には与えられるグラフの頂点の数 V ( 1 \leq V \leq 20 ) と辺の数 E ( 0 \leq E \leq 190 ) と K ( 1 \leq K \leq V ) が空白区切りで与えられる。
• 続く E 行には i 番目の辺がつなぐ頂点の番号 a_i と b_i ( 0 \leq{} a_i,\ b_i \leq{} V-1 ) が空白区切りで与えられる。
• 与えられるグラフは自己辺や多重辺を含まない。
• 条件を満たす頂点の選び方が存在することは保証される。
• V \leq 20, E \leq 190 の入力に対して正答すると AC となる。

出力

選んだ K 個の頂点の、頂点の番号を K 行に出力せよ。

配点

この問題の得点は、コンテスト開催時間終了後に以下の操作が行われて確定する。
コンテスト開催時間中に Text (cat) において AC となった他の本戦参加者の A 問題の提出のうち、各参加者の最後の提出を、その参加者の A 問題の本提出とする。
コンテスト開催時間中に AC となったあなたの B 問題の提出のうち、最後の提出を、あなたの B 問題の本提出とする。
B 問題の本提出を行うと、10 点が与えられる。
コンテスト開催時間終了後、他の参加者の A 問題の本提出の入力部分が、あなたの B 問題の本提出に入力として与えられる。
他の本戦参加者 n 人の A 問題の本提出の入力部分に対して、あなたの B 問題の本提出が正答し、
他の本戦参加者 m 人の A 問題の本提出がなかった場合、あなたに上記とは別に 2(n+m) 点が与えられる。

この問題には部分点は設定されていない。正解した場合は、10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

W H
a_0 a_1 a_2 ... a_{H-1}
b_0 b_1 b_2 ... b_{W-1}

• 縦線の本数を表す W\ (3 \leq{} W \leq{} 7) と既に書き込まれた横線の本数を表す H\ (0 \leq{} H \leq{} 100,000) が 1 行目に与えられる。
• 2 行目には既に書き込まれている上から n 本目の横線の左側の端点が接する縦線の位置 a_n\ (0 \leq{} a_n \leq{} W-2) が与えられる。
• 3 行目には改竄かいざん結果が与えられる。左から b_{m}\ (0 \leq{} b_{m} \leq{} W - 1) 番目の縦線の上端が、左から m 番目の縦線の下端に繋がることがオカモトくんの望みである。

配点

この問題には部分点が設定されている。

• H \leq{} 100 を満たすテストケース全てに正解した場合は、45 点が与えられる。
• 全てのテストケースに正解した場合は、上記とは別に 105 点が与えられる。

入力

入力は以下の形式で標準入力から与えられます。

L s

• 三角形の周長 a + b + c の上限を表す整数 L ( 1 \leq L \leq 10^8 ) と s ( 1 \leq s \leq 50 ) が空白区切りで与えられます。

出力

条件を満たす三角形の個数を 1 行で出力してください。

出力の末尾には改行を入れてください。

配点

この問題には部分点が設定されています。

• L \leq 10000 を満たすテストケース全てに正解した場合は、60 点が与えられます。
• 全てのテストケースに正解した場合は、上記とは別に 140 点が与えられます。

入力

入力は以下の形式で標準入力から与えられる。

N
w_1 h_1
w_2 h_2
:
w_N h_N

• 1 行目には、長方形の個数を表す整数 N (3≦N≦10^5) が与えられる。
• 2 行目からの N 行のうち i 行目には、i 番目の長方形の幅と高さを表す整数 w_i,h_i (1≦w_i,h_i≦10^9) が空白区切りで与えられる。

部分点

この問題には部分点が設定されている。

• 3≦N≦8 を満たすデータセットに正解した場合は 15 点が得られる。
• 3≦N≦2,000 を満たすデータセットに正解した場合はさらに 55 点が得られる。
• 3≦N≦10^5 を満たすデータセットに正解した場合はさらに 70 点が得られる。合計で 140 点となる。

出力

N! 通りのコップの容積の和を 10^9+7 で割った余りを出力せよ。 出力の末尾には改行を入れること。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Q
M_1 K_1
v_1_1 v_1_2 ... v_1_{M_1}
:
M_Q K_Q
v_Q_1 v_Q_2 ... v_Q_{M_Q}

• 1 行目には、みさわさんの頂点の個数を表す整数 N (3≦N≦10^5) が与えられる。
• 2 行目からの N-1 行のうち i 行目には、i 番目の辺の接続している 2 頂点を表す整数 a_i,b_i (1≦a_i＜b_i≦N) が空白区切りで与えられる。
  • このとき、みさわさんが木であることが保証されている。
• N+1 行目には、高橋君が実を取りつづける日数を表す整数 Q (1≦Q≦10^5) が与えられる。
• N+2 行目からの 2Q 行のうち、
  • 2i-1 行目には、i 日目にみさわさんがつける実の数を表す整数 M_i と、高橋君が取りたい実の数を表す整数 K_i (1 ≦ K_i ≦ M_i ≦ N) が与えられ、
  • 2i 行目には、i 日目にみさわさんが実をつける頂点を表す M_i 個の整数が与えられる。
• 但し、入力は ΣM_i ≦ 10^5 をみたす。

部分点

この問題には部分点が設定されている。

• 1≦N≦100 を満たすデータセットに正解した場合は 20 点が得られる。
• 全てのデータセットに正解した場合はさらに 110 点が得られる。合計で 130 点となる。

出力

Q 日分の入力について、条件を満たす頂点のうち、根からもっとも遠い頂点までの距離を、 1 行ずつ出力せよ。 出力の末尾には改行を入れること。

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1 a_1
u_2 v_2 a_2
:
u_M v_M a_M

• 1 行目には青木君が用意したグラフの頂点数を表す整数 N (1 ≦ N ≦ 40) と辺数を表す整数 M (1 ≦ M ≦ N×(N-1)/2)が空白区切りで与えられる。
• 2 行目からの M 行のうち i 行目には i 番目の辺が結ぶ 2 つの頂点の番号 u_i, v_i (1 ≦ u_i ＜ v_i ≦ N)と辺に書かれた整数 a_i(1 ≦ a_i ≦ 10^9) が空白区切りで与えられる。
• 与えられるグラフは多重辺や自己ループを含まない。
• a_i(1 ≦ i ≦ N)の値は相異なる。

部分点

この問題には部分点が設定されている。

• 1 ≦ N ≦ 20を満たすデータセットに正解した場合は 90 点が与えられる。
• 1 ≦ N ≦ 40を満たすデータセットに正解した場合はさらに 130 点が与えられる。合計で220点となる。

出力

出力は N 行からなる。 i 行目には高橋君の得点が最大になるように整数を書き込んだ時に i 番目の頂点に書き込まれる正の整数を出力せよ。 各整数の値は 10^9 を超えてはならない。 出力の末尾に改行を入れること。