A - Five Integers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

与えられる 5 つの整数 A, B, C, D, E の中に何種類の整数があるかを出力してください。

制約

  • 0 \leq A, B, C, D, E \leq 100
  • 入力はすべて整数

入力

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

A B C D E

出力

答えを出力せよ。

入力例 1

31 9 24 31 24

出力例 1

3

与えられる 5 つの整数 31, 9, 24, 31, 24 の中には、9, 24, 31 という 3 種類の整数があります。 よって、3 を出力します。

入力例 2

0 0 0 0 0

出力例 2

1

Score : 100 points

Problem Statement

Print how many distinct integers there are in given five integers A, B, C, D, and E.

Constraints

  • 0 \leq A, B, C, D, E \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

Print the answer.

Sample Input 1

31 9 24 31 24

Sample Output 1

3

In the given five integers 31, 9, 24, 31, and 24, there are three distinct integers 9, 24, and 31. Thus, 3 should be printed.

Sample Input 2

0 0 0 0 0

Sample Output 2

1
B - Echo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の英小文字からなる文字列 S が与えられます。
S の i 文字目を S_i と記します。
S_1,S_1,S_2,S_2,\dots,S_N,S_N をこの順に連結した長さ 2N の文字列を出力してください。
例えば、 S が beginner のときは bbeeggiinnnneerr と出力してください。

制約

  • N は 1 \le N \le 50 を満たす整数
  • S は長さ N の英小文字からなる文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
beginner

出力例 1

bbeeggiinnnneerr

問題文中の例と同じです。

入力例 2

3
aaa

出力例 2

aaaaaa

Score : 100 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

  • N is an integer such that 1 \le N \le 50.
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa
C - Pasta

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君の家には N 本の麺からなるパスタがあり、i 本目の麺の長さは A_i です。
高橋君はこれから M 日間の食事計画を立てており、 i 日目にはパスタの麺のうち長さがちょうど B_i であるようなものを 1 本選び、食べようと考えています。 もし、1 日目から M 日目の間に 1 日でもそのような麺が無い日があれば、食事計画は失敗となります。 また、同じ麺を複数の日に食べることはできません。

高橋君が食事計画を最後まで実行することは可能ですか？

制約

  • 1 \leq M \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数である。

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

高橋君が食事計画を最後まで実行できる場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

3 2
1 1 3
3 1

出力例 1

Yes

1 日目に 3 本目の麺を、2 日目に 1 本目の麺を食べれば良いので、高橋君の食事計画は実行可能です。

入力例 2

1 1
1000000000
1

出力例 2

No

長さがちょうど 1 の麺が存在する必要があります。

入力例 3

5 2
1 2 3 4 5
5 5

出力例 3

No

長さが 5 の麺は 1 本しか存在しないため、2 日目に食事をとる事が出来ません。

Score : 200 points

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

  • 1 \leq M \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

If Takahashi can accomplish his meal plan, print Yes; otherwise, print No.

Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.

Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.

Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.
D - The Middle Day

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 国の暦では、一年は 1,2,\dots,M 番目の月の M か月からなり、そのうち i 番目の月は 1,2,\dots,D_i 番目の日の D_i 日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち D_1+D_2+\dots+D_M は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、 1 番目の月の 1 番目の日を 1 日目としたときの (D_1+D_2+\dots+D_M+1)/2 日目が何番目の月の何番目の日かを求めてください。

制約

  • 入力は全て整数
  • 1 \le M \le 100
  • 1 \le D_i \le 100
  • D_1 + D_2 + \dots + D_M は奇数

入力

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

M
D_1 D_2 \dots D_M

出力

答えが a 番目の月の b 番目の日であるとき、以下の形式で出力せよ。

a b

入力例 1

12
31 28 31 30 31 30 31 31 30 31 30 31

出力例 1

7 2

この入力では、 1 年は 31+28+31+30+31+30+31+31+30+31+30+31=365 日からなります。
真ん中の日は (365+1)/2 = 183 日目であり、これを求めることを考えます。

  • 1,2,3,4,5,6 番目の月に含まれる日数の合計は 181 日です。
  • 7 番目の月の 1 番目の日は 182 日目です。
  • 7 番目の月の 2 番目の日は 183 日目です。

以上から、答えが 7 番目の月の 2 番目の日であることが分かります。

入力例 2

1
1

出力例 2

1 1

入力例 3

6
3 1 4 1 5 9

出力例 3

5 3

Score : 200 points

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

  • All input values are integers.
  • 1 \le M \le 100
  • 1 \le D_i \le 100
  • D_1 + D_2 + \dots + D_M is odd.

Input

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

M
D_1 D_2 \dots D_M

Output

Let the answer be day b of month a, and print it in the following format:

a b

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

  • Months 1,2,3,4,5,6 contain a total of 181 days.
  • Day 1 of month 7 is the 182-th day.
  • Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3
E - ±1 Operation 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 X が与えられます。この X に以下を施すことを「操作」と呼びます。

  • 以下の 2 つのうちどちらかを選択し、実行する。
    • X に 1 を加算する。
    • X から 1 を減算する。

初項 A 、公差 D 、項数 N の等差数列 S に含まれる数を「良い数」と呼びます。
「操作」を 0 回以上何度でも使って X を「良い数」にする時、必要な「操作」の最小回数を求めてください。

制約

  • 入力は全て整数
  • -10^{18} \le X,A \le 10^{18}
  • -10^6 \le D \le 10^6
  • 1 \le N \le 10^{12}

入力

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

X A D N

出力

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

入力例 1

6 2 3 3

出力例 1

1

A=2,D=3,N=3 であるため、 S=(2,5,8) です。
X=6 を「良い数」にするためには、 X から 1 を減算することを 1 度行えば良いです。
0 回の操作で X を「良い数」にすることはできません。

入力例 2

0 0 0 1

出力例 2

0

D=0 である場合もあります。また、操作を 1 回も必要としない場合もあります。

入力例 3

998244353 -10 -20 30

出力例 3

998244363

入力例 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

出力例 4

444445

Score : 300 points

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

  • Choose and do one of the following.
    • Add 1 to X.
    • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

  • All values in input are integers.
  • -10^{18} \le X,A \le 10^{18}
  • -10^6 \le D \le 10^6
  • 1 \le N \le 10^{12}

Input

Input is given from Standard Input in the following format:

X A D N

Output

Print the answer as an integer.

Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445