1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Five Dimensional Points
Contest: Codeforces Round 432 (Div. 1, based on IndiaHacks Final Round 2017)
Difficulty rating: 1700
Tags: brute force, geometry, math

You are given set of n points in 5-dimensional space. The points are labeled from 1 to n. No two points coincide.

We will call point a bad if there are different points b and c, not equal to a, from the given set such that angle between vectors $${ \vec { a } } { \vec { b } }$$ and $${ \vec { a } } { \vec { c } }$$ is acute (i.e. strictly less than $$90^\circ$$). Otherwise, the point is called good.

The angle between vectors $$\overrightarrow{\tau}$$ and $${ \overrightarrow { y } }$$ in 5-dimensional space is defined as $$\arccos\left(\frac{\vec{x} \cdot \vec{y}}{|\vec{x}||\vec{y}|}\right)$$, where $$\vec{x} \cdot \vec{y} = x_{1} y_{1} + x_{2} y_{2} + x_{3} y_{3} + x_{4} y_{4} + x_{5} y_{5}$$ is the scalar product and $$|\vec{x}| = \sqrt{\vec{x} \cdot \vec{x}}$$ is length of $$\overrightarrow{\tau}$$.

Given the list of points, print the indices of the good points in ascending order.

Input format:
The first line of input contains a single integer n (1 ≤ n ≤ 103) — the number of points.

The next n lines of input contain five integers ai, bi, ci, di, ei (|ai|, |bi|, |ci|, |di|, |ei| ≤ 103)  — the coordinates of the i-th point. All points are distinct.

Output format:
First, print a single integer k — the number of good points.

Then, print k integers, each on their own line — the indices of the good points in ascending order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the first point forms exactly a $$90^\circ$$ angle with all other pairs of points, so it is good.

In the second sample, along the cd plane, we can see the points look as follows:

We can see that all angles here are acute, so no points are good.

Example input:
6
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Example output:
1
1

Example input:
3
0 0 1 2 0
0 0 9 2 0
0 0 5 9 0

Example output:
0

Editorial:
It's easier to visualize this in 2D first. Fix a point p. If all other points form angles that are 90 degrees or greater, they must all be in different quadrants, so there can be at most 4 such points. In k dimension, this generalizes to 2*k such points, so for five dimensions, there can only be at most 10 other points. Thus, we can run the naive solution for small n and print 0 otherwise.
Arpa and a list of numbers
Contest: Codeforces Round 432 (Div. 1, based on IndiaHacks Final Round 2017)
Difficulty rating: 2100
Tags: implementation, number theory

Arpa has found a list containing n numbers. He calls a list bad if and only if it is not empty and gcd (see notes section for more information) of numbers in the list is 1.

Arpa can perform two types of operations:

- Choose a number and delete it with cost x.
- Choose a number and increase it by 1 with cost y.

Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.

Help Arpa to find the minimum possible cost to make the list good.

Input format:
First line contains three integers n, x and y (1 ≤ n ≤ 5·105, 1 ≤ x, y ≤ 109) — the number of elements in the list and the integers x and y.

Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106) — the elements of the list.

Output format:
Print a single integer: the minimum possible cost to make the list good.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In example, number 1 must be deleted (with cost 23) and number 16 must increased by 1 (with cost 17).

A gcd (greatest common divisor) of a set of numbers is the maximum integer that divides all integers in the set. Read more about gcd here.

Example input:
4 23 17
1 17 17 16

Example output:
40

Example input:
10 6 2
100 49 71 73 66 96 8 60 41 63

Example output:
10

Editorial:
Let's define cost(g) the cost if we want gcd of the array becomes g. The answer is min cost(g) for g > 1. Now, let's see how to calculate cost(g). For each number like c, we can delete it with cost x or we can add it till g divides it. So, we must pay $$\min(x,y\times(\left\lceil{\frac{c}{g}}\right\rceil\times g-c))$$. Let's iterate on possible values for $$\left\lceil \frac{c}{g} \right\rceil \times g$$.
Before entering the main part of the solution, let's define two helper functions:
– cnt(l, r): this function returns the number of i's such that l ≤ ai ≤ r.
– sum(l, r): this function returns $$\sum_{i \ni l \leq a_i \leq r} a_i$$. To implement this function, define an array ps, such that psi keeps the sum of values less than or equal to i. Then sum(l, r) = psr - psl - 1.
Now for each multiple of g like k, let's find the cost of numbers in the range (k - g, k], and sum up these values. We must find the best f and divide the range into two segments (k - g, f] and (f, k] and delete the numbers in the first range and add the numbers in second range till they become k. Now to find the best value for f, $$( g - f ) \times y = { \frac { x } { y } } \Rightarrow f = g - \min ( g, { \frac { x } { y } } )$$.
So, the total cost for this range is cnt(k - g + 1, k - ⌊ f⌋) × x + (cnt(k - ⌊ f⌋ + 1, k) × k - sum(k - ⌊ f⌋ + 1, k)) × y.
Time complexity: $${ \mathcal { O } } ( \max a _ { i } \log \max a _ { i } )$$.
Arpa and a game with Mojtaba
Contest: Codeforces Round 432 (Div. 1, based on IndiaHacks Final Round 2017)
Difficulty rating: 2200
Tags: bitmasks, dp, games

Mojtaba and Arpa are playing a game. They have a list of n numbers in the game.

In a player's turn, he chooses a number pk (where p is a prime number and k is a positive integer) such that pk divides at least one number in the list. For each number in the list divisible by pk, call it x, the player will delete x and add $$\frac{x}{p^k}$$ to the list. The player who can not make a valid choice of p and k loses.

Mojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of elements in the list.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the list.

Output format:
If Mojtaba wins, print "Mojtaba", otherwise print "Arpa" (without quotes).

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample test, Mojtaba can't move.

In the second sample test, Mojtaba chooses p = 17 and k = 1, then the list changes to [1, 1, 1, 1].

In the third sample test, if Mojtaba chooses p = 17 and k = 1, then Arpa chooses p = 17 and k = 1 and wins, if Mojtaba chooses p = 17 and k = 2, then Arpa chooses p = 17 and k = 1 and wins.

Example input:
4
1 1 1 1

Example output:
Arpa

Example input:
4
1 1 17 17

Example output:
Mojtaba

Editorial:
The problem is separate for each prime, so we will calculate Grundy number for each prime and xor these number to find the answer.
Now let's solve the problem for some prime like p. Let's show the game with a mask, i-th bit of mask is true if and only if there is a number in the list such that it is divisible by pi and it isn't divisible by pk + 1.
When some player chooses p and some k in his turn, in fact, he converts mask to (mask»k)|(mask&((1«k) - 1)). So, for each k, there is an edge between state (mask»k)|(mask&((1«k) - 1)) and mask. We can caluclate the grundy numbers by this way.
Mike and Fax
Contest: Codeforces Round 305 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation, strings

While Mike was walking in the subway, all the stuff in his back-bag dropped on the ground. There were several fax messages among them. He concatenated these strings in some order and now he has string s.

He is not sure if this is his own back-bag or someone else's. He remembered that there were exactly k messages in his own bag, each was a palindrome string and all those strings had the same length.

He asked you to help him and tell him if he has worn his own back-bag. Check if the given string s is a concatenation of k palindromes of the same length.

Input format:
The first line of input contains string s containing lowercase English letters (1 ≤ |s| ≤ 1000).

The second line contains integer k (1 ≤ k ≤ 1000).

Output format:
Print "YES"(without quotes) if he has worn his own back-bag or "NO"(without quotes) otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Palindrome is a string reading the same forward and backward.

In the second sample, the faxes in his back-bag can be "saddas" and "tavvat".

Example input:
saba
2

Example output:
NO

Example input:
saddastavvat
2

Example output:
YES

Editorial:
Mike and Fun
Contest: Codeforces Round 305 (Div. 2)
Difficulty rating: 1400
Tags: brute force, dp, greedy, implementation

Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an n × m grid, there's exactly one bear in each cell. We denote the bear standing in column number j of row number i by (i, j). Mike's hands are on his ears (since he's the judge) and each bear standing in the grid has hands either on his mouth or his eyes.

They play for q rounds. In each round, Mike chooses a bear (i, j) and tells him to change his state i. e. if his hands are on his mouth, then he'll put his hands on his eyes or he'll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.

Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.

Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round.

Input format:
The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 500 and 1 ≤ q ≤ 5000).

The next n lines contain the grid description. There are m integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).

The next q lines contain the information about the rounds. Each of them contains two integers i and j (1 ≤ i ≤ n and 1 ≤ j ≤ m), the row number and the column number of the bear changing his state.

Output format:
After each round, print the current score of the bears.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 4 5
0 1 1 0
1 0 0 1
0 1 1 0
1 0 0 1
0 0 0 0
1 1
1 4
1 1
4 2
4 3

Example output:
3
4
3
3
4

Editorial:
A Compatible Pair
Contest: Codeforces Round 462 (Div. 2)
Difficulty rating: 1400
Tags: brute force, games

Nian is a monster which lives deep in the oceans. Once a year, it shows up on the land, devouring livestock and even people. In order to keep the monster away, people fill their villages with red colour, light, and cracking noise, all of which frighten the monster out of coming.

Little Tommy has n lanterns and Big Banban has m lanterns. Tommy's lanterns have brightness a1, a2, ..., an, and Banban's have brightness b1, b2, ..., bm respectively.

Tommy intends to hide one of his lanterns, then Banban picks one of Tommy's non-hidden lanterns and one of his own lanterns to form a pair. The pair's brightness will be the product of the brightness of two lanterns.

Tommy wants to make the product as small as possible, while Banban tries to make it as large as possible.

You are asked to find the brightness of the chosen pair if both of them choose optimally.

Input format:
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 50).

The second line contains n space-separated integers a1, a2, ..., an.

The third line contains m space-separated integers b1, b2, ..., bm.

All the integers range from  - 109 to 109.

Output format:
Print a single integer — the brightness of the chosen pair.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, Tommy will hide 20 and Banban will choose 18 from Tommy and 14 from himself.

In the second example, Tommy will hide 3 and Banban will choose 2 from Tommy and 1 from himself.

Example input:
2 2
20 18
2 14

Example output:
252

Example input:
5 3
-1 0 1 2 3
-1 0 1

Example output:
2

Editorial:
We can do as what we are supposed to do — hide one of the Tommy's lantern, and then take one non-hidden lantern from Tommy and one lantern from Banban so that the product of their brightness is maximized and the minimum between all cases becomes our answer. This is a straightforward O(n2m) solution. Also, there are many other ways to solve the problem but needs overall consideration.
By the way, there were 10 pretests at first where most of contestants failed on the last one. However, considering not to make the judger running with heavy loads, I took away 3 pretests and the pretest 10 was taken by mistake. I must apologize for the extremely weak pretests that make tons of hacks now. But it looks not so bad from the result...
A Prosperous Lot
Contest: Codeforces Round 462 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, implementation

Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that when Sui tries to approach them, it will be driven away by the fairies inside.

Big Banban is hesitating over the amount of money to give out. He considers loops to be lucky since it symbolizes unity and harmony.

He would like to find a positive integer n not greater than 1018, such that there are exactly k loops in the decimal representation of n, or determine that such n does not exist.

A loop is a planar area enclosed by lines in the digits' decimal representation written in Arabic numerals. For example, there is one loop in digit 4, two loops in 8 and no loops in 5. Refer to the figure below for all exact forms.

Input format:
The first and only line contains an integer k (1 ≤ k ≤ 106) — the desired number of loops.

Output format:
Output an integer — if no such n exists, output -1; otherwise output any such n. In the latter case, your output should be a positive decimal integer not exceeding 1018.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2

Example output:
462

Example input:
6

Example output:
8080

Editorial:
What's the maximum number of loops in an integer no greater than 1018? Since 8 is the only digit with two loops, we tend to use as many eights as possible. It can be seen that the answer is 36, achieved by 888 888 888 888 888 888. Thus if k > 36, the answer does not exist under the constraints.
There are tons of approaches to the following part. Share yours in the comments!
The author considers 8 and 9 as lucky numbers and uses only 8 and 9 to construct a valid answer. In particular, the output consists of $$\left\lfloor \frac{k}{2} \right\rfloor$$ eight(s) and $$( k \bmod 2 )$$ nine(s).
Bonus. Solve the problem with the shortest code! The tester's Python solution is 51 bytes including a line break, can you beat them? ;)
Andryusha and Socks
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 800
Tags: implementation

Andryusha is an orderly boy and likes to keep things in their place.

Today he faced a problem to put his socks in the wardrobe. He has n distinct pairs of socks which are initially in a bag. The pairs are numbered from 1 to n. Andryusha wants to put paired socks together and put them in the wardrobe. He takes the socks one by one from the bag, and for each sock he looks whether the pair of this sock has been already took out of the bag, or not. If not (that means the pair of this sock is still in the bag), he puts the current socks on the table in front of him. Otherwise, he puts both socks from the pair to the wardrobe.

Andryusha remembers the order in which he took the socks from the bag. Can you tell him what is the maximum number of socks that were on the table at the same time?

Input format:
The first line contains the single integer n (1 ≤ n ≤ 105) — the number of sock pairs.

The second line contains 2n integers x1, x2, ..., x2n (1 ≤ xi ≤ n), which describe the order in which Andryusha took the socks from the bag. More precisely, xi means that the i-th sock Andryusha took out was from pair xi.

It is guaranteed that Andryusha took exactly two socks of each pair.

Output format:
Print single integer — the maximum number of socks that were on the table at the same time.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Andryusha took a sock from the first pair and put it on the table. Then he took the next sock which is from the first pair as well, so he immediately puts both socks to the wardrobe. Thus, at most one sock was on the table at the same time.

In the second example Andryusha behaved as follows:

- Initially the table was empty, he took out a sock from pair 2 and put it on the table.
- Sock (2) was on the table. Andryusha took out a sock from pair 1 and put it on the table.
- Socks (1, 2) were on the table. Andryusha took out a sock from pair 1, and put this pair into the wardrobe.
- Sock (2) was on the table. Andryusha took out a sock from pair 3 and put it on the table.
- Socks (2, 3) were on the table. Andryusha took out a sock from pair 2, and put this pair into the wardrobe.
- Sock (3) was on the table. Andryusha took out a sock from pair 3 and put this pair into the wardrobe.

Example input:
1
1 1

Example output:
1

Example input:
3
2 1 1 3 2 3

Example output:
2

Editorial:
This is a simple implementation problem. Store an array for whether a sock of each type is currently on the table, along with the total number of socks, and the largest number encountered. It is now easy to process socks one by one and maintain everything.
Complexity: O(n) time and memory.
The Meeting Place Cannot Be Changed
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 1600
Tags: binary search

The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.

At some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.

You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate.

Input format:
The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.

The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 109) — the current coordinates of the friends, in meters.

The third line contains n integers v1, v2, ..., vn (1 ≤ vi ≤ 109) — the maximum speeds of the friends, in meters per second.

Output format:
Print the minimum time (in seconds) needed for all the n friends to meet at some point on the road.

Your answer will be considered correct, if its absolute or relative error isn't greater than 10 - 6. Formally, let your answer be a, while jury's answer be b. Your answer will be considered correct if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$ holds.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

Example input:
3
7 1 3
1 2 1

Example output:
2.000000000000

Example input:
4
5 10 3 2
2 3 2 4

Example output:
1.400000000000

Editorial:
We will apply binary search to solve this problem. Inside the binary search we have to check if it is possible to meet within t seconds. In this time, i-th friend can get anywhere within the segment [xi - tvi, xi + tvi]. For the meeting to be possible, there must be a point common to all these segments, that is, their intersection must be non-empty.
An easy way to intersect a number of segments [l1, r1], ..., [ln, rn] is to compute L = max li and R = min ri. If L ≤ R, then [L, R] is the intersection, otherwise, the intersection is empty.
Complexity: $${\mathcal O}(n\log(\varepsilon^{-1}))$$ time and O(n) memory. Here ε is the required relative precision.
George and Accommodation
Contest: Codeforces Round 267 (Div. 2)
Difficulty rating: 800
Tags: implementation

George has recently entered the BSUCP (Berland State University for Cool Programmers). George has a friend Alex who has also entered the university. Now they are moving into a dormitory.

George and Alex want to live in the same room. The dormitory has n rooms in total. At the moment the i-th room has pi people living in it and the room can accommodate qi people in total (pi ≤ qi). Your task is to count how many rooms has free place for both George and Alex.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of rooms.

The i-th of the next n lines contains two integers pi and qi (0 ≤ pi ≤ qi ≤ 100) — the number of people who already live in the i-th room and the room's capacity.

Output format:
Print a single integer — the number of rooms where George and Alex can move in.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
1 1
2 2
3 3

Example output:
0

Example input:
3
1 10
0 10
10 10

Example output:
2

Editorial:
Fedor and New Game
Contest: Codeforces Round 267 (Div. 2)
Difficulty rating: 1100
Tags: bitmasks, brute force, constructive algorithms, implementation

After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (m + 1) players and n types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are numbered from 0 to n - 1. Each player has an army. Army of the i-th player can be described by non-negative integer xi. Consider binary representation of xi: if the j-th bit of number xi equal to one, then the army of the i-th player has soldiers of the j-th type.

Fedor is the (m + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits). Help Fedor and count how many players can become his friends.

Input format:
The first line contains three integers n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th of the next (m + 1) lines contains a single integer xi (1 ≤ xi ≤ 2n - 1), that describes the i-th player's army. We remind you that Fedor is the (m + 1)-th player.

Output format:
Print a single integer — the number of Fedor's potential friends.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
7 3 1
8
5
111
17

Example output:
0

Example input:
3 3 3
1
2
3
4

Example output:
3

Editorial:
George and Job
Contest: Codeforces Round 267 (Div. 2)
Difficulty rating: 1700
Tags: dp, implementation

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p1, p2, ..., pn. You are to choose k pairs of integers:

[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m),

in such a way that the value of sum $$\sum_{i=1}^{k}\sum_{j=l_i}^{r_i}p_j$$ is maximal possible. Help George to cope with the task.

Input format:
The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ 109).

Output format:
Print an integer in a single line — the maximum possible value of sum.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5 2 1
1 2 3 4 5

Example output:
9

Example input:
7 1 3
2 10 7 18 5 33 0

Example output:
61

Editorial: