Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
整数 n に対して、 n を十進法で表したときの各桁の和を S(n) で表すことにします。 例えば、S(123) = 1 + 2 + 3 = 6 です。
2 つの 3 桁の整数 A, B が与えられます。S(A) と S(B) のうち大きい方の値を求めてください。
制約
- 入力は全て整数
- 100 \le A, B \le 999
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
S(A) と S(B) のうち大きい方の値を出力せよ。
S(A) と S(B) が等しい場合は、S(A) を出力せよ。
入力例 1
123 234
出力例 1
9
S(123) = 1 + 2 + 3 = 6, \ S(234) = 2 + 3 + 4 = 9 なので、2 つのうち大きい方である 9 を出力します。
入力例 2
593 953
出力例 2
17
入力例 3
100 999
出力例 3
27
Score : 100 points
Problem Statement
For an integer n, let S(n) be the sum of digits in the decimal notation of n. For example, we have S(123) = 1 + 2 + 3 = 6.
Given two 3-digit integers A and B, find the greater of S(A) and S(B).
Constraints
- All values in input are integers.
- 100 \le A, B \le 999
Input
Input is given from Standard Input in the following format:
A B
Output
Print the value of the greater of S(A) and S(B).
If these are equal, print S(A).
Sample Input 1
123 234
Sample Output 1
9
We have S(123) = 1 + 2 + 3 = 6 and S(234) = 2 + 3 + 4 = 9, so we should print the greater of these: 9.
Sample Input 2
593 953
Sample Output 2
17
Sample Input 3
100 999
Sample Output 3
27
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
xy 平面上に 1, 2, \dots, N の番号が付けられた N 個の点があります。点 i は (x_i, y_i) にあり、N 個の点の x 座標は互いに異なります。
以下の条件を満たす整数の組 (i, j)\ (i < j) の個数を求めてください。
- 点 i と点 j を通る直線の傾きが -1 以上 1 以下である。
制約
- 入力は全て整数
- 1 \le N \le 10^3
- |x_i|, |y_i| \le 10^3
- i \neq j ならば x_i \neq x_j
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 \vdots x_N y_N
出力
答えを出力せよ。
入力例 1
3 0 0 1 2 2 1
出力例 1
2
(0, 0) と (1, 2) を通る直線の傾きは 2、 (0, 0) と (2, 1) を通る直線の傾きは \frac{1}{2}、 (1, 2) と (2, 1) を通る直線の傾きは -1 です。
入力例 2
1 -691 273
出力例 2
0
入力例 3
10 -31 -35 8 -36 22 64 5 73 -14 8 18 -58 -41 -85 1 -88 -21 -85 -11 82
出力例 3
11
Score : 200 points
Problem Statement
On the xy-plane, We have N points numbered 1 to N. Point i is at (x_i, y_i), and the x-coordinates of the N points are pairwise different.
Find the number of pairs of integers (i, j)\ (i < j) that satisfy the following condition:
- The line passing through Point i and Point j has a slope between -1 and 1 (inclusive).
Constraints
- All values in input are integers.
- 1 \le N \le 10^3
- |x_i|, |y_i| \le 10^3
- x_i \neq x_j for i \neq j.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 \vdots x_N y_N
Output
Print the answer.
Sample Input 1
3 0 0 1 2 2 1
Sample Output 1
2
The slopes of the lines passing through (0, 0) and (1, 2), passing through (0, 0) and (2, 1), and passing through (1, 2) and (2, 1) are 2, \frac{1}{2}, and -1, respectively.
Sample Input 2
1 -691 273
Sample Output 2
0
Sample Input 3
10 -31 -35 8 -36 22 64 5 73 -14 8 18 -58 -41 -85 1 -88 -21 -85 -11 82
Sample Output 3
11
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の文字列 S_1, S_2, \dots, S_N が与えられます。
各文字列は、英小文字からなる空でない文字列の先頭に ! を 0 文字か 1 文字付加したものです。
文字列 T は、T の先頭に ! を 0 文字付加しても 1 文字付加しても S_1, S_2, \dots, S_N のいずれかに一致するとき、不満な文字列であるといいます。
不満な文字列があるかどうか判定し、あれば 1 つ示してください。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le |S_i| \le 10
- S_i は英小文字からなる空でない文字列の先頭に
!を 0 文字か 1 文字付加したものである。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \vdots S_N
出力
不満な文字列が存在する場合、不満な文字列を 1 つ出力せよ。
不満な文字列が存在しない場合、satisfiable と出力せよ。
入力例 1
6 a !a b !c d !d
出力例 1
a
文字列 a は、先頭に ! を 0 文字付加する場合は S_1 と、1 文字付加する場合は S_2 と一致するため不満な文字列です。
a の他に、d を出力しても正解になります。
入力例 2
10 red red red !orange yellow !blue cyan !green brown !gray
出力例 2
satisfiable
Score : 300 points
Problem Statement
Given are N strings S_1, S_2, \dots, S_N.
Each of these is a non-empty string consisting of lowercase English letters, with zero or one ! added at the beginning.
We say a string T to be unsatisfied when it matches one of S_1, S_2, \dots, S_N regardless of whether we add an ! at the beginning of T.
Determine whether there exists an unsatisfied string. If so, present one such string.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le |S_i| \le 10
- S_i is a non-empty string consisting of lowercase English letters, with zero or one
!added at the beginning.
Input
Input is given from Standard Input in the following format:
N S_1 \vdots S_N
Output
If there exists an unsatisfied string, print one such string.
If there is no unsatisfied string, print satisfiable.
Sample Input 1
6 a !a b !c d !d
Sample Output 1
a
a matches S_1 as is, and it matches S_2 when we add an !, so it is unsatisfied.
Besides that, d will also be accepted.
Sample Input 2
10 red red red !orange yellow !blue cyan !green brown !gray
Sample Output 2
satisfiable
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。
市には N 個の町があり、i 番目の町には青木派の有権者が A_i 人、高橋派の有権者が B_i 人います。他に有権者はいません。
高橋氏は、それぞれの町で演説を行うことができます。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。
一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 1 \le A_i, B_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
4 2 1 2 2 5 1 1 3
出力例 1
1
3 番目の町で演説を行うと、青木氏が 5 票、高橋氏が 6 票を得ます。
入力例 2
5 2 1 2 1 2 1 2 1 2 1
出力例 2
3
3 つの町で演説を行うと、青木氏が 4 票、高橋氏が 9 票を得ます。
入力例 3
1 273 691
出力例 3
1
Score : 400 points
Problem Statement
AtCoder City will hold a mayoral election. The candidates are Aoki and Takahashi.
The city consists of N towns, the i-th of which has A_i pro-Aoki voters and B_i pro-Takahashi voters. There are no other voters.
Takahashi can make a speech in each town.
If he makes a speech in some town, all voters in that town, pro-Takahashi or pro-Aoki, will vote for Takahashi.
On the other hand, if he does not make a speech in some town, the pro-Aoki voters in that town will vote for Aoki, and the pro-Takahashi voters will not vote.
To get more votes than Aoki, in how many towns does Takahashi need to make speeches at least?
Constraints
- All values in input are integers.
- 1 \le N \le 2 \times 10^5
- 1 \le A_i, B_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
4 2 1 2 2 5 1 1 3
Sample Output 1
1
After making a speech in the third town, Aoki and Takahashi will get 5 and 6 votes, respectively.
Sample Input 2
5 2 1 2 1 2 1 2 1 2 1
Sample Output 2
3
After making speeches in three towns, Aoki and Takahashi will get 4 and 9 votes, respectively.
Sample Input 3
1 273 691
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 N-1 辺から成る木があり、頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, N-1 の番号がついています。辺 i は頂点 a_i と頂点 b_i を結びます。 この木の各頂点には 1 つの整数が書かれています。頂点 i に書かれている整数を c_i とします。はじめ、 c_i = 0 です。
Q 個のクエリが与えられます。 i 番目のクエリでは、整数 t_i, e_i, x_i が与えられます。クエリの内容は以下の通りです。
- t_i = 1 のとき : 頂点 a_{e_i} から辺をたどって頂点 b_{e_i} を通らずに到達できるような全ての頂点 v に対して、c_v を c_v + x_i に書き換える。
- t_i = 2 のとき : 頂点 b_{e_i} から辺をたどって頂点 a_{e_i} を通らずに到達できるような全ての頂点 v に対して、c_v を c_v + x_i に書き換える。
すべてのクエリを処理した後、各頂点に書かれた整数を出力してください。
制約
- 入力は全て整数
- 2 \le N \le 2 \times 10^5
- 1 \le a_i, b_i \le N
- 与えられるグラフは木である
- 1 \le Q \le 2 \times 10^5
- t_i \in \{1, 2\}
- 1 \le e_i \le N-1
- 1 \le x_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
t_1 e_1 x_1
\vdots
t_Q e_Q x_Q
出力
すべてのクエリを処理した後の c_1, c_2, \dots, c_N をこの順に改行区切りで出力せよ。
入力例 1
5 1 2 2 3 2 4 4 5 4 1 1 1 1 4 10 2 1 100 2 2 1000
出力例 1
11 110 1110 110 100
1 番目のクエリでは、頂点 1 から始めて頂点 2 を通らずに到達できる頂点 1 に 1 を足します。
2 番目のクエリでは、頂点 4 から始めて頂点 5 を通らずに到達できる頂点 1, 2, 3, 4 に 10 を足します。
3 番目のクエリでは、頂点 2 から始めて頂点 1 を通らずに到達できる頂点 2, 3, 4, 5 に 100 を足します。
4 番目のクエリでは、頂点 3 から始めて頂点 2 を通らずに到達できる頂点 3 に 1000 を足します。
入力例 2
7 2 1 2 3 4 2 4 5 6 1 3 7 7 2 2 1 1 3 2 2 2 4 1 6 8 1 3 16 2 4 32 2 1 64
出力例 2
72 8 13 26 58 72 5
入力例 3
11 2 1 1 3 3 4 5 2 1 6 1 7 5 8 3 9 3 10 11 4 10 2 6 688 1 10 856 1 8 680 1 8 182 2 2 452 2 4 183 2 6 518 1 3 612 2 6 339 2 3 206
出力例 3
1657 1657 2109 1703 1474 1657 3202 1474 1247 2109 2559
Score : 500 points
Problem Statement
We have a tree with N vertices and N-1 edges, where the vertices are numbered 1, 2, \dots, N and the edges are numbered 1, 2, \dots, N-1. Edge i connects Vertices a_i and b_i.
Each vertex in the tree has an integer written on it. Let c_i be the integer written on Vertex i. Initially, c_i = 0.
You will be given Q queries. The i-th query, consisting of integers t_i, e_i, and x_i, is as follows:
- If t_i = 1: for each Vertex v reachable from Vertex a_{e_i} without visiting Vertex b_{e_i} by traversing edges, replace c_v with c_v + x_i.
- If t_i = 2: for each Vertex v reachable from Vertex b_{e_i} without visiting Vertex a_{e_i} by traversing edges, replace c_v with c_v + x_i.
After processing all queries, print the integer written on each vertex.
Constraints
- All values in input are integers.
- 2 \le N \le 2 \times 10^5
- 1 \le a_i, b_i \le N
- The given graph is a tree.
- 1 \le Q \le 2 \times 10^5
- t_i \in \{1, 2\}
- 1 \le e_i \le N-1
- 1 \le x_i \le 10^9
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
t_1 e_1 x_1
\vdots
t_Q e_Q x_Q
Output
Print the values c_1, c_2, \dots, c_N after processing all queries, each in its own line.
Sample Input 1
5 1 2 2 3 2 4 4 5 4 1 1 1 1 4 10 2 1 100 2 2 1000
Sample Output 1
11 110 1110 110 100
In the first query, we add 1 to each vertex reachable from Vertex 1 without visiting Vertex 2, that is, Vertex 1.
In the second query, we add 10 to each vertex reachable from Vertex 4 without visiting Vertex 5, that is, Vertex 1, 2, 3, 4.
In the third query, we add 100 to each vertex reachable from Vertex 2 without visiting Vertex 1, that is, Vertex 2, 3, 4, 5.
In the fourth query, we add 1000 to each vertex reachable from Vertex 3 without visiting Vertex 2, that is, Vertex 3.
Sample Input 2
7 2 1 2 3 4 2 4 5 6 1 3 7 7 2 2 1 1 3 2 2 2 4 1 6 8 1 3 16 2 4 32 2 1 64
Sample Output 2
72 8 13 26 58 72 5
Sample Input 3
11 2 1 1 3 3 4 5 2 1 6 1 7 5 8 3 9 3 10 11 4 10 2 6 688 1 10 856 1 8 680 1 8 182 2 2 452 2 4 183 2 6 518 1 3 612 2 6 339 2 3 206
Sample Output 3
1657 1657 2109 1703 1474 1657 3202 1474 1247 2109 2559
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。 このグラフの頂点には 1, 2, \dots, N の番号が付けられており、i 番目の辺は頂点 A_i と頂点 B_i を結びます。
以下の条件を満たすように辺を 0 本以上取り除いたときの、グラフの連結成分の個数としてあり得る最小値を求めてください。
条件
1 \le a < b \le N を満たす任意の頂点の組 (a, b) について、 頂点 a と頂点 b が同じ連結成分に属するならば、頂点 a と頂点 b を直接結ぶ辺が存在する。
制約
- 入力は全て整数
- 1 \le N \le 18
- 0 \le M \le \frac{N(N - 1)}{2}
- 1 \le A_i < B_i \le N
- i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
3 2 1 2 1 3
出力例 1
2
辺を取り除かないと、 (2, 3) の組が条件を満たしません。
どちらかの辺を取り除くと、頂点 2 と頂点 3 が非連結になり、条件を満たします。
入力例 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
1
入力例 3
10 11 9 10 2 10 8 9 3 4 5 8 1 8 5 6 2 5 3 6 6 9 1 9
出力例 3
5
入力例 4
18 0
出力例 4
18
Score : 600 points
Problem Statement
Given is a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the i-th edge connects Vertices A_i and B_i.
Find the minimum possible number of connected components in the graph after removing zero or more edges so that the following condition will be satisfied:
Condition:
For every pair of vertices (a, b) such that 1 \le a < b \le N, if Vertices a and b belong to the same connected component, there is an edge that directly connects Vertices a and b.
Constraints
- All values in input are integers.
- 1 \le N \le 18
- 0 \le M \le \frac{N(N - 1)}{2}
- 1 \le A_i < B_i \le N
- (A_i, B_i) \neq (A_j, B_j) for i \neq j.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
3 2 1 2 1 3
Sample Output 1
2
Without removing edges, the pair (2, 3) violates the condition. Removing one of the edges disconnects Vertices 2 and 3, satisfying the condition.
Sample Input 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 2
1
Sample Input 3
10 11 9 10 2 10 8 9 3 4 5 8 1 8 5 6 2 5 3 6 6 9 1 9
Sample Output 3
5
Sample Input 4
18 0
Sample Output 4
18