2025.1.17——1200

Jellyfish has $n$ green apples with values $a_1,a_2,\dots ,a_n$ and Gellyfish has $m$ green apples with values $b_1,b_2,\dots ,b_m$.

They will play a game with $k$ rounds. For $i=1,2,\dots ,k$ in this order, they will perform the following actions:

• If $i$ is odd, Jellyfish can choose to swap one of her apples with one of Gellyfish’s apples or do nothing.
• If $i$ is even, Gellyfish can choose to swap one of his apples with one of Jellyfish’s apples or do nothing.

Both players want to maximize the sum of the values of their apples.

Since you are one of the smartest people in the world, Jellyfish wants you to tell her the final sum of the value of her apples after all $k$ rounds of the game. Assume that both Jellyfish and Gellyfish play optimally to maximize the sum of values of their apples.
Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 2000$). The description of the test cases follows.

The first line of each test case contains three integers, $n$, $m$ and $k$ ($1\le n,m\le 50$, $1\le k\le 10^9$) — the number of green apples Jellyfish has, the number of green apples Gellyfish has and the number of rounds of the game respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the values of Jellyfish’s green apples.

The third line of each test case contains $m$ integers $b_1,b_2,\dots ,b_m$ ($1\le b_i\le 10^9$) — the values of Gellyfish’s green apples.

Do note that the sum of $n$ and $m$ over all test cases are both not bounded.

Andrey is just starting to come up with problems, and it’s difficult for him. That’s why he came up with a strange problem about permutations${}^{†}$ and asks you to solve it. Can you do it?

Let’s call the cost of a permutation $p$ of length $n$ the value of the expression:

$({\sum }_{i=1}^n{p}_i\cdot i)-({\max }_{j=1}^n{p}_j\cdot j)$.

Find the maximum cost among all permutations of length $n$.

${}^{†}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 30$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($2\le n\le 250$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

Monocarp is going to make a purchase with cost of exactly $m$ burles.

He has two types of coins, in the following quantities:

• coins worth $1$ burle: $a_1$ regular coins and infinitely many fancy coins;
• coins worth $k$ burles: $a_k$ regular coins and infinitely many fancy coins.

Monocarp wants to make his purchase in such a way that there’s no change — the total worth of provided coins is exactly $m$. He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible.

What’s the smallest total number of fancy coins he can use to make a purchase?
Input

The first line contains a single integer $t$ ($1\le t\le 3\cdot 10^4$) — the number of testcases.

The only line of each testcase contains four integers $m,k,a_1$ and $a_k$ ($1\le m\le 10^8$; $2\le k\le 10^8$; $0\le a_1,a_k\le 10^8$) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.

Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements…

Given a string $s=s_1{s}_2\dots s_n$ of length $n$ consisting of characters p, s, and . (dot), determine whether a permutation${}^{\text{∗}}$ $p$ of length $n$ exists, such that for all integers $i$ ($1\le i\le n$):

• If $s_i$ is p, then $[p_1,p_2,\dots ,p_i]$ forms a permutation (of length $i$);
• If $s_i$ is s, then $[p_i,p_{i+1},\dots ,p_n]$ forms a permutation (of length $n-i+1$);
• If $s_i$ is ., then there is no additional restriction.

${}^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 500$), the length of $s$.

The second line of each test case contains a string $s$ of length $n$ that consists of the characters p, s, and …

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

You are given an array $a$ of $n$ integers, and $q$ queries.

Each query is represented by two integers $l$ and $r$ ($1\le l\le r\le n$). Your task is to find, for each query, two indices $i$ and $j$ (or determine that they do not exist) such that:

• $l\le i\le r$;
• $l\le j\le r$;
• $a_i\ne a_j$.

In other words, for each query, you need to find a pair of different elements among $a_l,a_{l+1},\dots ,a_r$, or report that such a pair does not exist.
Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$) — the elements of the array $a$.

The third line of each test case contains a single integer $q$ ($1\le q\le 2\cdot 10^5$) — the number of queries.

The next $q$ lines contain two integers each, $l$ and $r$ (KaTeX parse error: Expected 'EOF', got '&' at position 9: 1 \le l &̲lt; r \le n) — the boundaries of the query.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2\cdot 10^5$. Similarly, it is guaranteed that the sum of the values of $q$ across all test cases does not exceed $2\cdot 10^5$.

1. 贪心博弈：发现策略为将自己最小与其最大交换/不操作。

1. 神秘题：严谨证明太难，只能靠手玩/天马行空/打表/guess。