Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
縦 8 マス、横 8 マスの 64 マスからなるマス目があります。 上から i 行目 (1\leq i\leq8) 、左から j 列目 (1\leq j\leq8) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。
マスの状態は長さ 8 の文字列からなる長さ 8 の列 (S _ 1,S _ 2,S _ 3,\ldots,S _ 8) で表されます。
マス (i,j) (1\leq i\leq8,1\leq j\leq8) は、S _ i の j 文字目が . のとき空マスで、# のときコマが置かれています。
あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。
マス (i,j) に置かれているコマは、次のどちらかの条件を満たすコマを取ることができます。
- i 行目のマスに置かれている
- j 列目のマスに置かれている
たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。
あなたがコマを置くことができるマスがいくつあるか求めてください。
制約
- S _ i は
.,#からなる長さ 8 の文字列 (1\leq i\leq 8)
入力
入力は以下の形式で標準入力から与えられる。
S _ 1 S _ 2 S _ 3 S _ 4 S _ 5 S _ 6 S _ 7 S _ 8
出力
すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。
入力例 1
...#.... #....... .......# ....#... .#...... ........ ........ ..#.....
出力例 1
4
すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。
よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスはマス (6,6), マス (6,7), マス (7,6), マス (7,7) の 4 マスです。
入力例 2
........ ........ ........ ........ ........ ........ ........ ........
出力例 2
64
コマがひとつも置かれていないこともあります。
入力例 3
.#...... ..#..#.. ....#... ........ ..#....# ........ ...#.... ....#...
出力例 3
4
Score : 200 points
Problem Statement
There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).
Each square is either empty or has a piece placed on it.
The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8.
Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:
- Placed on a square in row i
- Placed on a square in column j
For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:
How many squares can you place your piece on?
Constraints
- Each S_i is a string of length 8 consisting of
.and#(1\leq i\leq 8).
Input
The input is given from Standard Input in the following format:
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
Output
Print the number of empty squares where you can place your piece without it being captured by any existing pieces.
Sample Input 1
...#.... #....... .......# ....#... .#...... ........ ........ ..#.....
Sample Output 1
4
The existing pieces can capture pieces placed on the squares shown in blue in the following figure:
Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).
Sample Input 2
........ ........ ........ ........ ........ ........ ........ ........
Sample Output 2
64
There may be no pieces on the grid.
Sample Input 3
.#...... ..#..#.. ....#... ........ ..#....# ........ ...#.... ....#...
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) が与えられます。
A_1,\ldots,A_N に含まれない最小の非負整数を求めてください。
制約
- 1 \leq N \leq 2000
- 0 \leq A_i \leq 2000
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
8 0 3 2 6 2 1 0 0
出力例 1
4
非負整数は 0,1,2,3,4,\ldots と続きます。
0,1,2,3 は A に含まれ、4 は A に含まれないので、答えは 4 です。
入力例 2
3 2000 2000 2000
出力例 2
0
Score : 200 points
Problem Statement
You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).
Find the smallest non-negative integer not in (A_1,\ldots,A_N).
Constraints
- 1 \leq N \leq 2000
- 0 \leq A_i \leq 2000
- 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
8 0 3 2 6 2 1 0 0
Sample Output 1
4
The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.
Sample Input 2
3 2000 2000 2000
Sample Output 2
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ある地方に、1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の道路があります。
i 番目の道路は街 A_i と街 B_i を双方向に結び、長さは C_i です。
好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。
制約
- 2 \leq N \leq 10
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1\leq A_i < B_i \leq N
- (A_i,B_i) は相異なる
- 1\leq C_i \leq 10^8
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 \vdots A_M B_M C_M
出力
答えを出力せよ。
入力例 1
4 4 1 2 1 2 3 10 1 3 100 1 4 1000
出力例 1
1110
4\to 1\to 3\to 2 と移動すると、通る道路の長さの和は 1110 となります。
入力例 2
10 1 5 9 1
出力例 2
1
道路と繋がっていない街が存在するかもしれません。
入力例 3
10 13 1 2 1 1 10 1 2 3 1 3 4 4 4 7 2 4 8 1 5 8 1 5 9 3 6 8 1 6 9 5 7 8 1 7 9 4 9 10 3
出力例 3
20
Score : 300 points
Problem Statement
A region has N towns numbered 1 to N, and M roads numbered 1 to M.
The i-th road connects town A_i and town B_i bidirectionally with length C_i.
Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.
Constraints
- 2 \leq N \leq 10
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i < B_i \leq N
- The pairs (A_i,B_i) are distinct.
- 1\leq C_i \leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 C_1 \vdots A_M B_M C_M
Output
Print the answer.
Sample Input 1
4 4 1 2 1 2 3 10 1 3 100 1 4 1000
Sample Output 1
1110
If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.
Sample Input 2
10 1 5 9 1
Sample Output 2
1
There may be a town that is not connected to a road.
Sample Input 3
10 13 1 2 1 1 10 1 2 3 1 3 4 4 4 7 2 4 8 1 5 8 1 5 9 3 6 8 1 6 9 5 7 8 1 7 9 4 9 10 3
Sample Output 3
20
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。
2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。
N 個の餅から 2 つの餅を選び、一方をもう一方の上に乗せることで鏡餅を 1 つ作ります。
何種類の鏡餅を作ることができるか求めてください。
ただし、鏡餅を構成する餅の大きさが同じでも、少なくとも一方が異なる餅であれば別の種類の鏡餅として数えます。
制約
- 2\leq N\leq 5\times 10 ^ 5
- 1\leq A _ i\leq 10 ^ 9\ (1\leq i\leq N)
- A _ i\leq A _ {i+1}\ (1\leq i\lt N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \cdots A _ N
出力
作ることができる鏡餅の種類数を出力せよ。
入力例 1
6 2 3 4 4 7 10
出力例 1
8
与えられた餅の大きさは以下のようになっています。
このとき、以下の 8 種類の鏡餅を作ることができます。
大きさ 4 の餅の上に大きさ 2 の餅を乗せた鏡餅や、大きさ 10 の餅の上に大きさ 4 の餅を乗せた鏡餅は 2 種類あることに注意してください。
入力例 2
3 387 388 389
出力例 2
0
鏡餅を 1 種類も作ることができない場合もあります。
入力例 3
32 1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
出力例 3
388
Score : 300 points
Problem Statement
There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.
Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.
You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.
Find how many different kinds of kagamimochi can be made.
Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.
Constraints
- 2 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
- A_i \leq A_{i+1} \ (1 \leq i < N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the number of different kinds of kagamimochi that can be made.
Sample Input 1
6 2 3 4 4 7 10
Sample Output 1
8
The sizes of the given mochi are as follows:
In this case, you can make the following eight kinds of kagamimochi:
Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.
Sample Input 2
3 387 388 389
Sample Output 2
0
It is possible that you cannot make any kagamimochi.
Sample Input 3
32 1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
Sample Output 3
388
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。
- f(0) = 1
- 任意の正整数 k に対し f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)
ここで、\lfloor A \rfloor は A の小数点以下を切り捨てた値を指します。
このとき、 f(N) を求めてください。
制約
- N は 0 \le N \le 10^{18} を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
3
f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3 です。
入力例 2
0
出力例 2
1
入力例 3
100
出力例 3
55
Score : 400 points
Problem Statement
A function f(x) defined for non-negative integers x satisfies the following conditions.
- f(0) = 1.
- f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.
Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.
Find f(N).
Constraints
- N is an integer satisfying 0 \le N \le 10^{18}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
3
We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.
Sample Input 2
0
Sample Output 2
1
Sample Input 3
100
Sample Output 3
55