AtCoder Beginner Contest 171

A - αlphabet

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

英大文字か英小文字のいずれか 1 文字 \alpha が入力されます。\alpha が英大文字なら A、英小文字なら a と出力してください。

制約

\alpha は英大文字 (A - Z) または英小文字 (a - z) である。

入力

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

α

出力

\alpha が英大文字なら A、英小文字なら a を出力せよ。

入力例 1

出力例 1

B は英大文字であるため、A と出力します。

入力例 2

出力例 2

a は英小文字であるため、a と出力します。

Score : 100 points

Problem Statement

An uppercase or lowercase English letter \alpha will be given as input. If \alpha is uppercase, print A; if it is lowercase, print a.

Constraints

\alpha is an uppercase (A - Z) or lowercase (a - z) English letter.

Input

Input is given from Standard Input in the following format:

α

Output

If \alpha is uppercase, print A; if it is lowercase, print a.

Sample Input 1

Sample Output 1

B is uppercase, so we should print A.

Sample Input 2

Sample Output 2

a is lowercase, so we should print a.

B - Mix Juice

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

ある店で N 種類の果物、果物 1, \ldots, N が売られており、それぞれの価格は一個あたり p_1, \ldots, p_N 円です。

この店で K 種類の果物を一個ずつ買うとき、それらの合計価格として考えられる最小の金額を求めてください。

制約

1 \leq K \leq N \leq 1000
1 \leq p_i \leq 1000
入力中の値はすべて整数である。

入力

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

N K
p_1 p_2 \ldots p_N

出力

果物の最小の合計価格を表す整数を出力せよ。

入力例 1

5 3
50 100 80 120 80

出力例 1

この店では、果物 1, 2, 3, 4, 5 がそれぞれ 50 円、100 円、80 円、120 円、80 円で売られています。

これらから 3 種類を買うときの最小合計価格は、果物 1, 3, 5 を買うときの 50 + 80 + 80 = 210 円です。

入力例 2

1 1
1000

出力例 2

Score : 200 points

Problem Statement

A shop sells N kinds of fruits, Fruit 1, \ldots, N, at prices of p_1, \ldots, p_N yen per item, respectively. (Yen is the currency of Japan.)

Here, we will choose K kinds of fruits and buy one of each chosen kind. Find the minimum possible total price of those fruits.

Constraints

1 \leq K \leq N \leq 1000
1 \leq p_i \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 p_2 \ldots p_N

Output

Print an integer representing the minimum possible total price of fruits.

Sample Input 1

5 3
50 100 80 120 80

Sample Output 1

This shop sells Fruit 1, 2, 3, 4, and 5 for 50 yen, 100 yen, 80 yen, 120 yen, and 80 yen, respectively.

The minimum total price for three kinds of fruits is 50 + 80 + 80 = 210 yen when choosing Fruit 1, 3, and 5.

Sample Input 2

1 1
1000

Sample Output 2

C - One Quadrillion and One Dalmatians

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

ロジャーは、彼のもとに突如現れた 1000000000000001 匹の犬をすべて飼うことを決意しました。犬たちにはもともと 1 から 1000000000000001 までの番号がふられていましたが、ロジャーは彼らに以下のルールで名前を授けました。

1,2,\cdots,26 番の番号がついた犬はその順に a,b,...,z と命名されます。
27,28,29,\cdots,701,702 番の番号がついた犬はその順に aa,ab,ac,...,zy,zz と命名されます。
703,704,705,\cdots,18277,18278 番の番号がついた犬はその順に aaa,aab,aac,...,zzy,zzz と命名されます。
18279,18280,18281,\cdots,475253,475254 番の番号がついた犬はその順に aaaa,aaab,aaac,...,zzzy,zzzz と命名されます。
475255,475256,\cdots 番の番号がついた犬はその順に aaaaa,aaaab,... と命名されます。
(以下省略)

つまり、ロジャーが授けた名前を番号順に並べると:

a,b,...,z,aa,ab,...,az,ba,bb,...,bz,...,za,zb,...,zz,aaa,aab,...,aaz,aba,abb,...,abz,...,zzz,aaaa,... のようになります。

ロジャーはあなたに問題を出しました。

「番号 N の犬の名前を答えよ。」

制約

N は整数
1 \leq N \leq 1000000000000001

入力

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

出力

ロジャーの問題に対する答えを、英小文字のみからなる文字列として出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

aa

入力例 3

123456789

出力例 3

jjddja

Score : 300 points

Problem Statement

1000000000000001 dogs suddenly appeared under the roof of Roger's house, all of which he decided to keep. The dogs had been numbered 1 through 1000000000000001, but he gave them new names, as follows:

the dogs numbered 1,2,\cdots,26 were respectively given the names a, b, ..., z;
the dogs numbered 27,28,29,\cdots,701,702 were respectively given the names aa, ab, ac, ..., zy, zz;
the dogs numbered 703,704,705,\cdots,18277,18278 were respectively given the names aaa, aab, aac, ..., zzy, zzz;
the dogs numbered 18279,18280,18281,\cdots,475253,475254 were respectively given the names aaaa, aaab, aaac, ..., zzzy, zzzz;
the dogs numbered 475255,475256,\cdots were respectively given the names aaaaa, aaaab, ...;
and so on.

To sum it up, the dogs numbered 1, 2, \cdots were respectively given the following names:

a, b, ..., z, aa, ab, ..., az, ba, bb, ..., bz, ..., za, zb, ..., zz, aaa, aab, ..., aaz, aba, abb, ..., abz, ..., zzz, aaaa, ...

Now, Roger asks you:

"What is the name for the dog numbered N?"

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print the answer to Roger's question as a string consisting of lowercase English letters.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

aa

Sample Input 3

123456789

Sample Output 3

jjddja

D - Replacing

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

あなたは、N 個の正整数 A_{1}, A_{2}, \cdots, A_{N} からなる数列 A を持っています。

あなたは、これから以下の操作を Q 回、続けて行います。

i 回目の操作では、値が B_{i} である要素すべてを C_{i} に置き換えます。

すべての i (1 \leq i \leq Q) に対して、i 回目の操作が行われた後の数列 A のすべての要素の和、S_{i} を求めてください。

制約

入力は全て整数
1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}
B_{i} \neq C_{i}

入力

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

N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

出力

Q 個の整数 S_{i} を以下の形式で標準出力に出力せよ。

S_{1}
S_{2}
\vdots
S_{Q}

S_{i} は 32 ビット整数に収まらない可能性があることに注意せよ。

入力例 1

出力例 1

11
12
16

はじめ、数列 A は 1,2,3,4 です。

各操作後、数列 A は以下のようになります。

2, 2, 3, 4
2, 2, 4, 4
4, 4, 4, 4

入力例 2

出力例 2

8
4
4

数列 A に要素の値が B_{i} であるものが 1 つも含まれていない可能性もあることに注意してください。

入力例 3

出力例 3

102
200
2000

Score : 400 points

Problem Statement

You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.

You will now successively do the following Q operations:

In the i-th operation, you replace every element whose value is B_{i} with C_{i}.

For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

Constraints

All values in input are integers.
1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}
B_{i} \neq C_{i}

Input

Input is given from Standard Input in the following format:

N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

Output

Print Q integers S_{i} to Standard Output in the following format:

S_{1}
S_{2}
\vdots
S_{Q}

Note that S_{i} may not fit into a 32-bit integer.

Sample Input 1

Sample Output 1

11
12
16

Initially, the sequence A is 1,2,3,4.

After each operation, it becomes the following:

2, 2, 3, 4
2, 2, 4, 4
4, 4, 4, 4

Sample Input 2

Sample Output 2

8
4
4

Note that the sequence A may not contain an element whose value is B_{i}.

Sample Input 3

Sample Output 3

102
200
2000

E - Red Scarf

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

猫のすぬけくんが N (\textbf{偶数}) 匹います。各すぬけくんには 1, 2, \ldots, N の番号が振られています。

各すぬけくんは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が 1 つ書き込まれています。

すぬけくんたちは最近、整数の xor（排他的論理和）と呼ばれる演算を覚えました。

xor とは

n 個の非負整数 x_1,x_2, \ldots, x_n について、それらの xor、 x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n は以下のように定義されます。

x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n を二進表記した際の 2^k(k \geq 0) の位の数は、x_1,x_2, \ldots, x_n のうち、二進表記した際の 2^k(k \geq 0) の位の数が 1 となるものの個数が奇数ならば 1、そうでなければ 0 となる。

例えば、3~\textrm{xor}~5 = 6 となります。

早速この演算を使いたくなったすぬけくんたちは、自分以外のすぬけくんのスカーフに書かれた整数の xor を計算することにしました。

番号 i が振られたすぬけくんが計算した、自分以外のすぬけくんのスカーフに書かれた整数の xor が a_i であることが分かっています。この情報を元に、各すぬけくんのスカーフに書かれた整数を特定してください。

制約

入力はすべて整数である
2 \leq N \leq 200000
N は\textbf{偶数}
0 \leq a_i \leq 10^9
与えられた情報と整合するようなスカーフ上の整数の組合せが存在する

入力

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

N
a_1 a_2 \ldots a_N

出力

1 行に N 個の整数を空白区切りで出力せよ。

このうち左から i 番目の整数は、番号 i が振られたすぬけくんのスカーフに書かれた整数を表すものとする。

与えられた条件を満たす解が複数存在する場合、どれを出力しても構わない。

入力例 1

4
20 11 9 24

出力例 1

26 5 7 22

5~\textrm{xor}~7~\textrm{xor}~22 = 20
26~\textrm{xor}~7~\textrm{xor}~22 = 11
26~\textrm{xor}~5~\textrm{xor}~22 = 9
26~\textrm{xor}~5~\textrm{xor}~7 = 24

より、この出力は与えられた情報と整合します。

Score : 500 points

Problem Statement

There are N Snuke Cats numbered 1, 2, \ldots, N, where N is even.

Each Snuke Cat wears a red scarf, on which his favorite non-negative integer is written.

Recently, they learned the operation called xor (exclusive OR).

What is xor?

For n non-negative integers x_1, x_2, \ldots, x_n, their xor, x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n is defined as follows:

When x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.

For example, 3~\textrm{xor}~5 = 6.

They wanted to use this operation quickly, so each of them calculated the xor of the integers written on their scarfs except his scarf.

We know that the xor calculated by Snuke Cat i, that is, the xor of the integers written on the scarfs except the scarf of Snuke Cat i is a_i. Using this information, restore the integer written on the scarf of each Snuke Cat.

Constraints

All values in input are integers.
2 \leq N \leq 200000
N is even.
0 \leq a_i \leq 10^9
There exists a combination of integers on the scarfs that is consistent with the given information.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print a line containing N integers separated with space.

The i-th of the integers from the left should represent the integer written on the scarf of Snuke Cat i.

If there are multiple possible solutions, you may print any of them.

Sample Input 1

4
20 11 9 24

Sample Output 1

26 5 7 22

5~\textrm{xor}~7~\textrm{xor}~22 = 20
26~\textrm{xor}~7~\textrm{xor}~22 = 11
26~\textrm{xor}~5~\textrm{xor}~22 = 9
26~\textrm{xor}~5~\textrm{xor}~7 = 24

Thus, this output is consistent with the given information.

F - Strivore

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600 点

問題文

「好きな英小文字 1 文字を好きな位置に挿入する」という操作を文字列 S にちょうど K 回繰り返してできる文字列は何通りあるでしょう？

答えは非常に大きくなる可能性があるので、(10^9+7) で割ったあまりを出力してください。

制約

K は 1 以上 10^6 以下の整数
S は英小文字からなる長さ 1 以上 10^6 以下の文字列

入力

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

K
S

出力

条件を満たす文字列の個数を (10^9+7) で割ったあまりを出力せよ。

入力例 1

5
oof

出力例 1

575111451

たとえば、proofend、moonwolf、onionpuf などが条件を満たします。

それに対し、oofsix、oofelevennn、voxafolt、fooooooo などは条件を満たしません。

入力例 2

37564
whydidyoudesertme

出力例 2

318008117

Score: 600 points

Problem Statement

How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?

The answer can be enormous, so print it modulo (10^9+7).

Constraints

K is an integer between 1 and 10^6 (inclusive).
S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

K
S

Output

Print the number of strings satisfying the condition, modulo (10^9+7).

Sample Input 1

5
oof

Sample Output 1

575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.

Sample Input 2

37564
whydidyoudesertme

Sample Output 2

318008117