Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君は、全 N ページから成る書類を両面印刷します。両面印刷では、1 枚の紙に 2 ページ分のデータを印刷することが出来ます。
最小で何枚の紙が必要か求めてください。
制約
- N は整数
- 1 \leq N \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
5
出力例 1
3
1 枚目の紙に 1, 2 ページ目のデータを印刷し、 2 枚目の紙に 3, 4 ページ目のデータを印刷し、 3 枚目の紙に 5 ページ目のデータを印刷すれば、 3枚の紙に全てのデータを印刷することが出来ます。
入力例 2
2
出力例 2
1
入力例 3
100
出力例 3
50
Score : 100 points
Problem Statement
Takahashi wants to print a document with N pages double-sided, where two pages of data can be printed on one sheet of paper.
At least how many sheets of paper does he need?
Constraints
- N is an integer.
- 1 \leq N \leq 100
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
5
Sample Output 1
3
By printing the 1-st, 2-nd pages on the 1-st sheet, 3-rd and 4-th pages on the 2-nd sheet, and 5-th page on the 3-rd sheet, we can print all the data on 3 sheets of paper.
Sample Input 2
2
Sample Output 2
1
Sample Input 3
100
Sample Output 3
50
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
3\times3 のサイズのビンゴカードがあります。上から i 行目、左から j 列目の数は A_{i, j} です。
続けて、 N 個の数 b_1, b_2, \cdots, b_N が選ばれます。選ばれた数がビンゴカードの中にあった場合、ビンゴカードのその数に印を付けます。
N 個の数字が選ばれた時点でビンゴが達成されているか、則ち、縦・横・斜めのいずれか 1 列に並んだ 3 つの数の組であって、全てに印の付いているものが存在するかどうかを判定してください。
制約
- 入力は全て整数
- 1 \leq A_{i, j} \leq 100
- A_{i_1, j_1} \neq A_{i_2, j_2} ((i_1, j_1) \neq (i_2, j_2))
- 1 \leq N \leq 10
- 1 \leq b_i \leq 100
- b_i \neq b_j (i \neq j)
入力
入力は以下の形式で標準入力から与えられる。
A_{1, 1} A_{1, 2} A_{1, 3} A_{2, 1} A_{2, 2} A_{2, 3} A_{3, 1} A_{3, 2} A_{3, 3} N b_1 \vdots b_N
出力
ビンゴが達成されているならば Yes
と、そうでないならば No
と出力せよ。
入力例 1
84 97 66 79 89 11 61 59 7 7 89 7 87 79 24 84 30
出力例 1
Yes
A_{1, 1}, A_{2, 1}, A_{2, 2}, A_{3, 3} に印が付けられます。このとき、左上から右下にかけて斜めに 3 個の印が並び、ビンゴが成立しています。
入力例 2
41 7 46 26 89 2 78 92 8 5 6 45 16 57 17
出力例 2
No
印は 1 つも付いていません。
入力例 3
60 88 34 92 41 43 65 73 48 10 60 43 88 11 48 73 65 41 92 34
出力例 3
Yes
全てのマスに印が付いています。
Score : 200 points
Problem Statement
We have a bingo card with a 3\times3 grid. The square at the i-th row from the top and the j-th column from the left contains the number A_{i, j}.
The MC will choose N numbers, b_1, b_2, \cdots, b_N. If our bingo sheet contains some of those numbers, we will mark them on our sheet.
Determine whether we will have a bingo when the N numbers are chosen, that is, the sheet will contain three marked numbers in a row, column, or diagonal.
Constraints
- All values in input are integers.
- 1 \leq A_{i, j} \leq 100
- A_{i_1, j_1} \neq A_{i_2, j_2} ((i_1, j_1) \neq (i_2, j_2))
- 1 \leq N \leq 10
- 1 \leq b_i \leq 100
- b_i \neq b_j (i \neq j)
Input
Input is given from Standard Input in the following format:
A_{1, 1} A_{1, 2} A_{1, 3} A_{2, 1} A_{2, 2} A_{2, 3} A_{3, 1} A_{3, 2} A_{3, 3} N b_1 \vdots b_N
Output
If we will have a bingo, print Yes
; otherwise, print No
.
Sample Input 1
84 97 66 79 89 11 61 59 7 7 89 7 87 79 24 84 30
Sample Output 1
Yes
We will mark A_{1, 1}, A_{2, 1}, A_{2, 2}, A_{3, 3}, and complete the diagonal from the top-left to the bottom-right.
Sample Input 2
41 7 46 26 89 2 78 92 8 5 6 45 16 57 17
Sample Output 2
No
We will mark nothing.
Sample Input 3
60 88 34 92 41 43 65 73 48 10 60 43 88 11 48 73 65 41 92 34
Sample Output 3
Yes
We will mark all the squares.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
以下の条件を満たす 0 以上の整数が存在すれば、それらのうち最小のものを出力してください。そのような整数が存在しなければ、 -1
と出力してください。
- 十進表記で丁度 N 桁である。(0 は 1 桁の整数とする。その他の整数については、先頭に 0 をつけた表記は認めない。)
- 左から数えて s_i 桁目は c_i である。\left(i = 1, 2, \cdots, M\right)
制約
- 入力は全て整数
- 1 \leq N \leq 3
- 0 \leq M \leq 5
- 1 \leq s_i \leq N
- 0 \leq c_i \leq 9
入力
入力は以下の形式で標準入力から与えられる。
N M s_1 c_1 \vdots s_M c_M
出力
答えを出力せよ。
入力例 1
3 3 1 7 3 2 1 7
出力例 1
702
702 の左から 1 桁目は 7
であり、 3 桁目は 2
ですから、 702 は問の条件を満たします。また、 701 以下の非負整数は問の条件を満たしません。
入力例 2
3 2 2 1 2 3
出力例 2
-1
入力例 3
3 1 1 0
出力例 3
-1
Score : 300 points
Problem Statement
If there is an integer not less than 0 satisfying the following conditions, print the smallest such integer; otherwise, print -1
.
- The integer has exactly N digits in base ten. (We assume 0 to be a 1-digit integer. For other integers, leading zeros are not allowed.)
- The s_i-th digit from the left is c_i. \left(i = 1, 2, \cdots, M\right)
Constraints
- All values in input are integers.
- 1 \leq N \leq 3
- 0 \leq M \leq 5
- 1 \leq s_i \leq N
- 0 \leq c_i \leq 9
Input
Input is given from Standard Input in the following format:
N M s_1 c_1 \vdots s_M c_M
Output
Print the answer.
Sample Input 1
3 3 1 7 3 2 1 7
Sample Output 1
702
702 satisfies the conditions - its 1-st and 3-rd digits are 7
and 2
, respectively - while no non-negative integer less than 702 satisfies them.
Sample Input 2
3 2 2 1 2 3
Sample Output 2
-1
Sample Input 3
3 1 1 0
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
とあるSNSに、人 1 、人 2、 \cdots、人 N が登録しています。
この N 人の間には、 M 組の「友達関係」と、 K 組の「ブロック関係」が存在します。
i = 1, 2, \cdots, M について、人 A_i と人 B_i は友達関係にあります。この関係は双方向的です。
i = 1, 2, \cdots, K について、人 C_i と人 D_i はブロック関係にあります。この関係は双方向的です。
以下の 4 つの条件が満たされるとき、人 a は人 b の「友達候補」であると定義します。
- a \neq b である。
- 人 a と人 b はブロック関係に無い。
- 人 a と人 b は友達関係に無い。
- 1 以上 N 以下の整数から成るある数列 c_0, c_1, c_2, \cdots, c_L が存在し、c_0 = a であり、 c_L = b であり、 i = 0, 1, \cdots, L - 1 について、人 c_i と人 c_{i+1} は友達関係にある。
人 i = 1, 2, ... N について、友達候補の数を答えてください。
制約
- 入力は全て整数
- 2 ≤ N ≤ 10^5
- 0 \leq M \leq 10^5
- 0 \leq K \leq 10^5
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- 1 \leq C_i, D_i \leq N
- C_i \neq D_i
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- (A_i, B_i) \neq (B_j, A_j)
- (C_i, D_i) \neq (C_j, D_j) (i \neq j)
- (C_i, D_i) \neq (D_j, C_j)
- (A_i, B_i) \neq (C_j, D_j)
- (A_i, B_i) \neq (D_j, C_j)
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 B_1 \vdots A_M B_M C_1 D_1 \vdots C_K D_K
出力
答えを空白区切りで順に出力せよ。
入力例 1
4 4 1 2 1 1 3 3 2 3 4 4 1
出力例 1
0 1 0 1
人 2 と人 3 は友達関係にあり, 人 3 と人 4 は友達関係にあり, かつ人 2 と人 4 は友達関係にもブロック関係にもありませんから, 人 4 は人 2の友達候補です。
人 1 と人 3 は人 2 の友達候補ではありませんから, 人 2 の友達候補は 1 人です。
入力例 2
5 10 0 1 2 1 3 1 4 1 5 3 2 2 4 2 5 4 3 5 3 4 5
出力例 2
0 0 0 0 0
全ての人は他の全ての人と友達関係にありますが、友達候補は 0 人です。
入力例 3
10 9 3 10 1 6 7 8 2 2 5 8 4 7 3 10 9 6 4 5 8 2 6 7 5 3 1
出力例 3
1 3 5 4 3 3 3 3 1 0
Score : 400 points
Problem Statement
An SNS has N users - User 1, User 2, \cdots, User N.
Between these N users, there are some relationships - M friendships and K blockships.
For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.
For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.
We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:
- a \neq b.
- There is not a friendship between User a and User b.
- There is not a blockship between User a and User b.
- There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.
For each user i = 1, 2, ... N, how many friend candidates does it have?
Constraints
- All values in input are integers.
- 2 ≤ N ≤ 10^5
- 0 \leq M \leq 10^5
- 0 \leq K \leq 10^5
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- 1 \leq C_i, D_i \leq N
- C_i \neq D_i
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- (A_i, B_i) \neq (B_j, A_j)
- (C_i, D_i) \neq (C_j, D_j) (i \neq j)
- (C_i, D_i) \neq (D_j, C_j)
- (A_i, B_i) \neq (C_j, D_j)
- (A_i, B_i) \neq (D_j, C_j)
Input
Input is given from Standard Input in the following format:
N M K A_1 B_1 \vdots A_M B_M C_1 D_1 \vdots C_K D_K
Output
Print the answers in order, with space in between.
Sample Input 1
4 4 1 2 1 1 3 3 2 3 4 4 1
Sample Output 1
0 1 0 1
There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.
However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.
Sample Input 2
5 10 0 1 2 1 3 1 4 1 5 3 2 2 4 2 5 4 3 5 3 4 5
Sample Output 2
0 0 0 0 0
Everyone is a friend of everyone else and has no friend candidate.
Sample Input 3
10 9 3 10 1 6 7 8 2 2 5 8 4 7 3 10 9 6 4 5 8 2 6 7 5 3 1
Sample Output 3
1 3 5 4 3 3 3 3 1 0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の英小文字から成る文字列 S が与えられます。
Q 個のクエリを処理してください。各クエリは以下の 2 種類のいずれかです。
- type 1 : S の i_q 文字目を c_q に変更してください。元々 S の i_q 文字目が c_q である場合は、何もしないでください。
- type 2 : S の l_q 文字目から r_q 文字目まで (両端含む) から成る部分文字列に表れる文字が何種類あるかを答えてください。
制約
- N, Q, i_q, l_q, r_q は整数
- S は英小文字列
- c_q は英小文字
- 1 \leq N \leq 500000
- 1 \leq Q \leq 20000
- |S| = N
- 1 \leq i_q \leq N
- 1 \leq l_q \leq r_q \leq N
- 各テストケースに type 2 のクエリは 1 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
N S Q Query_1 \vdots Query_Q
4 行目から Q+3 行目の Query_iは、以下の 2 つのいずれかである。
1 i_q c_q
2 l_q r_q
出力
type 2 の各クエリについて答えを改行区切りで出力せよ。
入力例 1
7 abcdbbd 6 2 3 6 1 5 z 2 1 1 1 4 a 1 7 d 2 1 7
出力例 1
3 1 5
1 つ目のクエリでは、 cdbb
には b
, c
, d
の 3 種類の文字が含まれますから、 3 を出力します。
2 つ目のクエリで、 S が abcdzbd
に変更されます。
3 つ目のクエリでは、 a
には a
の 1 種類の文字が含まれますから、 1 を出力します。
4 つ目のクエリで、 S が abcazbd
に変更されます。
5 つ目のクエリでは、 S は変わらず abcazbd
のままです。
6 つ目のクエリでは、 abcazbd
にはa
, b
, c
, d
, z
の 5 種類の文字が含まれますから、 5 を出力します。
Score : 500 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters.
Process Q queries of the following two types:
- Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)
- Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).
Constraints
- N, Q, i_q, l_q, and r_q are integers.
- S is a string consisting of lowercase English letters.
- c_q is a lowercase English letter.
- 1 \leq N \leq 500000
- 1 \leq Q \leq 20000
- |S| = N
- 1 \leq i_q \leq N
- 1 \leq l_q \leq r_q \leq N
- There is at least one query of type 2 in each testcase.
Input
Input is given from Standard Input in the following format:
N S Q Query_1 \vdots Query_Q
Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:
1 i_q c_q
2 l_q r_q
Output
For each query of type 2, print a line containing the answer.
Sample Input 1
7 abcdbbd 6 2 3 6 1 5 z 2 1 1 1 4 a 1 7 d 2 1 7
Sample Output 1
3 1 5
In the first query, cdbb
contains three kinds of letters: b
, c
, and d
, so we print 3.
In the second query, S is modified to abcdzbd
.
In the third query, a
contains one kind of letter: a
, so we print 1.
In the fourth query, S is modified to abcazbd
.
In the fifth query, S does not change and is still abcazbd
.
In the sixth query, abcazbd
contains five kinds of letters: a
, b
, c
, d
, and z
, so we print 5.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は二次元平面である網の上で N 枚の肉を焼こうとしています。 i 枚目の肉の位置は \left(x_i, y_i\right)であり、火の通りにくさは c_i です。
高橋君は熱源を 1 つ持っています。熱源を位置 \left(X, Y\right) (X, Yは実数)に置くと、 i枚目の肉は、 焼けるまでに c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} 秒掛かります。
高橋君は肉を K 枚食べたいと考えています。 K 枚以上の肉が焼けるまでに掛かる時間を最小化するように高橋君が熱源を配置したとき、その所要時間を求めてください。
制約
- 入力は全て整数
- 1 \leq N \leq 60
- 1 \leq K \leq N
- -1000 \leq x_i , y_i \leq 1000
- \left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)
- 1 \leq c_i \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N K x_1 y_1 c_1 \vdots x_N y_N c_N
出力
答えを出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
4 3 -1 0 3 0 0 3 1 0 2 1 1 40
出力例 1
2.4
熱源を \left(-0.2, 0\right)に置くと、 2.4 秒後までに 1, 2, 3 枚目の肉が焼けます。これが最適な熱源の置き方です。
入力例 2
10 5 -879 981 26 890 -406 81 512 859 97 362 -955 25 128 553 17 -885 763 2 449 310 57 -656 -204 11 -270 76 40 184 170 16
出力例 2
7411.2252
Score : 600 points
Problem Statement
Takahashi wants to grill N pieces of meat on a grilling net, which can be seen as a two-dimensional plane. The coordinates of the i-th piece of meat are \left(x_i, y_i\right), and its hardness is c_i.
Takahashi can use one heat source to grill the meat. If he puts the heat source at coordinates \left(X, Y\right), where X and Y are real numbers, the i-th piece of meat will be ready to eat in c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} seconds.
Takahashi wants to eat K pieces of meat. Find the time required to have K or more pieces of meat ready if he put the heat source to minimize this time.
Constraints
- All values in input are integers.
- 1 \leq N \leq 60
- 1 \leq K \leq N
- -1000 \leq x_i , y_i \leq 1000
- \left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)
- 1 \leq c_i \leq 100
Input
Input is given from Standard Input in the following format:
N K x_1 y_1 c_1 \vdots x_N y_N c_N
Output
Print the answer.
It will be considered correct if its absolute or relative error from our answer is at most 10^{-6}.
Sample Input 1
4 3 -1 0 3 0 0 3 1 0 2 1 1 40
Sample Output 1
2.4
If we put the heat source at \left(-0.2, 0\right), the 1-st, 2-nd, and 3-rd pieces of meat will be ready to eat within 2.4 seconds. This is the optimal place to put the heat source.
Sample Input 2
10 5 -879 981 26 890 -406 81 512 859 97 362 -955 25 128 553 17 -885 763 2 449 310 57 -656 -204 11 -270 76 40 184 170 16
Sample Output 2
7411.2252