AtCoder Daily Training EASY 2025/06/04 18:00start

A - Bitwise Exclusive Or

実行時間制限: 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 である。

例えば、3 \text{ xor } 5 = 6 となります (二進表記すると: 011 \text{ xor } 101 = 110)。

制約

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

入力

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

A B

出力

答えを出力せよ。

入力例 1

3 6

出力例 1

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

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

入力例 2

10 12

出力例 2

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

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

B - Doors in the Center

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

以下の条件を全て満たす長さ N の文字列を求めてください。

各文字は - または = である
回文である
文字列中に = は 1 個または 2 個含まれる。 2 個含まれる場合、それらの = は隣接している

なお、そのような文字列はちょうど 1 つ存在します。

制約

1 \leq N \leq 100
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

-==-

入力例 2

出力例 2

---=---

Score : 100 points

Problem Statement

Find a length-N string that satisfies all of the following conditions:

Each character is - or =.
It is a palindrome.
It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

1 \leq N \leq 100
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

-==-

Sample Input 2

Sample Output 2

---=---

C - Hurdle Parsing

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

いろはちゃんは長さ N ( N \ge 1 ) の正整数列 A=(A_1,A_2,\dots,A_N) を持っています。
いろはちゃんは A を使って、次のように文字列 S を生成しました。

S= | から始める。
i=1,2,\dots,N の順に、次の操作を行う。
- S の末尾に - を A_i 個追加する。
- その後、 S の末尾に | を 1 個追加する。

生成された文字列 S が与えられるので、正整数列 A を復元してください。

制約

S は問題文中の方法で生成された長さ 3 以上 100 以下の文字列
A は長さ 1 以上の正整数列

入力

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

出力

答えを以下の形式で、 1 行に空白区切りで出力せよ。

A_1 A_2 \dots A_N

入力例 1

|---|-|----|-|-----|

出力例 1

3 1 4 1 5

S= |---|-|----|-|-----| が生成されるような A は (3,1,4,1,5) です。

入力例 2

|----------|

出力例 2

入力例 3

|-|-|-|------|

出力例 3

1 1 1 6

Score : 200 points

Problem Statement

Iroha has a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N (N \ge 1).
She generated a string S using A as follows:

Start with S = |.
For i = 1, 2, \dots, N, perform the following operations in order:
- Append A_i copies of - to the end of S.
- Then, append one | to the end of S.

Given the generated string S, reconstruct the sequence A.

Constraints

S is a string of length between 3 and 100, inclusive, generated by the method in the problem statement.
A is a sequence of positive integers of length at least 1.

Input

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

Output

Print the answer in the following format, with elements separated by spaces in a single line:

A_1 A_2 \dots A_N

Sample Input 1

|---|-|----|-|-----|

Sample Output 1

3 1 4 1 5

S = |---|-|----|-|-----| is generated by A = (3, 1, 4, 1, 5).

Sample Input 2

|----------|

Sample Output 2

Sample Input 3

|-|-|-|------|

Sample Output 3

1 1 1 6

D - Number Box

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

正整数 N が与えられます。

N 行 N 列のマス目があり、上から i 行目、左から j 列目のマスには数字 A_{i,j} が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

(1,i) の上のマスは (N,i) であり、(N,i) の下のマスは (1,i) である。(1\le i\le N)
(i,1) の左のマスは (i,N) であり、(i,N) の右のマスは (i,1) である。(1\le i\le N)

高橋君は、上下左右および斜めの 8 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを N-1 回繰り返します。

高橋君は N 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

1 \le N \le 10
1 \le A_{i,j} \le 9
入力はすべて整数。

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君が上から 2 行目、左から 4 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ 9786 を作ることができます。 9786 より大きい値を作ることはできないため、9786 が解です。

入力例 2

出力例 2

1111111111

32bit整数型に答えが収まるとは限らないことに注意してください。

Score : 200 points

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

(N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
(i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

1 \le N \le 10
1 \le A_{i,j} \le 9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Print the answer.

Sample Input 1

Sample Output 1

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

E - Leftover Recipes

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

冷蔵庫に N 種類の材料があります。これらを材料 1、\dots、材料 N と呼びます。材料 i は Q_i グラムあります。

あなたは 2 種類の料理を作れます。料理 A は、1 人分を作るのに各材料 i (1 \leq i \leq N) が A_i グラム必要です。料理 B は、1 人分を作るのに各材料 i が B_i グラム必要です。どちらも整数人分しか作れません。

冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れますか。

制約

1 \leq N \leq 10
1 \leq Q_i \leq 10^6
0 \leq A_i \leq 10^6
A_i \geq 1 であるような i が存在する。
0 \leq B_i \leq 10^6
B_i \geq 1 であるような i が存在する。
入力値はすべて整数である。

入力

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

N
Q_1 Q_2 \dots Q_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

最大で合計 S 人分の料理を作れるとして、整数 S を出力せよ。

入力例 1

出力例 1

この冷蔵庫には、800 グラムの材料 1 と 300 グラムの材料 2 があります。

100 グラムの材料 1 と 100 グラムの材料 2 で料理 A を 1 人分作れ、200 グラムの材料 1 と 10 グラムの材料 2 で料理 B を 1 人分作れます。

料理 A を 2 人分、料理 B を 3 人分作るのに必要な材料 1 の量は 100 \times 2 + 200 \times 3 = 800 グラム、材料 2 の量は 100 \times 2 + 10 \times 3 = 230 グラムで、いずれも冷蔵庫にある量を超えません。このようにして合計 5 人分の料理を作ることができますが、6 人分を作る方法はなく、答えは 5 です。

入力例 2

出力例 2

800 グラムの材料 1 で料理 A を 8 人分、300 グラムの材料 2 で料理 B を 30 人分、合計 38 人分作れます。

入力例 3

出力例 3

何も作れません。

入力例 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

出力例 4

Score: 300 points

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

1 \leq N \leq 10
1 \leq Q_i \leq 10^6
0 \leq A_i \leq 10^6
There is an i such that A_i \geq 1.
0 \leq B_i \leq 10^6
There is an i such that B_i \geq 1.
All input values are integers.

Input

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

N
Q_1 Q_2 \dots Q_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Assuming that you can make a maximum total of S servings of dishes, print the integer S.

Sample Input 1

Sample Output 1

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

Sample Output 2

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

Sample Output 3

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0