AtCoder Beginner Contest 091

A - Two Coins

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

小学生の高橋君は雑貨店にやってきました。

高橋君は A 円硬貨と B 円硬貨の 2 枚を持っており，C 円のオモチャを買いたいと思っています。高橋君はオモチャを買うことができるでしょうか？

なお，高橋君は高橋王国に住んでいるため，日本円ではありえないような硬貨を持っていることもあります。

制約

入力は全て整数である
1 \leq A, B \leq 500
1 \leq C \leq 1000

入力

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

A B C

出力

オモチャを買えるならば Yes，買えないならば No を出力せよ。

入力例 1

50 100 120

出力例 1

Yes

高橋君は50 + 100 = 150円持っているため，120円のおもちゃが買えます。

入力例 2

500 100 1000

出力例 2

No

高橋君は500 + 100 = 600円持っていますが，1000円のおもちゃは買えません。

入力例 3

19 123 143

出力例 3

No

高橋王国には19円硬貨や123円硬貨も存在します。使いにくいですね。

入力例 4

19 123 142

出力例 4

Yes

Score : 100 points

Problem Statement

An elementary school student Takahashi has come to a variety store.

He has two coins, A-yen and B-yen coins (yen is the currency of Japan), and wants to buy a toy that costs C yen. Can he buy it?

Note that he lives in Takahashi Kingdom, and may have coins that do not exist in Japan.

Constraints

All input values are integers.
1 \leq A, B \leq 500
1 \leq C \leq 1000

Input

Input is given from Standard Input in the following format:

A B C

Output

If Takahashi can buy the toy, print Yes; if he cannot, print No.

Sample Input 1

50 100 120

Sample Output 1

Yes

He has 50 + 100 = 150 yen, so he can buy the 120-yen toy.

Sample Input 2

500 100 1000

Sample Output 2

No

He has 500 + 100 = 600 yen, but he cannot buy the 1000-yen toy.

Sample Input 3

19 123 143

Sample Output 3

No

There are 19-yen and 123-yen coins in Takahashi Kingdom, which are rather hard to use.

Sample Input 4

19 123 142

Sample Output 4

Yes

B - Two Colors Card Game

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

高橋君は青いカードを N 枚，赤いカードを M 枚持っています。カードにはそれぞれ文字列が書かれており， i 枚目の青いカードに書かれている文字列は s_i， i 枚目の赤いカードに書かれている文字列は t_i です。

高橋君は，文字列を 1 つ言います。そして，全てのカードを確認し，その文字列が書かれた青いカードを 1 枚見つけるごとに 1 円貰えます。また，その文字列が書かれた赤いカードを 1 枚見つけるごとに 1 円失います。

なお，高橋君の言った文字列と，カードに書かれた文字列が完全に一致していた場合のみを考えます。例えば，高橋君が atcoder と言った場合，atcoderr，atcode，btcoder などと書かれた青いカードがあってもお金は貰えません(逆に，このような文字列が書かれた赤いカードがあってもお金を失うことはありません)。

高橋君は，最大で差し引き何円貰うことができるでしょうか？

ただし，違うカードに同じ文字列が書かれていることもあることに注意してください。

制約

N, M は整数
1 \leq N, M \leq 100
s_1, s_2, ..., s_N, t_1, t_2, ..., t_M は全て長さ 1 以上 10 以下の文字列で，英小文字のみからなる

入力

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

N
s_1
s_2
:
s_N
M
t_1
t_2
:
t_M

出力

高橋君が最大で差し引き X 円貰える時，X を出力せよ。

入力例 1

3
apple
orange
apple
1
grape

出力例 1

apple と言えば，2 円貰うことができます。

入力例 2

3
apple
orange
apple
5
apple
apple
apple
apple
apple

出力例 2

apple と言うと，3 円失ってしまいます。orange と言えば，1 円貰うことができます。

入力例 3

1
voldemort
10
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort

出力例 3

voldemort と言うと，9 円失ってしまいます。例えば orange と言えば，1 円も失わずにすみます。

入力例 4

6
red
red
blue
yellow
yellow
red
5
red
red
yellow
green
blue

出力例 4

Score : 200 points

Problem Statement

Takahashi has N blue cards and M red cards. A string is written on each card. The string written on the i-th blue card is s_i, and the string written on the i-th red card is t_i.

Takahashi will now announce a string, and then check every card. Each time he finds a blue card with the string announced by him, he will earn 1 yen (the currency of Japan); each time he finds a red card with that string, he will lose 1 yen.

Here, we only consider the case where the string announced by Takahashi and the string on the card are exactly the same. For example, if he announces atcoder, he will not earn money even if there are blue cards with atcoderr, atcode, btcoder, and so on. (On the other hand, he will not lose money even if there are red cards with such strings, either.)

At most how much can he earn on balance?

Note that the same string may be written on multiple cards.

Constraints

N and M are integers.
1 \leq N, M \leq 100
s_1, s_2, ..., s_N, t_1, t_2, ..., t_M are all strings of lengths between 1 and 10 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
s_1
s_2
:
s_N
M
t_1
t_2
:
t_M

Output

If Takahashi can earn at most X yen on balance, print X.

Sample Input 1

3
apple
orange
apple
1
grape

Sample Output 1

He can earn 2 yen by announcing apple.

Sample Input 2

3
apple
orange
apple
5
apple
apple
apple
apple
apple

Sample Output 2

If he announces apple, he will lose 3 yen. If he announces orange, he can earn 1 yen.

Sample Input 3

1
voldemort
10
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort
voldemort

Sample Output 3

If he announces voldemort, he will lose 9 yen. If he announces orange, for example, he can avoid losing a yen.

Sample Input 4

6
red
red
blue
yellow
yellow
red
5
red
red
yellow
green
blue

Sample Output 4

C - 2D Plane 2N Points

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

二次元平面に，赤い点と青い点が N 個ずつあります。 i 個目の赤い点の座標は (a_i, b_i) で，i 個目の青い点の座標は (c_i, d_i) です。

赤い点と青い点は，赤い点の x 座標が青い点の x 座標より小さく，また赤い点の y 座標も青い点の y 座標より小さいとき，仲良しペアになれます。

あなたは最大で何個の仲良しペアを作ることができますか？ただし，1 つの点が複数のペアに所属することはできません。

制約

入力は全て整数
1 \leq N \leq 100
0 \leq a_i, b_i, c_i, d_i < 2N
a_1, a_2, ..., a_N, c_1, c_2, ..., c_N はすべて異なる
b_1, b_2, ..., b_N, d_1, d_2, ..., d_N はすべて異なる

入力

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

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

出力

仲良しペアの個数の最大値を出力せよ。

入力例 1

出力例 1

例えば， (2, 0) と (4, 2) をペアにし， (3, 1) と (5, 5) をペアにすればよいです。

入力例 2

出力例 2

例えば， (0, 0) と (2, 3) をペアにし， (1, 1) と (3, 4) をペアにすればよいです。

入力例 3

出力例 3

一つもペアが作れない場合もあります。

入力例 4

出力例 4

入力例 5

出力例 5

Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points. The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.
1 \leq N \leq 100
0 \leq a_i, b_i, c_i, d_i < 2N
a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.
b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

Sample Output 1

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

Sample Output 2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

Sample Output 3

It is possible that no pair can be formed.

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

D - Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

2 つの長さ N の非負整数列 a_1, ..., a_N, b_1, ..., b_N が与えられます。

1 \leq i, j \leq N となるように整数 i, j を選ぶ方法は N^2 通りありますが，この N^2 通りの i, j それぞれについて，a_i + b_j を計算し，紙に書き出します。つまり，紙に N^2 個の整数を書きます。

この N^2 個の整数のxorを計算してください。

xorの説明

整数 c_1, c_2, ..., c_m のxor X は，以下のように定義されます。

X を 2 進数表記したときの 2^k(0 \leq k, k は整数)の位の値は，c_1, c_2, ...c_m のうち，2 進数表記したときの 2^k の位の値が 1 となるものの個数が奇数個ならば 1，偶数個ならば 0 となります

例えば，3 と 5 のxorの値は，3 の 2 進数表記が 011，5 の 2 進数表記が 101 のため，2 進数表記が 110 の 6 となります。

制約

入力は全て整数
1 \leq N \leq 200,000
0 \leq a_i, b_i < 2^{28}

入力

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

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

出力

求めた結果を出力せよ。

入力例 1

2
1 2
3 4

出力例 1

紙には 4(1+3), 5(1+4), 5(2+3), 6(2+4) の 2^2 = 4 つの数が書かれます。

入力例 2

6
4 6 0 0 3 3
0 5 6 5 0 3

出力例 2

入力例 3

5
1 2 3 4 5
1 2 3 4 5

出力例 3

入力例 4

1
0
0

出力例 4

Score : 500 points

Problem Statement

You are given two integer sequences, each of length N: a_1, ..., a_N and b_1, ..., b_N.

There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N. For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper. That is, we will write N^2 integers in total.

Compute the XOR of these N^2 integers.

Definition of XOR

The XOR of integers c_1, c_2, ..., c_m is defined as follows:

Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.

For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

Constraints

All input values are integers.
1 \leq N \leq 200,000
0 \leq a_i, b_i < 2^{28}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

Output

Print the result of the computation.

Sample Input 1

2
1 2
3 4

Sample Output 1

On the sheet, the following four integers will be written: 4(1+3), 5(1+4), 5(2+3) and 6(2+4).

Sample Input 2

6
4 6 0 0 3 3
0 5 6 5 0 3

Sample Output 2

Sample Input 3

5
1 2 3 4 5
1 2 3 4 5

Sample Output 3

Sample Input 4

1
0
0