A - お茶

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はお茶のペットボトルが A 本入った箱を買うことにしました。 高橋君は少なくとも B 本のお茶のペットボトルがほしいです。 箱を何箱買えばよいですか。

制約

  • 1 ≤ A, B ≤ 1000

部分点

  • 50 点分のテストケースでは、B は A の倍数である。

入力

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

A B

出力

高橋君が買わなければならない箱の個数の最小値を出力せよ。

入力例1

12 36

出力例1

3

入力例2

12 100

出力例2

9
B - 回転

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N × N のマス目があります。 各マスには o または x という文字が書かれています。 上から i 番目、左から j 番目に書かれている文字は s_{i, j} です。 このマス目を時計回りに 90 度回転してください。

制約

  • 1 ≤ N ≤ 50
  • s_{i, j} は o または x である。

入力

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

N
s_{1, 1} … s_{1, N}
:
s_{N, 1} … s_{N, N}

出力

マス目を時計回りに 90 度回転した結果を出力せよ。 出力は N 行からなる。それぞれの行に N 文字出力せよ。 i 番目の行の j 番目の文字は、回転後の上から i 番目、左から j 番目のマス目を表す。

入力例1

4
ooxx
xoox
xxxx
xxxx

出力例1

xxxo
xxoo
xxox
xxxx
C - 座圧

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 人の人が座っています。 i 番目の人の座圧は a_i です。 すぬけ君は、大小関係を保存したまま座圧のデータを圧縮して保存することにしました。 以下の条件を満たす数列 b_1, …, b_N を求めてください。
  • b_i はすべて非負整数である。
  • a_i < a_j ならば b_i < b_j である。
  • a_i = a_j ならば b_i = b_j である。
  • 上の条件を満たす配列のうち、b_i の最大値が最小となる。
このような条件をみたす b は一意に定まることが知られています。

制約

  • 1 ≤ N ≤ 10^5
  • 0 ≤ a_i ≤ 10^9
  • a_i は整数である。

部分点

  • 30 点分のテストケースでは、1 ≤ N ≤ 10^3 をみたす。
  • 上とは別の 30 点分のテストケースでは、0 ≤ a_i ≤ 10^5 をみたす。

入力

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

N
a_1
:
a_N

出力

N 行出力せよ。i 行目には b_i を出力せよ。

入力例1

5
3
3
1
6
1

出力例1

1
1
0
2
0
D - 塗り絵

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の島があります。 島には 1 から N までの番号がついています。 また、N-1 個の橋があります。 i 番目の橋は a_i 番の島と b_i 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由して到達できることがわかっています。

すぬけ君は、それぞれの島を白または黒に塗ることにしました。 ただし、両端の島が黒で塗られているような橋があってはいけません。 色の塗り方が何通りあるか、10^9+7 で割った余りを求めてください。

制約

  • 2 ≤ N ≤ 10^5
  • 1 ≤ a_i, b_i ≤ N
  • どの島からどの島へも橋をいくつか経由して到達できる

入力

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

N
a_1 b_1
: 
a_{N-1} b_{N-1}

出力

色の塗り方が何通りあるか、10^9+7 で割った余りを出力せよ。

入力例1

5
2 5
1 5
2 4
3 2

出力例1

14

入力例2

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

出力例2

192