A - Bitwise Exclusive Or

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0 以上 255 以下の整数 A,B が与えられます。 A \text{ xor }C=B となる 0 以上の整数 C を求めてください。

なお、そのような C はただ 1 つ存在し、0 以上 255 以下であることが証明されます。

\text{ xor } とは

整数 a, b のビットごとの排他的論理和 a \text{ xor } b は、以下のように定義されます。

  • a \text{ xor } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \text{ xor } 5 = 6 となります (二進表記すると: 011 \text{ xor } 101 = 110)。

制約

  • 0\leq A,B \leq 255
  • 入力に含まれる値は全て整数である

入力

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

A B

出力

答えを出力せよ。

入力例 1

3 6

出力例 1

5

3 は 二進表記で 11、5 は二進表記で 101 なので、これらの \text{xor} は二進表記で 110 であり、十進表記で 6 です。

このように、3 \text{ xor } 5 = 6 となるので、答えは 5 です。

入力例 2

10 12

出力例 2

6

図

Score : 100 points

Problem Statement

You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.

It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:

  • When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
For example, we have 3\ \mathrm{XOR}\ 5 = 6 (in base two: 011\ \mathrm{XOR}\ 101 = 110).

Constraints

  • 0\leq A,B \leq 255
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the answer.

Sample Input 1

3 6

Sample Output 1

5

When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.

In short, 3 \text{ xor } 5 = 6, so the answer is 5.

Sample Input 2

10 12

Sample Output 2

6

Figure
B - Takahashi san

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

キーエンスでは、役割や年齢、立場の違いに関係なく「さん」付けして呼ぶという文化があります。 新入社員が社長を呼ぶときも「中田さん」と呼びます。

ある人の苗字と名前がそれぞれ文字列 S,T として与えられます。

苗字、スペース（ ）、敬称（san）をこの順に連結した文字列を出力してください。

制約

  • S,T は以下の各条件を満たす文字列
    • 長さ 1 以上 10 以下
    • 先頭の文字は英大文字
    • 先頭以外の文字は英小文字

入力

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

S T

出力

苗字、スペース（ ）、敬称（san）をこの順に連結した文字列を出力せよ。

入力例 1

Takahashi Chokudai

出力例 1

Takahashi san

苗字（Takahashi）、スペース（ ）、敬称（san）をこの順に連結した文字列を出力します。

入力例 2

K Eyence

出力例 2

K san

Score : 100 points

Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

  • Each of S and T is a string that satisfies the following conditions.
    • The length is between 1 and 10, inclusive.
    • The first character is an uppercase English letter.
    • All characters except the first one are lowercase English letters.

Input

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

S T

Output

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san
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 - 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 - Ladder Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^9 階建てのビルがあり、N 本のはしごがかかっています。
ビルの 1 階にいる高橋君ははしごを繰り返し使って（0 回でもよい）できるだけ高い階へ上りたいと考えています。
はしごには 1 から N までの番号がついており、はしご i は A_i 階と B_i 階を結んでいます。はしご i を利用すると A_i 階から B_i 階へ、または B_i 階から A_i 階へ双方向に移動することができますが、それ以外の階の間の移動は行うことはできません。
また、高橋君は同じ階での移動は自由に行うことができますが、はしご以外の方法で他の階へ移動することはできません。
高橋君は最高で何階へ上ることができますか？

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • A_i \neq B_i
  • 入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\ldots
A_N B_N

出力

答えを出力せよ。

入力例 1

4
1 4
4 3
4 10
8 3

出力例 1

10

はしご 1 で 4 階に進み、はしご 3 で 10 階に進むことにより、10 階にたどり着くことができます。

入力例 2

6
1 3
1 5
1 12
3 5
3 12
5 12

出力例 2

12

入力例 3

3
500000000 600000000
600000000 700000000
700000000 800000000

出力例 3

1

他の階への移動ができない場合もあります。

Score : 300 points

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • A_i \neq B_i
  • All values in the input are integers.

Input

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

N
A_1 B_1
A_2 B_2
\ldots
A_N B_N

Output

Print an integer representing the answer.

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.