Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
AtCoder 王国では、英小文字を用いる高橋語という言語が使われています。
高橋語では、名詞の複数形は次のルールで綴られます。
- 単数形の末尾が
s
以外なら、単数形の末尾にs
をつける - 単数形の末尾が
s
なら、単数形の末尾にes
をつける
高橋語の名詞の単数形 S が与えられるので、複数形を出力してください。
制約
- S は長さ 1 以上 1000 以下の文字列
- S は英小文字のみを含む
入力
入力は以下の形式で標準入力から与えられる。
S
出力
与えられた高橋語の複数形を出力せよ。
入力例 1
apple
出力例 1
apples
apple
の末尾は e
なので、複数形は apples
になります。
入力例 2
bus
出力例 2
buses
bus
の末尾は s
なので、複数形は buses
になります。
入力例 3
box
出力例 3
boxs
Score : 100 points
Problem Statement
In the Kingdom of AtCoder, people use a language called Taknese, which uses lowercase English letters.
In Taknese, the plural form of a noun is spelled based on the following rules:
- If a noun's singular form does not end with
s
, appends
to the end of the singular form. - If a noun's singular form ends with
s
, appendes
to the end of the singular form.
You are given the singular form S of a Taknese noun. Output its plural form.
Constraints
- S is a string of length 1 between 1000, inclusive.
- S contains only lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the plural form of the given Taknese word.
Sample Input 1
apple
Sample Output 1
apples
apple
ends with e
, so its plural form is apples
.
Sample Input 2
bus
Sample Output 2
buses
bus
ends with s
, so its plural form is buses
.
Sample Input 3
box
Sample Output 3
boxs
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君は、「サイコロを 2 個振る」という行動を N 回行いました。 i 回目の出目は D_{i,1},D_{i,2} です。
ゾロ目が 3 回以上続けて出たことがあるかどうか判定してください。 より正確には、D_{i,1}=D_{i,2} かつ D_{i+1,1}=D_{i+1,2} かつ D_{i+2,1}=D_{i+2,2} を満たすような i が少なくとも一つ存在するかどうか判定してください。
制約
- 3 \leq N \leq 100
- 1\leq D_{i,j} \leq 6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N D_{1,1} D_{1,2} \vdots D_{N,1} D_{N,2}
出力
ゾロ目が 3 回以上続けて出たことがあるならば Yes
、ないならば No
を出力せよ。
入力例 1
5 1 2 6 6 4 4 3 3 3 2
出力例 1
Yes
2 回目から 4 回目にかけて、ゾロ目が 3 回続けて出ています。
入力例 2
5 1 1 2 2 3 4 5 5 6 6
出力例 2
No
入力例 3
6 1 1 2 2 3 3 4 4 5 5 6 6
出力例 3
Yes
Score : 200 points
Problem Statement
Tak performed the following action N times: rolling two dice. The result of the i-th roll is D_{i,1} and D_{i,2}.
Check if doublets occurred at least three times in a row. Specifically, check if there exists at lease one i such that D_{i,1}=D_{i,2}, D_{i+1,1}=D_{i+1,2} and D_{i+2,1}=D_{i+2,2} hold.
Constraints
- 3 \leq N \leq 100
- 1\leq D_{i,j} \leq 6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N D_{1,1} D_{1,2} \vdots D_{N,1} D_{N,2}
Output
Print Yes
if doublets occurred at least three times in a row. Print No
otherwise.
Sample Input 1
5 1 2 6 6 4 4 3 3 3 2
Sample Output 1
Yes
From the second roll to the fourth roll, three doublets occurred in a row.
Sample Input 2
5 1 1 2 2 3 4 5 5 6 6
Sample Output 2
No
Sample Input 3
6 1 1 2 2 3 3 4 4 5 5 6 6
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 N が与えられます。A \times B + C = N を満たす正整数の組 (A,B,C) はいくつありますか?
制約
- 2 \leq N \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
3
A \times B + C = 3 を満たす正整数の組は、(A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1) の 3 つあります。
入力例 2
100
出力例 2
473
入力例 3
1000000
出力例 3
13969985
Score : 300 points
Problem Statement
Given is a positive integer N. How many tuples (A,B,C) of positive integers satisfy A \times B + C = N?
Constraints
- 2 \leq N \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
3
There are 3 tuples of integers that satisfy A \times B + C = 3: (A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1).
Sample Input 2
100
Sample Output 2
473
Sample Input 3
1000000
Sample Output 3
13969985
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
一列に並んだ N マスから成るマス目があり、マスには左から順番に1, 2, \ldots, N の番号がついています。
このマス目で暮らしている高橋君は、現在マス 1 にいて、後述の方法で移動を繰り返してマス N へ行こうとしています。
10 以下の整数 K と、共通部分を持たない K 個の区間 [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K] が与えられ、これらの区間の和集合を S とします。ただし、区間 [l, r] は l 以上 r 以下の整数の集合を表します。
- マス i にいるとき、S から整数を 1 つ選んで (d とする)、マス i + d に移動する。ただし、マス目の外に出るような移動を行ってはならない。
高橋君のために、マス N に行く方法の個数を 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(N, 10)
- 1 \leq L_i \leq R_i \leq N
- [L_i, R_i] と [L_j, R_j] は共通部分を持たない (i \neq j)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N K L_1 R_1 L_2 R_2 : L_K R_K
出力
高橋くんがマス 1 からマス N に行く方法の個数を 998244353 で割った余りを出力せよ。
入力例 1
5 2 1 1 3 4
出力例 1
4
集合 S は 区間 [1, 1] と区間 [3, 4] の和集合であり、S = \{ 1, 3, 4 \} です。
マス 5 へ移動する方法は次の 4 通りが考えられます。
- マス 1, 2, 3, 4, 5 の順に移動する。
- マス 1, 2, 5 の順に移動する。
- マス 1, 4, 5 の順に移動する。
- マス 1, 5 の順に移動する。
入力例 2
5 2 3 3 5 5
出力例 2
0
S = \{ 3, 5 \} であり、そもそもマス 5 にたどり着けないので 0 を出力してください。
入力例 3
5 1 1 2
出力例 3
5
入力例 4
60 3 5 8 1 3 10 15
出力例 4
221823067
998244353 で割った余りを出力することに注意してください。
Score : 400 points
Problem Statement
There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.
Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.
You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.
- When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.
To help Tak, find the number of ways to go to Cell N, modulo 998244353.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(N, 10)
- 1 \leq L_i \leq R_i \leq N
- [L_i, R_i] and [L_j, R_j] do not intersect (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K L_1 R_1 L_2 R_2 : L_K R_K
Output
Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.
Sample Input 1
5 2 1 1 3 4
Sample Output 1
4
The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.
There are 4 possible ways to get to Cell 5:
- 1 \to 2 \to 3 \to 4 \to 5,
- 1 \to 2 \to 5,
- 1 \to 4 \to 5 and
- 1 \to 5.
Sample Input 2
5 2 3 3 5 5
Sample Output 2
0
Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5. Print 0.
Sample Input 3
5 1 1 2
Sample Output 3
5
Sample Input 4
60 3 5 8 1 3 10 15
Sample Output 4
221823067
Note that you have to print the answer modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
x を m で割った余りを f(x,m) と表します。
初期値 A_1=X および漸化式 A_{n+1}= f(A_n^2, M) で定まる数列を A とします。\displaystyle{\sum_{i=1}^N A_i} を求めてください。
制約
- 1 \leq N \leq 10^{10}
- 0 \leq X < M \leq 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X M
出力
\displaystyle{\sum_{i=1}^N A_i} を出力せよ。
入力例 1
6 2 1001
出力例 1
1369
数列 A は 2,4,16,256,471,620,\ldots となるので、答えは 2+4+16+256+471+620=1369 となります。
入力例 2
1000 2 16
出力例 2
6
数列 A は 2,4,0,0,\ldots となるので、答えは 6 となります。
入力例 3
10000000000 10 99959
出力例 3
492443256176507
Score : 500 points
Problem Statement
Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.
Constraints
- 1 \leq N \leq 10^{10}
- 0 \leq X < M \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X M
Output
Print \displaystyle{\sum_{i=1}^N A_i}.
Sample Input 1
6 2 1001
Sample Output 1
1369
The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.
Sample Input 2
1000 2 16
Sample Output 2
6
The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.
Sample Input 3
10000000000 10 99959
Sample Output 3
492443256176507
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 N マス、横 N マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス(i,j) と表します。
グリッドの中央 (N-2)\times (N-2) マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 2N-1 マスには白い石が 1 個ずつ置いてあります。
Q 個のクエリが与えられるので、順番に処理してください。 クエリには 2 種類あり、入力形式とクエリの内容は以下のとおりです。
1 x
: (1,x) に白い石を置く。そこから下方向に最も近い白い石との間にある黒い石を全て白い石に置き換える2 x
: (x,1) に白い石を置く。そこから右方向に最も近い白い石との間にある黒い石を全て白い石に置き換える
Q 個のクエリを全て処理したあとグリッド上に黒い石はいくつありますか。
制約
- 3 \leq N \leq 2\times 10^5
- 0 \leq Q \leq \min(2N-4,2\times 10^5)
- 2 \leq x \leq N-1
- 同じクエリが複数回与えられることはない
入力
入力は以下の形式で標準入力から与えられる。
N Q Query_1 \vdots Query_Q
出力
Q 個のクエリを全て処理したあとグリッド上にある黒い石の個数を出力せよ。
入力例 1
5 5 1 3 2 3 1 4 2 2 1 2
出力例 1
1
各クエリにより、グリッドは次のように変化します。
入力例 2
200000 0
出力例 2
39999200004
入力例 3
176527 15 1 81279 2 22308 2 133061 1 80744 2 44603 1 170938 2 139754 2 15220 1 172794 1 159290 2 156968 1 56426 2 77429 1 97459 2 71282
出力例 3
31159505795
Score : 600 points
Problem Statement
There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.
Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it. Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.
Q queries are given. We ask you to process them in order. There are two kinds of queries. Their input format and description are as follows:
1 x
: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.2 x
: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.
How many black stones are there on the grid after processing all Q queries?
Constraints
- 3 \leq N \leq 2\times 10^5
- 0 \leq Q \leq \min(2N-4,2\times 10^5)
- 2 \leq x \leq N-1
- Queries are pairwise distinct.
Input
Input is given from Standard Input in the following format:
N Q Query_1 \vdots Query_Q
Output
Print how many black stones there are on the grid after processing all Q queries.
Sample Input 1
5 5 1 3 2 3 1 4 2 2 1 2
Sample Output 1
1
After each query, the grid changes in the following way:
Sample Input 2
200000 0
Sample Output 2
39999200004
Sample Input 3
176527 15 1 81279 2 22308 2 133061 1 80744 2 44603 1 170938 2 139754 2 15220 1 172794 1 159290 2 156968 1 56426 2 77429 1 97459 2 71282
Sample Output 3
31159505795