実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
直線上に 7 個の点 A, B, C, D, E, F, G がこの順に並んでいます。(下の図も参考にしてください)
隣り合う点の距離は次の通りです。
- 点 A と点 B の距離は 3
- 点 B と点 C の距離は 1
- 点 C と点 D の距離は 4
- 点 D と点 E の距離は 1
- 点 E と点 F の距離は 5
- 点 F と点 G の距離は 9
2 つの英大文字 p, q が与えられます。p, q は A,B,C,D,E,F,G のいずれかで、 p \neq q が成り立ちます。
点 p と点 q の間の距離を答えてください。
制約
- p, q は
A,B,C,D,E,F,Gのいずれか - p \neq q
入力
入力は以下の形式で標準入力から与えられる。
p q
出力
点 p と点 q の間の距離を出力せよ。
入力例 1
A C
出力例 1
4
点 A と点 C の距離は 3 + 1 = 4 です。
入力例 2
G B
出力例 2
20
点 G と点 B の距離は 9 + 5 + 1 + 4 + 1 = 20 です。
入力例 3
C F
出力例 3
10
Score : 200 points
Problem Statement
There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.
- Between A and B: 3
- Between B and C: 1
- Between C and D: 4
- Between D and E: 1
- Between E and F: 5
- Between F and G: 9
You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.
Constraints
- Each of p and q is
A,B,C,D,E,F, orG. - p \neq q
Input
The input is given from Standard Input in the following format:
p q
Output
Print the distance between the points p and q.
Sample Input 1
A C
Sample Output 1
4
The distance between the points A and C is 3 + 1 = 4.
Sample Input 2
G B
Sample Output 2
20
The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.
Sample Input 3
C F
Sample Output 3
10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。
1 x: A の末尾に x を追加する。2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。
制約
- 1 \leq Q \leq 100
- 1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
- 2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
クエリは以下の 2 つのいずれかの形式である。
1 x
2 k
出力
2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。
入力例 1
5 1 20 1 30 2 1 1 40 2 3
出力例 1
30 20
- 最初 A は空である。
- 1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
- 2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
- 3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
- 4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
- 5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。
Score: 200 points
Problem Statement
You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:
1 x: Append x to the end of A.2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.
Constraints
- 1 \leq Q \leq 100
- In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
- In the second type of query, k is a positive integer not greater than the current length of sequence A.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in one of the following two formats:
1 x
2 k
Output
Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.
Sample Input 1
5 1 20 1 30 2 1 1 40 2 3
Sample Output 1
30 20
- Initially, A is empty.
- The first query appends 20 to the end of A, making A=(20).
- The second query appends 30 to the end of A, making A=(20,30).
- The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
- The fourth query appends 40 to the end of A, making A=(20,30,40).
- The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
英小文字からなる長さ M の文字列 N 個 S_1,S_2,\dots,S_N が与えられます。ここで、S_i は互いに異なります。
これらを並び替えた文字列の列 T_1,T_2,\dots,T_N であって、以下の条件を満たすものが存在するか判定してください。
- 1 \le i \le N-1 を満たす全ての整数 i に対して、T_i を 1 文字だけ別の英小文字に変えて T_{i+1} にすることが出来る。
制約
- 2 \le N \le 8
- 1 \le M \le 5
- S_i は英小文字からなる長さ M の文字列である。(1 \le i \le N)
- S_i は互いに異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 4 bbed abcd abed fbed
出力例 1
Yes
abcd , abed , bbed , fbed の順に並び替えると条件を満たします。
入力例 2
2 5 abcde abced
出力例 2
No
どのように並び替えても条件を満たすことは出来ません。
入力例 3
8 4 fast face cast race fact rice nice case
出力例 3
Yes
Score : 250 points
Problem Statement
You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.
Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:
- for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.
Constraints
- 2 \le N \le 8
- 1 \le M \le 5
- S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
- S_i are pairwise distinct.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print Yes if one can obtain a conforming sequence; print No otherwise.
Sample Input 1
4 4 bbed abcd abed fbed
Sample Output 1
Yes
One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.
Sample Input 2
2 5 abcde abced
Sample Output 2
No
No matter how the strings are rearranged, the condition is never satisfied.
Sample Input 3
8 4 fast face cast race fact rice nice case
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
整数 N が与えられるので、以下の問題を解いてください。
f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。
制約
- N は整数
- 1 \le N < 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
16
出力例 1
73
- 1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
- これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
- 10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
- これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。
結局、求める答えは 73 です。
入力例 2
238
出力例 2
13870
入力例 3
999999999999999999
出力例 3
762062362
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, solve the following problem.
Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.
Constraints
- N is an integer.
- 1 \le N < 10^{18}
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
16
Sample Output 1
73
- For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
- Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
- For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
- Thus, we have f(10)=1,f(11)=2,...,f(16)=7.
The final answer is 73.
Sample Input 2
238
Sample Output 2
13870
Sample Input 3
999999999999999999
Sample Output 3
762062362
Be sure to find the sum modulo 998244353.
実行時間制限: 2.5 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
項数が N の正整数列 A=(a_1,\ldots,a_N) が与えられます。
A の項を 1 個以上選ぶ方法は 2^N-1 通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq a_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
3 2 6 2
出力例 1
6
A の項を選ぶ方法それぞれに対する平均値は以下のようになります。
-
a_1 のみを選んだ場合、平均値は \frac{a_1}{1}=\frac{2}{1} = 2 であり、整数である。
-
a_2 のみを選んだ場合、平均値は \frac{a_2}{1}=\frac{6}{1} = 6 であり、整数である。
-
a_3 のみを選んだ場合、平均値は \frac{a_3}{1}=\frac{2}{1} = 2 であり、整数である。
-
a_1 と a_2 を選んだ場合、平均値は \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4 であり、整数である。
-
a_1 と a_3 を選んだ場合、平均値は \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2 であり、整数である。
-
a_2 と a_3 を選んだ場合、平均値は \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4 であり、整数である。
-
a_1 と a_2 と a_3 を選んだ場合、平均値は \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3} であり、整数ではない。
以上より、6 通りの選び方が条件を満たします。
入力例 2
5 5 5 5 5 5
出力例 2
31
どのように A の項を 1 個以上選んでも平均値が 5 になります。
Score : 400 points
Problem Statement
You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.
Constraints
- 1 \leq N \leq 100
- 1 \leq a_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
3 2 6 2
Sample Output 1
6
For each way to choose terms of A, the average is obtained as follows:
-
If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.
-
If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.
-
If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.
-
If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.
-
If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.
-
If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.
-
If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.
Therefore, 6 ways satisfy the condition.
Sample Input 2
5 5 5 5 5 5
Sample Output 2
31
Regardless of the choice of one or more terms of A, the average equals 5.