#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

/*
*  rnd.next(4) - Random int bw 0-3
*  rnd.next(4, 100) - Random int bw 4-100
*  rnd.next(10.0) - Random real [0;10)
*  rnd.next("one|two|three") Random word out of 'one', 'two' and 'three'
*  rnd.next("[1-9][0-9]{99}") Random REGEX (100-digit number as a string)
*  rnd.wnext(4,t) wnext is a method of obtaining an uneven distribution (with a biased expectation)
*  rnd.any(container) A random element of the container container (with random access via an iterator), for example, it works for std::vector and std::string
*  shuffle
*/

int main(int argc, char* argv[])
{
  registerGen(argc, argv, 0);
  vector <int> shirt_winners = {};
  vector <int> bag_winners = {};

  for (int i = 21; i <= 200; i++) shirt_winners.push_back(i);
  for (int i = 201; i <= 1500; i++) bag_winners.push_back(i);

  shuffle(shirt_winners.begin(), shirt_winners.end());
  shuffle(bag_winners.begin(), bag_winners.end());

  // list of shirt winners
  cout << "===== Rank of SHIRT WINNERS =====\n";
  for (int i = 0; i < 30; i++) {
    cout << shirt_winners[i] << ' ';
  }
  cout << "\n";

  // list of bag winners
  cout << "===== Rank of BAG WINNERS =====\n";
  for (int i = 0; i < 100; i++) {
    cout << bag_winners[i] << ' ';
  }
  cout << "\n";
}

To solve the problem, you'll only need to note that in $$$(N+1)$$$-th turn: Seo moved through exactly $$$(N+1)*V_s$$$ property, that is exactly $$$V_s$$$ full round of the board, so that he end up in $$$1$$$ afterwards. The same happens with B21 and Lowie. After that, the game keeps repeating itself.

We can conclude that: if there isn't any event of one paying other in the first $$$3*(N+1)$$$ turns, it will never happen, so we can output $$$3000000000$$$. Otherwise, we can find the first event of it by brute force in $$$O(3*(N+1))$$$ time complexity.

Maximum time complexity: $$$O(3*(N+1))$$$.

This problems could be solved in multiple ways: Heavy-light decomposition, Centroid decomposition,.... However, this solution only used a little knowledge of LCA, DFS and binary search.

Basic knowledges:

First, we take a little research into the characteristics of a rooted tree (let its root be node $$$1$$$): The distance between two nodes is the number of edges on the simple path between two nodes.

• Height of a node $$$u$$$, denoted as $$$h_u$$$ is the distance from that node to the root:

• Least Common Ancestor (LCA) of node $$$u$$$ and $$$v$$$ is the node $$$X$$$ such that:

-- $$$X$$$ lies both in the path from $$$1-u$$$ and from $$$1-v$$$.

-- $$$h_X$$$ is as large as possible.

• The distance between node $$$u$$$ and node $$$v$$$, denoted as $$$d_{u, v}$$$ equals to the sum of distance from $$$u$$$ to $$$LCA(u,v)$$$ and distance from $$$LCA(u, v)$$$ to $$$v$$$.

Especially, if $$$h_u$$$ $$$=$$$ $$$h_v$$$ then $$$d_{u, v}$$$ $$$=$$$ $$$2*d_{u, LCA(u, v)}$$$.

Solution: Let $$$x$$$ be the node we are looking for:

Given the tree, we could define the set $$$S_d$$$ contains all nodes $$$u$$$ such that $$$h_u = d$$$. All nodes in the set is sorted based on DFS order.

This could be done by vector in C++ and one DFS.

The first query is "$$$?$$$ $$$1$$$ $$$1$$$" => $$$h_x$$$, so we know that $$$x$$$ must be in the set $$$S_{h_x}$$$.

Because nodes in a set is sorted in increasing order, thus if in the set $$$S_{h_x}$$$ we have nodes ordered like this

$$$...,u_3, u_2, u_1, x, v_1, v_2, v_3, ...$$$

then:

$$$...d_{u_2, x}, d_{u_1, x}, d_{x, x}=0, d_{v_1,x}, d_{v_2,x}...$$$

Here we could apply binary search in the set to find the index of node $$$x$$$ in the set

Suppose we have to binary search in the range $$$[l,r]$$$ and we have to check the index $$$m = (l+r)/2$$$, which means we are checking node $$$S_m$$$.

Query "$$$?$$$ $$$1$$$ $$$S_m$$$" => $$$d_{S_m,x}= 2d$$$, so we could find in the path from $$$S_m$$$ to $$$1$$$:

• The $$$(d-1)$$$-th node, let it be node $$$u$$$.
• The $$$d$$$-th node, which is also the $$$LCA(S_m, x)$$$, let it be node $$$L$$$.
• Or if $$$d = 0$$$ then $$$S_m = x$$$. Output $$$S_m$$$. In binary search, we can prove that we at least once access to node $$$x$$$.

Query "$$$?$$$ $$$2$$$ $$$L$$$" => $$$v$$$ is the second node in the path from $$$L$$$ to $$$x$$$.

• If $$$v$$$ is before $$$u$$$ in dfs order, then $$$S_m$$$ is definitely before $$$x$$$ in dfs order, thus we move to the range $$$[l, m-1]$$$, or else we move to the range $$$[m+1,r]$$$.

Maximum time complexity: $$$O(n*log(n))$$$.

Maximum queries possible: $$$2*log(n)+1$$$ $$$<$$$ $$$36$$$.

Firstly, sort the locations of the bombs in increasing order.

• Let $$$jump1_i$$$ is the index of the farthest bomb that could be destroyed if we destroy the $$$i$$$-th bomb using the a type-1 tool.
• Let $$$jump2_i$$$ is the index of the farthest bomb that could be destroyed if we destroy the $$$i$$$-th bomb using the a type-2 tool.

Because if $$$w_0$$$ satisfies then all $$$w>w_0$$$ satisfy, we could use binary search in the range $$$[1,10^9]$$$ to find satisfactory $$$w_0$$$.

So how could we check whether a particular value w is satisfactory?

If $$$n \le P+Q$$$ then every $$$w_1$$$ is satisfactory. If $$$P+Q < n \le 2000$$$:

• Naively, we could define a dynamic programming function as this: Let $$$f[i][j][k]$$$ true if we could destroy $$$i$$$ to $$$n$$$-th bombs from using $$$j$$$ type-1 tools and $$$k$$$ type-2 tools, or else false. Thus $$$f[i][j][k]$$$ $$$=$$$ $$$f[jump1_i][j-1][k]$$$ or $$$f[jump2_i][j][k-1]$$$.

• Optimally, we could define our DP function as this: $$$f[i][j]$$$ is the minimal amount of type-2 tools we have to use to destroy all bombs $$$i$$$ to $$$n$$$ while using at most $$$j$$$ type-1 tools.

So $$$f[i][j]=min(f[jump1_i][j-1], 1+f[jump2_i][j])$$$

After that, we have to check if $$$f[1][P] \le Q$$$.

Overall complexity is $$$O(n^2*log_2(10^9))$$$.

Dahlia can only reach targets in the circle of radius $$$R$$$ around her. But the trick here is she only pull one target in each direction she throw her arm to.

Here is the test that some may failed:

Input:
0 0 3 2
0 1
0 2

Output:
1

Maximum time complexity: $$$(O(N))$$$

It’s not very difficult to recognize the solution of this problem is to complete the $$$n$$$-th set of attack as soon as possible. Now we can solve this problem by computing $$$DP[i] = max(DP[j] + b[j] * a[i])$$$ , $$$1 \le j < i$$$ , which can be computed naively in $$$O(n^2)$$$. To optimize it to $$$O(n)$$$, you must use Convex Hull Trick.

Maximum time complexity: $$$O(n)$$$

Indeed, only the structure like this can hold water:

So for every $$$i$$$ from $$$1$$$ to $$$n$$$ we have to find the smallest $$$r_i> i$$$ and $$$y_{r_i} > y_i$$$ or if this condition does not hold, find the smallest $$$r_i > i$$$ and $$$y_{r_i}$$$ $$$=$$$ $$$max{y_j | j = i+1, n}$$$.

We can prove that between two distinct ranges $$$[i, r_i]$$$ and $$$[j, r_j]$$$, either (suppose $$$i < j$$$)

a, $$$i<j$$$ and $$$r_i \ge r_j$$$ (one include another)

b, $$$j \ge r_i$$$ (they separate from each other)

Range $$$[i, r_i]$$$ can hold water if and only if $$$r_i > i+1$$$.

So we keep an index $$$i$$$:

Initially, $$$i=1$$$

While $$$i \le n$$$:

• Calculate the area that can hold water in the range $$$[i, r_i]$$$ and add it the current answer.
• Assign $$$i=r_i+1$$$.

Maximum time complexity: $$$O(n)$$$.

The statement can be simplified to: comparing the tree in B21's best root possible and the tree in Lowie's worst root.

Call $$$d$$$ as the diameter of a tree, which can be calculated by two times DFS, we can prove that:

-- Maximum height of a tree by changing the node of root: $$$d$$$.

-- Minimum height of a tree by changing the node of root: $$$\lceil \frac{d}{2} \rceil$$$.

By simple DFS's we can find the answer easily.

Maximum time complexity: $$$O(2(N+M))$$$.

This problem requires no brainstorming at all. You can just brute force to find every combination possible.

Maximum time complexity: $$$O(N!*2^N)$$$.

Editorial by NamSPro, wrote it after the contest ends.

We will divide this problem into two cases, odd $$$N$$$ and even $$$N$$$.

Firstly, let's call the total number of cards $$$sum$$$ and the number of cards in the pile with the least cards $$$min$$$.

If $$$N$$$ is odd, then we can prove that the answer is solely based on $$$sum$$$.

We can observe that the parity of sum would change no matter the moves players use (since $$$1$$$ and $$$N$$$ are odd). From this observation, we can conclude that the winner is the one to make sum even after his turn, since $$$0$$$ is an even number. If sum is odd, that would be Lowie, otherwise Imitater wins.

If $$$N$$$ is even, then we'll check the parity of both sum and min. There are 4 cases:

-- $$$sum$$$ and $$$min$$$ are both even (we'll call this the 'base case'): Let's prove that Imitater wins this case. Since sum is even, there must be an even number of piles with their amount of cards odd (call this number $$$k$$$). Consider all moves Lowie can make:

• If he takes one card from all piles, Imitater will do the same move. Imitater can do this since min is even and nonzero (all piles must be nonempty, so $$$min \le 2$$$, remember that min is even).

• If he takes one card from one of the $$$k$$$ piles, Imitater takes one card from one of the remaining $$$(k-1)$$$ piles.

• If he takes one card from a pile different from the k piles, Imitater takes another card from the same pile. Imitater can do this since the amount of cards in that piles is even and greater than zero (players' moves must be from a nonempty pile, so the pile lowie picked must have at least $$$2$$$ cards).

After the Imitater's move, the parity of everything we are considering $$$(sum, min, k)$$$ stays the same. and because sum is initially even, Imitater will eventually win. And since Imitater goes second, we can imply that the player who goes second in this case wins.

-- $$$sum$$$ is even and $$$min$$$ is odd: Lowie can draw one card from all piles. Since $$$N$$$ is even, $$$sum$$$ would still be even. But $$$min$$$ is now one less, so it'll be even.

-- $$$sum$$$ is odd and $$$min$$$ is even: Lowie can draw one card from any pile that is not min. After that, min stays even, but sum is no longer odd.

-- $$$sum$$$ and $$$min$$$ are both odd: Lowie can draw one card from the 'min' pile. After that, sum and min are now both even. In the above 3 cases, Lowie can change this into the base case with the Imitater's turn, and as proven above, he'll win the game.

Overall complexity: $$$O(n)$$$ for input and $$$O(1)$$$ for computing and output.

Read the input as a string, then just use simple brute force to assess on all swaps possible.

Maximum time complexity: $$$O(N^3/2)$$$.

Obviously, you cannot ask for a single element in the array, because that would cost you $$$1$$$ burles, while you only have $$$0.45$$$!

Notice that the prime array is sorted and each element is smaller than $$$10^4$$$. So, you can ask for a subsegment of length $$$2$$$ and find out both element 100% correctly (because the product of two element is smaller than $$$10^9+9$$$, so it won't be deformed by $$$MOD$$$ operations). This will cost you $$$0.25$$$ burles.

From that, you can ask for another subsegment of $$$2$$$ next to it to "save money". For example, if you want to ask for subsegment $$$[r+1, r+2]$$$ and you've already got $$$[l, r]$$$, you should ask for $$$[l, r+2]$$$ and use modulo inversion to get the answer you wanted. That way, you could save a lot of money.

By two observations above, you can ask for a fixed set of queries for every tests: $$$[1, 2]$$$, $$$[1, 4]$$$,...,$$$[1, N-N\%2]$$$, $$$[1, N]$$$.

Some of the worst cases:

$$$N=3$$$: $$$0.25+0.(1) = 0.36(1)$$$ burles.

$$$N=499$$$ and $$$N=500$$$: about $$$0.410236$$$ burles.

Maximum time complexity: $$$O(N*log2(10^9+9))$$$.

Initially, create a weighted directed graph with $$$n$$$ vertices ($$$n$$$ positions in the array) and $$$2*n-2$$$ directed edges (to move left or right). To be clear: for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, there is an edge from vertex $$$i$$$ to vertex $$$i+1$$$ with weight $$$R$$$, and for every vertex $$$i$$$ from $$$2$$$ to $$$n$$$, there is an edge from it to vertex $$$i-1$$$ with weight $$$L$$$.

Now, for the "teleport" move, we will create additional vertices and edges to help us to implement the move:

• Call the initial set of vertices is $$$S$$$, and the set of additional vertex is $$$T$$$. Each vertex in $$$T$$$ represents an unique value that are in the array $$$A$$$.

• Each vertex in $$$T$$$ and a vertex $$$i$$$ in $$$S$$$ will have two edges connect them in both direction weighted $$$C/2$$$ if and only if the vertex in $$$T$$$ represent value $$$A_i$$$.

This method can be implemented using number mapping (sort the array then unique it). Please, don't use std::map: NH.O(1) lost bitterly in the very last minute of the contest for a TLE submission!

After that, you have complete the graph (because every path possible is fully implemented on it), you now can find the shortest path using Dijkstra's Algorithm.

Overall Complexity: $$$O(n*log_2(n))$$$.