Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
AtCoder Beginner Contestが始まってから早数十年。
コンテストは 1 回目から順に ABC001,ABC002,... と名付けられてきましたが、 999 回目のコンテスト ABC999 を終え、これからのコンテストの名前をどうするかという問題が生じました。
そこで、1000 回目から 1998 回目のコンテストを順に ABD001,ABD002,...,ABD999 と名付けることとなりました。
1 以上 1998 以下の整数 N が与えられるので、N 回目のコンテストの名前の最初の 3 文字を出力してください。
制約
- 1 \leq N \leq 1998
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 回目のコンテストの名前の最初の 3 文字を出力せよ。
入力例 1
999
出力例 1
ABC
999 回目のコンテストの名前は ABC999 です。
入力例 2
1000
出力例 2
ABD
1000 回目のコンテストの名前は ABD001 です。
入力例 3
1481
出力例 3
ABD
1481 回目のコンテストの名前は ABD482 です。
Score : 100 points
Problem Statement
Decades have passed since the beginning of AtCoder Beginner Contest.
The contests are labeled as ABC001, ABC002, ... from the first round, but after the 999-th round ABC999, a problem occurred: how the future rounds should be labeled?
In the end, the labels for the rounds from the 1000-th to the 1998-th are decided: ABD001, ABD002, ..., ABD999.
You are given an integer N between 1 and 1998 (inclusive). Print the first three characters of the label of the N-th round of AtCoder Beginner Contest.
Constraints
- 1 \leq N \leq 1998
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the first three characters of the label of the N-th round of AtCoder Beginner Contest.
Sample Input 1
999
Sample Output 1
ABC
The 999-th round of AtCoder Beginner Contest is labeled as ABC999.
Sample Input 2
1000
Sample Output 2
ABD
The 1000-th round of AtCoder Beginner Contest is labeled as ABD001.
Sample Input 3
1481
Sample Output 3
ABD
The 1481-th round of AtCoder Beginner Contest is labeled as ABD482.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
ある村には、高さ 1,(1+2),(1+2+3),...,(1+2+3+...+999) メートルの 999 本の塔が、西から順に 1 メートル間隔で立っています。
長く降り続けた雪がようやく収まったので、まだ雪に完全には埋もれていない、互いに 1 メートル離れたある 2 つの塔の、雪に埋もれていない部分の高さを測ったところ、西側の塔は a メートル、東側の塔は b メートルでした。
積雪量と標高が村内のどこでも等しいと仮定したとき、雪が何メートル積もっているか求めてください。
ただし、雪は必ず 1 メートル以上積もっているものとします。
制約
- 1 \leq a < b < 499500(=1+2+3+...+999)
- 入力は全て整数
- 仮定が成り立たない入力は与えられない
入力
入力は以下の形式で標準入力から与えられる。
a b
出力
雪が x メートル積もっているとき、x を整数で出力せよ。
入力例 1
8 13
出力例 1
2
2 本の塔の高さはそれぞれ 10 メートルと 15 メートルです。 よって、雪が 2 メートル積もっているとわかります。
入力例 2
54 65
出力例 2
1
Score : 200 points
Problem Statement
In some village, there are 999 towers that are 1,(1+2),(1+2+3),...,(1+2+3+...+999) meters high from west to east, at intervals of 1 meter.
It had been snowing for a while before it finally stopped. For some two adjacent towers located 1 meter apart, we measured the lengths of the parts of those towers that are not covered with snow, and the results are a meters for the west tower, and b meters for the east tower.
Assuming that the depth of snow cover and the altitude are the same everywhere in the village, find the amount of the snow cover.
Assume also that the depth of the snow cover is always at least 1 meter.
Constraints
- 1 \leq a < b < 499500(=1+2+3+...+999)
- All values in input are integers.
- There is no input that contradicts the assumption.
Input
Input is given from Standard Input in the following format:
a b
Output
If the depth of the snow cover is x meters, print x as an integer.
Sample Input 1
8 13
Sample Output 1
2
The heights of the two towers are 10 meters and 15 meters, respectively. Thus, we can see that the depth of the snow cover is 2 meters.
Sample Input 2
54 65
Sample Output 2
1
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。
-
1 円
-
6 円、6^2(=36) 円、6^3(=216) 円、...
-
9 円、9^2(=81) 円、9^3(=729) 円、...
この銀行からちょうど N 円を引き出すには少なくとも何回の操作が必要か求めてください。
ただし、一度引き出したお金を再び預け入れてはならないとします。
制約
- 1 \leq N \leq 100000
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
この銀行からちょうど N 円を引き出すのに少なくとも x 回の操作が必要な時、x を出力せよ。
入力例 1
127
出力例 1
4
1 円、9 円、36(=6^2) 円、81(=9^2) 円を引き出す操作をそれぞれ 1 回ずつ行うことで、合計 4 回の操作で 127 円を引き出すことができます。
入力例 2
3
出力例 2
3
1 円を 引き出す操作を 3 回 行うことで、合計 3 回の操作で 3 円を引き出すことができます。
入力例 3
44852
出力例 3
16
Score : 300 points
Problem Statement
To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:
-
1 yen (the currency of Japan)
-
6 yen, 6^2(=36) yen, 6^3(=216) yen, ...
-
9 yen, 9^2(=81) yen, 9^3(=729) yen, ...
At least how many operations are required to withdraw exactly N yen in total?
It is not allowed to re-deposit the money you withdrew.
Constraints
- 1 \leq N \leq 100000
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
If at least x operations are required to withdraw exactly N yen in total, print x.
Sample Input 1
127
Sample Output 1
4
By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.
Sample Input 2
3
Sample Output 2
3
By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.
Sample Input 3
44852
Sample Output 3
16
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
N 行 N 列からなるグリッドがあり、上から i 行目の左から j 列目のマスを (i,j) とします。
これらのマスは色 1 から 色 C までのいずれかの色で塗られていなければならず、はじめに (i,j) は色 c_{i,j} で塗られています。
グリッドが、1 \leq i,j,x,y \leq N を満たす任意の i,j,x,y に対して以下の条件を満たす場合、良いグリッドであるとします。
-
(i+j) \% 3=(x+y) \% 3 ならば (i,j) の色と (x,y) の色は同じ
-
(i+j) \% 3 \neq (x+y) \% 3 ならば (i,j) の色と (x,y) の色は異なる
ただし、X \% Y は X を Y で割った余りを表すこととします。
グリッドが良いグリッドになるように 0 個以上のマスを塗り替えます。
あるマスにおいて、塗り替える前の色が X であり、塗り替えた後の色が Y である場合に感じる、そのマスに対して感じる違和感は D_{X,Y} です。
すべてのマスに対して感じる違和感の和のとりうる最小値を求めてください。
制約
- 1 \leq N \leq 500
- 3 \leq C \leq 30
- 1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)
- 1 \leq c_{i,j} \leq C
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}
出力
すべてのマスに対して感じる違和感の和のとりうる最小値が x のとき、x を出力せよ。
入力例 1
2 3 0 1 1 1 0 1 1 4 0 1 2 3 3
出力例 1
3
-
(1,1) を色 2 に塗り替えます。(1,1) に対して感じる違和感は D_{1,2}=1 となります。
-
(1,2) を色 3 に塗り替えます。(1,2) に対して感じる違和感は D_{2,3}=1 となります。
-
(2,2) を色 1 に塗り替えます。(2,2) に対して感じる違和感は D_{3,1}=1 となります。
このとき、すべてのマスに対して感じる違和感の和は 3 です。
なお、D_{i,j} \neq D_{j,i} である場合に注意してください。
入力例 2
4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2
出力例 2
428
Score : 400 points
Problem Statement
There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.
These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.
We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:
- If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.
- If (i+j) \% 3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.
Here, X \% Y represents X modulo Y.
We will repaint zero or more squares so that the grid will be a good grid.
For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.
Find the minimum possible sum of the wrongness of all the squares.
Constraints
- 1 \leq N \leq 500
- 3 \leq C \leq 30
- 1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)
- 1 \leq c_{i,j} \leq C
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}
Output
If the minimum possible sum of the wrongness of all the squares is x, print x.
Sample Input 1
2 3 0 1 1 1 0 1 1 4 0 1 2 3 3
Sample Output 1
3
- Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.
- Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.
- Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.
In this case, the sum of the wrongness of all the squares is 3.
Note that D_{i,j} \neq D_{j,i} is possible.
Sample Input 2
4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2
Sample Output 2
428