実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
トラックが 1 台あります。このトラックには合計で N キログラム以下の荷物を載せることができます。
このトラックに、1 個 W キログラムのレンガを最大でいくつ載せることができますか？
制約
- 1\leq N,W \leq 1000
- N,W は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N W
出力
トラックに載せることができるレンガの個数の最大値を整数で出力せよ。
入力例 1
10 3
出力例 1
3
レンガは 1 個 3 キログラムなので、3 個で 9 キログラム、4 個で 12 キログラムになります。
したがって、10 キログラムまで載せることができるトラックには、最大 3 個のレンガを載せることができます。
入力例 2
1000 1
出力例 2
1000
Score : 100 points
Problem Statement
We have a truck, which can carry at most N kilograms.
We will load bricks onto this truck, each of which weighs W kilograms. At most how many bricks can be loaded?
Constraints
- 1\leq N,W \leq 1000
- N and W are integers.
Input
Input is given from Standard Input in the following format:
N W
Output
Print an integer representing the maximum number of bricks that can be loaded onto the truck.
Sample Input 1
10 3
Sample Output 1
3
Each brick weighs 3 kilograms, so 3 bricks weigh 9 kilograms, and 4 weigh 12 kilograms.
Thus, we can load at most 3 bricks onto the truck that can carry at most 10 kilograms.
Sample Input 2
1000 1
Sample Output 2
1000
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
縦 H マス、横 W マスのマス目があります。上から i 行目、左から j 列目のマスには、ブロックが A_{i,j} 個あります。
どのマスにも同じ個数のブロックがある状態にするには、最小で何個のブロックを取り除けばよいでしょうか？
制約
- 1 \leq H,W \leq 100
- 0\leq A_{i,j} \leq 100
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
出力
取り除くブロックの個数の最小値を出力せよ。
入力例 1
2 3 2 2 3 3 2 2
出力例 1
2
右上と左下のマスからそれぞれ 1 つずつブロックを取り除くことで、どのマスにも 2 個のブロックがある状態にできます。
入力例 2
3 3 99 99 99 99 0 99 99 99 99
出力例 2
792
入力例 3
3 2 4 4 4 4 4 4
出力例 3
0
Score : 200 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has A_{i, j} blocks stacked on it.
At least how many blocks must be removed to make all squares have the same number of blocks?
Constraints
- 1 \leq H,W \leq 100
- 0\leq A_{i,j} \leq 100
Input
Input is given from Standard Input in the following format:
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
Output
Print the minimum number of blocks that must be removed.
Sample Input 1
2 3 2 2 3 3 2 2
Sample Output 1
2
Removing 1 block from the top-right square and 1 from the bottom-left square makes all squares have 2 blocks.
Sample Input 2
3 3 99 99 99 99 0 99 99 99 99
Sample Output 2
792
Sample Input 3
3 2 4 4 4 4 4 4
Sample Output 3
0
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
高橋君は 7 が嫌いです。
1 以上 N 以下の整数のうち、10 進法で表しても 8 進法で表しても 7 を含まないような数はいくつありますか？
制約
- 1 \leq N \leq 10^5
- N は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数で出力せよ。
入力例 1
20
出力例 1
17
1 以上 20 以下の整数のうち、10 進法で表したときに 7 を含む数は 7,17、8 進法で表したときに 7 を含む数は 7,15 です。
よって、7,15,17 以外の 17 個の数が条件を満たします。
入力例 2
100000
出力例 2
30555
Score : 300 points
Problem Statement
Takahashi hates the number 7.
We are interested in integers without the digit 7 in both decimal and octal. How many such integers are there between 1 and N (inclusive)?
Constraints
- 1 \leq N \leq 10^5
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print an integer representing the answer.
Sample Input 1
20
Sample Output 1
17
Among the integers between 1 and 20, 7 and 17 contain the digit 7 in decimal. Additionally, 7 and 15 contain the digit 7 in octal.
Thus, the 17 integers other than 7, 15, and 17 meet the requirement.
Sample Input 2
100000
Sample Output 2
30555
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 個の整数 A_1,\ldots,A_N が与えられます。
1\leq i < j \leq N を満たす全ての i,j の組についての |A_i-A_j| の和を求めてください。
すなわち、\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|} を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- |A_i|\leq 10^8
- A_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 5 1 2
出力例 1
8
|5-1|+|5-2|+|1-2|=8 です。
入力例 2
5 31 41 59 26 53
出力例 2
176
Score : 400 points
Problem Statement
Given are N integers A_1,\ldots,A_N.
Find the sum of |A_i-A_j| over all pairs i,j such that 1\leq i < j \leq N.
In other words, find \displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- |A_i|\leq 10^8
- A_i is an integer.
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 5 1 2
Sample Output 1
8
We have |5-1|+|5-2|+|1-2|=8.
Sample Input 2
5 31 41 59 26 53
Sample Output 2
176
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
円周上に N 個の椅子が並べられています。そのうち 1 つは玉座です。
高橋君は最初、玉座から時計回りに数えて S 個隣の椅子に座っており、次の行動を繰り返します。
行動：いま座っている椅子から時計回りに数えて K 個隣の椅子に移動し座る。
高橋君がはじめて玉座に座ることができるのは何回目の行動の後ですか？ ただし、玉座に座ることが永遠にできない場合は、代わりに -1 を出力してください。
T 個のテストケースに答えてください。
制約
- 1\leq T \leq 100
- 2\leq N \leq 10^9
- 1\leq S < N
- 1\leq K \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。1 行目は以下の通りである。
T
そして、続く T 行が T 個のテストケースを表す。これらはそれぞれ以下の形式の行である。
N S K
出力
各テストケースに対し、答えを出力せよ。テストケースごとに改行すること。
入力例 1
4 10 4 3 1000 11 2 998244353 897581057 595591169 10000 6 14
出力例 1
2 -1 249561088 3571
1 つ目のテストケースでは、椅子が 10 個あり、高橋君は最初、玉座から時計回りに数えて 4 個隣の席に座っています。 時計回りに 3 個隣の席に移動する行動を 2 回行うと玉座に座れます。
2 つ目のテストケースでは、高橋君が玉座に座ることは永遠にできないので、-1 を出力します。
Score : 500 points
Problem Statement
We have N chairs arranged in a circle, one of which is a throne.
Takahashi is initially sitting on the chair that is S chairs away from the throne in the clockwise direction. Now, he will repeat the move below.
Move: Go to the chair that is K chairs away from the chair he is currently sitting on in the clockwise direction.
After how many moves will he be sitting on the throne for the first time? If he is never going to sit on it, report -1 instead.
You are asked to solve T test cases.
Constraints
- 1\leq T \leq 100
- 2\leq N \leq 10^9
- 1\leq S < N
- 1\leq K \leq 10^9
Input
Input is given from Standard Input in the following format. The first line is in the format below:
T
Then, the following T lines represent T test cases. Each of these lines is in the format below:
N S K
Output
For each test case, print the answer in its own line.
Sample Input 1
4 10 4 3 1000 11 2 998244353 897581057 595591169 10000 6 14
Sample Output 1
2 -1 249561088 3571
In the first test case, we have 10 chairs, and Takahashi is initially sitting on the chair that is 4 chairs away from the throne in the clockwise direction. He will be sitting on the throne after 2 moves of moving 3 chairs in the clockwise direction.
In the second test case, he will never sit on the throne, so we should print -1.
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。
グリッド上には M 個の障害物があり、i 番目の障害物はマス (X_i,Y_i) に置かれています。
マス (1,1) に飛車の駒が置いてあります。飛車の駒は、今いる位置から右または下方向に伸びる直線上にあり、障害物を飛び越えずに到達できるマスに 1 手で移動することができます。
2 手以内の移動で飛車の駒が到達できるマスの数を求めてください。
制約
- 1\leq H,W \leq 2\times 10^5
- 0\leq M \leq 2\times 10^5
- 1\leq X_i \leq H
- 1\leq Y_i \leq W
- (X_i,Y_i) \neq (1,1)
- (X_i,Y_i) は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
H W M X_1 Y_1 \vdots X_M Y_M
出力
2 手以内の移動で飛車の駒が到達できるマスの数を出力せよ。
入力例 1
4 3 2 2 2 3 3
出力例 1
10
障害物のない全てのマスに 2 手以内で移動できます。
入力例 2
5 4 4 3 2 3 4 4 2 5 2
出力例 2
14
障害物のないマスのうち、(4,4),(5,4) 以外の全てのマスに 2 手以内で移動できます。
入力例 3
200000 200000 0
出力例 3
40000000000
Score : 600 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. Let Square (i,j) be the square at the i-th row and j-th column.
There are M obstacles on this grid. The i-th obstacle is at Square (X_i, Y_i).
We have a rook, the chess piece, on Square (1, 1). In one move, it can move to the right or downward through any number of squares without obstacles.
Find the number of squares the rook can reach in two moves or less.
Constraints
- 1\leq H,W \leq 2\times 10^5
- 0\leq M \leq 2\times 10^5
- 1\leq X_i \leq H
- 1\leq Y_i \leq W
- (X_i,Y_i) \neq (1,1)
- (X_i,Y_i) are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W M X_1 Y_1 \vdots X_M Y_M
Output
Print the number of squares the rook can reach in two moves or less.
Sample Input 1
4 3 2 2 2 3 3
Sample Output 1
10
Every square without an obstacle can be reached in two moves or less.
Sample Input 2
5 4 4 3 2 3 4 4 2 5 2
Sample Output 2
14
Every square without an obstacle except (4,4) and (5,4) can be reached in two moves or less.
Sample Input 3
200000 200000 0
Sample Output 3
40000000000