- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک دنباله از اعداد صحیح $a_1, a_2, a_3, \dots, a_n ,$ و دو عدد صحیح و مثبت $k$ و $m$ داریم ($1 \le k \le n ,$) و از روی آن دنباله $b$ را می‌سازیم.
ابتدا دنباله $b$ خالی است و به‌عنوان اولین عنصر این دنباله $a_k$ را در آن قرار می‌دهیم. سپس تا زمانی که تعداد اعداد موجود در دنباله $b$ برابر $m$ نشده است، اگر سمت راست ترین عددی که به دنباله $b$ اضافه کردیم برابر $a_i$ بوده است عدد $a_{i % n + 1}$ را به سمت راست دنباله $b$ اضافه می‌کنیم.
برای مثال فرض کنید دنباله $a$ برابر $$1, 12, 7, -4$$
و $m = 9$ و $k = 3$ باشد، دنباله $b$ در نهایت برابر $$b = 7, -4, 1, 12, 7, -4, 1, 12, 7$$ خواهد بود.
حال دنباله $a$ و مقدار $k$ گمشده است و فقط مقدار $m$ و دنباله نهایی $b$ را داریم. از شما می‌خواهیم کمترین طول ممکن برای دنباله $a$ که بشود با انتخاب یک $k$ مناسب به این دنباله $b$ رسید را بیاید و دنباله $a$ را پیدا کنید.
اگر چند دنباله با کمترین طول وجود دارد یکی از جواب‌ها را به دلخواه چاپ کنید.
ورودی
در سطر اول ورودی عدد صحیح و مثبت $t$ آمده که تعداد تست‌های نمونه‌ای که به شما داده می‌شود را نشان می‌دهد. سپس برای هر تست در یک سطر عدد صحیح $m$، در سطر بعدی $m$ عدد صحیح $b_1, b_2, b_3, \dots, b_m ,$ که با فاصله از هم جدا شده‌اند، آمده است.
$$1 \le m \le 100,000$$ $$|b_i| \le 10^9$$
تضمین می‌شود مجموع $m$ برای همه دنباله‌هایی که در این $t$ تست به شما داده می‌شود از ۱۰۰,۰۰۰ بیشتر نمی‌شود.
خروجی
برای هر کدام از این $t$ تست در یک سطر کمترین طول ممکن برای دنباله $a$ و در سطر بعدی دنباله $a$ای با همان طول که اعضای آن با فاصله جدا شده است را چاپ کنید.
اگر چندین جواب برای یک مسئله وجود دارد یکی را به دلخواه چاپ کنید.
مثال
ورودی نمونه
3
9
7 -4 1 12 7 -4 1 12 7
6
3 1 2 3 1 2
5
1 2 3 4 5
خروجی نمونه
4
1 12 7 -4
3
1 2 3
5
1 2 3 4 5
توضیح نمونه اول.
توضیح این نمونه در متن سوال آمده است.
توضیح نمونه دوم.
کافی است دنباله $a$ را به صورت $<1, 2, 3>$ و مقدار $k = 3$ باشد تا دنباله ورودی داده شده ساخته شود.
توضیح نمونه سوم.
کافی است دنباله $a$ را به صورت $<1, 2, 3, 4, 5>$ و مقدار $k = 1$ باشد تا دنباله ورودی داده شده ساخته شود.
ارسال پاسخ برای این سؤال