Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 x が美しい整数であるとは,x が 9 桁の整数であり,その 10 進法表記 S_1\ldots S_9 (S_i は x の 10 進法表記の i 文字目)が以下の条件をすべて満たすことをいいます:
- S_1 は
0
ではない - S_1 = S_2
- S_5 = S_6
- S_7 = S_9
例えば 998244353 や 333333333 は美しい整数です.111112222 は S_5 \neq S_6 であるため美しい整数ではありません.
正の整数 N が与えられます.小さい方から数えて N 番目の美しい整数を答えてください.
制約
- N は正の整数
- 美しい整数が N 個以上存在する
入力
入力は以下の形式で標準入力から与えられます.
N
出力
小さい方から数えて N 番目の美しい整数を出力してください.
入力例 1
3
出力例 1
110000020
美しい整数を小さい順に並べると,110000000, 110000010, 110000020, \ldots となります.
入力例 2
882436
出力例 2
998244353
入力例 3
2023
出力例 3
110200222
Score : 300 points
Problem Statement
A positive integer x is said to be a beautiful integer if and only if x is a 9-digit integer whose decimal notation S_1\ldots S_9 (S_i is the i-th character) satisfies all of the following conditions:
- S_1 is not
0
, - S_1 = S_2,
- S_5 = S_6, and
- S_7 = S_9.
For instance, 998244353 and 333333333 are beautiful integers, while 111112222 is not, since S_5 \neq S_6.
You are given a positive integer N. Print the N-th smallest beautiful integer.
Constraints
- N is a positive integer.
- There are at least N beautiful integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the N-th smallest beautiful integer.
Sample Input 1
3
Sample Output 1
110000020
The beautiful integers in ascending order are 110000000, 110000010, 110000020, \ldots.
Sample Input 2
882436
Sample Output 2
998244353
Sample Input 3
2023
Sample Output 3
110200222
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 H 行,横 W 列のグリッドがあります.はじめ,上から i 行目,左から j 列目のマスには英小文字 A_{i,j} が書かれています.
このグリッドに対して Q 回の操作を行います.i 回目の操作では,1\leq a_i \leq H-1, 1\leq b_i\leq W-1 を満たす整数 a_i, b_i が与えられ,次を行います.
- グリッド内の長方形領域 R_1, R_2, R_3, R_4 を次で定める:
- 上から a_i 行,左から b_i 列の部分を R_1 とする.
- 上から a_i 行,右から W-b_i 列の部分を R_2 とする.
- 下から H-a_i 行,左から b_i 列の部分を R_3 とする.
- 下から H-a_i 行,右から W-b_i 列の部分を R_4 とする.
- R_1, R_2, R_3, R_4 のそれぞれを 180 度回転する.
ただし,グリッド内の長方形領域 R の 180 度回転とは,R において上から i 番目,左から j 番目のマスに書かれた文字を,R において 下から i 番目,右から j 番目のマスに移すことをいいます.入出力例の図も参考にしてください.
Q 回すべての操作を行ったとき,操作後のグリッドの状態を出力してください.
制約
- 2\leq H, W かつ HW \leq 5\times 10^5
- A_{i,j} は英小文字
- 1\leq Q\leq 2\times 10^5
- 1\leq a_i\leq H - 1
- 1\leq b_i\leq W - 1
入力
入力は以下の形式で標準入力から与えられます.
H W A_{1,1}\cdots A_{1, W} \vdots A_{H,1}\cdots A_{H, W} Q a_1 b_1 \vdots a_Q b_Q
出力
操作後のマス (i,j) に書かれている文字を B_{i,j} とするとき,操作後のグリッドの状態を,次の形式で出力してください.
B_{1,1}\cdots B_{1, W} \vdots B_{H,1}\cdots B_{H, W}
入力例 1
4 5 abcde fghij klmno pqrst 1 3 3
出力例 1
mlkon hgfji cbaed rqpts
グリッドの状態は次の図のように変化します.
入力例 2
3 7 atcoder regular contest 2 1 1 2 5
出力例 2
testcon oderatc ularreg
グリッドの状態は次の図のように変化します.
入力例 3
2 2 ac wa 3 1 1 1 1 1 1
出力例 3
ac wa
グリッドの状態は次の図のように変化します.
Score : 500 points
Problem Statement
We have a grid with H rows from top to bottom and W columns from left and right. Initially, the square at the i-th row from the top and j-th column from the left has a lowercase English letter A_{i,j}.
Let us perform Q operations on this grid. In the i-th operation, we are given integers a_i and b_i such that 1\leq a_i \leq H-1 and 1\leq b_i\leq W-1, and do the following.
- Let R_1, R_2, R_3, and R_4 be rectangular regions within the grid defined as follows:
- R_1 is the intersection of the top a_i rows and leftmost b_i columns;
- R_2 is the intersection of the top a_i rows and rightmost W-b_i columns;
- R_3 is the intersection of the bottom H-a_i rows and leftmost b_i columns;
- R_4 is the intersection of the bottom H-a_i rows and rightmost W-b_i columns.
- Rotate 180 degrees each of R_1, R_2, R_3, and R_4.
Here, a 180-degree rotation of a rectangular region R within the grid moves the character on the square at the i-th from the top and j-th column from the left in R to the square at the i-th from the bottom and j-th column from the right in R. See also the figures for the samples.
Print the grid after all Q operations.
Constraints
- 2\leq H, W, and HW \leq 5\times 10^5.
- A_{i,j} is a lowercase English letter.
- 1\leq Q\leq 2\times 10^5
- 1\leq a_i\leq H - 1
- 1\leq b_i\leq W - 1
Input
The input is given from Standard Input in the following format:
H W A_{1,1}\cdots A_{1, W} \vdots A_{H,1}\cdots A_{H, W} Q a_1 b_1 \vdots a_Q b_Q
Output
Print the grid after the operations in the following format, where B_{i,j} is the character on the square (i,j) on the final grid.
B_{1,1}\cdots B_{1, W} \vdots B_{H,1}\cdots B_{H, W}
Sample Input 1
4 5 abcde fghij klmno pqrst 1 3 3
Sample Output 1
mlkon hgfji cbaed rqpts
The grid will change as follows.
Sample Input 2
3 7 atcoder regular contest 2 1 1 2 5
Sample Output 2
testcon oderatc ularreg
The grid will change as follows.
Sample Input 3
2 2 ac wa 3 1 1 1 1 1 1
Sample Output 3
ac wa
The grid will change as follows.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 と -1 のみからなる長さ N の数列 A = (A_1, \ldots, A_N) が与えられます.
以下の条件をすべて満たす整数列 x = (x_1, \ldots, x_N) が存在するか否かを判定し, 存在する場合にはそのような整数列をひとつ答えてください.
- 任意の i (1\leq i\leq N) に対して |x_i| \leq 10^{12}.
- x は狭義単調増加である.つまり x_1 < \cdots < x_N.
- \sum_{i=1}^N A_ix_i = 0.
制約
- 1\leq N\leq 2\times 10^5
- A_i \in \lbrace 1, -1\rbrace
入力
入力は以下の形式で標準入力から与えられます.
N A_1 \ldots A_N
出力
問題の条件をすべて満たす整数列 x が存在するならば Yes
を,そうでなければ No
を出力してください.Yes
の場合には,2 行目にそのような整数列 x の各要素を,空白で区切って 1 行で出力してください.
x_1 \ldots x_N
条件を満たす整数列が複数存在する場合は,どれを出力しても正解となります.
入力例 1
5 -1 1 -1 -1 1
出力例 1
Yes -3 -1 4 5 7
この出力について \sum_{i=1}^NA_ix_i= -(-3) + (-1) - 4 - 5 + 7 = 0 となります.
入力例 2
1 -1
出力例 2
Yes 0
入力例 3
2 1 -1
出力例 3
No
Score : 600 points
Problem Statement
You are given a sequence of length N, A = (A_1, \ldots, A_N), consisting of 1 and -1.
Determine whether there is an integer sequence x = (x_1, \ldots, x_N) that satisfies all of the following conditions, and print one such sequence if it exists.
- |x_i| \leq 10^{12} for every i (1\leq i\leq N).
- x is strictly increasing. That is, x_1 < \cdots < x_N.
- \sum_{i=1}^N A_ix_i = 0.
Constraints
- 1\leq N\leq 2\times 10^5
- A_i \in \lbrace 1, -1\rbrace
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
If there is an integer sequence x that satisfies all of the conditions in question, print Yes
; otherwise, print No
. In case of Yes
, print the elements of such an integer sequence x in the subsequent line, separated by spaces.
x_1 \ldots x_N
If multiple integer sequences satisfy the conditions, you may print any of them.
Sample Input 1
5 -1 1 -1 -1 1
Sample Output 1
Yes -3 -1 4 5 7
For this output, we have \sum_{i=1}^NA_ix_i= -(-3) + (-1) - 4 - 5 + 7 = 0.
Sample Input 2
1 -1
Sample Output 2
Yes 0
Sample Input 3
2 1 -1
Sample Output 3
No
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
正整数 x に対し,その各桁の和を f(x) と表すことにします.例えば f(153) = 1 + 5 + 3 = 9,f(2023) = 2 + 0 + 2 + 3 = 7,f(1) = 1 です.
正整数列 A = (A_1, \ldots, A_N) が与えられます.x を非負整数とするとき,\sum_{i=1}^N f(A_i + x) としてありうる最小値を求めてください.
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i < 10^9
入力
入力は以下の形式で標準入力から与えられます.
N A_1 \ldots A_N
出力
x を非負整数とするとき,\sum_{i=1}^N f(A_i + x) としてありうる最小値を出力してください.
入力例 1
4 4 13 8 6
出力例 1
14
例えば x = 7 とすると,\sum_{i=1}^N f(A_i+x) = f(11) + f(20) + f(15) + f(13) = 14 となります.
入力例 2
4 123 45 678 90
出力例 2
34
例えば x = 22 とすると,\sum_{i=1}^N f(A_i+x) = f(145) + f(67) + f(700) + f(112) = 34 となります.
入力例 3
3 1 10 100
出力例 3
3
例えば x = 0 とすると,\sum_{i=1}^N f(A_i+x) = f(1) + f(10) + f(100) = 3 となります.
入力例 4
1 153153153
出力例 4
1
例えば x = 9999846846847 とすると,\sum_{i=1}^N f(A_i+x) = f(10000000000000) = 1 となります.
Score : 800 points
Problem Statement
For a positive integer x, let f(x) denote the sum of its digits. For instance, we have f(153) = 1 + 5 + 3 = 9, f(2023) = 2 + 0 + 2 + 3 = 7, and f(1) = 1.
You are given a sequence of positive integers A = (A_1, \ldots, A_N). Find the minimum possible value of \sum_{i=1}^N f(A_i + x) where x is a non-negative integer.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A_i < 10^9
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the minimum possible value of \sum_{i=1}^N f(A_i + x) where x is a non-negative integer.
Sample Input 1
4 4 13 8 6
Sample Output 1
14
For instance, x = 7 makes \sum_{i=1}^N f(A_i+x) = f(11) + f(20) + f(15) + f(13) = 14.
Sample Input 2
4 123 45 678 90
Sample Output 2
34
For instance, x = 22 makes \sum_{i=1}^N f(A_i+x) = f(145) + f(67) + f(700) + f(112) = 34.
Sample Input 3
3 1 10 100
Sample Output 3
3
For instance, x = 0 makes \sum_{i=1}^N f(A_i+x) = f(1) + f(10) + f(100) = 3.
Sample Input 4
1 153153153
Sample Output 4
1
For instance, x = 9999846846847 makes \sum_{i=1}^N f(A_i+x) = f(10000000000000) = 1.
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
どの桁も 0 ではないような正整数 X に対して,次の手順により正整数 Y を得ることを考えます:
- 文字列 S を空文字列で初期化する.
- X の桁数を N とするとき,i = 1, \ldots, N の順に次を行う:X の 10 進法表記の i 文字目を,S の先頭または末尾に挿入する.
- 文字列 S が表す正整数を Y とする.
この手順により X から得ることが可能な正整数のうちで,最小のものを f(X) と書くことにします.
どの桁も 0 ではないような正整数 Y が与えられます.どの桁も 0 ではないような正整数 X であって f(X) = Y を満たすものの個数を 998244353 で割った余りを答えてください.
制約
- Y はどの桁も 0 ではないような正整数
- 1\leq Y < 10^{200000}
入力
入力は以下の形式で標準入力から与えられます.
Y
出力
どの桁も 0 ではないような正整数 X であって f(X) = Y を満たすものの個数を 998244353 で割った余りを出力してください.
入力例 1
1332
出力例 1
3
条件を満たす X は,1332, 3132, 3312 の 3 個です.
入力例 2
3312
出力例 2
0
入力例 3
12234433442
出力例 3
153
Score : 800 points
Problem Statement
For a positive integer X none of whose digits is 0, consider obtaining a positive integer Y as follows.
- Initialize S as an empty string.
- Let N be the number of digits in X. For i = 1, \ldots, N in this order, do the following: insert the i-th character in the decimal notation of X at the beginning or end of S.
- Let Y be the positive integer represented by the string S.
Let f(X) denote the minimum positive integer that can be obtained from X in this way.
You are given a positive integer Y none of whose digits is 0. Print the number, modulo 998244353, of positive integers X none of whose digits is 0 such that f(X) = Y.
Constraints
- Y is a positive integer none of whose digits is 0.
- 1\leq Y < 10^{200000}
Input
The input is given from Standard Input in the following format:
Y
Output
Print the number, modulo 998244353, of positive integers X none of whose digits is 0 such that f(X) = Y.
Sample Input 1
1332
Sample Output 1
3
Three integers, 1332, 3132, and 3312, satisfy the conditions.
Sample Input 2
3312
Sample Output 2
0
Sample Input 3
12234433442
Sample Output 3
153
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 頂点 M 辺からなる連結かつ単純な無向グラフ G が与えられます.頂点には 1 から N の番号がついており,i 番目の辺は頂点 A_i, B_i を結んでいます.
G の各辺を色 1, 2, 3 のいずれかで塗る方法であって,次の条件を満たすものの個数を 998244353 で割った余りを求めてください.
- G の単純パスであって,色 1 の辺,色 2 の辺,色 3 の辺のすべてを含むものが存在する.
単純パスとは
単純パスとは,頂点の列 (v_1, \ldots, v_{k+1}) および辺の列 (e_1, \ldots, e_k) の組であって,以下を満たすもののことをいいます.- i\neq j \implies v_i\neq v_j
- 辺 e_i は頂点 v_i と v_{i+1} を結ぶ.
制約
- 3 \leq N\leq 2\times 10^5
- 3 \leq M\leq 2\times 10^5
- 1 \leq A_i, B_i \leq N
- 与えられるグラフは連結かつ単純である
入力
入力は以下の形式で標準入力から与えられます.
N M A_1 B_1 \vdots A_M B_M
出力
G の各辺を色 1, 2, 3 のいずれかで塗る方法であって,問題の条件を満たすものの個数を 998244353 で割った余りを出力してください.
入力例 1
3 3 1 2 1 3 3 2
出力例 1
0
G の単純パスはいずれも辺を 2 つ以下しか含まないので,条件を満たす塗り方は存在しません.
入力例 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
534
入力例 3
6 5 1 3 4 3 5 4 4 2 1 6
出力例 3
144
入力例 4
6 7 1 2 2 3 3 1 4 5 5 6 6 4 1 6
出力例 4
1794
Score : 1000 points
Problem Statement
You are given a simple connected undirected graph G with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.
Find the number of ways to paint each edge of G in color 1, 2, or 3 so that the following condition is satisfied, modulo 998244353.
- There is a simple path in G that contains an edge in color 1, an edge in color 2, and an edge in color 3.
What is a simple path?
A simple path is a pair of a sequence of vertices (v_1, \ldots, v_{k+1}) and a sequence of edges (e_1, \ldots, e_k) that satisfies the following:- i\neq j \implies v_i\neq v_j;
- edge e_i connects vertices v_i and v_{i+1}.
Constraints
- 3 \leq N\leq 2\times 10^5
- 3 \leq M\leq 2\times 10^5
- 1 \leq A_i, B_i \leq N
- The given graph is simple and connected.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print the number of ways to paint each edge of G in color 1, 2, or 3 so that the condition in question is satisfied, modulo 998244353.
Sample Input 1
3 3 1 2 1 3 3 2
Sample Output 1
0
Any simple path in G contains two or fewer edges, so there is no way to satisfy the condition.
Sample Input 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 2
534
Sample Input 3
6 5 1 3 4 3 5 4 4 2 1 6
Sample Output 3
144
Sample Input 4
6 7 1 2 2 3 3 1 4 5 5 6 6 4 1 6
Sample Output 4
1794