実行時間制限: 2 sec / メモリ制限: 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
実行時間制限: 2 sec / メモリ制限: 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
2
apple
と言えば,2 円貰うことができます。
入力例 2
3 apple orange apple 5 apple apple apple apple apple
出力例 2
1
apple
と言うと,3 円失ってしまいます。orange
と言えば,1 円貰うことができます。
入力例 3
1 voldemort 10 voldemort voldemort voldemort voldemort voldemort voldemort voldemort voldemort voldemort voldemort
出力例 3
0
voldemort
と言うと,9 円失ってしまいます。例えば orange
と言えば,1 円も失わずにすみます。
入力例 4
6 red red blue yellow yellow red 5 red red yellow green blue
出力例 4
1
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
2
He can earn 2 yen by announcing apple
.
Sample Input 2
3 apple orange apple 5 apple apple apple apple apple
Sample Output 2
1
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
0
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
1
実行時間制限: 2 sec / メモリ制限: 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
3 2 0 3 1 1 3 4 2 0 4 5 5
出力例 1
2
例えば, (2, 0) と (4, 2) をペアにし, (3, 1) と (5, 5) をペアにすればよいです。
入力例 2
3 0 0 1 1 5 2 2 3 3 4 4 5
出力例 2
2
例えば, (0, 0) と (2, 3) をペアにし, (1, 1) と (3, 4) をペアにすればよいです。
入力例 3
2 2 2 3 3 0 0 1 1
出力例 3
0
一つもペアが作れない場合もあります。
入力例 4
5 0 0 7 3 2 2 4 8 1 6 8 5 6 9 5 4 9 1 3 7
出力例 4
5
入力例 5
5 0 0 1 1 5 5 6 6 7 7 2 2 3 3 4 4 8 8 9 9
出力例 5
4
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
3 2 0 3 1 1 3 4 2 0 4 5 5
Sample Output 1
2
For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).
Sample Input 2
3 0 0 1 1 5 2 2 3 3 4 4 5
Sample Output 2
2
For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).
Sample Input 3
2 2 2 3 3 0 0 1 1
Sample Output 3
0
It is possible that no pair can be formed.
Sample Input 4
5 0 0 7 3 2 2 4 8 1 6 8 5 6 9 5 4 9 1 3 7
Sample Output 4
5
Sample Input 5
5 0 0 1 1 5 5 6 6 7 7 2 2 3 3 4 4 8 8 9 9
Sample Output 5
4
実行時間制限: 3 sec / メモリ制限: 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
2
紙には 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
8
入力例 3
5 1 2 3 4 5 1 2 3 4 5
出力例 3
2
入力例 4
1 0 0
出力例 4
0
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
2
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
8
Sample Input 3
5 1 2 3 4 5 1 2 3 4 5
Sample Output 3
2
Sample Input 4
1 0 0
Sample Output 4
0