AtCoder Daily Training MEDIUM 2024/07/04 16:30start

C - Hard Calculation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 A,B が与えられます。
A+B を(十進法で)計算する時、繰り上がりが生じないなら Easy 、生じるなら Hard と出力してください。

制約

A,B は整数
1 \le A,B \le 10^{18}

入力

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

A B

出力

繰り上がりが生じないなら Easy 、生じるなら Hard と出力せよ。

入力例 1

229 390

出力例 1

Hard

229+390 を計算する際、十の位から百の位へと繰り上がりが発生します。よって、答えは Hard です。

入力例 2

123456789 9876543210

出力例 2

Easy

繰り上がりは発生しません。答えは Easy です。
また、入力が 32bit 整数に収まらないこともあります。

Score : 200 points

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

A and B are integers.
1 \le A,B \le 10^{18}

Input

Input is given from Standard Input in the following format:

A B

Output

If the calculation does not involve a carry, print Easy; if it does, print Hard.

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

D - MissingNo.

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ナオヒロ君は N+1 個の連続する整数を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。

残っている N 個の整数が順不同で A_1,\ldots,A_N として与えられるので、なくした整数を求めてください。

なお、なくした整数が一意に定まるような入力のみが与えられます。

制約

2 \leq N \leq 100
1 \leq A_i \leq 1000
入力は全て整数である
なくした整数は一意に定まる

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 5

出力例 1

ナオヒロ君は初め 2,3,4,5 の 4 個の整数を持っており、4 をなくし、2,3,5 が残っていました。

なくした整数である 4 を出力します。

入力例 2

8
3 1 4 5 9 2 6 8

出力例 2

入力例 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

出力例 3

Score : 200 points

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000
All input values are integers.
The lost integer is uniquely determined.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
2 3 5

Sample Output 1

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

E - 1111gal password

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。

N 桁の正整数である。
X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1

制約

N は整数
2 \le N \le 10^6

入力

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

出力

答えを整数として出力せよ。

入力例 1

出力例 1

4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。

入力例 2

出力例 2

入力例 3

出力例 3

248860093

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

X is an N-digit positive integer.
Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

N is an integer.
2 \le N \le 10^6

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

F - kasaka

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 S の先頭に a をいくつか（ 0 個でも良い）つけ加えて回文にすることができるか判定してください。

ただし、長さ N の文字列 A=A_1A_2\ldots A_N が回文であるとは、すべての 1\leq i\leq N について A_i=A_{N+1-i} が成り立っていることをいいます。

制約

1 \leq \lvert S \rvert \leq 10^6
S は英小文字のみからなる。

入力

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

出力

S の先頭に a をいくつかつけ加えて回文にすることができるならば Yes を、そうでないならば No を出力せよ。

入力例 1

kasaka

出力例 1

Yes

kasaka の先頭に a を 1 つ付け加えることによって、akasaka となり回文となるため Yes を出力します。

入力例 2

atcoder

出力例 2

No

atcoder の先頭に a をいくつ付け加えても回文となる事はありません。

入力例 3

php

出力例 3

Yes

php はそれ自体回文です。S の先頭に付け加える a は 0 個でも許されるため、Yes を出力します。

Score : 300 points

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

1 \leq \lvert S \rvert \leq 10^6
S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

If adding some number of a's (possibly zero) at the beginning of S can make it a palindrome, print Yes; otherwise, print No.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

G - Intersecting Intervals

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個の実数の区間が与えられます。i\,(1 \leq i \leq N) 番目の区間は [l_i,r_i] です。i 番目の区間と j 番目の区間が共通部分を持つような組 (i,j)\,(1\leq i < j \leq N) の個数を求めてください。

制約

2 \leq N \leq 5 \times 10^5
0 \leq l_i < r_i \leq 10^9
入力はすべて整数

入力

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

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

出力

答えを出力せよ。

入力例 1

出力例 1

与えられた区間は [1,5], [7,8], [3,7] です。このうち，1 番目と 3 番目、 2 番目と 3 番目の区間が共通部分を持つため、答えは 2 です。

入力例 2

出力例 2

入力例 3

2
1 2
3 4

出力例 3

Score : 400 points

Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

Constraints

2 \leq N \leq 5 \times 10^5
0 \leq l_i < r_i \leq 10^9
All input values are integers.

Input

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

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

Output

Print the answer.

Sample Input 1

Sample Output 1

The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

Sample Input 2

Sample Output 2

Sample Input 3

2
1 2
3 4