CodeEff/ECCO huggingface dataset:
Problem Description: Score : 300 points
Problem Statement
There is a circular pond with a perimeter of
K
meters, and
N
houses around them.
The
i
-th house is built at a distance of
A_i
meters from the northmost point of the pond, measured clockwise around the pond.
When traveling between these houses, you can only go around the pond.
Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the
N
houses.
Constraints
2 \leq K \leq 10^6
2 \leq N \leq 2 \times 10^5
0 \leq A_1 < ... < A_N < K
All values in input are integers.
Input
Input is given from Standard Input in the following format:
K
N
A_1
A_2
...
A_N
Output
Print the minimum distance that needs to be traveled when you start at one of the houses and visit all the
N
houses.
Sample Input 1
20 3
5 10 15
Sample Output 1
10
If you start at the
1
-st house and go to the
2
-nd and
3
-rd houses in this order, the total distance traveled will be
10
.
Sample Input 2
20 3
0 5 15
Sample Output 2
10
If you start at the
2
-nd house and go to the
1
-st and
3
-rd houses in this order, the total distance traveled will be
10
.
Problem Description: Score : 400 points
Problem Statement
We have an undirected graph
G
with
N
vertices numbered
1
to
N
and
N
edges as follows:
For each
i=1,2,...,N-1
, there is an edge between Vertex
i
and Vertex
i+1
.
There is an edge between Vertex
X
and Vertex
Y
.
For each
k=1,2,...,N-1
, solve the problem below:
Find the number of pairs of integers
(i,j) (1 \leq i < j \leq N)
such that the shortest distance between Vertex
i
and Vertex
j
in
G
is
k
.
Constraints
3 \leq N \leq 2 \times 10^3
1 \leq X,Y \leq N
X+1 < Y
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
X
Y
Output
For each
k=1, 2, ..., N-1
in this order, print a line containing the answer to the problem.
Sample Input 1
5 2 4
Sample Output 1
5
4
1
0
The graph in this input is as follows:
There are five pairs
(i,j) (1 \leq i < j \leq N)
such that the shortest distance between Vertex
i
and Vertex
j
is
1
:
(1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5)
.
There are four pairs
(i,j) (1 \leq i < j \leq N)
such that the shortest distance between Vertex
i
and Vertex
j
is
2
:
(1,3)\,,(1,4)\,,(2,5)\,,(3,5)
.
There is one pair
(i,j) (1 \leq i < j \leq N)
such that the shortest distance between Vertex
i
and Vertex
j
is
3
:
(1,5)
.
There are no pairs
(i,j) (1 \leq i < j \leq N)
such that the shortest distance between Vertex
i
and Vertex
j
is
4
.
Sample Input 2
3 1 3
Sample Output 2
3
0
The graph in this input is as follows:
Sample Input 3
7 3 7
Sample Output 3
7
8
4
2
0
0
Sample Input 4
10 4 8
Sample Output 4
10
12
10
8
4
1
0
0
0
Problem Description: Score : 500 points
Problem Statement
You are going to eat
X
red apples and
Y
green apples.
You have
A
red apples of deliciousness
p_1,p_2, \dots, p_A
,
B
green apples of deliciousness
q_1,q_2, \dots, q_B
, and
C
colorless apples of deliciousness
r_1,r_2, \dots, r_C
.
Before eating a colorless apple, you can paint it red or green, and it will count as a red or green apple, respectively.
From the apples above, you will choose the apples to eat while making the sum of the deliciousness of the eaten apples as large as possible.
Find the maximum possible sum of the deliciousness of the eaten apples that can be achieved when optimally coloring zero or more colorless apples.
Constraints
1 \leq X \leq A \leq 10^5
1 \leq Y \leq B \leq 10^5
1 \leq C \leq 10^5
1 \leq p_i \leq 10^9
1 \leq q_i \leq 10^9
1 \leq r_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Y
A
B
C
p_1
p_2
...
p_A
q_1
q_2
...
q_B
r_1
r_2
...
r_C
Output
Print the maximum possible sum of the deliciousness of the eaten apples.
Sample Input 1
1 2 2 2 1
2 4
5 1
3
Sample Output 1
12
The maximum possible sum of the deliciousness of the eaten apples can be achieved as follows:
Eat the
2
-nd red apple.
Eat the
1
-st green apple.
Paint the
1
-st colorless apple green and eat it.
Sample Input 2
2 2 2 2 2
8 6
9 1
2 1
Sample Output 2
25
Sample Input 3
2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4
Sample Output 3
74
Problem Description: Score : 600 points
Problem Statement
We have a tree with
N
vertices numbered
1
to
N
. The
i
-th edge in this tree connects Vertex
a_i
and
b_i
.
For each
k=1, ..., N
, solve the problem below:
Consider writing a number on each vertex in the tree in the following manner:
First, write
1
on Vertex
k
.
Then, for each of the numbers
2, ..., N
in this order, write the number on the vertex chosen as follows:
Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.
Find the number of ways in which we can write the numbers on the vertices, modulo
(10^9+7)
.
Constraints
2 \leq N \leq 2 \times 10^5
1 \leq a_i,b_i \leq N
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1
b_1
:
a_{N-1}
b_{N-1}
Output
For each
k=1, 2, ..., N
in this order, print a line containing the answer to the problem.
Sample Input 1
3
1 2
1 3
Sample Output 1
2
1
1
The graph in this input is as follows:
For
k=1
, there are two ways in which we can write the numbers on the vertices, as follows:
Writing
1, 2, 3
on Vertex
1, 2, 3
, respectively
Writing
1, 3, 2
on Vertex
1, 2, 3
, respectively
Sample Input 2
2
1 2
Sample Output 2
1
1
The graph in this input is as follows:
Sample Input 3
5
1 2
2 3
3 4
3 5
Sample Output 3
2
8
12
3
3
The graph in this input is as follows:
Sample Input 4
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
Sample Output 4
40
280
840
120
120
504
72
72
The graph in this input is as follows:
Problem Description: Score : 100 points
Problem Statement
We have
N+M
balls, each of which has an integer written on it.
It is known that:
The numbers written on
N
of the balls are even.
The numbers written on
M
of the balls are odd.
Find the number of ways to choose two of the
N+M
balls (disregarding order) so that the sum of the numbers written on them is even.
It can be shown that this count does not depend on the actual values written on the balls.
Constraints
0 \leq N,M \leq 100
2 \leq N+M
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
Output
Print the answer.
Sample Input 1
2 1
Sample Output 1
1
For example, let us assume that the numbers written on the three balls are
1,2,4
.
If we choose the two balls with
1
and
2
, the sum is odd;
If we choose the two balls with
1
and
4
, the sum is odd;
If we choose the two balls with
2
and
4
, the sum is even.
Thus, the answer is
1
.
Sample Input 2
4 3
Sample Output 2
9
Sample Input 3
1 1
Sample Output 3
0
Sample Input 4
13 3
Sample Output 4
81
Sample Input 5
0 3
Sample Output 5
3
Problem Description: Score : 300 points
Problem Statement
Given is a positive integer
L
.
Find the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is
L
.
Constraints
1 ≤ L ≤ 1000
L
is an integer.
Input
Input is given from Standard Input in the following format:
L
Output
Print the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is
L
.
Your output is considered correct if its absolute or relative error from our answer is at most
10^{-6}
.
Sample Input 1
3
Sample Output 1
1.000000000000
For example, a rectangular cuboid whose dimensions are
0.8
,
1
, and
1.2
has a volume of
0.96
.
On the other hand, if the dimensions are
1
,
1
, and
1
, the volume of the rectangular cuboid is
1
, which is greater.
Sample Input 2
999
Sample Output 2
36926037.000000000000
Problem Description: Score : 500 points
Problem Statement
We have a chocolate bar partitioned into
H
horizontal rows and
W
vertical columns of squares.
The square
(i, j)
at the
i
-th row from the top and the
j
-th column from the left is dark if
S_{i,j}
is
0
, and white if
S_{i,j}
is
1
.
We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.
How many times do we need to cut the bar so that every block after the cuts has
K
or less white squares?
Constraints
1 \leq H \leq 10
1 \leq W \leq 1000
1 \leq K \leq H \times W
S_{i,j}
is
0
or
1
.
Input
Input is given from Standard Input in the following format:
H
W
K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}
Output
Print the number of minimum times the bar needs to be cut so that every block after the cuts has
K
or less white squares.
Sample Input 1
3 5 4
11100
10001
00111
Sample Output 1
2
For example, cutting between the
1
-st and
2
-nd rows and between the
3
-rd and
4
-th columns - as shown in the figure to the left - works.
Note that we cannot cut the bar in the ways shown in the two figures to the right.
Sample Input 2
3 5 8
11100
10001
00111
Sample Output 2
0
No cut is needed.
Sample Input 3
4 10 4
1110010010
1000101110
0011101001
1101000111
Sample Output 3
3
Problem Description: Score : 900 points
Problem Statement
Given are simple undirected graphs
X
,
Y
,
Z
, with
N
vertices each and
M_1
,
M_2
,
M_3
edges, respectively.
The vertices in
X
,
Y
,
Z
are respectively called
x_1, x_2, \dots, x_N
,
y_1, y_2, \dots, y_N
,
z_1, z_2, \dots, z_N
.
The edges in
X
,
Y
,
Z
are respectively
(x_{a_i}, x_{b_i})
,
(y_{c_i}, y_{d_i})
,
(z_{e_i}, z_{f_i})
.
Based on
X
,
Y
,
Z
, we will build another undirected graph
W
with
N^3
vertices.
There are
N^3
ways to choose a vertex from each of the graphs
X
,
Y
,
Z
. Each of these choices corresponds to the vertices in
W
one-to-one. Let
(x_i, y_j, z_k)
denote the vertex in
W
corresponding to the choice of
x_i, y_j, z_k
.
We will span edges in
W
as follows:
For each edge
(x_u, x_v)
in
X
and each
w, l
, span an edge between
(x_u, y_w, z_l)
and
(x_v, y_w, z_l)
.
For each edge
(y_u, y_v)
in
Y
and each
w, l
, span an edge between
(x_w, y_u, z_l)
and
(x_w, y_v, z_l)
.
For each edge
(z_u, z_v)
in
Z
and each
w, l
, span an edge between
(x_w, y_l, z_u)
and
(x_w, y_l, z_v)
.
Then, let the weight of the vertex
(x_i, y_j, z_k)
in
W
be
1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}
. Find the maximum possible total weight of the vertices in an
independent set
in
W
, and print that total weight modulo
998,244,353
.
Constraints
2 \leq N \leq 100,000
1 \leq M_1, M_2, M_3 \leq 100,000
1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N
X
,
Y
, and
Z
are simple, that is, they have no self-loops and no multiple edges.
Input
Input is given from Standard Input in the following format:
N
M_1
a_1
b_1
a_2
b_2
\vdots
a_{M_1}
b_{M_1}
M_2
c_1
d_1
c_2
d_2
\vdots
c_{M_2}
d_{M_2}
M_3
e_1
f_1
e_2
f_2
\vdots
e_{M_3}
f_{M_3}
Output
Print the maximum possible total weight of an independent set in
W
, modulo
998,244,353
.
Sample Input 1
2
1
1 2
1
1 2
1
1 2
Sample Output 1
46494701
The maximum possible total weight of an independent set is that of the set
(x_2, y_1, z_1)
,
(x_1, y_2, z_1)
,
(x_1, y_1, z_2)
,
(x_2, y_2, z_2)
. The output should be
(3 \times 10^{72} + 10^{108})
modulo
998,244,353
, which is
46,494,701
.
Sample Input 2
3
3
1 3
1 2
3 2
2
2 1
2 3
1
2 1
Sample Output 2
883188316
Sample Input 3
100000
1
1 2
1
99999 100000
1
1 100000
Sample Output 3
318525248
Problem Description: Score : 1200 points
Problem Statement
Given is a positive integer
N
.
Find the number of permutations
(P_1,P_2,\cdots,P_{3N})
of
(1,2,\cdots,3N)
that can be generated through the procedure below.
This number can be enormous, so print it modulo a prime number
M
.
Make
N
sequences
A_1,A_2,\cdots,A_N
of length
3
each, using each of the integers
1
through
3N
exactly once.
Let
P
be an empty sequence, and do the following operation
3N
times.
Among the elements that are at the beginning of one of the sequences
A_i
that is non-empty, let the smallest be
x
.
Remove
x
from the sequence, and add
x
at the end of
P
.
Constraints
1 \leq N \leq 2000
10^8 \leq M \leq 10^9+7
M
is a prime number.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
Output
Print the number of permutations modulo
M
.
Sample Input 1
1 998244353
Sample Output 1
6
All permutations of length
3
count.
Sample Input 2
2 998244353
Sample Output 2
261
Sample Input 3
314 1000000007
Sample Output 3
182908545
Problem Description: Score : 100 points
Problem Statement
Print the
K
-th element of the following sequence of length
32
:
1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
Constraints
1 \leq K \leq 32
All values in input are integers.
Input
Input is given from Standard Input in the following format:
K
Output
Print the
K
-th element.
Sample Input 1
6
Sample Output 1
2
The
6
-th element is
2
.
Sample Input 2
27
Sample Output 2
5
The
27
-th element is
5
.
Problem Description: Score : 200 points
Problem Statement
We have a board with
H
horizontal rows and
W
vertical columns of squares.
There is a bishop at the top-left square on this board.
How many squares can this bishop reach by zero or more movements?
Here the bishop can only move diagonally.
More formally, the bishop can move from the square at the
r_1
-th row (from the top) and the
c_1
-th column (from the left) to the square at the
r_2
-th row and the
c_2
-th column if and only if exactly one of the following holds:
r_1 + c_1 = r_2 + c_2
r_1 - c_1 = r_2 - c_2
For example, in the following figure, the bishop can move to any of the red squares in one move:
Constraints
1 \leq H, W \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
H \ W
Output
Print the number of squares the bishop can reach.
Sample Input 1
4 5
Sample Output 1
10
The bishop can reach the cyan squares in the following figure:
Sample Input 2
7 3
Sample Output 2
11
The bishop can reach the cyan squares in the following figure:
Sample Input 3
1000000000 1000000000
Sample Output 3
500000000000000000
Problem Description: Score : 300 points
Problem Statement
Does
\sqrt{a} + \sqrt{b} < \sqrt{c}
hold?
Constraints
1 \leq a, b, c \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
a \ b \ c
Output
If
\sqrt{a} + \sqrt{b} < \sqrt{c}
, print
Yes
; otherwise, print
No
.
Sample Input 1
2 3 9
Sample Output 1
No
\sqrt{2} + \sqrt{3} < \sqrt{9}
does not hold.
Sample Input 2
2 3 10
Sample Output 2
Yes
\sqrt{2} + \sqrt{3} < \sqrt{10}
holds.
Problem Description: Score : 400 points
Problem Statement
In this problem, we only consider strings consisting of lowercase English letters.
Strings
s
and
t
are said to be
isomorphic
when the following conditions are satisfied:
|s| = |t|
holds.
For every pair
i, j
, one of the following holds:
s_i = s_j
and
t_i = t_j
.
s_i \neq s_j
and
t_i \neq t_j
.
For example,
abcac
and
zyxzx
are isomorphic, while
abcac
and
ppppp
are not.
A string
s
is said to be in
normal form
when the following condition is satisfied:
For every string
t
that is isomorphic to
s
,
s \leq t
holds. Here
\leq
denotes lexicographic comparison.
For example,
abcac
is in normal form, but
zyxzx
is not since it is isomorphic to
abcac
, which is lexicographically smaller than
zyxzx
.
You are given an integer
N
.
Print all strings of length
N
that are in normal form, in lexicographically ascending order.
Constraints
1 \leq N \leq 10
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Assume that there are
K
strings of length
N
that are in normal form:
w_1, \ldots, w_K
in lexicographical order.
Output should be in the following format:
w_1
:
w_K
Sample Input 1
1
Sample Output 1
a
Sample Input 2
2
Sample Output 2
aa
ab
Problem Description: Score : 500 points
Problem Statement
Snuke has a string
s
.
From this string, Anuke, Bnuke, and Cnuke obtained strings
a
,
b
, and
c
, respectively, as follows:
Choose a non-empty (contiguous) substring of
s
(possibly
s
itself). Then, replace some characters (possibly all or none) in it with
?
s.
For example, if
s
is
mississippi
, we can choose the substring
ssissip
and replace its
1
-st and
3
-rd characters with
?
to obtain
?s?ssip
.
You are given the strings
a
,
b
, and
c
.
Find the minimum possible length of
s
.
Constraints
1 \leq |a|, |b|, |c| \leq 2000
a
,
b
, and
c
consists of lowercase English letters and
?
s.
Input
Input is given from Standard Input in the following format:
a
b
c
Output
Print the minimum possible length of
s
.
Sample Input 1
a?c
der
cod
Sample Output 1
7
For example,
s
could be
atcoder
.
Sample Input 2
atcoder
atcoder
???????
Sample Output 2
7
a
,
b
, and
c
may not be distinct.
Problem Description: Score : 600 points
Problem Statement
For a non-negative integer
K
, we define a fractal of level
K
as follows:
A fractal of level
0
is a grid with just one white square.
When
K > 0
, a fractal of level
K
is a
3^K \times 3^K
grid. If we divide this grid into nine
3^{K-1} \times 3^{K-1}
subgrids:
The central subgrid consists of only black squares.
Each of the other eight subgrids is a fractal of level
K-1
.
For example, a fractal of level
2
is as follows:
In a fractal of level
30
, let
(r, c)
denote the square at the
r
-th row from the top and the
c
-th column from the left.
You are given
Q
quadruples of integers
(a_i, b_i, c_i, d_i)
.
For each quadruple, find the distance from
(a_i, b_i)
to
(c_i, d_i)
.
Here the distance from
(a, b)
to
(c, d)
is the minimum integer
n
that satisfies the following condition:
There exists a sequence of white squares
(x_0, y_0), \ldots, (x_n, y_n)
satisfying the following conditions:
(x_0, y_0) = (a, b)
(x_n, y_n) = (c, d)
For every
i (0 \leq i \leq n-1)
,
(x_i, y_i)
and
(x_{i+1}, y_{i+1})
share a side.
Constraints
1 \leq Q \leq 10000
1 \leq a_i, b_i, c_i, d_i \leq 3^{30}
(a_i, b_i) \neq (c_i, d_i)
(a_i, b_i)
and
(c_i, d_i)
are white squares.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q
a_1 \ b_1 \ c_1 \ d_1
:
a_Q \ b_Q \ c_Q \ d_Q
Output
Print
Q
lines.
The
i
-th line should contain the distance from
(a_i, b_i)
to
(c_i, d_i)
.
Sample Input 1
2
4 2 7 4
9 9 1 9
Sample Output 1
5
8
Problem Description: Score : 200 points
Problem Statement
You are visiting a large electronics store to buy a refrigerator and a microwave.
The store sells
A
kinds of refrigerators and
B
kinds of microwaves. The
i
-th refrigerator (
1 \le i \le A
) is sold at
a_i
yen (the currency of Japan), and the
j
-th microwave (
1 \le j \le B
) is sold at
b_j
yen.
You have
M
discount tickets. With the
i
-th ticket (
1 \le i \le M
), you can get a discount of
c_i
yen from the total price when buying the
x_i
-th refrigerator and the
y_i
-th microwave together. Only one ticket can be used at a time.
You are planning to buy one refrigerator and one microwave. Find the minimum amount of money required.
Constraints
All values in input are integers.
1 \le A \le 10^5
1 \le B \le 10^5
1 \le M \le 10^5
1 \le a_i , b_i , c_i \le 10^5
1 \le x_i \le A
1 \le y_i \le B
c_i \le a_{x_i} + b_{y_i}
Input
Input is given from Standard Input in the following format:
A
B
M
a_1
a_2
...
a_A
b_1
b_2
...
b_B
x_1
y_1
c_1
\vdots
x_M
y_M
c_M
Output
Print the answer.
Sample Input 1
2 3 1
3 3
3 3 3
1 2 1
Sample Output 1
5
With the ticket, you can get the
1
-st refrigerator and the
2
-nd microwave for
3+3-1=5
yen.
Sample Input 2
1 1 2
10
10
1 1 5
1 1 10
Sample Output 2
10
Note that you cannot use more than one ticket at a time.
Sample Input 3
2 2 1
3 5
3 5
2 2 2
Sample Output 3
6
You can get the
1
-st refrigerator and the
1
-st microwave for
6
yen, which is the minimum amount to pay in this case.
Note that using a ticket is optional.
Problem Description: Score : 600 points
Problem Statement
We have a tree with
N
vertices. The vertices are numbered
1
to
N
, and the
i
-th edge connects Vertex
a_i
and Vertex
b_i
.
Takahashi loves the number
3
. He is seeking a permutation
p_1, p_2, \ldots , p_N
of integers from
1
to
N
satisfying the following condition:
For every pair of vertices
(i, j)
, if the distance between Vertex
i
and Vertex
j
is
3
, the sum or product of
p_i
and
p_j
is a multiple of
3
.
Here the distance between Vertex
i
and Vertex
j
is the number of edges contained in the shortest path from Vertex
i
to Vertex
j
.
Help Takahashi by finding a permutation that satisfies the condition.
Constraints
2\leq N\leq 2\times 10^5
1\leq a_i, b_i \leq N
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1
b_1
a_2
b_2
\vdots
a_{N-1}
b_{N-1}
Output
If no permutation satisfies the condition, print
-1
.
Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.
Sample Input 1
5
1 2
1 3
3 4
3 5
Sample Output 1
1 2 5 4 3
The distance between two vertices is
3
for the two pairs
(2, 4)
and
(2, 5)
.
p_2 + p_4 = 6
p_2\times p_5 = 6
Thus, this permutation satisfies the condition.
Problem Description: Score : 800 points
Problem Statement
There are
N
stores called Store
1
, Store
2
,
\cdots
, Store
N
. Takahashi, who is at his house at time
0
, is planning to visit some of these stores.
It takes Takahashi one unit of time to travel from his house to one of the stores, or between any two stores.
If Takahashi reaches Store
i
at time
t
, he can do shopping there after standing in a queue for
a_i \times t + b_i
units of time. (We assume that it takes no time other than waiting.)
All the stores close at time
T + 0.5
. If Takahashi is standing in a queue for some store then, he cannot do shopping there.
Takahashi does not do shopping more than once in the same store.
Find the maximum number of times he can do shopping before time
T + 0.5
.
Constraints
All values in input are integers.
1 \leq N \leq 2 \times 10^5
0 \leq a_i \leq 10^9
0 \leq b_i \leq 10^9
0 \leq T \leq 10^9
Input
Input is given from Standard Input in the following format:
N
T
a_1
b_1
a_2
b_2
\vdots
a_N
b_N
Output
Print the answer.
Sample Input 1
3 7
2 0
3 2
0 3
Sample Output 1
2
Here is one possible way to visit stores:
From time
0
to time
1
: in
1
unit of time, he travels from his house to Store
1
.
From time
1
to time
3
: for
2
units of time, he stands in a queue for Store
1
to do shopping.
From time
3
to time
4
: in
1
unit of time, he travels from Store
1
to Store
3
.
From time
4
to time
7
: for
3
units of time, he stands in a queue for Store
3
to do shopping.
In this way, he can do shopping twice before time
7.5
.
Sample Input 2
1 3
0 3
Sample Output 2
0
Sample Input 3
5 21600
2 14
3 22
1 3
1 10
1 9
Sample Output 3
5
Sample Input 4
7 57
0 25
3 10
2 4
5 15
3 22
2 14
1 15
Sample Output 4
3
Problem Description: Score : 200 points
Problem Statement
Takahashi has many red balls and blue balls. Now, he will place them in a row.
Initially, there is no ball placed.
Takahashi, who is very patient, will do the following operation
10^{100}
times:
Place
A
blue balls at the end of the row of balls already placed. Then, place
B
red balls at the end of the row.
How many blue balls will be there among the first
N
balls in the row of balls made this way?
Constraints
1 \leq N \leq 10^{18}
A, B \geq 0
0 < A + B \leq 10^{18}
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
Output
Print the number of blue balls that will be there among the first
N
balls in the row of balls.
Sample Input 1
8 3 4
Sample Output 1
4
Let
b
denote a blue ball, and
r
denote a red ball. The first eight balls in the row will be
bbbrrrrb
, among which there are four blue balls.
Sample Input 2
8 0 4
Sample Output 2
0
He placed only red balls from the beginning.
Sample Input 3
6 2 4
Sample Output 3
2
Among
bbrrrr
, there are two blue balls.