Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 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
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に x\mathrm{\,m} のところにある地点の座標は x と定められています。 特に、基準となる地点から西に x\mathrm{\,m} のところにある地点の座標は -x です。
すぬけ君は今から、座標が A である地点を基点にして M\mathrm{\,m} おきにクリスマスツリーを立てます。 すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。
高橋君と青木君はそれぞれ座標が L,R\ (L\leq R) である地点に立っています。 高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を求めてください。
制約
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A M L R
出力
高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を出力せよ。
入力例 1
5 3 -1 6
出力例 1
3
すぬけ君は、座標が \dots,-4,-1,2,5,8,11,14\dots である地点にクリスマスツリーを立てます。 これらのうち高橋君と青木君の間にあるのは、座標が -1,2,5 である地点に立てられる 3 本です。
入力例 2
-2 2 1 1
出力例 2
0
高橋君と青木君が同じ地点に立っていることもあります。
入力例 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
出力例 3
273142010859
Score : 250 points
Problem Statement
There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.
Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.
Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Constraints
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- All input values are integers.
Input
Input is given from Standard Input in the following format:
A M L R
Output
Print the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Sample Input 1
5 3 -1 6
Sample Output 1
3
Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.
Sample Input 2
-2 2 1 1
Sample Output 2
0
Sometimes, Takahashi and Aoki are standing at the same point.
Sample Input 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
Sample Output 3
273142010859
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英大文字からなる長さ 3 の文字列 T が、英小文字からなる文字列 S の 空港コード であるとは、 T が S から次のいずれかの方法により得られることとします。
- S の長さ 3 の（連続とは限らない）部分列をとり、それを英大文字に変換したものを T とする
- S の長さ 2 の（連続とは限らない）部分列をとり、それを英大文字に変換したものの末尾に
Xを追加したものを T とする
文字列 S, T が与えられるので、 T が S の空港コードであるか判定してください。
制約
- S は英小文字からなる長さ 3 以上 10^5 以下の文字列
- T は英大文字からなる長さ 3 の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が S の空港コードであるならば Yes を、そうでないならば No を出力せよ。
入力例 1
narita NRT
出力例 1
Yes
narita の部分列 nrt を英大文字に変換した文字列 NRT は、 narita の空港コードです。
入力例 2
losangeles LAX
出力例 2
Yes
losangeles の部分列 la を英大文字に変換した文字列 LA の末尾に X を追加したもの LAX は、 losangeles の空港コードです。
入力例 3
snuke RNG
出力例 3
No
Score: 300 points
Problem Statement
A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:
- Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
- Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append
Xto the end to form T.
Given strings S and T, determine if T is an airport code for S.
Constraints
- S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
- T is a string of uppercase English letters with a length of 3.
Input
The input is given from Standard Input in the following format:
S T
Output
Print Yes if T is an airport code for S, and No otherwise.
Sample Input 1
narita NRT
Sample Output 1
Yes
The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.
Sample Input 2
losangeles LAX
Sample Output 2
Yes
The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.
Sample Input 3
snuke RNG
Sample Output 3
No
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。
i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。
- i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。
制約
- N は 2 以上 3000 以下の偶数
- A_{i, j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}
出力
すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。
B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}
入力例 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
出力例 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
操作によってグリッドの各マスの色は以下のように変化します。
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
入力例 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
出力例 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
入力例 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
出力例 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Score : 400 points
Problem Statement
You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.
Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.
- For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.
Constraints
- N is an even number between 2 and 3000, inclusive.
- Each A_{i, j} is
#or..
Input
The input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:
B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}
Sample Input 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
Sample Output 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
The operations change the colors of the grid cells as follows:
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
Sample Input 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
Sample Output 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
Sample Input 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
Sample Output 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
正整数 N に対して、N を N 個つなげた整数を V_N とします。
より厳密には、N を文字列とみなしたものを N 個連結し、
それを再度整数とみなしたものを V_N とします。
例えば、V_3=333, V_{10}=10101010101010101010 です。
V_N を 998244353 で割った余りを求めてください。
制約
- 1\leq N\leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
V_N を 998244353 で割った余りを出力せよ。
入力例 1
5
出力例 1
55555
V_5=55555 を 998244353 で割った余りは 55555 です。
入力例 2
9
出力例 2
1755646
V_9=999999999 を 998244353 で割った余りは 1755646 です。
入力例 3
10000000000
出力例 3
468086693
入力が 32 bit 整数型に収まらない可能性があることに注意してください。
Score : 350 points
Problem Statement
For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.
Find the remainder when V_N is divided by 998244353.
Constraints
- 1 \leq N \leq 10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the remainder when V_N is divided by 998244353.
Sample Input 1
5
Sample Output 1
55555
The remainder when V_5=55555 is divided by 998244353 is 55555.
Sample Input 2
9
Sample Output 2
1755646
The remainder when V_9=999999999 is divided by 998244353 is 1755646.
Sample Input 3
10000000000
Sample Output 3
468086693
Note that the input may not fit into a 32-bit integer type.