A - G1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 国では馬のレースが N 個開催されています。
i 個目のレースには A_i 歳以下の馬が出場できます。
N 個のレースのうち、 K 歳の馬が出場できるレースの個数はいくつですか？

制約

  • 入力は全て整数
  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 1 \le K \le 100

入力

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

N
A_1 A_2 \dots A_N
K

出力

答えを整数として出力せよ。

入力例 1

5
3 1 4 1 5
4

出力例 1

2
  • 1 個目のレースには 3 歳以下の馬が出場できます。
  • 2 個目のレースには 1 歳以下の馬が出場できます。
  • 3 個目のレースには 4 歳以下の馬が出場できます。
  • 4 個目のレースには 1 歳以下の馬が出場できます。
  • 5 個目のレースには 5 歳以下の馬が出場できます。

5 個のレースのうち、 4 歳の馬が出場できるものは 3,5 個目の 2 つです。

入力例 2

1
1
100

出力例 2

0

K 歳の馬が出場できるレースがひとつもない場合もあります。

入力例 3

15
18 89 31 2 15 93 64 78 58 19 79 59 24 50 30
38

出力例 3

8

Score : 100 points

Problem Statement

In AtCoder Kingdom, there are N horse races being held.
Horses aged A_i or younger can participate in the i-th race.
Among the N races, how many races can a K-year-old horse participate in?

Constraints

  • All input values are integers.
  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 1 \le K \le 100

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
K

Output

Output the answer as an integer.

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

2
  • Horses aged 3 or younger can participate in the 1st race.
  • Horses aged 1 or younger can participate in the 2nd race.
  • Horses aged 4 or younger can participate in the 3rd race.
  • Horses aged 1 or younger can participate in the 4th race.
  • Horses aged 5 or younger can participate in the 5th race.

Among the 5 races, a 4-year-old horse can participate in the 3rd and 5th races, which is 2 races.

Sample Input 2

1
1
100

Sample Output 2

0

There may be no races that a K-year-old horse can participate in.

Sample Input 3

15
18 89 31 2 15 93 64 78 58 19 79 59 24 50 30
38

Sample Output 3

8
B - Full Moon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんは満月が好きです。

今日を 1 日目とすると、今日以降で満月を見られる最初の日は M 日目です。以後は P 日ごと、つまり M+P 日目、M+2P 日目、\ldots に満月を見られます。

1 日目から N 日目まで（両端を含む）の中で、高橋くんが満月を見られる日の数を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq M \leq P \leq 2\times 10^5
  • 入力される数値は全て整数

入力

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

N M P

出力

答えを整数として出力せよ。

入力例 1

13 3 5

出力例 1

3

満月を見られる日は、3 日目、8 日目、13 日目、18 日目、\ldots です。

1 日目から 13 日目までの中で高橋くんが満月を見られる日は、3 日目、8 日目、13 日目の 3 個です。

入力例 2

5 6 6

出力例 2

0

高橋くんが満月を見られる日が存在しない場合もあります。

入力例 3

200000 314 318

出力例 3

628

Score : 100 points

Problem Statement

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq M \leq P \leq 2\times 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M P

Output

Print the answer as an integer.

Sample Input 1

13 3 5

Sample Output 1

3

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

0

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

628
C - String Shifting

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。

例えば、abcde に対して左シフトを 1 回行うと bcdea となり、右シフトを 2 回行うと deabc となります。

英小文字からなる空でない文字列 S が与えられます。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • S は英小文字からなる。
  • S の長さは 1 以上 1000 以下である。

入力

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

S

出力

2 行にわたって出力せよ。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ S_{\min}, S_{\max} とおいたとき、1 行目には S_{\min} を、2 行目には S_{\max} を出力せよ。

入力例 1

aaba

出力例 1

aaab
baaa

操作によって、aaab , aaba , abaa , baaa の 4 通りの文字列を得ることができます。 これらのうち辞書順で最小、最大のものはそれぞれ aaab , baaa です。

入力例 2

z

出力例 2

z
z

どのように操作を行っても、得られる文字列は z のみです。

入力例 3

abracadabra

出力例 3

aabracadabr
racadabraab

Score : 200 points

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

  1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
  3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

  • S consists of lowercase English letters.
  • The length of S is between 1 and 1000 (inclusive).

Input

Input is given from Standard Input in the following format:

S

Output

Print two lines. The first line should contain S_{\min}, and the second line should contain S_{\max}. Here, S_{\min} and S_{\max} are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on S.

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab
D - Right Triangle

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

xy 平面上に、同一直線上にない 3 点 A(x_A,y_A), B(x_B,y_B),C(x_C,y_C) があります。三角形 ABC が直角三角形であるかどうか判定してください。

制約

  • -1000\leq x_A,y_A,x_B,y_B,x_C,y_C\leq 1000
  • 3 点 A,B,C は同一直線上にない
  • 入力は全て整数

入力

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

x_A y_A
x_B y_B
x_C y_C

出力

三角形 ABC が直角三角形であるならば Yes を、そうでないならば No を出力せよ。

入力例 1

0 0
4 0
0 3

出力例 1

Yes

三角形 ABC は直角三角形です。

入力例 2

-4 3
2 1
3 4

出力例 2

Yes

三角形 ABC は直角三角形です。

入力例 3

2 4
-3 2
1 -2

出力例 3

No

三角形 ABC は直角三角形ではありません。

Score : 200 points

Problem Statement

In the xy-plane, there are three points A(x_A, y_A), B(x_B, y_B), and C(x_C, y_C) that are not collinear. Determine whether the triangle ABC is a right triangle.

Constraints

  • -1000 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 1000
  • The three points A, B, and C are not collinear.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

x_A y_A
x_B y_B
x_C y_C

Output

Print Yes if the triangle ABC is a right triangle, and No otherwise.

Sample Input 1

0 0
4 0
0 3

Sample Output 1

Yes

The triangle ABC is a right triangle.

Sample Input 2

-4 3
2 1
3 4

Sample Output 2

Yes

The triangle ABC is a right triangle.

Sample Input 3

2 4
-3 2
1 -2

Sample Output 3

No

The triangle ABC is not a right triangle.
E - Enumerate Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

  • i 番目の要素は 1 以上 R_i 以下
  • 総和が K の倍数
数列の辞書順とは？ 数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
  1. |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
  2. ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
    • A_i < B_i

制約

  • 入力は全て整数
  • 1 \le N \le 8
  • 2 \le K \le 10
  • 1 \le R_i \le 5

入力

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

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2



出力すべき数列が無い場合もあります。

この場合、出力は空で構いません。













入力例 3
5 5
2 3 2 3 2












出力例 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







Score : 300 points







Problem Statement
Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.


    

  • The i-th element is between 1 and R_i, inclusive.
    • 

  • The sum of all elements is a multiple of K.
    • 



 What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

    

  1. |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
    2. 

  2. There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:

      

    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
      • 

    • A_i < B_i
      • 

    















Constraints
    

  • All input values are integers.
    • 

  • 1 \le N \le 8
    • 

  • 2 \le K \le 10
    • 

  • 1 \le R_i \le 5
    • 
















Input
The input is given from Standard Input in the following format:


N K
R_1 R_2 \dots R_N












Output
Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):


A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
















Sample Input 1
3 2
2 1 3












Sample Output 1
1 1 2
2 1 1
2 1 3



There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.













Sample Input 2
1 2
1












Sample Output 2


There may be no sequences to print.

In this case, the output can be empty.













Sample Input 3
5 5
2 3 2 3 2












Sample Output 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1