CodeEff/ECCO huggingface dataset:
Problem Description: Score : 100 points
Problem Statement
Given a lowercase English letter
c
, determine whether it is a vowel. Here, there are five vowels in the English alphabet:
a
,
e
,
i
,
o
and
u
.
Constraints
c
is a lowercase English letter.
Input
The input is given from Standard Input in the following format:
c
Output
If
c
is a vowel, print
vowel
. Otherwise, print
consonant
.
Sample Input 1
a
Sample Output 1
vowel
Since
a
is a vowel, print
vowel
.
Sample Input 2
z
Sample Output 2
consonant
Sample Input 3
s
Sample Output 3
consonant
Problem Description: Score : 200 points
Problem Statement
There is an image with a height of
H
pixels and a width of
W
pixels. Each of the pixels is represented by either
.
or
*
. The character representing the pixel at the
i
-th row from the top and the
j
-th column from the left, is denoted by
C_{i,j}
.
Extend this image vertically so that its height is doubled. That is, print a image with a height of
2H
pixels and a width of
W
pixels where the pixel at the
i
-th row and
j
-th column is equal to
C_{(i+1)/2,j}
(the result of division is rounded down).
Constraints
1≦H, W≦100
C_{i,j}
is either
.
or
*
.
Input
The input is given from Standard Input in the following format:
H
W
C_{1,1}...C_{1,W}
:
C_{H,1}...C_{H,W}
Output
Print the extended image.
Sample Input 1
2 2
*.
.*
Sample Output 1
*.
*.
.*
.*
Sample Input 2
1 4
***.
Sample Output 2
***.
***.
Sample Input 3
9 20
.....***....***.....
....*...*..*...*....
...*.....**.....*...
...*.....*......*...
....*.....*....*....
.....**..*...**.....
.......*..*.*.......
........**.*........
.........**.........
Sample Output 3
.....***....***.....
.....***....***.....
....*...*..*...*....
....*...*..*...*....
...*.....**.....*...
...*.....**.....*...
...*.....*......*...
...*.....*......*...
....*.....*....*....
....*.....*....*....
.....**..*...**.....
.....**..*...**.....
.......*..*.*.......
.......*..*.*.......
........**.*........
........**.*........
.........**.........
.........**.........
Problem Description: Score : 300 points
Problem Statement
You are given a string
S
consisting of lowercase English letters.
Another string
T
is initially empty.
Determine whether it is possible to obtain
S = T
by performing the following operation an arbitrary number of times:
Append one of the following at the end of
T
:
dream
,
dreamer
,
erase
and
eraser
.
Constraints
1≦|S|≦10^5
S
consists of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
If it is possible to obtain
S = T
, print
YES
. Otherwise, print
NO
.
Sample Input 1
erasedream
Sample Output 1
YES
Append
erase
and
dream
at the end of
T
in this order, to obtain
S = T
.
Sample Input 2
dreameraser
Sample Output 2
YES
Append
dream
and
eraser
at the end of
T
in this order, to obtain
S = T
.
Sample Input 3
dreamerer
Sample Output 3
NO
Problem Description: Score : 400 points
Problem Statement
There are
N
cities. There are also
K
roads and
L
railways, extending between the cities.
The
i
-th road bidirectionally connects the
p_i
-th and
q_i
-th cities, and the
i
-th railway bidirectionally connects the
r_i
-th and
s_i
-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.
We will say city
A
and
B
are
connected by roads
if city
B
is reachable from city
A
by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define
connectivity by railways
similarly.
For each city, find the number of the cities connected to that city by both roads and railways.
Constraints
2 ≦ N ≦ 2*10^5
1 ≦ K, L≦ 10^5
1 ≦ p_i, q_i, r_i, s_i ≦ N
p_i < q_i
r_i < s_i
When
i ≠ j
,
(p_i, q_i) ≠ (p_j, q_j)
When
i ≠ j
,
(r_i, s_i) ≠ (r_j, s_j)
Input
The input is given from Standard Input in the following format:
N
K
L
p_1
q_1
:
p_K
q_K
r_1
s_1
:
r_L
s_L
Output
Print
N
integers. The
i
-th of them should represent the number of the cities connected to the
i
-th city by both roads and railways.
Sample Input 1
4 3 1
1 2
2 3
3 4
2 3
Sample Output 1
1 2 2 1
All the four cities are connected to each other by roads.
By railways, only the second and third cities are connected. Thus, the answers for the cities are
1, 2, 2
and
1
, respectively.
Sample Input 2
4 2 2
1 2
2 3
1 4
2 3
Sample Output 2
1 2 2 1
Sample Input 3
7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7
Sample Output 3
1 1 2 1 2 2 2
Problem Description: Score : 900 points
Problem Statement
There are
N
pinholes on the
xy
-plane. The
i
-th pinhole is located at
(x_i,y_i)
.
We will denote the Manhattan distance between the
i
-th and
j
-th pinholes as
d(i,j)(=|x_i-x_j|+|y_i-y_j|)
.
You have a peculiar pair of compasses, called
Manhattan Compass
.
This instrument always points at two of the pinholes.
The two legs of the compass are indistinguishable, thus we do not distinguish the following two states: the state where the compass points at the
p
-th and
q
-th pinholes, and the state where it points at the
q
-th and
p
-th pinholes.
When the compass points at the
p
-th and
q
-th pinholes and
d(p,q)=d(p,r)
, one of the legs can be moved so that the compass will point at the
p
-th and
r
-th pinholes.
Initially, the compass points at the
a
-th and
b
-th pinholes.
Find the number of the pairs of pinholes that can be pointed by the compass.
Constraints
2≦N≦10^5
1≦x_i, y_i≦10^9
1≦a < b≦N
When
i ≠ j
,
(x_i, y_i) ≠ (x_j, y_j)
x_i
and
y_i
are integers.
Input
The input is given from Standard Input in the following format:
N
a
b
x_1
y_1
:
x_N
y_N
Output
Print the number of the pairs of pinholes that can be pointed by the compass.
Sample Input 1
5 1 2
1 1
4 3
6 1
5 5
4 8
Sample Output 1
4
Initially, the compass points at the first and second pinholes.
Since
d(1,2) = d(1,3)
, the compass can be moved so that it will point at the first and third pinholes.
Since
d(1,3) = d(3,4)
, the compass can also point at the third and fourth pinholes.
Since
d(1,2) = d(2,5)
, the compass can also point at the second and fifth pinholes.
No other pairs of pinholes can be pointed by the compass, thus the answer is
4
.
Sample Input 2
6 2 3
1 3
5 3
3 5
8 4
4 7
2 5
Sample Output 2
4
Sample Input 3
8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8
Sample Output 3
7
Problem Description: Score : 100 points
Problem Statement
Snuke is going to open a contest named "AtCoder
s
Contest".
Here,
s
is a string of length
1
or greater, where the first character is an uppercase English letter, and the second and subsequent characters are lowercase English letters.
Snuke has decided to abbreviate the name of the contest as "A
x
C".
Here,
x
is the uppercase English letter at the beginning of
s
.
Given the name of the contest, print the abbreviation of the name.
Constraints
The length of
s
is between
1
and
100
, inclusive.
The first character in
s
is an uppercase English letter.
The second and subsequent characters in
s
are lowercase English letters.
Input
The input is given from Standard Input in the following format:
AtCoder
s
Contest
Output
Print the abbreviation of the name of the contest.
Sample Input 1
AtCoder Beginner Contest
Sample Output 1
ABC
The contest in which you are participating now.
Sample Input 2
AtCoder Snuke Contest
Sample Output 2
ASC
This contest does not actually exist.
Sample Input 3
AtCoder X Contest
Sample Output 3
AXC
Problem Description: Score : 200 points
Problem Statement
You are given nonnegative integers
a
and
b
(
a ≤ b
), and a positive integer
x
.
Among the integers between
a
and
b
, inclusive, how many are divisible by
x
?
Constraints
0 ≤ a ≤ b ≤ 10^{18}
1 ≤ x ≤ 10^{18}
Input
The input is given from Standard Input in the following format:
a
b
x
Output
Print the number of the integers between
a
and
b
, inclusive, that are divisible by
x
.
Sample Input 1
4 8 2
Sample Output 1
3
There are three integers between
4
and
8
, inclusive, that are divisible by
2
:
4
,
6
and
8
.
Sample Input 2
0 5 1
Sample Output 2
6
There are six integers between
0
and
5
, inclusive, that are divisible by
1
:
0
,
1
,
2
,
3
,
4
and
5
.
Sample Input 3
9 9 2
Sample Output 3
0
There are no integer between
9
and
9
, inclusive, that is divisible by
2
.
Sample Input 4
1 1000000000000000000 3
Sample Output 4
333333333333333333
Watch out for integer overflows.
Problem Description: Score : 300 points
Problem Statement
There are
N
boxes arranged in a row.
Initially, the
i
-th box from the left contains
a_i
candies.
Snuke can perform the following operation any number of times:
Choose a box containing at least one candy, and eat one of the candies in the chosen box.
His objective is as follows:
Any two neighboring boxes contain at most
x
candies in total.
Find the minimum number of operations required to achieve the objective.
Constraints
2 ≤ N ≤ 10^5
0 ≤ a_i ≤ 10^9
0 ≤ x ≤ 10^9
Input
The input is given from Standard Input in the following format:
N
x
a_1
a_2
...
a_N
Output
Print the minimum number of operations required to achieve the objective.
Sample Input 1
3 3
2 2 2
Sample Output 1
1
Eat one candy in the second box.
Then, the number of candies in each box becomes
(2, 1, 2)
.
Sample Input 2
6 1
1 6 1 2 0 4
Sample Output 2
11
For example, eat six candies in the second box, two in the fourth box, and three in the sixth box.
Then, the number of candies in each box becomes
(1, 0, 1, 0, 0, 1)
.
Sample Input 3
5 9
3 1 4 1 5
Sample Output 3
0
The objective is already achieved without performing operations.
Sample Input 4
2 0
5 5
Sample Output 4
10
All the candies need to be eaten.
Problem Description: Score : 500 points
Problem Statement
There is a string
s
of length
3
or greater.
No two neighboring characters in
s
are equal.
Takahashi and Aoki will play a game against each other.
The two players alternately performs the following operation, Takahashi going first:
Remove one of the characters in
s
, excluding both ends. However, a character cannot be removed if removal of the character would result in two neighboring equal characters in
s
.
The player who becomes unable to perform the operation, loses the game. Determine which player will win when the two play optimally.
Constraints
3 ≤ |s| ≤ 10^5
s
consists of lowercase English letters.
No two neighboring characters in
s
are equal.
Input
The input is given from Standard Input in the following format:
s
Output
If Takahashi will win, print
First
. If Aoki will win, print
Second
.
Sample Input 1
aba
Sample Output 1
Second
Takahashi, who goes first, cannot perform the operation, since removal of the
b
, which is the only character not at either ends of
s
, would result in
s
becoming
aa
, with two
a
s neighboring.
Sample Input 2
abc
Sample Output 2
First
When Takahashi removes
b
from
s
, it becomes
ac
.
Then, Aoki cannot perform the operation, since there is no character in
s
, excluding both ends.
Sample Input 3
abcab
Sample Output 3
First
Problem Description: Score : 500 points
Problem Statement
There are
N
computers and
N
sockets in a one-dimensional world.
The coordinate of the
i
-th computer is
a_i
, and the coordinate of the
i
-th socket is
b_i
.
It is guaranteed that these
2N
coordinates are pairwise distinct.
Snuke wants to connect each computer to a socket using a cable.
Each socket can be connected to only one computer.
In how many ways can he minimize the total length of the cables?
Compute the answer modulo
10^9+7
.
Constraints
1 ≤ N ≤ 10^5
0 ≤ a_i, b_i ≤ 10^9
The coordinates are integers.
The coordinates are pairwise distinct.
Input
The input is given from Standard Input in the following format:
N
a_1
:
a_N
b_1
:
b_N
Output
Print the number of ways to minimize the total length of the cables, modulo
10^9+7
.
Sample Input 1
2
0
10
20
30
Sample Output 1
2
There are two optimal connections:
0-20, 10-30
and
0-30, 10-20
.
In both connections the total length of the cables is
40
.
Sample Input 2
3
3
10
8
7
12
5
Sample Output 2
1
Problem Description: Score : 500 points
Problem Statement
A cheetah and a cheater are going to play the game of Nim.
In this game they use
N
piles of stones.
Initially the
i
-th pile contains
a_i
stones.
The players take turns alternately, and the cheetah plays first.
In each turn, the player chooses one of the piles, and takes one or more stones from the pile.
The player who can't make a move loses.
However, before the game starts, the cheater wants to cheat a bit to make sure that he can win regardless of the moves by the cheetah.
From each pile, the cheater takes zero or one stone and eats it before the game.
In case there are multiple ways to guarantee his winning, he wants to minimize the number of stones he eats.
Compute the number of stones the cheater will eat.
In case there is no way for the cheater to win the game even with the cheating, print
-1
instead.
Constraints
1 ≤ N ≤ 10^5
2 ≤ a_i ≤ 10^9
Input
The input is given from Standard Input in the following format:
N
a_1
:
a_N
Output
Print the answer.
Sample Input 1
3
2
3
4
Sample Output 1
3
The only way for the cheater to win the game is to take stones from all piles and eat them.
Sample Input 2
3
100
100
100
Sample Output 2
-1
Problem Description: Score : 100 points
Problem Statement
We have a cord whose length is a positive integer. We will perform the following condition until the length of the cord becomes at most
2
:
Operation:
  Cut the rope at two positions to obtain three cords, each with a length of a positive integer.
  Among these, discard one with the longest length and one with the shortest length, and keep the remaining one.
Let
f(N)
be the maximum possible number of times to perform this operation, starting with a cord with the length
N
.
You are given a positive integer
X
. Find the maximum integer
N
such that
f(N)=X
.
Constraints
1 \leq X \leq 40
Input
The input is given from Standard Input in the following format:
X
Output
Print the value of the maximum integer
N
such that
f(N)=X
.
Sample Input 1
2
Sample Output 1
14
Problem Description: Score : 100 points
Problem Statement
You have
N
cups and
1
ball.
The cups are arranged in a row, from left to right.
You turned down all the cups, then inserted the ball into the leftmost cup.
Then, you will perform the following
Q
operations:
The
i
-th operation: swap the positions of the
A_i
-th and
B_i
-th cups from the left. If one of these cups contains the ball, the ball will also move.
Since you are a magician, you can cast a magic described below:
Magic: When the ball is contained in the
i
-th cup from the left, teleport the ball into the adjacent cup (that is, the
(i-1)
-th or
(i+1)
-th cup, if they exist).
The magic can be cast before the first operation, between two operations, or after the last operation, but you are allowed to cast it at most once during the whole process.
Find the number of cups with a possibility of containing the ball after all the operations and possibly casting the magic.
Constraints
2 \leq N \leq 10^5
1 \leq Q \leq 10^5
1 \leq A_i < B_i \leq N
Input
The input is given from Standard Input in the following format:
N
Q
A_1
B_1
A_2
B_2
:
A_Q
B_Q
Output
Print the number of cups with a possibility of eventually containing the ball.
Sample Input 1
10 3
1 3
2 4
4 5
Sample Output 1
4
Sample Input 2
20 3
1 7
8 20
1 19
Sample Output 2
5
Problem Description: Score : 700 points
Problem Statement
There are
N
panels arranged in a row in Takahashi's house, numbered
1
through
N
. The
i
-th panel has a number
A_i
written on it. Takahashi is playing by throwing balls at these panels.
Takahashi threw a ball
K
times. Let the panel hit by a boll in the
i
-th throw be panel
p_i
. He set the score for the
i
-th throw as
i \times A_{p_i}
.
He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls,
p_1,p_2,...,p_K
. The only fact he remembers is that for every
i
(1 ≦ i ≦ K-1)
,
1 ≦ p_{i+1}-p_i ≦ M
holds. Based on this fact, find the maximum possible total score for his throws.
Constraints
1 ≦ M ≦ N ≦ 100,000
1 ≦ K ≦ min(300,N)
1 ≦ A_i ≦ 10^{9}
Partial Scores
In the test set worth
100
points,
M = N
.
In the test set worth another
200
points,
N ≦ 300
and
K ≦ 30
.
In the test set worth another
300
points,
K ≦ 30
.
Input
The input is given from Standard Input in the following format:
N
M
K
A_1
A_2
…
A_N
Output
Print the maximum possible total score for Takahashi's throws.
Sample Input 1
5 2 3
10 2 8 10 2
Sample Output 1
56
The total score is maximized when panels
1,3
and
4
are hit, in this order.
Sample Input 2
5 5 2
5 2 10 5 9
Sample Output 2
28
This case satisfies the additional constraint
M = N
for a partial score.
Sample Input 3
10 3 5
3 7 2 6 9 4 8 5 1 1000000000
Sample Output 3
5000000078
Problem Description: Score : 700 points
Problem Statement
Takahashi found an undirected connected graph with
N
vertices and
M
edges. The vertices are numbered
1
through
N
. The
i
-th edge connects vertices
a_i
and
b_i
, and has a weight of
c_i
.
He will play
Q
rounds of a game using this graph. In the
i
-th round, two vertices
S_i
and
T_i
are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices
S_i
or
T_i
by traversing chosen edges.
For each round, find the minimum possible total weight of the edges chosen by Takahashi.
Constraints
1 ≦ N ≦ 4,000
1 ≦ M ≦ 400,000
1 ≦ Q ≦ 100,000
1 ≦ a_i,b_i,S_i,T_i ≦ N
1 ≦ c_i ≦ 10^{9}
a_i \neq b_i
S_i \neq T_i
The given graph is connected.
Partial Scores
In the test set worth
200
points,
Q = 1
.
In the test set worth another
300
points,
Q ≦ 3000
.
Input
The input is given from Standard Input in the following format:
N
M
a_1
b_1
c_1
a_2
b_2
c_2
:
a_M
b_M
c_M
Q
S_1
T_1
S_2
T_2
:
S_Q
T_Q
Output
Print
Q
lines. The
i
-th line should contain the minimum possible total weight of the edges chosen by Takahashi.
Sample Input 1
4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4
Sample Output 1
8
7
We will examine each round:
In the
1
-st round, choosing edges
1
and
3
achieves the minimum total weight of
8
.
In the
2
-nd round, choosing edges
1
and
2
achieves the minimum total weight of
7
.
Sample Input 2
4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3
Sample Output 2
8
This input satisfies the additional constraints for both partial scores.
Problem Description: Score : 100 points
Problem Statement
There is a grid with
H
rows and
W
columns.
The square at the
i
-th row and
j
-th column contains a string
S_{i,j}
of length
5
.
The rows are labeled with the numbers from
1
through
H
, and the columns are labeled with the uppercase English letters from
A
through the
W
-th letter of the alphabet.
Exactly one of the squares in the grid contains the string
snuke
. Find this square and report its location.
For example, the square at the
6
-th row and
8
-th column should be reported as
H6
.
Constraints
1≦H, W≦26
The length of
S_{i,j}
is
5
.
S_{i,j}
consists of lowercase English letters (
a
-
z
).
Exactly one of the given strings is equal to
snuke
.
Input
The input is given from Standard Input in the following format:
H
W
S_{1,1}
S_{1,2}
...
S_{1,W}
S_{2,1}
S_{2,2}
...
S_{2,W}
:
S_{H,1}
S_{H,2}
...
S_{H,W}
Output
Print the labels of the row and the column of the square containing the string
snuke
, with no space inbetween.
Sample Input 1
15 10
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snuke snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
snake snake snake snake snake snake snake snake snake snake
Sample Output 1
H6
Sample Input 2
1 1
snuke
Sample Output 2
A1
Problem Description: Score : 400 points
Problem Statement
On a planet far, far away,
M
languages are spoken. They are conveniently numbered
1
through
M
.
For
CODE FESTIVAL 20XX
held on this planet,
N
participants gathered from all over the planet.
The
i
-th
(1≦i≦N)
participant can speak
K_i
languages numbered
L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}
.
Two participants
A
and
B
can
communicate
with each other if and only if one of the following conditions is satisfied:
There exists a language that both
A
and
B
can speak.
There exists a participant
X
that both
A
and
B
can communicate with.
Determine whether all
N
participants can communicate with all other participants.
Constraints
2≦N≦10^5
1≦M≦10^5
1≦K_i≦M
(
The sum of all
K_i)≦10^5
1≦L_{i,j}≦M
L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}
are pairwise distinct.
Partial Score
200
points will be awarded for passing the test set satisfying the following:
N≦1000
,
M≦1000
and
(
The sum of all
K_i)≦1000
.
Additional
200
points will be awarded for passing the test set without additional constraints.
Input
The input is given from Standard Input in the following format:
N
M
K_1
L_{1,1}
L_{1,2}
...
L_{1,{}K_1}
K_2
L_{2,1}
L_{2,2}
...
L_{2,{}K_2}
:
K_N
L_{N,1}
L_{N,2}
...
L_{N,{}K_N}
Output
If all
N
participants can communicate with all other participants, print
YES
. Otherwise, print
NO
.
Sample Input 1
4 6
3 1 2 3
2 4 2
2 4 6
1 6
Sample Output 1
YES
Any two participants can communicate with each other, as follows:
Participants
1
and
2
: both can speak language
2
.
Participants
2
and
3
: both can speak language
4
.
Participants
1
and
3
: both can communicate with participant
2
.
Participants
3
and
4
: both can speak language
6
.
Participants
2
and
4
: both can communicate with participant
3
.
Participants
1
and
4
: both can communicate with participant
2
.
Note that there can be languages spoken by no participant.
Sample Input 2
4 4
2 1 2
2 1 2
1 3
2 4 3
Sample Output 2
NO
For example, participants
1
and
3
cannot communicate with each other.
Problem Description: Score : 700 points
Problem Statement
Takahashi is playing with
N
cards.
The
i
-th card has an integer
X_i
on it.
Takahashi is trying to create as many pairs of cards as possible satisfying one of the following conditions:
The integers on the two cards are the same.
The sum of the integers on the two cards is a multiple of
M
.
Find the maximum number of pairs that can be created.
Note that a card cannot be used in more than one pair.
Constraints
2≦N≦10^5
1≦M≦10^5
1≦X_i≦10^5
Input
The input is given from Standard Input in the following format:
N
M
X_1
X_2
...
X_N
Output
Print the maximum number of pairs that can be created.
Sample Input 1
7 5
3 1 4 1 5 9 2
Sample Output 1
3
Three pairs
(3,2), (1,4)
and
(1,9)
can be created.
It is possible to create pairs
(3,2)
and
(1,1)
, but the number of pairs is not maximized with this.
Sample Input 2
15 10
1 5 6 10 11 11 11 20 21 25 25 26 99 99 99
Sample Output 2
6
Problem Description: Score : 300 points
Problem Statement
The problem set at
CODE FESTIVAL 20XX Finals
consists of
N
problems.
The score allocated to the
i
-th
(1≦i≦N)
problem is
i
points.
Takahashi, a contestant, is trying to score exactly
N
points. For that, he is deciding which problems to solve.
As problems with higher scores are harder, he wants to minimize the highest score of a problem among the ones solved by him.
Determine the set of problems that should be solved.
Constraints
1≦N≦10^7
Partial Score
200
points will be awarded for passing the test set satisfying
1≦N≦1000
.
Additional
100
points will be awarded for passing the test set without additional constraints.
Input
The input is given from Standard Input in the following format:
N
Output
Among the sets of problems with the total score of
N
, find a set in which the highest score of a problem is minimum, then print the indices of the problems in the set in any order, one per line.
If there exists more than one such set, any of them will be accepted.
Sample Input 1
4
Sample Output 1
1
3
Solving only the
4
-th problem will also result in the total score of
4
points, but solving the
1
-st and
3
-rd problems will lower the highest score of a solved problem.
Sample Input 2
7
Sample Output 2
1
2
4
The set
\{3,4\}
will also be accepted.
Sample Input 3
1
Sample Output 3
1