Many great mathematicians have sequences named after them. Timmy is a great mathematician, so he created a sequence called $$$t$$$, but he needs help to compute its values. Let $$$t_i$$$ be the number of unordered triples $$$(a, b, c)$$$ where $$$a \leq b \leq c$$$ and $$$a \cdot b \cdot c = i$$$. For all $$$i$$$ from $$$1$$$ to $$$n$$$, find and print $$$t_i$$$.
Please see the announcement to see how to abuse these constraints.
If you're using Python, please submit as PyPy rather than Python itself.
The only line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^3)$$$.
For all $$$i$$$ from $$$1$$$ to $$$n$$$, print $$$t_i$$$.
10
1 1 1 2 1 2 1 3 2 2
There are $$$3$$$ triples that have product $$$8$$$: $$$(1, 1, 8)$$$, $$$(1, 2, 4)$$$, and $$$(2, 2, 2)$$$. However, there is only $$$1$$$ triple that has product $$$7$$$: $$$(1, 1, 7)$$$.
Many great mathematicians have sequences named after them. Timmy is a great mathematician, so he created a sequence called $$$t$$$, but he needs help to compute its values. Let $$$t_i$$$ be the number of unordered triples $$$(a, b, c)$$$ where $$$a \leq b \leq c$$$ and $$$a \cdot b \cdot c = i$$$. For all $$$i$$$ from $$$1$$$ to $$$n$$$, find and print $$$t_i$$$.
The only line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^4)$$$.
For all $$$i$$$ from $$$1$$$ to $$$n$$$, print $$$t_i$$$.
10
1 1 1 2 1 2 1 3 2 2
There are $$$3$$$ triples that have product $$$8$$$: $$$(1, 1, 8)$$$, $$$(1, 2, 4)$$$, and $$$(2, 2, 2)$$$. However, there is only $$$1$$$ triple that has product $$$7$$$: $$$(1, 1, 7)$$$.
Timmy has two arrays $$$A$$$ and $$$B$$$, both of length $$$n$$$. It is guaranteed that when $$$A$$$ and $$$B$$$ are concatenated, they form a permutation of the numbers $$$1 \dots 2n$$$. He wants to create a new array $$$C$$$ by performing the following operation $$$2n$$$ times: choose either $$$A$$$ or $$$B$$$ if it still has elements, remove the element at the beginning of the chosen array, and append that element to the end of $$$C$$$. Of all ways that Timmy can create an array $$$C$$$ with these operations, he wants to find the lexicographically minimal possible one.
An array $$$a$$$ is lexicographically less than an array $$$b$$$ if, at the first position where $$$a$$$ and $$$b$$$ differ, the element of $$$a$$$ in this position is less than the element of $$$b$$$ in this position.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$. The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$. The third line contains $$$n$$$ space-separated integers $$$B_1, B_2, \dots, B_n$$$.
Print $$$2n$$$ space-separated integers, the elements of the lexicographically minimal $$$C$$$.
3 1 2 3 4 5 6
1 2 3 4 5 6
5 1 3 5 7 9 2 4 6 8 10
1 2 3 4 5 6 7 8 9 10
7 6 10 4 2 13 12 7 9 8 11 3 5 1 14
6 9 8 10 4 2 11 3 5 1 13 12 7 14
For the first sample, Timmy can first take $$$1, 2, $$$ and $$$3$$$ from $$$A$$$. Since $$$A$$$ is now empty, you must take $$$4, 5, $$$ and $$$6$$$ from $$$B$$$.
For the second sample, Timmy can alternate taking from $$$A$$$ and $$$B$$$.
One of the hardest parts about learning how to play the guitar is transitioning between different chords, as they can require complicated finger positions. In total, there are $$$k$$$ chords. It takes Timmy $$$s_{i, j}$$$ seconds to switch from being able to play chord $$$i$$$ to chord $$$j$$$.
Timmy has to play a song that consists of $$$n$$$ notes, and he wants to do it quickly so he can practice as much as possible. The total time it takes him to play a song is the time it takes for him to transition from each chord to the next one, in order, until the end of the song is reached. You can assume the song starts when he plays the first chord, that is, he immediately starts ready to play the first chord.
However, when transitioning between a chord $$$i$$$ and a chord $$$j$$$, he may not directly switch from $$$i$$$ to $$$j$$$. Instead, he may switch from $$$i$$$ to some sequence of intermediate chords to get to $$$j$$$ if it's faster for him. For example, if the song requires him to switch from chord $$$1$$$ to chord $$$7$$$, one possible way for him to do this is to switch from chord $$$1$$$ to $$$6$$$, $$$6$$$ to $$$3$$$, and finally $$$3$$$ to $$$7$$$, if it's faster than switching directly from $$$1$$$ to $$$7$$$.
To minimize the time it takes him to play the song, he can change at most one chord in the song to a different one. What is the minimum time required to play the song he can achieve?
The first line contains two space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 100)$$$. The next $$$k$$$ lines contains $$$k$$$ space-separated integers each. On line $$$i$$$ of these $$$k$$$ lines, the $$$j$$$-th integer denotes $$$s_{i, j}$$$ $$$(1 \leq s_{i, j} \leq 10^9)$$$: the time it takes Timmy to switch from chord $$$i$$$ to chord $$$j$$$. It is guaranteed that for all $$$i$$$, $$$s_{i, i} = 0$$$. The last line contains $$$n$$$ space-separated integers each, with the $$$i$$$-th integer denoting the $$$i$$$-th chord in the song.
Print a single integer - the minimum time required to play the song Timmy can achieve.
5 3 0 1 5 5 0 3 3 1 0 1 2 3 2 1
5
7 4 0 1 100 100 100 0 1 1 1 1 0 100 100 100 100 0 1 3 3 1 4 3 1
6
One optimal solution for sample 1 is the order $$$1, 2, 3, 2, 2$$$. Timmy will start at $$$1$$$, transition from $$$1$$$ to $$$2$$$ ($$$1$$$ second), $$$2$$$ to $$$3$$$ ($$$3$$$ seconds), $$$3$$$ to $$$2$$$ ($$$1$$$ second), and $$$2$$$ to $$$2$$$ ($$$0$$$ seconds), for a total of $$$5$$$ seconds.
One optimal solution for sample 2 is the order $$$1, 3, 3, 1, 1, 3, 1$$$. Timmy will start at $$$1$$$, transition from $$$1$$$ to $$$2$$$ to $$$3$$$, $$$3$$$ to $$$3$$$, $$$3$$$ to $$$1$$$, $$$1$$$ to $$$1$$$, $$$1$$$ to $$$2$$$ to $$$3$$$, and $$$3$$$ to $$$1$$$, for a total of $$$6$$$ seconds. Note that it's faster for Timmy to transition from $$$1$$$ to $$$2$$$ to $$$3$$$ rather than directly transitioning from $$$1$$$ to $$$3$$$.
Timmy is creating a basketball team. In front of him are $$$n$$$ players, lined up. Each one has a skill level $$$a_i$$$, and he must select $$$k$$$ of them in the order that they're lined up in. The $$$j$$$-th player he takes will contribute $$$a_i \cdot b_j$$$ value to the team. Find the maximum possible value.
The first line contains two space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^3)$$$ and $$$k$$$ $$$(1 \leq k \leq n)$$$. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^5)$$$: the players' skill levels, in the order that they're lined up in.. The third line contains $$$k$$$ space-separated integers $$$b_1, b_2, \dots, b_k$$$ $$$(1 \leq b_i \leq 10^5)$$$.
Print the maximum possible value of the team you can make.
3 2 1 2 3 2 1
7
5 4 5 9 10 3 2 10 10 5 5
215
7 4 1 9 3 8 19 3 2 50 1 9 3
638
In sample 1, Timmy can take players $$$2$$$ and $$$3$$$ to obtain a value of $$$2 \cdot 2 + 3 \cdot 1 = 7$$$.
In sample 2, Timmy can take players $$$2, 3, 4, $$$ and $$$5$$$ to obtain a value of $$$9 \cdot 10 + 10 \cdot 10 + 3 \cdot 5 + 2 \cdot 5 = 215$$$.
In sample 3, Timmy can take players $$$2, 4, 5, $$$ and $$$6$$$.
In a directed graph, two vertices $$$A$$$ and $$$B$$$ are called strongly connected if there exists a path from $$$A$$$ to $$$B$$$ and a path from $$$B$$$ to $$$A$$$.
A strongly connected component is a subset of vertices where all pairs of vertices in the component are strongly connected, and the subset is of maximal size - there does not exist another vertex that can be added to the subset satisfying the first condition.
Timmy has a directed graph with $$$n$$$ vertices and $$$m$$$ edges, where all pairs of vertices are strongly connected. He has to select a subset of exactly $$$k$$$ edges in this graph, then remove all others. Of all subsets of $$$k$$$ edges, he wants to find a subset that creates a graph with the maximum possible number of strongly connected components. Nobody really knows why he wants this, not even Timmy himself, but that's your task for this problem.
The first line contains three space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, $$$m$$$ $$$(n \leq m \leq 2 \cdot 10^5)$$$, and $$$k$$$ $$$(0 \leq k \lt n)$$$. The next $$$m$$$ lines contain two space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$, denoting a directed edge between $$$u$$$ and $$$v$$$. No edge is repeated, and there are no self-loops.
On the first line, print the maximum possible number of strongly connected components. On the next line, print the indices of edges in any subset of size $$$k$$$ that achieves this maximum. You can print any valid subset.
4 5 1 1 2 2 3 1 4 4 3 3 1
4 1
7 7 0 1 2 2 3 3 4 4 5 5 6 6 7 7 1
7
In the first example, taking any edge will give you $$$n$$$ components, because it requires at least two edges for there to be a path from $$$u$$$ to $$$v$$$ and $$$v$$$ to $$$u$$$ for any $$$u, v$$$.
In the second example, no edges are taken, so there are always $$$n$$$ components.
Create your own, stronger samples :)