A - 足し算

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

正整数 N と、 2 の累乗数 1,2,4,8 があります。

これらのうち、 同じ 2 の累乗数をいくつ使っても良い ので、それらの和が N となるような組み合わせを 1 つ求めてください。 組み合わせが複数考えられる場合は、そのうちのどれを出力しても構いません。

例えば N=5 のとき、5=1+2+2 となることから 1 つの組み合わせとして {1,2,2} が考えられます。

入力

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

N
  • 1 行目には、正整数 N (1 ≦ N ≦ 10) が与えられる。

出力

1 行目に、組み合わせを構成する整数の個数 K を出力せよ。

2 行目から K 行には、組み合わせを構成する K 個の整数をそれぞれ出力せよ。 和がちょうど N になり、組み合わせを構成する各整数が 2 の累乗数であるならば正解として扱われる。それ以外の場合は不正解として扱われる。

末尾の改行を忘れないこと。

入力例1

5

出力例1

3
1
2
2

問題文の例です。5=1+2+2 と表せるので、このように出力すると正解になります。最初に組み合わせを構成する整数の個数である 3 を出力するのを忘れないでください。

他にも、5=1+4 なので、1,4 という組み合わせを出力しても正解となります。

入力例2

1

出力例2

1
1
B - 嘘つきの高橋くん

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町同士を結ぶ何本かの道路が存在し、道路は双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。

高橋君はあなたの家に遊びに行くことにしました。そして、高橋君は町 a から出発して、ちょうど K 回 AtCoder 王国のどこかの町を経由して町 b にあるあなたの家に到着しました。

高橋君は町 a から町 b まで最短経路で移動してきたと主張していますが、あなたには彼が嘘をついているよう思えます。 しかし、あなたは具体的に町同士を結ぶ道路がどのような構成になっているか全く知らないため、高橋君が辿った経路が本当に最短経路なのかどうか判定できません。

あなたは高橋君がどの順番で町を経由したかを聞き出すことに成功しました。ただし、この情報には出発/到着地点である町 a と町 b が含まれません。

あなたはこの情報を元に、高橋君が最短経路で移動していた可能性があるかどうかを出力するプログラムを書くことにしました。 町 a から町 b への最短経路とは、町 a から町 b への移動経路において道路を通る回数が最小となるような経路のことを言います。

高橋君が辿った経路が最短経路となるような町と道路の構成が 1 つでも存在する場合、最短経路で移動した可能性があると言えます。一方、そのような構成がない場合、その可能性は無いと言えます。

入力

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

N
a b
K
P_1 P_2 … P_K
  • 1 行目には、AtCoder 王国に存在する町の個数を表す整数 N(2≦N≦100) が与えられる。
  • 2 行目には、高橋君が出発する町とあなたの家がある町の番号を表す 2 つの整数 a,b(1≦a,b≦N,a≠b) が空白区切りで与えられる。
  • 3 行目には、高橋君の移動において経由した町の個数を表す整数 K (1≦K≦100) が与えられる。
  • 4 行目には、高橋君の移動において経由した町の番号が順番に空白区切りで与えられる。そのうち i(1≦i≦K) 番目の整数は、町 a を出発した後 i 番目に経由した町の番号 P_i(1≦P_i≦N) を表す。
  • \{P_i\} の隣接する要素は全て異なる。つまり全ての j(2≦j≦K)について、P_j≠P_{j-1} が成り立つ。さらに、P_1 ≠ a かつ P_K ≠ b が成り立つ。

出力

1 行目に、高橋君が最短経路で移動していた可能性があるならば YES、その可能性がないならば NO と出力せよ。

末尾の改行を忘れないこと。

入力例1

5
1 5
3
3 4 2

出力例1

YES

たとえば以下のような道路の構成を考えると 1→3→4→2→5 という経路が最短経路となります。

入力例2

7
1 3
4
2 4 2 7

出力例2

NO

1→2→4→2→7→3 という経路が最短経路となるような道路の構成は存在しません。 どのような道路の構成においても、一度訪れた町に再び訪れるような移動は必ず省略できるからです。

入力例3

4
1 4
3
2 1 3

出力例3

NO

1→2→1→3→4 と移動しています。一度出発地点に戻っていますが、そのような移動をしてしまうと最短経路を達成することはできません。

入力例4

4
1 4
3
2 4 3

出力例4

NO

1→2→4→3→4 と移動しています。今度は到着地点に一度辿り着いたのにも関わらず移動しています。

入力例5

20
1 4
12
2 3 5 7 8 9 10 11 12 15 13 14

出力例5

YES
C - 正直者の高橋くん

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町どうしを結ぶ M 本の道路が存在し、それらは双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。 また、M 個の道路はそれぞれ 道路 1,道路 2,…,道路 M と呼ばれています。

高橋君はあなたの家に遊びに行くことにしました。そして、高橋君は町 a から出発して、AtCoder 王国のいくつかの町（0 個でも良い）を経由して町 b にあるあなたの家に到着しました。

高橋君は最短経路を辿ってきたと主張しています。 高橋君は正直なので、絶対に嘘をつきません。

そこで、あなたは町 a から町 b への最短経路が何通りあるかを数えることにしました。答えは非常に大きくなる可能性があるので、実際の答えを 1,000,000,007(=10^9+7) で割った余りを出力してください。

町 a から町 b への最短経路とは、町 a から町 b への移動経路において道路を通る回数が最小となるような経路のことを言います。

入力

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

N
a b
M
x_1 y_1
x_2 y_2
:
x_M y_M
  • 1 行目には、AtCoder 王国に存在する町の個数を表す整数 N(2≦N≦100) が与えられる。
  • 2 行目には、高橋君が出発する町とあなたの家がある町の番号を表す 2 つの整数 a,b(1≦a,b≦N,a≠b) が空白区切りで与えられる。
  • 3 行目には、AtCoder 王国に存在する道路の個数を表す整数 M(1≦M≦200) が与えられる。
  • 4 行目から M 行には、道路の情報が与えられる。そのうち i(1≦i≦M) 行目には道路 i が結んでいる 2 つの町の番号 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) が空白区切りで与えられる。
  • どの町からどの町へもいくつかの道を辿ることによって行くことができる。

出力

1 行目に、町 a から町 b への最短経路の個数を 1,000,000,007 で割った余りを出力してください。

末尾の改行を忘れないこと。

入力例1

7
1 7
8
1 2
1 3
4 2
4 3
4 5
4 6
7 5
7 6

出力例1

4

この入力例に対する図は以下の通りで、最短経路として次の 4 通りが考えられます。

  • 1→2→4→5→7
  • 1→3→4→5→7
  • 1→2→4→6→7
  • 1→3→4→6→7

入力例2

7
1 7
9
1 2
1 3
4 2
4 3
4 5
4 6
7 5
7 6
4 7

出力例2

2

この入力例に対する図は以下の通りです。

D - 多重ループ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

新入社員の高橋君は、とある企業の新人プログラマーとして部署に配属されました。 高橋君が担当した初めての仕事は、以下の擬似コードで表されるプログラムを高速化するというものでした。

n←(標準入力)
ans←0
for i=1..n
  for j=i..n
    ans ← ans+1
ansの値を表示

高橋君にかかってしまえばこんな仕事はお茶の子さいさいです。 各 i に対する内側のループ回数を考えて総和の公式を用いれば ans=n+n-1+…+1=n(n+1)/2 となり、これを用いればすぐ答えが出せます。

劇的な高速化に成功した高橋君への部署からの期待は鰻登りです。そこで、上司は彼に更なる仕事を与えることにしました。

その仕事内容は、以下のような for ループのネストの深さが k の場合におけるプログラムの高速化です。

n←(標準入力)
k←(標準入力)
ans←0
for a_1=1..n
  for a_2=a_1..n
    for a_3=a_2..n
      …
      for a_k=a_{k-1}..n // a_0=1とする
        ans ← ans+1
ansの値を表示

さすがの高橋君もこれには少し悩みました。総和の公式が使えないからです。

いろいろ考えてみたところ、このプログラムの出力する答えは 1≦a_1≦a_2≦…≦a_k≦n であるような整数の組 (a_1,a_2,…,a_k) の個数に等しいということに気づきました。 しかし、彼はそのようなものの個数を数える方法を思いつきませんでした。

彼の同僚であるあなたは、彼の代わりにこの課題をこなすプログラムを作ってあげることにしました。 ただし、答えは非常に大きくなることがあるので、ans の代わりに ans を 1,000,000,007(=10^9+7) で割った余りを出力してください。

入力

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

n
k
  • 1 行目には、整数 n (1 ≦ n ≦ 10^5) が与えられる。
  • 2 行目には、整数 k (1 ≦ k ≦ 10^5) が与えられる。

部分点

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

  • 1≦n≦1000 かつ 1≦k≦1000 であるようなデータセットに正解した場合は 99 点が得られる。
  • 上記のデータセットを含む全てのデータセットに正解した場合はさらに 1 点が得られる。

出力

1 行目に、2 つ目のプログラムにおける最終的な ans の値を 1,000,000,007 で割った余りを出力してください。

末尾の改行を忘れないこと。

入力例1

10
2

出力例1

55

入力例2

10
3

出力例2

220

入力例3

10
4

出力例3

715

入力例4

400
296

出力例4

546898535

入力例5

100000
100000

出力例5

939733670