Innopolis Open 2024. Qualification Round 2
A. Coffee Cocktail
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sometimes the deadline sneaks up unnoticed and in order to finish a task on time you have to work all night. To stay awake it's easiest to drink coffee.

Programmer Lev from VK usually manages to complete all the assigned tasks in advance but this time he procrastinated the last task for too long and plans to finish it tonight. In order to stay alert he needs at least $$$x$$$ caffeine. To achieve this he plans to assemble a set of coffee snacks that are always available in the office.

There are a total of $$$n$$$ snacks, each with a mass of $$$m_i$$$ and a caffeine content of $$$k_i \%$$$. Additionally, each snack has a type (drink, cookie, chocolate bar, etc.) characterized by the integer $$$t_i$$$.

Mixing snacks of different types is not ideal, so Lev wants to use as few different types of snacks as possible. Help him choose a set of snacks with a total caffeine mass of at least $$$x$$$, while minimizing the number of different types of snacks.

Input

The first line of input contains three integers $$$n$$$, $$$q$$$, and $$$x$$$ separated by a space, representing the number of different snacks, the number of snack types, and the required caffeine mass, respectively ($$$1 \le q \le n \le 2 \cdot 10^5$$$; $$$1 \le x \le 10^9$$$).

Each of the following lines contains three integers $$$t_i$$$, $$$m_i$$$, and $$$k_i$$$ separated by a space, representing the type, total mass, and percentage caffeine content of the $$$i$$$-th snack ($$$1 \le t_i \le q$$$; $$$1 \le m_i \le 10^9$$$; $$$0 \le k_i \le 100$$$).

Output

Output a single integer representing the minimum number of snack types required to achieve $$$x$$$ caffeine. If it is impossible to achieve $$$x$$$ caffeine even by taking all the snacks, output "-1" (without quotes).

Scoring

Points for each subtask are awarded only if all the tests of that subtask and the required subtasks are successfully passed.

SubtaskPointsConstraintsRequired Subtasks
0–examples from the statement
112$$$q = 1$$$
216$$$k_i = 100$$$, $$$t_i \ne t_j$$$, $$$m_i = m_j$$$ for all $$$i$$$, $$$j$$$
318$$$t_i \ne t_j$$$, $$$k_i = k_j$$$ for all $$$i$$$, $$$j$$$2
417$$$t_i \ne t_j$$$ for all $$$i$$$, $$$j$$$2, 3
517$$$k_i = k_j$$$ for all $$$i, j$$$2, 3
620none0 – 5
Examples
Input
4 3 10
1 4 25
2 5 100
2 4 100
3 1 10
Output
2
Input
5 4 3
1 4 50
1 5 20
2 2 50
2 2 25
4 2 100
Output
1

B. Fraction Conversion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a decimal fraction, that is, a number containing an integer part and a fractional part, in which both parts are written in the decimal number system. Unfortunately it may have a repeating decimal (fraction period) and working with fractions with repeating decimals is not very convenient.

A fraction with a repeating decimal is written in the format $$$a.b(c)$$$, which corresponds to $$$a.bccc\ldots$$$, where $$$c$$$ is repeated infinitely. For example, $$$1.25(13)$$$ represents the number $$$$$$1 + \tfrac{2}{10} + \tfrac{5}{10^2} + \tfrac{1}{10^3} + \tfrac{3}{10^4} + \tfrac{1}{10^5} + \tfrac{3}{10^6} + \ldots$$$$$$

Find the minimum positive base of the number system in which the same number is represented by a non-repeating fraction.

A number is represented as a non-repeating fraction in the number system with base $$$c$$$ if it can be represented as a finite sum $$$\sum\limits_{i} \frac{a_i}{c^i}$$$. In particular, we consider that for an integer the answer to the problem will be $$$c = 1$$$.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ separated by a space — the number of digits in the integer part, non-repeating fractional part, and the repeating part, respectively ($$$1 \le n \le 12$$$; $$$0 \le m, k \le 12$$$).

The second, third, and fourth lines contain integers $$$a$$$, $$$b$$$, and $$$c$$$ — the integer part, fractional part, and period of the number, respectively ($$$0 \le a, b, c \le 10^{12}$$$).

Note that the representation of each part can be either an empty string or a number with leading zeros, as the number of occupied positions in the number is important ($$$1.01 \neq 1.1$$$).

Output

Output a single integer — the minimum base of the number system in which the given number is represented without a repeating decimal. Print the answer by modulo $$$10^9 + 7$$$.

Scoring

Points for each subtask are awarded only if all the tests of this subtask and the required subtasks are successfully passed.

SubtaskPointsConstraintsRequired Subtasks
0–examples from the statement
110$$$m = 0$$$, $$$k \le 1$$$
210$$$m \le 1$$$, $$$k \le 1$$$1
314$$$m \le 6$$$, $$$k = 0$$$
416$$$m = 0$$$, $$$k \le 6$$$1
523$$$m + k \le 12$$$0 – 4
627$$$m, k \le 12$$$0 – 5
Examples
Input
2 1 0
10
1

Output
10
Input
1 2 1
0
25
0
Output
2
Input
1 0 1
1

5
Output
3
Note

In C++, to read a string until the end, you can use std::getline.

C. Public Transportation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The project of a new city involves the construction of a grid of size $$$n \times m$$$ cells. A house with $$$t_{i,j}$$$ residents will be located at the intersection of the $$$i$$$-th row and the $$$j$$$-th column.

Three houses in cells $$$(i, j)$$$, $$$(i + a, j)$$$ and $$$(i, j + b)$$$ form a good triangle suitable for a public transportation line if:

  • $$$a \gt 0$$$ and $$$b \gt 0$$$;
  • in the house $$$(i, j)$$$, exactly $$$a + b$$$ residents live;
  • in the house $$$(i + a, j)$$$, exactly $$$b$$$ residents live;
  • and in the house $$$(i, j + b)$$$, exactly $$$a$$$ residents live.

You can change the construction plan by increasing or decreasing all $$$t_{i,j}$$$ by the same integer $$$d$$$. If $$$t_{i,j}$$$ should become less than zero, consider it to be equal to zero. Let $$$T + d$$$ denote the matrix of values $$$t_{i,j} + d$$$, and let $$$\triangle(T + d)$$$ be the number of good triangles when the city is constructed accordingly.

Find $$$$$$\sum\limits_{d=-\infty}^{+\infty} \triangle(T + d) \text{,}$$$$$$ or in other words, the total number of good triangles for all possible construction plans.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ separated by a space, representing the number of rows and columns of the grid, respectively ($$$1 \le n, m \le 1000$$$).

In the $$$i$$$-th of the following $$$n$$$ lines, there are $$$m$$$ integers $$$t_{i,j}$$$ listed, representing the number of residents in each house of the $$$i$$$-th row of the grid ($$$1 \le t_{i,j} \le 10^9$$$).

Output

Output a single integer, the number of sets of three cells that satisfy the given conditions.

Scoring

Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks are successfully passed.

SubtaskPointsConstraintsRequired subtasks
0–examples from the statement
18$$$t_{i,j} \le 2$$$ for all $$$i$$$, $$$j$$$
213$$$n \le 2$$$
317$$$n, m \le 50$$$, $$$t_{i,j} \le 50$$$0
417$$$n, m \le 500$$$0, 3
520$$$t_{i,j}$$$ are generated randomly and uniformly0
625none0 – 5
Examples
Input
3 3
3 1 1
1 2 1
1 1 1
Output
2
Input
2 4
5 4 3 2
4 3 2 1
Output
6
Note

In this problem the input data size is large so it may be useful to use fast IO.

Statement is not available in English language
E. DequeQL
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the modern world there are many different databases based on various structures and principles. In addition to relational (e.g., MySQL) and graph (e.g., GraphQL) databases, a recent intern at VK company proposed the idea of a new database called DequeQL based on deques. Of course not all intern ideas are really good, but being a responsible mentor, Lev decided to implement his idea and test its efficiency.

A deque is a data structure that stores a sequence of elements and allows adding a new element or removing an element from either end of the sequence. The basic data block in DequeQL is called a unit — an empty deque representing the minimal block of information. The database itself consists of a set of numbered deques nested within each other. A deque that is not nested within any other is called a root. Of course, if a unit is not contained within another deque, it is also considered a root.

DequeQL supports four modification operations:

  1. push_back($$$d_1$$$, $$$d_2$$$) — place the root $$$d_1$$$ at the end of the root $$$d_2$$$ ($$$d_1$$$ ceases to be a root);
  2. push_front($$$d_1$$$, $$$d_2$$$) — place the root $$$d_1$$$ at the beginning of the root $$$d_2$$$ ($$$d_1$$$ ceases to be a root);
  3. pop_back($$$d$$$) — extract the last element from the root $$$d$$$ (this element becomes a root);
  4. pop_front($$$d$$$) — extract the first element from the root $$$d$$$ (the extracted element also becomes a root);

Note that operations can only be performed on root elements of the database. Lev has already implemented these operations and decided that DequeQL could be useful in one of the new VK projects if its functionality is expanded to include support for answering the pop_complexity($$$d$$$) query: what is the minimum number of pop_back or pop_front operations needed to make $$$d$$$ a root? The structure of the database itself does not change, so there is no need to perform the corresponding pop actions.

While Lev is on vacation you have the opportunity to prove yourself as a qualified developer. You are given a database consisting of $$$n$$$ units numbered from $$$1$$$ to $$$n$$$. Implement the required functionality and output the answer to each query.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ — the number of units in the database and the number of queries ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The $$$i$$$-th of the following lines contains the $$$i$$$-th query in the format "<command> $$$d$$$" or "<command> $$$d_1$$$ $$$d_2$$$" where <command> is the command or query described in the statement ($$$1 \le d, d_1, d_2 \le n$$$). It is guaranteed that database modification operations are only performed on root vertices, and that pop operations are only performed on non-empty deques.

Output

For each query, output the answer on a separate line — the minimum number of pop operations required to make the corresponding element a root.

Scoring

Points for each subtask are awarded only if all tests of this subtask and the required subtasks are successfully passed.

SubtaskPointsConstraints Required Subtasks Testing Feedback
0–examples from the statementfull
18$$$n, m \le 10$$$0full
29each deque directly contains no more than two elementsfirst error
313each deque directly contains no more than three elements2first error
412$$$n, m \le 2000$$$0, 1first error
520all pop_complexity queries come after modification operationsfirst error
614no pop operationsfirst error
724none0 – 6first error
Example
Input
6 11
push_back 2 1
push_front 3 1
pop_back 1
push_back 4 2
push_front 6 5
push_front 2 1
push_back 5 1
pop_complexity 3
pop_complexity 4
pop_complexity 5
pop_complexity 6
Output
2
2
1
2