+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک دنباله از اعداد صحیح $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$ باشد تا دنباله ورودی داده شده ساخته شود.

دنباله گمشده

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

یک دنباله از اعداد صحیح $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

خروجی نمونه🔗

توضیح نمونه اول.

توضیح این نمونه در متن سوال آمده است.

توضیح نمونه دوم.

کافی است دنباله $a$ را به صورت $<1, 2, 3>$ و مقدار $k = 3$ باشد تا دنباله ورودی داده شده ساخته شود.

توضیح نمونه سوم.

کافی است دنباله $a$ را به صورت $<1, 2, 3, 4, 5>$ و مقدار $k = 1$ باشد تا دنباله ورودی داده شده ساخته شود.

ارسال پاسخ برای این سؤال

در حال حاضر شما دسترسی ندارید.

حل سؤال در بانک سؤالات