AtCoder Daily Training EASY 2024/10/10 20:30start

A - 3.14

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

配点 : 100 点

問題文

円周率の小数第 100 位までの値は

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

です。

1 以上 100 以下の整数 N が与えられます。

円周率を小数第 N 位まで出力してください。

より厳密には、円周率を小数第 N+1 位で切り捨て、末尾の 0 を取り除かずに出力してください。

制約

1\leq N\leq 100
N は整数

入力

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

出力

円周率を小数第 N 位まで 1 行で出力せよ。

入力例 1

出力例 1

3.14

円周率を小数第 2+1 位で切り捨てると値は 3.14 になります。よって、3.14 を出力してください。

入力例 2

出力例 2

3.14159265358979323846264338327950

末尾の 0 は取り除かずに出力してください。

入力例 3

出力例 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

Score : 100 points

Problem Statement

The number pi to the 100-th decimal place is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679.

You are given an integer N between 1 and 100, inclusive.

Print the value of pi to the N-th decimal place.

More precisely, truncate the value of pi to N decimal places and print the result without removing the trailing 0s.

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 value of pi to the N-th decimal place in a single line.

Sample Input 1

Sample Output 1

3.14

Truncating the value of pi to 2 decimal places results in 3.14. Thus, you should print 3.14.

Sample Input 2

Sample Output 2

3.14159265358979323846264338327950

Do not remove the trailing 0s.

Sample Input 3

Sample Output 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

B - Majority

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

配点 : 100 点

問題文

ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。

i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。

過半数の人がこの提案に賛成しているかどうかを判定してください。

制約

N は 1 以上 99 以下の奇数
全ての i = 1, 2, \dots, N に対し、S_i = For または S_i = Against

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。

入力例 1

3
For
Against
For

出力例 1

Yes

提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。

入力例 2

5
Against
Against
For
Against
For

出力例 2

No

提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。

入力例 3

1
For

出力例 3

Yes

Score : 100 points

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

N is an odd number between 1 and 99, inclusive.
S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if the majority of the N people agree with the proposal; print No otherwise.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

C - Integer Division

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

配点 : 200 点

問題文

-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lfloor \dfrac{X}{10} \right\rfloor を出力してください。

注記

実数 x に対して、「x 以下の整数の中で最大の整数」を \left\lfloor x \right\rfloor と表します。たとえば \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, \left\lfloor 5 \right\rfloor = 5 のようになります。(詳しくは入出力例にある説明を参考にしてください。)

制約

-10^{18} \leq X \leq 10^{18}
入力はすべて整数である。

入力

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

出力

\left\lfloor \frac{X}{10} \right\rfloor を出力せよ。整数として出力する必要があることに注意せよ。

入力例 1

出力例 1

\frac{47}{10} = 4.7 以下の整数は、すべての負の整数および 0, 1, 2, 3, 4 です。この中で一番大きい整数は 4 なので、\left\lfloor \frac{47}{10} \right\rfloor = 4 となります。

入力例 2

-24

出力例 2

-3

\frac{-24}{10} = -2.4 以下の整数の中で一番大きい整数は -3 なので、 \left\lfloor \frac{-24}{10} \right\rfloor = -3 となります。
-2 は -2.4 よりも大きいので、条件を満たさないことに注意してください。

入力例 3

出力例 3

\frac{50}{10} = 5 以下の整数の中で一番大きい整数は 5 自身です。よって \left\lfloor \frac{50}{10} \right\rfloor = 5 となります。

入力例 4

-30

出力例 4

-3

上の例と同様に \left\lfloor \frac{-30}{10} \right\rfloor = -3 となります。

入力例 5

987654321987654321

出力例 5

98765432198765432

答えは 98765432198765432 となります。すべての桁が正しく合っているか確認しましょう。

なお、もしも自分で書いたプログラムが想定通りの挙動をしない場合は、使用しているプログラミング言語の仕様を調べてみることを推奨します。
また、自分の書いたコードがどのように動作するかを確認したい場合は問題文上部の「コードテスト」をご利用ください。

Score : 200 points

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

-10^{18} \leq X \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print \left\lfloor \frac{X}{10} \right\rfloor. Note that it should be output as an integer.

Sample Input 1

Sample Output 1

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

Sample Output 3

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

D - Minimize Ordering

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

配点 : 200 点

問題文

文字列 S が与えられます。S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力してください。

なお、相異なる 2 つの文字列 s = s_1 s_2 \ldots s_n と t = t_1 t_2 \ldots t_m について、それらが以下の条件のいずれかを満たすとき、辞書順で s \lt t であるとします。

ある整数 i\ (1 \leq i \leq \min(n,m)) が存在し、s_i \lt t_i かつすべての整数 j\ (1 \leq j \lt i) について s_j=t_j
すべての整数 i\ (1 \leq i \leq \min(n,m)) について s_i = t_i かつ、n \lt m

制約

S は英小文字のみからなる長さ 1 以上 2 \times 10^5 以下の文字列

入力

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

出力

S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力せよ。

入力例 1

aba

出力例 1

aab

S= aba を並び替えて得られる文字列は以下の 3 つが考えられます。

aba
aab
baa

この中で辞書順で最小のものは、aab です。

入力例 2

zzzz

出力例 2

zzzz

Score : 200 points

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

Print the lexicographically smallest string S' obtained by permuting the characters in S.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

aba
aab
baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

E - Calendar Validator

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

配点 : 300 点

問題文

10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。

N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を（向きを変えずに）切り出したものであるかを判定してください。

制約

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
入力はすべて整数

入力

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

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

出力

B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。

入力例 1

2 3
1 2 3
8 9 10

出力例 1

Yes

与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。

入力例 2

2 1
1
2

出力例 2

No

与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。

入力例 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

出力例 3

Yes

Score : 300 points

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

1 \leq N \leq 10^4
1 \leq M \leq 7
1 \leq B_{i,j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

Output

If B is some rectangular part of A, print Yes; otherwise, print No.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes