CodeEff/ECCO huggingface dataset:
Problem Name: Count
Problem Description: For a given sequence of integers $A = \{a_0, a_1, ..., a_{n-1}\}$, perform the following operations.
count($b, e, k$): print the number of the specific values $k$ in $a_b, a_{b+1}, ..., a_{e-1}$.
Input
The input is given in the following format.
$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$b_1 \; e_1 \; k_1$
$b_2 \; e_2 \; k_2$
:
$b_q \; e_q \; k_q$
The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $b_i \; b_e \; k_i$ are given as queries.
Output
For each query, print the number of specified values.
Constraints
$1 \leq n \leq 1,000$
$-1,000,000,000 \leq a_i, k_i \leq 1,000,000,000$
$1 \leq q \leq 1,000$
$0 \leq b  < e \leq n$
Sample Input 1
9
1 4 1 4 2 1 3 5 6
3
0 9 1
1 6 1
3 7 5
Sample Output 1
3
2
0
Problem Name: Binary Search
Problem Description: For a given sequence $A = \{a_0, a_1, ..., a_{n-1}\}$ which is sorted by ascending order, find a specific value $k$ given as a query.
Input
The input is given in the following format.
$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$
The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.
Output
For each query, print
1
if any element in $A$ is equivalent to $k$, and
0
otherwise.
Constraints
$1 \leq n \leq 100,000$
$1 \leq q \leq 200,000$
$0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
$0 \leq k_i \leq 1,000,000,000$
Sample Input 1
4
1 2 2 4
3
2
3
5
Sample Output 1
1
0
0
Problem Name: Multi-Set
Problem Description: For a set $S$ of integers, perform a sequence of the following operations. Note that multiple elements can have equivalent values in $S$.
insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.
find($x$): Report the number of $x$ in $S$.
delete($x$): Delete all $x$ from $S$.
dump($L$, $R$): Print elements $x$ in $S$ such that $L \leq x \leq R$.
Input
The input is given in the following format.
$q$
$query_1$
$query_2$
:
$query_q$
Each query $query_i$ is given by
0 $x$
or
1 $x$
or
2 $x$
or
3 $L$ $R$
where the first digits
0
,
1
,
2
and
3
represent insert, find, delete and dump operations respectively.
Output
For each insert operation, print the number of elements in $S$.
For each find operation, print the number of specified elements in $S$.
For each dump operation, print the corresponding elements in ascending order. Print an element in a line.
Constraints
$1 \leq q \leq 200,000$
$0 \leq x \leq 1,000,000,000$
The total number of elements printed by dump operations does not exceed $1,000,000$
The sum of numbers printed by find operations does not exceed $2,000,000$
Sample Input 1
10
0 1
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 1 4
Sample Output 1
1
2
3
4
2
0
1
4
1
1
3
4
Problem Name: Prime Factorization
Problem Description: Factorize a given integer n.
Input
n
An integer
n
is given in a line.
Output
Print the given integer
n
and
:
. Then, print prime factors in ascending order. If
n
is divisible by a prime factor several times, the prime factor should be printed according to the number of times. Print a space before each prime factor.
Constraints
2 ≤
n
≤ 10
9
Sample Input 1
12
Sample Output 1
12: 2 2 3
Sample Input 2
126
Sample Output 2
126: 2 3 3 7
Problem Name: Power
Problem Description: For given integers m and n, compute mn (mod 1,000,000,007). Here, A (mod M) is the remainder when A is divided by M.
Input
m
n
Two integers
m
and
n
are given in a line.
Output
Print
m
n
(mod 1,000,000,007) in a line.
Constraints
1 ≤
m
≤ 100
1 ≤
n
≤ 10
9
Sample Input 1
2 3
Sample Output 1
8
Sample Input 2
5 8
Sample Output 2
390625
Problem Name: Least Common Multiple
Problem Description: Find the least common multiple (LCM) of given n integers.
Input
n
a
1
a
2
...
a
n
n
is given in the first line. Then,
n
integers are given in the second line.
Output
Print the least common multiple of the given integers in a line.
Constraints
2 ≤
n
≤ 10
1 ≤
a
i
≤ 1000
Product of given integers
a
i
(
i = 1, 2, ... n
) does not exceed 2
31
-1
Sample Input 1
3
3 4 6
Sample Output 1
12
Sample Input 2
4
1 2 3 5
Sample Output 2
30
Problem Name: Euler's Phi Function
Problem Description: For given integer n, count the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n.
Input
n
An integer
n
(1 ≤
n
≤ 1000000000).
Output
The number of totatives in a line.
Sample Input 1
6
Sample Output 1
2
Sample Input 2
1000000
Sample Output 2
400000
Problem Description: Score : 100 points
Problem Statement
You are given an integer
K
.
Print the string obtained by repeating the string
ACL
K
times and concatenating them.
For example, if
K = 3
, print
ACLACLACL
.
Constraints
1 \leq K \leq 5
All values in input are integers.
Input
Input is given from Standard Input in the following format:
K
Output
Print the string obtained by repeating the string
ACL
K
times and concatenating them.
Sample Input 1
3
Sample Output 1
ACLACLACL
Problem Description: Score : 300 points
Problem Statement
There are
N
cities numbered
1
through
N
, and
M
bidirectional roads numbered
1
through
M
.
Road
i
connects City
A_i
and City
B_i
.
Snuke can perform the following operation zero or more times:
Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.
After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).
What is the minimum number of roads he must build to achieve the goal?
Constraints
2 \leq N \leq 100,000
1 \leq M \leq 100,000
1 \leq A_i < B_i \leq N
No two roads connect the same pair of cities.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
A_1
B_1
:
A_M
B_M
Output
Print the answer.
Sample Input 1
3 1
1 2
Sample Output 1
1
Initially, there are three cities, and there is a road between City
1
and City
2
.
Snuke can achieve the goal by building one new road, for example, between City
1
and City
3
.
After that,
We can travel between
1
and
2
directly.
We can travel between
1
and
3
directly.
We can travel between
2
and
3
by following both roads (
2
-
1
-
3
).
Problem Description: Score : 400 points
Problem Statement
You are given a sequence
A_1, A_2, ..., A_N
and an integer
K
.
Print the maximum possible length of a sequence
B
that satisfies the following conditions:
B
is a (not necessarily continuous) subsequence of
A
.
For each pair of adjacents elements of
B
, the absolute difference of the elements is at most
K
.
Constraints
1 \leq N \leq 300,000
0 \leq A_i \leq 300,000
0 \leq K \leq 300,000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
A_1
A_2
:
A_N
Output
Print the answer.
Sample Input 1
10 3
1
5
4
3
8
6
9
7
2
4
Sample Output 1
7
For example,
B = (1, 4, 3, 6, 9, 7, 4)
satisfies the conditions.
It is a subsequence of
A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4)
.
All of the absolute differences between two adjacent elements (
|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|
) are at most
K = 3
.
Problem Description: Score : 500 points
Problem Statement
You have a string
S
of length
N
.
Initially, all characters in
S
are
1
s.
You will perform queries
Q
times.
In the
i
-th query, you are given two integers
L_i, R_i
and a character
D_i
(which is a digit).
Then, you must replace all characters from the
L_i
-th to the
R_i
-th (inclusive) with
D_i
.
After each query, read the string
S
as a decimal integer, and print its value modulo
998,244,353
.
Constraints
1 \leq N, Q \leq 200,000
1 \leq L_i \leq R_i \leq N
1 \leq D_i \leq 9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Q
L_1
R_1
D_1
:
L_Q
R_Q
D_Q
Output
Print
Q
lines.
In the
i
-th line print the value of
S
after the
i
-th query, modulo
998,244,353
.
Sample Input 1
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1
Sample Output 1
11222211
77772211
77333333
72333333
72311333
Sample Input 2
200000 1
123 456 7
Sample Output 2
641437905
Don't forget to take the modulo.
Problem Description: Score : 600 points
Problem Statement
There are
2N
people numbered
1
through
2N
.
The height of Person
i
is
h_i
.
How many ways are there to make
N
pairs of people such that the following conditions are satisfied?
Compute the answer modulo
998,244,353
.
Each person is contained in exactly one pair.
For each pair, the heights of the two people in the pair are different.
Two ways are considered different if for some
p
and
q
, Person
p
and Person
q
are paired in one way and not in the other.
Constraints
1 \leq N \leq 50,000
1 \leq h_i \leq 100,000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
h_1
:
h_{2N}
Output
Print the answer.
Sample Input 1
2
1
1
2
3
Sample Output 1
2
There are two ways:
Form the pair (Person
1
, Person
3
) and the pair (Person
2
, Person
4
).
Form the pair (Person
1
, Person
4
) and the pair (Person
2
, Person
3
).
Sample Input 2
5
30
10
20
40
20
10
10
30
50
60
Sample Output 2
516
Problem Description: Score : 300 points
Problem Statement
There are
N
cities on a 2D plane. The coordinate of the
i
-th city is
(x_i, y_i)
. Here
(x_1, x_2, \dots, x_N)
and
(y_1, y_2, \dots, y_N)
are both permuations of
(1, 2, \dots, N)
.
For each
k = 1,2,\dots,N
, find the answer to the following question:
Rng is in City
k
.
Rng can perform the following move arbitrarily many times:
move to another city that has a smaller
x
-coordinate and a smaller
y
-coordinate, or a larger
x
-coordinate and a larger
y
-coordinate, than the city he is currently in.
How many cities (including City
k
) are reachable from City
k
?
Constraints
1 \leq N \leq 200,000
(x_1, x_2, \dots, x_N)
is a permutation of
(1, 2, \dots, N)
.
(y_1, y_2, \dots, y_N)
is a permutation of
(1, 2, \dots, N)
.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
x_1
y_1
x_2
y_2
:
x_N
y_N
Output
Print
N
lines. In
i
-th line print the answer to the question when
k = i
.
Sample Input 1
4
1 4
2 3
3 1
4 2
Sample Output 1
1
1
2
2
Rng can reach City
4
from City
3
, or conversely City
3
from City
4
.
Sample Input 2
7
6 4
4 3
3 5
7 1
2 7
5 2
1 6
Sample Output 2
3
3
1
1
2
3
2
Problem Description: Score : 600 points
Problem Statement
Given is an integer
N
.
Find the minimum possible positive integer
k
such that
(1+2+\cdots+k)
is a multiple of
N
.
It can be proved that such a positive integer
k
always exists.
Constraints
1 \leq N \leq 10^{15}
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer in a line.
Sample Input 1
11
Sample Output 1
10
1+2+\cdots+10=55
holds and
55
is indeed a multple of
N=11
.
There are no positive integers
k \leq 9
that satisfy the condition, so the answer is
k = 10
.
Sample Input 2
20200920
Sample Output 2
1100144
Problem Description: Score : 100 points
Problem Statement
In the Kingdom of AtCoder, people use a language called Taknese, which uses lowercase English letters.
In Taknese, the plural form of a noun is spelled based on the following rules:
If a noun's singular form does not end with
s
, append
s
to the end of the singular form.
If a noun's singular form ends with
s
, append
es
to the end of the singular form.
You are given the singular form
S
of a Taknese noun. Output its plural form.
Constraints
S
is a string of length
1
between
1000
, inclusive.
S
contains only lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the plural form of the given Taknese word.
Sample Input 1
apple
Sample Output 1
apples
apple
ends with
e
, so its plural form is
apples
.
Sample Input 2
bus
Sample Output 2
buses
bus
ends with
s
, so its plural form is
buses
.
Sample Input 3
box
Sample Output 3
boxs
Problem Description: Score : 200 points
Problem Statement
Tak performed the following action
N
times: rolling two dice.
The result of the
i
-th roll is
D_{i,1}
and
D_{i,2}
.
Check if doublets occurred at least three times in a row.
Specifically, check if there exists at lease one
i
such that
D_{i,1}=D_{i,2}
,
D_{i+1,1}=D_{i+1,2}
and
D_{i+2,1}=D_{i+2,2}
hold.
Constraints
3 \leq N \leq 100
1\leq D_{i,j} \leq 6
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
D_{1,1}
D_{1,2}
\vdots
D_{N,1}
D_{N,2}
Output
Print
Yes
if doublets occurred at least three times in a row. Print
No
otherwise.
Sample Input 1
5
1 2
6 6
4 4
3 3
3 2
Sample Output 1
Yes
From the second roll to the fourth roll, three doublets occurred in a row.
Sample Input 2
5
1 1
2 2
3 4
5 5
6 6
Sample Output 2
No
Sample Input 3
6
1 1
2 2
3 3
4 4
5 5
6 6
Sample Output 3
Yes
Problem Description: Score : 300 points
Problem Statement
Given is a positive integer
N
.
How many tuples
(A,B,C)
of positive integers satisfy
A \times B + C = N
?
Constraints
2 \leq N \leq 10^6
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
3
There are
3
tuples of integers that satisfy
A \times B + C = 3
:
(A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1)
.
Sample Input 2
100
Sample Output 2
473
Sample Input 3
1000000
Sample Output 3
13969985
Problem Description: Score : 400 points
Problem Statement
There are
N
cells arranged in a row, numbered
1, 2, \ldots, N
from left to right.
Tak lives in these cells and is currently on Cell
1
. He is trying to reach Cell
N
by using the procedure described below.
You are given an integer
K
that is less than or equal to
10
, and
K
non-intersecting segments
[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]
.
Let
S
be the union of these
K
segments.
Here, the segment
[l, r]
denotes the set consisting of all integers
i
that satisfy
l \leq i \leq r
.
When you are on Cell
i
, pick an integer
d
from
S
and move to Cell
i + d
. You cannot move out of the cells.
To help Tak, find the number of ways to go to Cell
N
, modulo
998244353
.
Constraints
2 \leq N \leq 2 \times 10^5
1 \leq K \leq \min(N, 10)
1 \leq L_i \leq R_i \leq N
[L_i, R_i]
and
[L_j, R_j]
do not intersect (
i \neq j
)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
L_1
R_1
L_2
R_2
:
L_K
R_K
Output
Print the number of ways for Tak to go from Cell
1
to Cell
N
, modulo
998244353
.
Sample Input 1
5 2
1 1
3 4
Sample Output 1
4
The set
S
is the union of the segment
[1, 1]
and the segment
[3, 4]
, therefore
S = \{ 1, 3, 4 \}
holds.
There are
4
possible ways to get to Cell
5
:
1 \to 2 \to 3 \to 4 \to 5
,
1 \to 2 \to 5
,
1 \to 4 \to 5
and
1 \to 5
.
Sample Input 2
5 2
3 3
5 5
Sample Output 2
0
Because
S = \{ 3, 5 \}
holds, you cannot reach to Cell
5
.
Print
0
.
Sample Input 3
5 1
1 2
Sample Output 3
5
Sample Input 4
60 3
5 8
1 3
10 15
Sample Output 4
221823067
Note that you have to print the answer modulo
998244353
.
Problem Description: Score : 500 points
Problem Statement
Let us denote by
f(x, m)
the remainder of the Euclidean division of
x
by
m
.
Let
A
be the sequence that is defined by the initial value
A_1=X
and the recurrence relation
A_{n+1} = f(A_n^2, M)
.
Find
\displaystyle{\sum_{i=1}^N A_i}
.
Constraints
1 \leq N \leq 10^{10}
0 \leq X < M \leq 10^5
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
X
M
Output
Print
\displaystyle{\sum_{i=1}^N A_i}
.
Sample Input 1
6 2 1001
Sample Output 1
1369
The sequence
A
begins
2,4,16,256,471,620,\ldots
Therefore, the answer is
2+4+16+256+471+620=1369
.
Sample Input 2
1000 2 16
Sample Output 2
6
The sequence
A
begins
2,4,0,0,\ldots
Therefore, the answer is
6
.
Sample Input 3
10000000000 10 99959
Sample Output 3
492443256176507
Problem Description: Score : 600 points
Problem Statement
There is a grid with
N
rows and
N
columns of squares. Let
(i, j)
be the square at the
i
-th row from the top and the
j
-th column from the left.
Each of the central
(N-2) \times (N-2)
squares in the grid has a black stone on it.
Each of the
2N - 1
squares on the bottom side and the right side has a white stone on it.
Q
queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:
1 x
: Place a white stone on
(1, x)
. After that, for each black stone between
(1, x)
and the first white stone you hit if you go down from
(1, x)
, replace it with a white stone.
2 x
: Place a white stone on
(x, 1)
. After that, for each black stone between
(x, 1)
and the first white stone you hit if you go right from
(x, 1)
, replace it with a white stone.
How many black stones are there on the grid after processing all
Q
queries?
Constraints
3 \leq N \leq 2\times 10^5
0 \leq Q \leq \min(2N-4,2\times 10^5)
2 \leq x \leq N-1
Queries are pairwise distinct.
Input
Input is given from Standard Input in the following format:
N
Q
Query_1
\vdots
Query_Q
Output
Print how many black stones there are on the grid after processing all
Q
queries.
Sample Input 1
5 5
1 3
2 3
1 4
2 2
1 2
Sample Output 1
1
After each query, the grid changes in the following way:
Sample Input 2
200000 0
Sample Output 2
39999200004
Sample Input 3
176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282
Sample Output 3
31159505795
Problem Description: Score : 100 points
Problem Statement
Given is an integer
x
that is greater than or equal to
0
, and less than or equal to
1
.
Output
1
if
x
is equal to
0
, or
0
if
x
is equal to
1
.
Constraints
0 \leq x \leq 1
x
is an integer
Input
Input is given from Standard Input in the following format:
x
Output
Print
1
if
x
is equal to
0
, or
0
if
x
is equal to
1
.
Sample Input 1
1
Sample Output 1
0
Sample Input 2
0
Sample Output 2
1
Problem Description: Score : 200 points
Problem Statement
Given are integers
a,b,c
and
d
.
If
x
and
y
are integers and
a \leq x \leq b
and
c\leq y \leq d
hold, what is the maximum possible value of
x \times y
?
Constraints
-10^9 \leq a \leq b \leq 10^9
-10^9 \leq c \leq d \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
a
b
c
d
Output
Print the answer.
Sample Input 1
1 2 1 1
Sample Output 1
2
If
x = 1
and
y = 1
then
x \times y = 1
.
If
x = 2
and
y = 1
then
x \times y = 2
.
Therefore, the answer is
2
.
Sample Input 2
3 5 -4 -2
Sample Output 2
-6
The answer can be negative.
Sample Input 3
-1000000000 0 -1000000000 0
Sample Output 3
1000000000000000000
Problem Description: Score : 600 points
Problem Statement
Given are two sequences
A
and
B
, both of length
N
.
A
and
B
are each sorted in the ascending order.
Check if it is possible to reorder the terms of
B
so that for each
i
(
1 \leq i \leq N
)
A_i \neq B_i
holds, and if it is possible, output any of the reorderings that achieve it.
Constraints
1\leq N \leq 2 \times 10^5
1\leq A_i,B_i \leq N
A
and
B
are each sorted in the ascending order.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
\cdots
A_N
B_1
B_2
\cdots
B_N
Output
If there exist no reorderings that satisfy the condition, print
No
.
If there exists a reordering that satisfies the condition, print
Yes
on the first line.
After that, print a reordering of
B
on the second line, separating terms with a whitespace.
If there are multiple reorderings that satisfy the condition, you can print any of them.
Sample Input 1
6
1 1 1 2 2 3
1 1 1 2 2 3
Sample Output 1
Yes
2 2 3 1 1 1
Sample Input 2
3
1 1 2
1 1 3
Sample Output 2
No
Sample Input 3
4
1 1 2 3
1 2 3 3
Sample Output 3
Yes
3 3 1 2
Problem Description: Score: 100 points
Problem
You are given an undirected graph with
N
vertices and
0
edges. Process the following
Q
queries:
0 u v
: Add an edge
(u, v)
.
1 u v
: Output
1
if
u
and
v
belong to the same connected component,
0
otherwise.
Constraints
1 \leq N \leq 200,000
1 \leq Q \leq 200,000
0 \leq u_i, v_i \lt N
Input
The input is given in the following format:
N
Q
t_1
u_1
v_1
t_2
u_2
v_2
:
t_Q
u_Q
v_Q
Output
For each query of the second type, output its answer.
Sample Input 1
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
Sample Output 1
0
1
0
1
Problem Description: Score : 100 points
Problem Statement
You are given an array
a_0, a_1, ..., a_{N-1}
of length
N
. Process
Q
queries of the following types.
0 p x
:
a_p \gets a_p + x
1 l r
: Print
\sum_{i = l}^{r - 1}{a_i}
.
Constraints
1 \leq N, Q \leq 500,000
0 \leq a_i, x \leq 10^9
0 \leq p < N
0 \leq l_i < r_i \leq N
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
Q
a_0
a_1
...
a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}
Output
For each query of the latter type, print the answer.
Sample Input 1
5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3
Sample Output 1
15
7
25
6
Problem Description: Score : 100 points
Problem Statement
In this problem, you should process
T
testcases.
For each testcase, you are given four integers
N, M, A, B
.
Calculate
\sum_{i = 0}^{N - 1} floor((A \times i + B) / M)
.
Constraints
1 \leq T \leq 100,000
1 \leq N, M \leq 10^9
0 \leq A, B < M
Input
Input is given from Standard Input in the following format:
T
N_0
M_0
A_0
B_0
N_1
M_1
A_1
B_1
:
N_{T - 1}
M_{T - 1}
A_{T - 1}
B_{T - 1}
Output
Print the answer for each testcase.
Sample Input 1
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
Sample Output 1
3
13
0
314095480
499999999500000000
Problem Description: Score : 100 points
Problem Statement
You are given a grid of
N
rows and
M
columns. The square at the
i
-th row and
j
-th column will be denoted as
(i,j)
.
A nonnegative integer
A_{i,j}
is written for each square
(i,j)
.
You choose some of the squares so that each row and column contains at most
K
chosen squares.
Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares.
Additionally, calculate a way to choose squares that acheives the maximum.
Constraints
1 \leq N \leq 50
1 \leq K \leq N
0 \leq A_{i,j} \leq 10^9
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
K
A_{1,1}
A_{1,2}
\cdots
A_{1,N}
A_{2,1}
A_{2,2}
\cdots
A_{2,N}
\vdots
A_{N,1}
A_{N,2}
\cdots
A_{N,N}
Output
On the first line, print the maximum value of the sum of the integers written on the chosen squares.
On the next
N
lines, print a way that achieves the maximum.
Precisely, output the strings
t_1,t_2,\cdots,t_N
, that satisfies
t_{i,j}=
X
if you choose
(i,j)
and
t_{i,j}=
.
otherwise.
You may print any way to choose squares that maximizes the sum.
Sample Input 1
3 1
5 3 2
1 4 8
7 6 9
Sample Output 1
19
X..
..X
.X.
Sample Input 2
3 2
10 10 1
10 10 1
1 1 10
Sample Output 2
50
XX.
XX.
..X
Problem Description: Score : 100 points
Problem Statement
Consider placing
N
flags on a line. Flags are numbered through
1
to
N
.
Flag
i
can be placed on the coordinate
X_i
or
Y_i
.
For any two different flags, the distance between them should be at least
D
.
Decide whether it is possible to place all
N
flags. If it is possible, print such a configulation.
Constraints
1 \leq N \leq 1000
0 \leq D \leq 10^9
0 \leq X_i < Y_i \leq 10^9
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
D
X_1
Y_1
X_2
Y_2
\vdots
X_N
Y_N
Output
Print
No
if it is impossible to place
N
flags.
If it is possible, print
Yes
first.
After that, print
N
lines.
i
-th line of them should contain the coodinate of flag
i
.
Sample Input 1
3 2
1 4
2 5
0 6
Sample Output 1
Yes
4
2
0
Sample Input 2
3 3
1 4
2 5
0 6
Sample Output 2
No
Problem Description: Score : 100 points
Problem Statement
You are given a string of length
N
. Calculate the number of distinct substrings of
S
.
Constraints
1 \leq N \leq 500,000
S
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
abcbcba
Sample Output 1
21
Sample Input 2
mississippi
Sample Output 2
53
Sample Input 3
ababacaca
Sample Output 3
33
Sample Input 4
aaaaa
Sample Output 4
5