AtCoder Beginner Contest 106

A - Garden

Time Limit: 2 sec / Memory Limit: 976 MB

配点: 100 点

問題文

縦 A ヤード、横 B ヤードの畑がある. 農夫ジョンは, 畑の内部に, 畑の上端と下端を結ぶ縦方向の幅 1 ヤードの道, 畑の左端と畑の右端を結ぶ横方向の幅 1 ヤードの道を作った. 畑は下図のようになっている. (灰色の部分が道)

さて, 道を除いた畑の面積は, 何平方ヤードだろうか? 求めなさい.

注意

道の位置が変わっても, 道を除く畑の面積が変わらないことが証明できます.

制約

A は 2 以上 100 以下の整数
B は 2 以上 100 以下の整数

入力

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

A B

出力

道を除いた畑の面積 (平方ヤード) を出力しなさい.

入力例 1

2 2

出力例 1

この場合, 面積は 1 平方ヤードになる.

入力例 2

5 7

出力例 2

この場合, 面積は 24 平方ヤードになる.

Score: 100 points

Problem Statement

There is a farm whose length and width are A yard and B yard, respectively. A farmer, John, made a vertical road and a horizontal road inside the farm from one border to another, as shown below: (The gray part represents the roads.)

What is the area of this yard excluding the roads? Find it.

Note

It can be proved that the positions of the roads do not affect the area.

Constraints

A is an integer between 2 and 100 (inclusive).
B is an integer between 2 and 100 (inclusive).

Input

Input is given from Standard Input in the following format:

A B

Output

Print the area of this yard excluding the roads (in square yards).

Sample Input 1

2 2

Sample Output 1

In this case, the area is 1 square yard.

Sample Input 2

5 7

Sample Output 2

In this case, the area is 24 square yards.

B - 105

Time Limit: 2 sec / Memory Limit: 976 MB

配点: 200 点

問題文

105 という数は, 非常に特殊な性質を持つ - 奇数なのに, 約数が 8 個もある.
さて, 1 以上 N 以下の奇数のうち, 正の約数を ちょうど 8 個持つようなものの個数を求めよ.

制約

N は 1 以上 200 以下の整数

入力

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

出力

条件を満たす数の個数を出力しなさい.

入力例 1

出力例 1

1 以上 105 以下の整数の中で, ただ一つの「奇数かつ約数が 8 個」を満たす数は 105 である.

入力例 2

出力例 2

1 は約数が 1 個, 3, 5, 7 は全て素数なので約数が 2 個である. よって前述の条件を満たすような数は存在しない.

Score: 200 points

Problem Statement

The number 105 is quite special - it is odd but still it has eight divisors. Now, your task is this: how many odd numbers with exactly eight positive divisors are there between 1 and N (inclusive)?

Constraints

N is an integer between 1 and 200 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the count.

Sample Input 1

Sample Output 1

Among the numbers between 1 and 105, the only number that is odd and has exactly eight divisors is 105.

Sample Input 2

Sample Output 2

1 has one divisor. 3, 5 and 7 are all prime and have two divisors. Thus, there is no number that satisfies the condition.

C - To Infinity

Time Limit: 2 sec / Memory Limit: 976 MB

配点: 300 点

問題文

Mr. Infinity は, 1 から 9 までの数字からなる文字列 S を持っている. この文字列は, 日付が変わるたびに次のように変化する.

文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666666, 7 が 7777777, 8 が 88888888, 9 が 999999999 に置き換わる. 1 は 1 のまま残る.

例えば, S が 1324 の場合, 翌日には 1333224444 になり, 翌々日には 133333333322224444444444444444 になる.
あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K 文字目は何か？

制約

S は 1 文字以上 100 文字以下の文字列.
K は 1 以上 10^{18} 以下の整数.
5000 兆日後の文字列の長さは K 文字以上である.

入力

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

S
K

出力

5000 兆日後に Mr. Infinity が持っている文字列の K 文字目の数字を出力しなさい.

入力例 1

1214
4

出力例 1

文字列 S は次のように変化していく.

現在: 1214
1 日後: 12214444
2 日後: 1222214444444444444444
3 日後: 12222222214444444444444444444444444444444444444444444444444444444444444444

5000 兆日後の文字列の最初 5 文字は 12222 となる. K=4 なので, 4 文字目の 2 を出力すればよい.

入力例 2

3
157

出力例 2

文字列ははじめ 3 である. 5000 兆日経ったとき, 文字列は 3 だけで構成される.

入力例 3

299792458
9460730472580800

出力例 3

Score: 300 points

Problem Statement

Mr. Infinity has a string S consisting of digits from 1 to 9. Each time the date changes, this string changes as follows:

Each occurrence of 2 in S is replaced with 22. Similarly, each 3 becomes 333, 4 becomes 4444, 5 becomes 55555, 6 becomes 666666, 7 becomes 7777777, 8 becomes 88888888 and 9 becomes 999999999. 1 remains as 1.

For example, if S is 1324, it becomes 1333224444 the next day, and it becomes 133333333322224444444444444444 the day after next. You are interested in what the string looks like after 5 \times 10^{15} days. What is the K-th character from the left in the string after 5 \times 10^{15} days?

Constraints

S is a string of length between 1 and 100 (inclusive).
K is an integer between 1 and 10^{18} (inclusive).
The length of the string after 5 \times 10^{15} days is at least K.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the K-th character from the left in Mr. Infinity's string after 5 \times 10^{15} days.

Sample Input 1

1214
4

Sample Output 1

The string S changes as follows:

Now: 1214
After one day: 12214444
After two days: 1222214444444444444444
After three days: 12222222214444444444444444444444444444444444444444444444444444444444444444

The first five characters in the string after 5 \times 10^{15} days is 12222. As K=4, we should print the fourth character, 2.

Sample Input 2

3
157

Sample Output 2

The initial string is 3. The string after 5 \times 10^{15} days consists only of 3.

Sample Input 3

299792458
9460730472580800

Sample Output 3

D - AtCoder Express 2

Time Limit: 3 sec / Memory Limit: 976 MB

配点: 400 点

問題文

高橋王国には, 東西にのびる 1 本の線路がある. これに沿って N 個の都市があり, 西から順に都市 1, 2, 3, \cdots, N と番号づけられている.
AtCoder Express という会社は M 本の列車を保有しており, 列車 i は都市 L_i から都市 R_i の区間 (L_i = R_i の場合もある) を走っている.

この王国の国王である高橋君は, Q 個のことに興味を持った. 具体的には, i=1, 2, 3, \dots, Q のときの以下の質問の答えを求めたくなった.

都市 p_i から都市 q_i までの区間に, 走る区間が 完全に含まれる 列車の本数. 言い換えれば, p_i \leq L_j と R_j \leq q_i が両方成り立つような列車 j の本数.

高橋君は天才である. しかし流石の彼でも, 膨大なデータを処理することはできない. 高橋君のために, Q 個の質問それぞれに対して答えを求めよ.

制約

N は 1 以上 500 以下の整数
M は 1 以上 200 \ 000 以下の整数
Q は 1 以上 100 \ 000 以下の整数
1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

入力

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

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

出力

Q 行出力せよ. i 行目には, 都市 p_i から都市 q_i までの区間に, それぞれの走る区間が完全に含まれる列車の本数を出力せよ.

入力例 1

出力例 1

全ての列車の走る区間が, 都市 1 から都市 2 までの区間に含まれているので, この質問の答えは 3 となる.

入力例 2

出力例 2

1
1

1 個目の質問は, 都市 1 から 7 までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 1 のみである. 2 個目の質問は, 都市 3 から 10 までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 3 のみである.

入力例 3

出力例 3

Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i). Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).
M is an integer between 1 and 200 \ 000 (inclusive).
Q is an integer between 1 and 100 \ 000 (inclusive).
1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

Sample Output 1

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1. The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

Sample Output 3