Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
非負整数 X に対し、 i=0,1,\dots,K-1 の順に次の操作を行ったとき、操作を全て終えた時点での X を求めてください。
- X の 10^i の位以下を四捨五入する。
- 厳密には、 X を「 |Y-X| が最小となる 10^{i+1} の倍数のうち最大のもの」である Y に置き換える。
- 具体例を挙げる。
- 273 の 10^1 の位以下を四捨五入すれば 300 となる。
- 999 の 10^2 の位以下を四捨五入すれば 1000 となる。
- 100 の 10^9 の位以下を四捨五入すれば 0 となる。
- 1015 の 10^0 の位以下を四捨五入すれば 1020 となる。
制約
- X,K は整数
- 0 \le X < 10^{15}
- 1 \le K \le 15
入力
入力は以下の形式で標準入力から与えられる。
X K
出力
答えを整数として出力せよ。
入力例 1
2048 2
出力例 1
2100
操作の過程で、 X は 2048 \rightarrow 2050 \rightarrow 2100 と変化します。
入力例 2
1 15
出力例 2
0
入力例 3
999 3
出力例 3
1000
入力例 4
314159265358979 12
出力例 4
314000000000000
X は 32bit 整数型に収まらない可能性があります。
Score : 200 points
Problem Statement
Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.
- Round X off to the nearest 10^i.
- Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
- Here are some examples:
- Rounding 273 off to the nearest 10^2 yields 300.
- Rounding 999 off to the nearest 10^3 yields 1000.
- Rounding 100 off to the nearest 10^{10} yields 0.
- Rounding 1015 off to the nearest 10^1 yields 1020.
Constraints
- X and K are integers.
- 0 \le X < 10^{15}
- 1 \le K \le 15
Input
The input is given from Standard Input in the following format:
X K
Output
Print the answer as an integer.
Sample Input 1
2048 2
Sample Output 1
2100
X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.
Sample Input 2
1 15
Sample Output 2
0
Sample Input 3
999 3
Sample Output 3
1000
Sample Input 4
314159265358979 12
Sample Output 4
314000000000000
X may not fit into a 32-bit integer type.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。
X の各マスは以下のように塗られています。
- 各タイルは白いタイルまたは黒いタイルである。
- 白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
- タイル (1,1) は白いタイルである。
- 辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。
マス目 X を出力の形式に従って出力してください。
制約
- 1 \leq N,A,B \leq 10
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。
- S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の
.または#からなる文字列である。 - 各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は
.であり、黒く塗られているならば#である。
入力例 1
4 3 2
出力例 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
入力例 2
5 1 5
出力例 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
入力例 3
4 4 1
出力例 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
入力例 4
1 4 4
出力例 4
.... .... .... ....
Score : 200 points
Problem Statement
Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.
Each square of X is painted as follows.
- Each tile is either a white tile or a black tile.
- Every square in a white tile is painted white; every square in a black tile is painted black.
- Tile (1,1) is a white tile.
- Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).
Print the grid X in the format specified in the Output section.
Constraints
- 1 \leq N,A,B \leq 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.
- Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of
.and#. - For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is
.if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is#if the square is painted black.
Sample Input 1
4 3 2
Sample Output 1
..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##.. ..##..## ..##..## ..##..## ##..##.. ##..##.. ##..##..
Sample Input 2
5 1 5
Sample Output 2
.....#####.....#####..... #####.....#####.....##### .....#####.....#####..... #####.....#####.....##### .....#####.....#####.....
Sample Input 3
4 4 1
Sample Output 3
.#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#. .#.# .#.# .#.# .#.# #.#. #.#. #.#. #.#.
Sample Input 4
1 4 4
Sample Output 4
.... .... .... ....
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N),B=(B_1,\ldots,B_N) が与えられます。
以下の条件を全て満たす長さ N の数列 X=(X_1,\ldots,X_N) が存在するかを判定してください。
-
すべての i(1\leq i\leq N) について、X_i = A_i または X_i = B_i
-
すべての i(1\leq i\leq N-1) について、|X_i - X_{i+1}| \leq K
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \ldots A_N B_1 \ldots B_N
出力
条件を全て満たす X が存在するならば Yes と、存在しないならば No と出力せよ。
入力例 1
5 4 9 8 3 7 2 1 6 2 9 5
出力例 1
Yes
X=(9,6,3,7,5) が全ての条件を満たします。
入力例 2
4 90 1 1 1 100 1 2 3 100
出力例 2
No
条件を満たす X は存在しません。
入力例 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
出力例 3
Yes
Score : 300 points
Problem Statement
You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).
Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.
-
X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).
-
|X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 \ldots A_N B_1 \ldots B_N
Output
If there is an X that satisfies all of the conditions, print Yes; otherwise, print No.
Sample Input 1
5 4 9 8 3 7 2 1 6 2 9 5
Sample Output 1
Yes
X=(9,6,3,7,5) satisfies all conditions.
Sample Input 2
4 90 1 1 1 100 1 2 3 100
Sample Output 2
No
No X satisfies all conditions.
Sample Input 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は数直線上の座標 0 の位置にいます。
これから高橋君は N 回のジャンプを行います。i \, (1 \leq i \leq N) 回目のジャンプでは、正の方向に a_i または b_i 移動します。
N 回のジャンプの後に座標 X の位置にいるようにすることはできますか？
制約
- 1 \leq N \leq 100
- 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
- 1 \leq X \leq 10000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X a_1 b_1 \vdots a_N b_N
出力
N 回のジャンプの後に座標 X の位置にいるようにすることができるならば Yes と、そうでないなら No と出力せよ。
入力例 1
2 10 3 6 4 5
出力例 1
Yes
1 回目のジャンプでは b_1 (= 6) 移動し、2 回目のジャンプでは a_2 (= 4) 移動することで、座標 X (= 10) の位置にいるようにすることができます。
入力例 2
2 10 10 100 10 100
出力例 2
No
1 回目のジャンプの後に座標 X (= 10) の位置にいるようにすることはできますが、全てのジャンプの後に座標 X (= 10) の位置にいるようにすることはできません。
入力例 3
4 12 1 8 5 7 3 4 2 6
出力例 3
Yes
Score : 300 points
Problem Statement
Takahashi is standing at the coordinate 0 on a number line.
He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.
Is it possible for him to be at the coordinate X after N jumps?
Constraints
- 1 \leq N \leq 100
- 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
- 1 \leq X \leq 10000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X a_1 b_1 \vdots a_N b_N
Output
If it is possible for Takahashi to be at the coordinate X after N jumps, print Yes; otherwise, print No.
Sample Input 1
2 10 3 6 4 5
Sample Output 1
Yes
By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).
Sample Input 2
2 10 10 100 10 100
Sample Output 2
No
He can be at the coordinate X (= 10) after the first jump, but not after all jumps.
Sample Input 3
4 12 1 8 5 7 3 4 2 6
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
正の整数 k について、サイズ k の ピラミッド数列 とは、長さ (2k-1) の数列であって各項の値が順に 1,2,\ldots,k-1,k,k-1,\ldots,2,1 であるようなものをさします。
長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に対して、次の操作のうち一方を選んで行うことを繰り返して (0 回でも良い) 得ることのできるピラミッド数列のサイズの最大値を求めてください。
- 数列の項を 1 つ選び、その項の値を 1 減少させる。
- 先頭または末尾の項を削除する。
なお、問題の制約のもとで、操作を繰り返すことで必ず 1 種類以上のピラミッド数列を得ることができることが証明できます。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
数列 A に問題文の操作を繰り返して得ることのできるピラミッド数列のサイズの最大値を出力せよ。
入力例 1
5 2 2 3 1 1
出力例 1
2
A=(2,2,3,1,1) から始めて、 次のようにして数列 A からサイズ 2 のピラミッド数列を作る事ができます。
- 第 3 項を選び、1 減少させる。数列は A=(2,2,2,1,1) となる。
- 先頭を削除する。数列は A=(2,2,1,1) となる。
- 末尾を削除する。数列は A=(2,2,1) となる。
- 第 1 項を選び、1 減少させる。数列は A=(1,2,1) となる。
(1,2,1) はサイズ 2 のピラミッド数列です。
一方、どのように操作を行ってもサイズ 3 以上のピラミッド数列を作ることはできないため 2 を出力します。
入力例 2
5 1 2 3 4 5
出力例 2
3
入力例 3
1 1000000000
出力例 3
1
Score: 400 points
Problem Statement
For a positive integer k, the Pyramid Sequence of size k is a sequence of length (2k-1) where the terms of the sequence have the values 1,2,\ldots,k-1,k,k-1,\ldots,2,1 in this order.
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
Find the maximum size of a Pyramid Sequence that can be obtained by repeatedly choosing and performing one of the following operations on A (possibly zero times).
- Choose one term of the sequence and decrease its value by 1.
- Remove the first or last term.
It can be proved that the constraints of the problem guarantee that at least one Pyramid Sequence can be obtained by repeating the operations.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the maximum size of the Pyramid Sequence that can be obtained by repeatedly performing the operations described in the problem statement on the sequence A.
Sample Input 1
5 2 2 3 1 1
Sample Output 1
2
Starting with A=(2,2,3,1,1), you can create a Pyramid Sequence of size 2 as follows:
- Choose the third term and decrease it by 1. The sequence becomes A=(2,2,2,1,1).
- Remove the first term. The sequence becomes A=(2,2,1,1).
- Remove the last term. The sequence becomes A=(2,2,1).
- Choose the first term and decrease it by 1. The sequence becomes A=(1,2,1).
(1,2,1) is a Pyramid Sequence of size 2.
On the other hand, there is no way to perform the operations to create a Pyramid Sequence of size 3 or larger, so you should print 2.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
3
Sample Input 3
1 1000000000
Sample Output 3
1