A - Weird Function

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。

制約

  • t は 0 以上 10 以下の整数である

入力

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

t

出力

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


入力例 1

0

出力例 1

1371

答えは以下の手順によって計算されます。

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

入力例 2

3

出力例 2

722502

入力例 3

10

出力例 3

1111355571

Score : 100 points

Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

  • t is an integer between 0 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

t

Output

Print the answer as an integer.


Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571
B - Divisible

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N,K 及び長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。

制約

  • 1\leq N,K\leq 100
  • 1\leq A_1 < A_2 < \ldots < A_N \leq 100
  • A には K の倍数が 1 個以上含まれる
  • 入力される数値は全て整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

A に含まれる要素のうち、K の倍数であるもの全てを K で割った値を、空白区切りで昇順に出力せよ。


入力例 1

5 2
2 5 6 7 10

出力例 1

1 3 5

A に含まれる要素のうち、2 の倍数は 2,6,10 です。それらを 2 で割って得られる 1,3,5 を空白区切りで昇順に出力してください。


入力例 2

3 1
3 4 7

出力例 2

3 4 7

入力例 3

5 10
50 51 54 60 65

出力例 3

5 6

Score: 100 points

Problem Statement

You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

  • 1\leq N,K\leq 100
  • 1\leq A_1 < A_2 < \ldots < A_N \leq 100
  • A has at least one multiple of K.
  • All given numbers are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Divide all elements of A that are multiples of K and print the quotients in ascending order with spaces in between.


Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.


Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6
C - Inverse Prefix Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 N と長さ N の数列 S=(S_1,\ldots,S_N) が与えられます。

長さ N の数列 A=(A_1,\ldots,A_N) であって、k=1,\ldots,N の全てについて以下の条件を満たすものを求めてください。

  • A_1+A_2+\ldots+A_k = S_k

なお、このような数列 A は必ず存在し、一意に定まります。

制約

  • 1 \leq N \leq 10
  • -10^9\leq S_i \leq 10^9
  • 入力は全て整数である

入力

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

N
S_1 \ldots S_N

出力

全ての条件を満たす数列 A=(A_1,\ldots,A_N) の各要素を、順に空白区切りで出力せよ。


入力例 1

3
3 4 8

出力例 1

3 1 4
  • A_1=3=S_1
  • A_1+A_2=3+1=4=S_2
  • A_1+A_2+A_3=3+1+4=8=S_3

であり、たしかに全ての条件を満たしています。


入力例 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

出力例 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381

Score : 200 points

Problem Statement

You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.

Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:

  • A_1+A_2+\ldots+A_k = S_k.

Such a sequence A always exists and is unique.

Constraints

  • 1 \leq N \leq 10
  • -10^9\leq S_i \leq 10^9
  • All values in the input are integers.

Input

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

N
S_1 \ldots S_N

Output

Print the elements of a sequence A=(A_1,\ldots,A_N) that satisfies all the conditions in order, separated by spaces.


Sample Input 1

3
3 4 8

Sample Output 1

3 1 4

The sequence in the output actually satisfies all the conditions:

  • A_1=3=S_1;
  • A_1+A_2=3+1=4=S_2;
  • A_1+A_2+A_3=3+1+4=8=S_3.

Sample Input 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

Sample Output 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381
D - Same Name

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人がいます。i \, (1 \leq i \leq N) 人目の人の姓は S_i、名は T_i です。

同姓同名であるような人の組が存在するか、すなわち 1 \leq i \lt j \leq N かつ S_i=S_j かつ T_i=T_j を満たすような整数対 (i,j) が存在するか判定してください。

制約

  • 2 \leq N \leq 1000
  • N は整数
  • S_i,T_i は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

出力

同姓同名であるような人の組が存在するなら Yes を、存在しないなら No を出力せよ。


入力例 1

3
tanaka taro
sato hanako
tanaka taro

出力例 1

Yes

1 人目の人と 3 人目の人が同姓同名です。


入力例 2

3
saito ichiro
saito jiro
saito saburo

出力例 2

No

同姓同名であるような人の組は存在しません。


入力例 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

出力例 3

No

Score : 200 points

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

  • 2 \leq N \leq 1000
  • N is an integer.
  • Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Input

Input is given from Standard Input in the following format:

N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N

Output

If there is a pair of people with the same family and given names, print Yes; otherwise, print No.


Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.


Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.


Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No
E - 321-like Searcher

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす正整数 x を 321-like Number と呼びます。 この定義は A 問題と同様です。

  • x の各桁を上から見ると狭義単調減少になっている。
  • すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
    • ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。

例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。

K 番目に小さい 321-like Number を求めてください。

制約

  • 入力は全て整数
  • 1 \le K
  • 321-like Number は K 個以上存在する

入力

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

K

出力

K 番目に小さい 321-like Number を整数として出力せよ。


入力例 1

15

出力例 1

32

321-like Number は小さいものから順に (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) です。
このうち 15 番目に小さいものは 32 です。


入力例 2

321

出力例 2

9610

入力例 3

777

出力例 3

983210

Score : 300 points

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

  • The digits of x are strictly decreasing from top to bottom.
  • In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
    • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

  • All input values are integers.
  • 1 \le K
  • At least K 321-like Numbers exist.

Input

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

K

Output

Print the K-th smallest 321-like Number as an integer.


Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.


Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210