Muallif: Shoyim Obloqulov
Kamol va Permutatsiya
Sizga uchta butun son — $n, x$ va $y$ beriladi. $p_1, p_2, \dots, p_n$ permutatsiyasining$^\dagger$ bali quyidagicha hisoblanadi:
$$(p_{1 \cdot x} + p_{2 \cdot x} + \dots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \dots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})$$
Ya'ni, permutatsiyaning bali — $x$ ga bo'linadigan indeksli elementlar yig'indisi, minus $y$ ga bo'linadigan indeksli elementlar yig'indisi.
Uzunligi $n$ bo'lgan barcha permutatsiyalar orasida maksimal balni toping.
$^\dagger$ Permutatsiya — $1$ dan $n$ gacha bo'lgan butun sonlarning ixtiyoriy tartibda joylashgani. Masalan, $[2, 3, 1, 5, 4]$ — to'g'ri permutatsiya; $[1, 2, 2]$ — to'g'ri emas ($2$ ikki marta uchraydi); $[1, 3, 4]$ ham to'g'ri emas ($n=3$, lekin massivda $4$ bor).
Masalan, $n=7, x=2, y=3$ bo'lsa, maksimal bal $[2, 6, 1, 7, 5, 4, 3]$ permutatsiyasida erishiladi va $(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$ ga teng.
Kiruvchi ma'lumotlar
Birinchi qatorda test-holatlari soni $t$ beriladi $(1 \le t \le 10^4)$.
Har bir test-holat uchun bitta qatorda uchta butun son: $n, x, y$ beriladi $(1 \le n \le 10^9, 1 \le x, y \le n)$.
Chiquvchi ma'lumotlar
Har bir test-holat uchun bitta butun son chiqaring - barcha permutatsiyalar orasidagi maksimal bal. Javob manfiy bo'lishi ham mumkin.
Misollar
| # | Input TXT | Output TXT |
|---|---|---|
| 1 |
8 7 2 3 12 6 3 9 1 9 2 2 2 100 20 50 24 4 6 1000000000 5575 25450 4 4 1 |
12 -3 44 0 393 87 179179179436104 -6 |
Izoh
1-test: $n=7, x=2, y=3$. Masala shartidagi misolda tushuntirilgan. Javob: $12$.
2-test: $n=12, x=4, y=6$. Optimal permutatsiyaning bali $(9+7) - (2+9+1+7) = -3$. Bundan katta balni olish mumkin emas. Javob: $-3$.
3-test: $n=9, x=1, y=9$. Permutatsiyaning bali $(p_1 + p_2 + \dots + p_9) - p_9$ ga teng. Optimal permutatsiya $[9, 8, 7, 6, 5, 4, 3, 2, 1]$ bo'lib, bal $= 44$. Javob: $44$.
4-test: $n=10, x=5, y=5$. $x=y$ bo'lganda, istalgan permutatsiyaning bali $0$ ga teng. Javob: $0$.