実行時間制限: 2 sec / メモリ制限: 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 である。
制約
- 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.
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
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は、レストランで「AtCoder ドリンク」というドリンクを飲もうとしています。 AtCoder ドリンクは定価である P 円を払えば飲むことができます。
また、高橋君は割引券を持っており、それを使うと AtCoder ドリンクを定価より安い価格である Q 円で飲むことができますが、 その場合には AtCoder ドリンクの他に、N 品ある料理の中から 1 つを追加で注文しなければなりません。 i = 1, 2, \ldots, N について、i 番目の料理の価格は D_i 円です。
高橋君がドリンクを飲むため支払う合計金額の最小値を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq Q \lt P \leq 10^5
- 1 \leq D_i \leq 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P Q D_1 D_2 \ldots D_N
出力
答えを出力せよ。
入力例 1
3 100 50 60 20 40
出力例 1
70
割引券を使用して 2 番目の料理を注文することで、ドリンク代 50 円と料理代 20 円の合計 70 円の支払いで AtCoder ドリンクを飲むことができ、支払う合計金額が最小となります。
入力例 2
3 100 50 60000 20000 40000
出力例 2
100
割引券を使用せず定価の 100 円で AtCoder ドリンクを飲むことで、支払う合計金額が最小となります。
Score : 100 points
Problem Statement
Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.
He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.
Print the minimum total amount of money that he must pay to get the drink.
Constraints
- 1 \leq N \leq 100
- 1 \leq Q \lt P \leq 10^5
- 1 \leq D_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P Q D_1 D_2 \ldots D_N
Output
Print the answer.
Sample Input 1
3 100 50 60 20 40
Sample Output 1
70
If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.
Sample Input 2
3 100 50 60000 20000 40000
Sample Output 2
100
The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
直線上に 7 個の点 A, B, C, D, E, F, G がこの順に並んでいます。(下の図も参考にしてください)
隣り合う点の距離は次の通りです。
- 点 A と点 B の距離は 3
- 点 B と点 C の距離は 1
- 点 C と点 D の距離は 4
- 点 D と点 E の距離は 1
- 点 E と点 F の距離は 5
- 点 F と点 G の距離は 9
2 つの英大文字 p, q が与えられます。p, q は A,B,C,D,E,F,G のいずれかで、 p \neq q が成り立ちます。
点 p と点 q の間の距離を答えてください。
制約
- p, q は
A,B,C,D,E,F,Gのいずれか - p \neq q
入力
入力は以下の形式で標準入力から与えられる。
p q
出力
点 p と点 q の間の距離を出力せよ。
入力例 1
A C
出力例 1
4
点 A と点 C の距離は 3 + 1 = 4 です。
入力例 2
G B
出力例 2
20
点 G と点 B の距離は 9 + 5 + 1 + 4 + 1 = 20 です。
入力例 3
C F
出力例 3
10
Score : 200 points
Problem Statement
There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.
- Between A and B: 3
- Between B and C: 1
- Between C and D: 4
- Between D and E: 1
- Between E and F: 5
- Between F and G: 9
You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.
Constraints
- Each of p and q is
A,B,C,D,E,F, orG. - p \neq q
Input
The input is given from Standard Input in the following format:
p q
Output
Print the distance between the points p and q.
Sample Input 1
A C
Sample Output 1
4
The distance between the points A and C is 3 + 1 = 4.
Sample Input 2
G B
Sample Output 2
20
The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.
Sample Input 3
C F
Sample Output 3
10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。
1 x: A の末尾に x を追加する。2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。
制約
- 1 \leq Q \leq 100
- 1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
- 2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
クエリは以下の 2 つのいずれかの形式である。
1 x
2 k
出力
2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。
入力例 1
5 1 20 1 30 2 1 1 40 2 3
出力例 1
30 20
- 最初 A は空である。
- 1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
- 2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
- 3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
- 4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
- 5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。
Score: 200 points
Problem Statement
You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:
1 x: Append x to the end of A.2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.
Constraints
- 1 \leq Q \leq 100
- In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
- In the second type of query, k is a positive integer not greater than the current length of sequence A.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in one of the following two formats:
1 x
2 k
Output
Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.
Sample Input 1
5 1 20 1 30 2 1 1 40 2 3
Sample Output 1
30 20
- Initially, A is empty.
- The first query appends 20 to the end of A, making A=(20).
- The second query appends 30 to the end of A, making A=(20,30).
- The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
- The fourth query appends 40 to the end of A, making A=(20,30,40).
- The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
英小文字からなる長さ M の文字列 N 個 S_1,S_2,\dots,S_N が与えられます。ここで、S_i は互いに異なります。
これらを並び替えた文字列の列 T_1,T_2,\dots,T_N であって、以下の条件を満たすものが存在するか判定してください。
- 1 \le i \le N-1 を満たす全ての整数 i に対して、T_i を 1 文字だけ別の英小文字に変えて T_{i+1} にすることが出来る。
制約
- 2 \le N \le 8
- 1 \le M \le 5
- S_i は英小文字からなる長さ M の文字列である。(1 \le i \le N)
- S_i は互いに異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 4 bbed abcd abed fbed
出力例 1
Yes
abcd , abed , bbed , fbed の順に並び替えると条件を満たします。
入力例 2
2 5 abcde abced
出力例 2
No
どのように並び替えても条件を満たすことは出来ません。
入力例 3
8 4 fast face cast race fact rice nice case
出力例 3
Yes
Score : 250 points
Problem Statement
You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.
Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:
- for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.
Constraints
- 2 \le N \le 8
- 1 \le M \le 5
- S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
- S_i are pairwise distinct.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print Yes if one can obtain a conforming sequence; print No otherwise.
Sample Input 1
4 4 bbed abcd abed fbed
Sample Output 1
Yes
One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.
Sample Input 2
2 5 abcde abced
Sample Output 2
No
No matter how the strings are rearranged, the condition is never satisfied.
Sample Input 3
8 4 fast face cast race fact rice nice case
Sample Output 3
Yes