A - 世界のFizzBuzz

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

数字 N が与えられます。 N に 3 が含まれる、もしくは 3 で割り切れる場合はYES、それ以外は NO と出力してください。

A問題では、提出した結果、全てのテストに対する判定がWAまたはREになってしまった場合のみ、質問タブにて可能な限りのトラブルシューティングを受け付けます。
提出結果のURLを添えて、お気軽にご質問ください。よくある質問も、併せてご活用ください。

入力

入力は以下の形式で標準入力から与えられる。 
N
整数 N(1≦N≦9) が 1 行で与えられる。

出力

N に 3 が含まれる、もしくは 3 で割り切れる場合はYES、それ以外は NO と出力してください。

また、出力の末尾には改行を入れること。

入力例 1

2

出力例 1

NO
  • 2 は 3 で割り切ることができません。また 3 が含まれている数字でもありません。

入力例 2

9

出力例 2

YES
  • 9 は 3 で割り切ることができます。

入力例 3

3

出力例 3

YES
  • 3 は 3 で割り切ることができます。
B - トリボナッチ数列

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

トリボナッチ数列というものがあります。この数列は3つ前までの数字を足したものです。
厳密には、

  1. a_1 = 0, a_2 = 0, a_3 = 1
  2. a_n = a_{n-1} + a_{n-2} + a_{n-3}
と定義されています。参考までに、トリボナッチ数列表を掲載します。

# a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 ... a_n
値 0 0 1 1 2 4 7 13 ... a_{n-1}+a_{n-2}+a_{n-3}

この数列の第 n 項、a_n を 10007 で割った余りを求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
n
整数 n(1≦n≦10^6) が 1 行で与えられる。

出力

トリボナッチ数列の第 n 項、a_n を 10007 で割った余りを 1 行で出力してください。

また、出力の末尾には改行を入れること。

入力例 1

7

出力例 1

7
  • 7 番目のトリボナッチ数は 7 です。

入力例 2

1

出力例 2

0
  • 最初のトリボナッチ数は 0 です。

入力例 3

100000

出力例 3

7927
  • a_n を 10007 で割った余りを出力することに気をつけてください。
C - スフィンクスのなぞなぞ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

新学期に向けて新たな気持ちで通学しているあなたの前に、スフィンクスが立ちふさがっています。
このスフィンクスは「なぞなぞ」を出すことで有名で、このなぞなぞに答えられない場合、留年します。

なぞなぞは以下のとおりです。
「この街には人間が N 人いる。人間は、大人、老人、赤ちゃんの 3 通りだ。
この街にいる人間の、足の数の合計は M 本で、大人の足は 2 本、老人の足は 3 本、赤ちゃんの足は 4 本と仮定した場合、存在する人間の組み合わせとしてあり得るものを 1 つ答えよ。」

新学期早々留年したくないあなたは、このなぞなぞに正解する必要があります。
なぞなぞの答えとなる「この街に存在する人間の組み合わせ」を 1 つ出力してください。
もし、そのような組み合わせが存在しない場合は-1 -1 -1と出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
N M
この街に住んでいる人間の数 N(1≦N≦10^5)、この街に住んでいる人間の足の本数 M(1≦M≦5 \times 10^5) が半角スペース区切りで 1 行で与えられる。
  • N と M は整数である。
  • この問題には部分点が設定されている。後述する部分点の項も参照すること。

出力

なぞなぞの答えとなる「この街に存在する人間の組み合わせ」を 1 つ出力してください。
出力形式は、「大人の数 老人の数 赤ちゃんの数」順番で、半角スペース区切りで 1 行に出力してください。
もし、そのような組み合わせが存在しない場合は -1 -1 -1 と出力してください。

出力の末尾には改行を入れること。

部分点

この問題には 3 つのデータセットがあり、データセット毎に部分点が設定されている。

  • N(1≦N≦100)、M(1≦M≦500) を満たすデータセット全てに正解すると、10 点が与えられる。
  • N(1≦N≦1,500)、M(1≦M≦7,500) を満たすデータセット全てに正解すると、上記のデータセットとは別に 20 点が与えられる。
  • 全てのデータセットに正解すると、100 点が与えられる。

入力例 1

3 9

出力例 1

1 1 1

入力は、人間が 3 人いて、足の数の合計が 9 本であることを示します。

出力は、大人が 1 人、老人が 1 人、赤ちゃんが 1 であることを示しています。

  • 大人 1 人の足の数は 2 本。
  • 老人 1 人の足の数は 3 本。
  • 赤ちゃん 1 人の足の数は 4 本。

人間の数が 3 人で、足の数を 9 本とする組み合わせの例です。

入力例 2

7 23

出力例 2

1 3 3
  • 大人 1 人の足の数は 2 本。
  • 老人 3 人の足の数は 9 本。
  • 赤ちゃん 3 人の足の数は 12 本。

入力例 3

10 41

出力例 3

-1 -1 -1
  • なぞなぞの答えとなる組み合わせは存在しません。
D - トランプ挿入ソート

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

数字が書かれたカードが N 枚あります。このカードの束（山札）に対して以下の操作が可能です。

  • 山札からカードを 1 枚抜き取り、任意の場所に挿入する。

山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
N
c_1
c_2
:
c_N
  1. 1 行目にはカードの枚数を示す整数 N(1≦N≦3 \times 10^4) が与えられる。
  2. 2 行目からは N 行にわたって、山札の初期状態が与えられる。
    • c_i は山札の上から i 番目にあるカードを示す整数で、1≦c_i≦N を満たす。
      • c_1 が山札の一番上にあるカードで、c_N が山札の一番下にあるカードを示す。
    • i \neq j ならば c_i \neq c_j である。つまり、N 枚のカードは全て異なる数字が書かれている。

出力

山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

また、出力の末尾には改行を入れること。

部分点

この問題には 3 つのデータセットがあり、データセット毎に部分点が設定されている。

  • N(1≦N≦16) を満たすデータセット全てに正解すると、10 点が与えられる。
  • N(1≦N≦1,000) を満たすデータセット全てに正解すると、上記のデータセットとは別に 40 点が与えられる。
  • 全てのデータセットに正解すると、100 点が与えられる。

入力例 1

6
1
3
5
2
4
6

出力例 1

2
  • 2 を抜いて 1 と 3 の間に入れます。
  • 5 を抜いて 4 と 6 の間に入れます。

入力例 2

5
5
4
3
2
1

出力例 2

4

入力例 3

7
1
2
3
4
5
6
7

出力例 3

0