AtCoder Beginner Contest 084

A - New Year

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

12 月 30 日の M 時から次の年になるまでは何時間か、求めてください。

制約

1≦M≦23
入力は全て整数

入力

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

出力

12 月 30 日の M 時から次の年になるまでが x 時間のとき、x を出力せよ。

入力例 1

出力例 1

12 月 30 日の 21 時から次の年になるまでは 27 時間です。

入力例 2

出力例 2

Score : 100 points

Problem Statement

How many hours do we have until New Year at M o'clock (24-hour notation) on 30th, December?

Constraints

1≤M≤23
M is an integer.

Input

Input is given from Standard Input in the following format:

Output

If we have x hours until New Year at M o'clock on 30th, December, print x.

Sample Input 1

Sample Output 1

We have 27 hours until New Year at 21 o'clock on 30th, December.

Sample Input 2

Sample Output 2

B - Postal Code

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

Atcoder国では、郵便番号は A+B+1 文字からなり、A+1 文字目はハイフン -、それ以外の全ての文字は 0 以上 9 以下の数字です。

文字列 S が与えられるので、Atcoder国の郵便番号の形式を満たすかどうか判定してください。

制約

1≦A,B≦5
|S|=A+B+1
S は 0 以上 9 以下の数字、およびハイフン - からなる

入力

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

A B
S

出力

S がAtcoder国の郵便番号の形式を満たすならば Yes 、そうでなければ No を出力せよ。

入力例 1

3 4
269-6650

出力例 1

Yes

S の A+1 文字目がハイフンで、それ以外の全ての文字が 0 以上 9 以下の数字なので、Atcoder国の郵便番号の形式を満たしています。

入力例 2

1 1
---

出力例 2

No

S の A+1 文字目以外もハイフンとなっており、Atcoder国の郵便番号の形式を満たしていません。

入力例 3

1 2
7444

出力例 3

No

Score : 200 points

Problem Statement

The postal code in Atcoder Kingdom is A+B+1 characters long, its (A+1)-th character is a hyphen -, and the other characters are digits from 0 through 9.

You are given a string S. Determine whether it follows the postal code format in Atcoder Kingdom.

Constraints

1≤A,B≤5
|S|=A+B+1
S consists of - and digits from 0 through 9.

Input

Input is given from Standard Input in the following format:

A B
S

Output

Print Yes if S follows the postal code format in AtCoder Kingdom; print No otherwise.

Sample Input 1

3 4
269-6650

Sample Output 1

Yes

The (A+1)-th character of S is -, and the other characters are digits from 0 through 9, so it follows the format.

Sample Input 2

1 1
---

Sample Output 2

No

S contains unnecessary -s other than the (A+1)-th character, so it does not follow the format.

Sample Input 3

1 2
7444

Sample Output 3

No

C - Special Trains

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

Atcoder国に、 1 本の東西方向に走る鉄道が完成しました。

この鉄道には N 個の駅があり、西から順に 1,2,...,N の番号がついています。

明日、鉄道の開通式が開かれます。

この鉄道では、1≦i≦N-1 を満たす全ての整数 i に対して、駅 i から駅 i+1 に、C_i 秒で向かう列車が運行されます。ただし、これら以外の列車は運行されません。

駅 i から駅 i+1 に移動する列車のうち最初の列車は、開通式開始 S_i 秒後に駅 i を発車し、その後は F_i 秒おきに駅 i を発車する列車があります。

また、S_i は F_i で割り切れることが保証されます。

つまり、A％B で A を B で割った余りを表すとき、S_i≦t,t％F_i=0 を満たす全ての t に対してのみ、開通式開始 t 秒後に駅 i を出発し、開通式開始 t+C_i 秒後に駅 i+1 に到着する列車があります。

列車の乗り降りにかかる時間を考えないとき、全ての駅 i に対して、開通式開始時に駅 i にいる場合、駅 N に到着できるのは最も早くて開通式開始何秒後か、答えてください。

制約

1≦N≦500
1≦C_i≦100
1≦S_i≦10^5
1≦F_i≦100
S_i％F_i=0
入力は全て整数

入力

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

N
C_1 S_1 F_1
:
C_{N-1} S_{N-1} F_{N-1}

出力

i 行目 (1≦i≦N) に、開通式開始時に駅 i にいる場合、駅 N に到着できるのが最も早くて開通式開始 x 秒後のとき、x を出力せよ。

入力例 1

3
6 5 1
1 10 1

出力例 1

12
11
0

駅 1 からは、以下のように移動します。

開通式開始 5 秒後に、駅 2 に向かう列車に乗る。
開通式開始 11 秒後に、駅 2 に到着する。
開通式開始 11 秒後に、駅 3 に向かう列車に乗る。
開通式開始 12 秒後に、駅 3 に到着する。

駅 2 からは、以下のように移動します。

開通式開始 10 秒後に、駅 3 に向かう列車に乗る。
開通式開始 11 秒後に、駅 3 に到着する。

駅 3 に対しても、0 を出力しなければならないことに注意してください。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

A railroad running from west to east in Atcoder Kingdom is now complete.

There are N stations on the railroad, numbered 1 through N from west to east.

Tomorrow, the opening ceremony of the railroad will take place.

On this railroad, for each integer i such that 1≤i≤N-1, there will be trains that run from Station i to Station i+1 in C_i seconds. No other trains will be operated.

The first train from Station i to Station i+1 will depart Station i S_i seconds after the ceremony begins. Thereafter, there will be a train that departs Station i every F_i seconds.

Here, it is guaranteed that F_i divides S_i.

That is, for each Time t satisfying S_i≤t and t％F_i=0, there will be a train that departs Station i t seconds after the ceremony begins and arrives at Station i+1 t+C_i seconds after the ceremony begins, where A％B denotes A modulo B, and there will be no other trains.

For each i, find the earliest possible time we can reach Station N if we are at Station i when the ceremony begins, ignoring the time needed to change trains.

Constraints

1≤N≤500
1≤C_i≤100
1≤S_i≤10^5
1≤F_i≤10
S_i％F_i=0
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 S_1 F_1
:
C_{N-1} S_{N-1} F_{N-1}

Output

Print N lines. Assuming that we are at Station i (1≤i≤N) when the ceremony begins, if the earliest possible time we can reach Station N is x seconds after the ceremony begins, the i-th line should contain x.

Sample Input 1

3
6 5 1
1 10 1

Sample Output 1

12
11
0

We will travel from Station 1 as follows:

5 seconds after the beginning: take the train to Station 2.
11 seconds: arrive at Station 2.
11 seconds: take the train to Station 3.
12 seconds: arrive at Station 3.

We will travel from Station 2 as follows:

10 seconds: take the train to Station 3.
11 seconds: arrive at Station 3.

Note that we should print 0 for Station 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - 2017-like Number

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。

Q 個のクエリが与えられます。

クエリ i(1≦i≦Q) では奇数 l_i,r_i が与えられるので、l_i≦x≦r_i かつ 2017に似た数 となる奇数 x の個数を求めてください。

制約

1≦Q≦10^5
1≦l_i≦r_i≦10^5
l_i,r_i は奇数
入力は全て整数

入力

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

Q
l_1 r_1
:
l_Q r_Q

出力

i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。

入力例 1

1
3 7

出力例 1

3 も (3+1)÷2=2 も素数であるため、3 は 2017に似た数 です。
5 も (5+1)÷2=3 も素数であるため、5 は 2017に似た数 です。
7 は素数ですが、 (7+1)÷2=4 は素数ではないため、7 は 2017に似た数 ではありません。

よって、クエリ 1 の答えは 2 個です。

入力例 2

出力例 2

2017 も 2017に似た数 であることに注意してください。

入力例 3

出力例 3

Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5
1≤l_i≤r_i≤10^5
l_i and r_i are odd.
All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.
5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.
7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

Sample Output 2

Note that 2017 is also similar to 2017.

Sample Input 3

Sample Output 3