実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lfloor \dfrac{X}{10} \right\rfloor を出力してください。
注記
実数 x に対して、「x 以下の整数の中で最大の整数」を \left\lfloor x \right\rfloor と表します。たとえば \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, \left\lfloor 5 \right\rfloor = 5 のようになります。(詳しくは入出力例にある説明を参考にしてください。)
制約
- -10^{18} \leq X \leq 10^{18}
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X
出力
\left\lfloor \frac{X}{10} \right\rfloor を出力せよ。整数として出力する必要があることに注意せよ。
入力例 1
47
出力例 1
4
\frac{47}{10} = 4.7 以下の整数は、すべての負の整数および 0, 1, 2, 3, 4 です。この中で一番大きい整数は 4 なので、\left\lfloor \frac{47}{10} \right\rfloor = 4 となります。
入力例 2
-24
出力例 2
-3
\frac{-24}{10} = -2.4 以下の整数の中で一番大きい整数は -3 なので、 \left\lfloor \frac{-24}{10} \right\rfloor = -3 となります。
-2 は -2.4 よりも大きいので、条件を満たさないことに注意してください。
入力例 3
50
出力例 3
5
\frac{50}{10} = 5 以下の整数の中で一番大きい整数は 5 自身です。よって \left\lfloor \frac{50}{10} \right\rfloor = 5 となります。
入力例 4
-30
出力例 4
-3
上の例と同様に \left\lfloor \frac{-30}{10} \right\rfloor = -3 となります。
入力例 5
987654321987654321
出力例 5
98765432198765432
答えは 98765432198765432 となります。すべての桁が正しく合っているか確認しましょう。
なお、もしも自分で書いたプログラムが想定通りの挙動をしない場合は、使用しているプログラミング言語の仕様を調べてみることを推奨します。
また、自分の書いたコードがどのように動作するかを確認したい場合は問題文上部の「コードテスト」をご利用ください。
Score : 200 points
Problem Statement
Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.
Notes
For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)
Constraints
- -10^{18} \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
Print \left\lfloor \frac{X}{10} \right\rfloor. Note that it should be output as an integer.
Sample Input 1
47
Sample Output 1
4
The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.
Sample Input 2
-24
Sample Output 2
-3
Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.
Sample Input 3
50
Sample Output 3
5
The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.
Sample Input 4
-30
Sample Output 4
-3
Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.
Sample Input 5
987654321987654321
Sample Output 5
98765432198765432
The answer is 98765432198765432. Make sure that all the digits match.
If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。
(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。
順列とは？
(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。
辞書順とは？
長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
制約
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 \ldots P_N
出力
求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。
入力例 1
3 3 1 2
出力例 1
2 3 1
(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。
入力例 2
10 9 8 6 5 10 3 1 2 4 7
出力例 2
9 8 6 5 10 2 7 4 3 1
Score : 300 points
Problem Statement
You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).
Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.
What are permutations?
A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.
What is lexicographical order?
For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
Constraints
- 2 \leq N \leq 100
- 1 \leq P_i \leq N \, (1 \leq i \leq N)
- P_i \neq P_j \, (i \neq j)
- (P_1, \dots, P_N) \neq (1, \dots, N)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N P_1 \ldots P_N
Output
Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.
Sample Input 1
3 3 1 2
Sample Output 1
2 3 1
Here are the permutations of (1, 2, 3) in ascending lexicographical order.
- (1, 2, 3)
- (1, 3, 2)
- (2, 1, 3)
- (2, 3, 1)
- (3, 1, 2)
- (3, 2, 1)
Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).
Sample Input 2
10 9 8 6 5 10 3 1 2 4 7
Sample Output 2
9 8 6 5 10 2 7 4 3 1
実行時間制限: 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
配点 : 400 点
問題文
高橋君は N 枚のカードを手札として持っています。 i = 1, 2, \ldots, N について、i 番目のカードには非負整数 A_i が書かれています。
高橋君は、まず手札から好きなカードを 1 枚選んで、テーブルの上に置きます。 その後、高橋君は好きな回数（ 0 回でも良い）だけ、下記の操作を繰り返します。
- 最後にテーブルの上に置いたカードに書かれた整数を X とする。手札に整数 X または整数 (X+1)\bmod M が書かれたカードがあれば、そのうち好きなものを 1 枚選んで、テーブルの上に置く。ここで、(X+1)\bmod M は (X+1) を M で割ったあまりを表す。
最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i \lt M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
9 7 3 0 2 5 5 3 0 6 3
出力例 1
11
高橋君が、まず 4 番目のカード（書かれた整数は 5 ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。
- 5 番目のカード（書かれた整数は 5 ）をテーブルの上に置く。
- 8 番目のカード（書かれた整数は 6 ）をテーブルの上に置く。
- 2 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。
- 7 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。
このとき、最終的に手札に残ったカードは、1, 3, 6, 9 枚目のカードであり、それらに書かれた整数の総和は 3 + 2 + 3 +3 = 11 です。 これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。
入力例 2
1 10 4
出力例 2
0
入力例 3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
出力例 3
99
Score : 400 points
Problem Statement
Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.
First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).
- Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.
Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i \lt M
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
9 7 3 0 2 5 5 3 0 6 3
Sample Output 1
11
Assume that he first puts the fourth card (5 is written) on the table and then performs the following.
- Put the fifth card (5 is written) on the table.
- Put the eighth card (6 is written) on the table.
- Put the second card (0 is written) on the table.
- Put the seventh card (0 is written) on the table.
Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.
Sample Input 2
1 10 4
Sample Output 2
0
Sample Input 3
20 20 18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12
Sample Output 3
99