Шатан Тоглоом

2s

512MB

1283

0%

Mathematics

$1,2,\ldots,n$ гэж дугаарласан $n$ шат байна. Эхлээд шат бүр дээр хэдэн бөмбөлөг байна.

Хоёр тоглогч ээлжлэн нүүнэ. Нүүлт бүрт тоглогч $k \neq 1$ бөгөөд дор хаяж нэг бөмбөлөгтэй $k$ шатыг сонгоно. Дараа нь тэр тоглогч $k$ шатаас $k-1$ шат руу хүссэн тооны бөмбөлөг зөөнө. Сүүлд нүүсэн тоглогч тоглоомд хождог.

Хоёр тоглогч оптимал тогловол хэн ялахыг ол.

Ямар ч нүүлт хийх боломжгүй бол хоёрдугаар тоглогч ялна.

https://cses.fi/problemset/task/1099

Оролтын формат

Эхний мөрөнд тестийн тоо болох $t$ бүхэл тоо байна. Үүний дараа $t$ тест өгөгдөнө:

Эхний мөрөнд шатуудын тоо болох $n$ бүхэл тоо байна.

Дараагийн мөрөнд $n$ бүхэл тоо $p_1,p_2,\ldots,p_n$ байна: шат бүр дэх бөмбөлгийн анхны тоо.

Гаралтын формат

Тест бүрт эхний тоглогч ялбал "first", хоёрдугаар тоглогч ялбал "second" гэж хэвлэ.

Хязгаарлалт

$1 \le t \le 2 \cdot 10^5$
$1 \le n \le 2 \cdot 10^5$
$0 \le p_i \le 10^9$
бүх $n$ -ийн нийлбэр $2 \cdot 10^5$ -аас хэтрэхгүй

Жишээ

Оролт1

Гаралт1

first
second
first

0.1 / 64 KiB

Редактор уншиж байна...