Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
数直線があり、高橋君はこれを赤色と青色で次のように塗りました。
- X=L_1 から X=R_1 までをすべて赤色で塗る。
- X=L_2 から X=R_2 までをすべて青色で塗る。
数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。
制約
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
L_1 R_1 L_2 R_2
出力
両方の色で塗られている部分の長さを整数で出力せよ。
入力例 1
0 3 1 5
出力例 1
2
X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。
よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。
入力例 2
0 1 4 5
出力例 2
0
両方の色で塗られている部分はありません。
入力例 3
0 3 3 7
出力例 3
0
赤色と青色で塗られている部分が接している場合でも、 両方の色で塗られている部分の長さは 0 となります。
Score : 100 points
Problem Statement
We have a number line. Takahashi painted some parts of this line, as follows:
- First, he painted the part from X=L_1 to X=R_1 red.
- Next, he painted the part from X=L_2 to X=R_2 blue.
Find the length of the part of the line painted both red and blue.
Constraints
- 0\leq L_1<R_1\leq 100
- 0\leq L_2<R_2\leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
L_1 R_1 L_2 R_2
Output
Print the length of the part of the line painted both red and blue, as an integer.
Sample Input 1
0 3 1 5
Sample Output 1
2
The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.
Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.
Sample Input 2
0 1 4 5
Sample Output 2
0
No part is painted both red and blue.
Sample Input 3
0 3 3 7
Sample Output 3
0
If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P は (1,2,…,N) を並び替えてできる数列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 3 2 3 1 4
出力例 1
2
P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。
入力例 2
5 2 3 5 1 4 2
出力例 2
5
入力例 3
6 6 1 2 3 4 5 6
出力例 3
6
Score : 100 points
Problem Statement
You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P is a permutation of (1,2,…,N).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 3 2 3 1 4
Sample Output 1
2
We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.
Sample Input 2
5 2 3 5 1 4 2
Sample Output 2
5
Sample Input 3
6 6 1 2 3 4 5 6
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
キーエンスには世界各地に N 個の拠点があり、1 から N までの番号が付けられています。 拠点 i には W_i 人の社員が所属しており、世界標準時で 0 時のとき拠点 i は X_i 時です。
あなたはキーエンス全社で 1 時間の会議を開きたいです。 各社員は、会議の開催時間帯が所属する拠点における 9:00-18:00 の時間帯に完全に含まれる場合にのみ会議に参加できます。 なるべく多くの社員が参加できるように会議の開催時間帯を決めるとき、会議に参加できる社員の数の最大値を求めてください。
制約
- 1\leq N \leq 1000
- 1\leq W_i \leq 10^6
- 0\leq X_i < 24
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N W_1 X_1 W_2 X_2 \vdots W_N X_N
出力
会議に参加できる社員の数の最大値を出力せよ。
入力例 1
3 5 0 3 3 2 18
出力例 1
8
世界標準時で 14:00-15:00 の時間帯に会議を開催することを考えます。
- 拠点 1 における 14:00-15:00 の時間帯に会議が開催されるため、拠点 1 に所属する 5 人の社員は会議に参加できます。
- 拠点 2 における 17:00-18:00 の時間帯に会議が開催されるため、拠点 2 に所属する 3 人の社員は会議に参加できます。
- 拠点 3 における 8:00-9:00 の時間帯に会議が開催されるため、拠点 3 に所属する 2 人の社員は会議に参加できません。
よって、合計で 5+3=8 人の社員が会議に参加できます。 これより多くの社員が参加できるような会議の開催時間帯はありません。
入力例 2
2 1 10 1000000 20
出力例 2
1000000
入力例 3
6 31 3 20 8 11 5 4 3 47 14 1 18
出力例 3
67
Score : 250 points
Problem Statement
Keyence has N bases worldwide, numbered 1 to N. Base i has W_i employees, and at 0 o'clock in Coordinated Universal Time (UTC), it is X_i o'clock at base i.
You want to hold a one-hour meeting across the entire company. Each employee can only participate in the meeting if the meeting time is completely within the 9:00-18:00 time slot at their base. Find the maximum number of employees who can participate when deciding the meeting time to allow as many employees as possible to participate.
Constraints
- 1\leq N \leq 1000
- 1\leq W_i \leq 10^6
- 0\leq X_i < 24
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N W_1 X_1 W_2 X_2 \vdots W_N X_N
Output
Print the maximum number of employees who can participate in the meeting.
Sample Input 1
3 5 0 3 3 2 18
Sample Output 1
8
Consider holding the meeting from 14:00 to 15:00 in UTC.
- The meeting is held from 14:00 to 15:00 at base 1, so the 5 employees at base 1 can participate in the meeting.
- The meeting is held from 17:00 to 18:00 at base 2, so the 3 employees at base 2 can participate in the meeting.
- The meeting is held from 8:00 to 9:00 at base 3, so the 2 employees at base 3 cannot participate in the meeting.
Thus, a total of 5+3=8 employees can participate in the meeting. No meeting time allows more employees to participate.
Sample Input 2
2 1 10 1000000 20
Sample Output 2
1000000
Sample Input 3
6 31 3 20 8 11 5 4 3 47 14 1 18
Sample Output 3
67
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。
- 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
-
各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。
- j=0 または j=i の時、a_{i,j}=1
- それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}
制約
- 1 \leq N \leq 30
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。
入力例 1
3
出力例 1
1 1 1 1 2 1
入力例 2
10
出力例 2
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Score : 200 points
Problem Statement
Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.
- For each i (0\leq i \leq N-1), the length of A_i is i+1.
- For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
- a_{i,j}=1, if j=0 or j=i.
- a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.
Constraints
- 1 \leq N \leq 30
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.
Sample Input 1
3
Sample Output 1
1 1 1 1 2 1
Sample Input 2
10
Sample Output 2
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 枚の靴下があります。i 枚目の靴下の色は A_i です。
あなたは以下の操作をできるだけ多い回数行いたいです。最大で何回行うことができますか？
- まだペアになっていない靴下の中から同じ色の靴下を 2 枚選んでペアにする。
制約
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
6 4 1 7 4 1 4
出力例 1
2
以下のようにして、2 回の操作を行うことができます。
- 色が 1 である靴下を 2 枚選んでペアにする。
- 色が 4 である靴下を 2 枚選んでペアにする。
このとき、色が 4 である靴下と 7 である靴下が 1 枚ずつ残るため、これ以上操作はできません。 また、どのように操作をしても 3 回以上操作を行うことはできないため、2 を出力します。
入力例 2
1 158260522
出力例 2
0
入力例 3
10 295 2 29 295 29 2 29 295 2 29
出力例 3
4
Score : 300 points
Problem Statement
You have N socks. The color of the i-th sock is A_i.
You want to perform the following operation as many times as possible. How many times can it be performed at most?
- Choose two same-colored socks that are not paired yet, and pair them.
Constraints
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print an integer representing the answer.
Sample Input 1
6 4 1 7 4 1 4
Sample Output 1
2
You can do the operation twice as follows.
- Choose two socks with the color 1 and pair them.
- Choose two socks with the color 4 and pair them.
Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.
Sample Input 2
1 158260522
Sample Output 2
0
Sample Input 3
10 295 2 29 295 29 2 29 295 2 29
Sample Output 3
4