گواهی لول‌آپ

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

در نوشته‌های گروه لول‌آپ می‌خواهیم بگردیم و ببینم آيا عبارت LevelUp Certificate پشت سر هم، قرار دارد یا نه.

ورودی🔗

ورودی یک سطر دارد و در آن یک رشته از حروف کوچک (a-z)، بزرگ (A-Z) و فاصله (Space) به شما داده می‌شود.

طول این رشته حداکثر شامل ۲۰۰ کاراکتر خواهد بود.

خروجی🔗

در صورتی که در این رشته، عبارت بالا بود، پیام I've Got و در غیر این صورت پیام Not Found را چاپ کنید.

توجه کنید سیستم داوری نسبت به کوچک و بزرگ بودن حروف حساس است.

مثال🔗

ورودی نمونه ۱🔗

I Want LevelUp Certificate so I registered in

خروجی نمونه ۱🔗

I've Got

ورودی نمونه ۲🔗

I want LevelUp for Certificate but I cant get it

خروجی نمونه ۲🔗

Not Found

ورودی نمونه ۳🔗

I want Levelup Certificate but I cant get it

خروجی نمونه ۳🔗

Not Found

معادله‌ی فاکتوریل

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

در این سوال به شما دو عدد طبیعی $a$ و $b$ داده می‌شود. از شما بخواهیم بررسی کنید آیا عدد طبیعی مثل $c$ وجود دارد که $a! \times b! = c!$ شود یا نه.

منظور از $n!$ همان $1 \times 2 \times \dots n$ است.

ورودی🔗

در سطر اول ورودی، دو عدد صحیح و مثبت $a$ و $b$ که با یک فاصله از هم جدا شده‌اند آمده است. $1 \leq a, b \leq 10$

خروجی🔗

اگر چنین $c$ وجود دارد مقدار $c$ و در غیر این صورت No Answer را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6 7

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

3 3

خروجی نمونه ۲🔗

No Answer

گاری در معدن

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

در یک معدن $n$ گاری روی یک ریل در حال حرکت به سمت ته معدن هستند. گاری $i$ ام با سرعت $v_i$ در حال حرکت است.

اگر در یک لحظه، دو یا چند گاری به هم برخورد کنند، گاری کندتر با همان روند قبلی به حرکت خود ادامه می‌دهد و گاری‌های سریع‌تر منفجر می‌شوند.

در ابتدا می‌دانیم گاری $i$ ام در نقطه‌ی $x_i$ است و هیچ دو گاری در یک نقطه قرار ندارند.

می‌خواهیم بدانیم اگر این روند حرکت تا ابد ادامه داشته باشد در نهایت چند گاری مختلف روی ریل باقی می‌ماند.

ورودی🔗

در سطر اول ورودی،‌ عدد صحیح و مثبت $n$ آمده که تعداد گاری‌ها را نشان می‌دهد. $1 \leq n \leq 100 \, 000$

در $n$ سطر بعدی، در هر سطر دو عدد $x_i$ و $v_i$ با یک فاصله از هم می‌آیند که به ترتیب مکان اولیه و سرعت گاری $i$ ام را نشان می‌دهد. $1 \leq x_i, v_i \leq 10^9$

خروجی🔗

در سطر اول خروجی، تعداد گاری‌هایی که تا ابد روی ریل به حرکت ادامه می‌دهند را چاپ کنید.

در سطر دوم خروجی، شماره‌ی گاری‌هایی که تا ابد روی ریل حرکت می‌کنند را به ترتیب صعودی و با یک فاصله از هم چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

2
3 5

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

2
1 2

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌خواهیم یک مسیر را از ابتدا تا انتها با خودرو برویم. ابتدای مسیر در نقطه $0$ و انتهای مسیر در نقطه $L$ قرار دارد. در مسیر $n$ پمپ بنزین وجود دارد که به ترتیب در فاصله‌های $d_1, d_2, \dots, d_n\,$ کیلومتری از مبدا قرار دارند. با یک باک پر، می‌توان $k$ کیلومتر رفت. در ابتدا باک خودرو پر است. کدام پمپ بنزین‌ها را برای بزنین زدن انتخاب کنیم که در نهایت در کمترین پمپ بنزین توقف کنیم. اگر رسیدن به مقصد ممکن نیست، اعلام کنید. # ورودی در سطر اول ورودی، سه عدد صحیح و مثبت $n$، $k$ و $L$ که با یک فاصله از هم جدا شده‌اند، آمده است. $$1 \leq n \leq 100 \, 000$$ $$1 \leq k, L \leq 10^9$$ در سطر دوم ورودی، $n$ عدد صحیح و مثبت $d_1, d_2, \dots, d_n$ که با یک فاصله از هم جدا شده‌اند، آمده است و نشان‌دهنده‌ی محل پمپ بنزین‌ها هستند. تضیمن می‌شود که شرط زیر برقرار است. $$0 < d_1 < d_2 < \dots < d_n < L$$ # خروجی در صورتی که رسیدن به مقصد ممکن نیست، در تنها سطر خروجی `-1` چاپ کنید. در غیر این‌صورت در سطر اول خروجی، عدد صحیح و مثبت $k$ که نشان‌دهنده‌ی تعداد پمپ بنزین‌ها است. در سطر دوم خروجی، $i_1, i_2, \dots, i_k\,$ را چاپ کنید که اندیس پمپ بنزین‌هایی که باید در آن توقف کنیم را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 5 4 10 1 2 5 6 7 ``` ## خروجی نمونه ۱ ``` 2 2 4 ``` ## ورودی نمونه ۲ ``` 2 9 15 7 13 ``` ## خروجی نمونه ۲ ``` 1 1 ```

پمپ بنزین

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

می‌خواهیم یک مسیر را از ابتدا تا انتها با خودرو برویم. ابتدای مسیر در نقطه $0$ و انتهای مسیر در نقطه $L$ قرار دارد.

در مسیر $n$ پمپ بنزین وجود دارد که به ترتیب در فاصله‌های $d_1, d_2, \dots, d_n\,$ کیلومتری از مبدا قرار دارند. با یک باک پر، می‌توان $k$ کیلومتر رفت. در ابتدا باک خودرو پر است.

کدام پمپ بنزین‌ها را برای بزنین زدن انتخاب کنیم که در نهایت در کمترین پمپ بنزین توقف کنیم.

اگر رسیدن به مقصد ممکن نیست، اعلام کنید.

ورودی🔗

در سطر اول ورودی، سه عدد صحیح و مثبت $n$ ، $k$ و $L$ که با یک فاصله از هم جدا شده‌اند، آمده است. $1 \leq n \leq 100 \, 000$ $1 \leq k, L \leq 10^9$

در سطر دوم ورودی، $n$ عدد صحیح و مثبت $d_1, d_2, \dots, d_n$ که با یک فاصله از هم جدا شده‌اند، آمده است و نشان‌دهنده‌ی محل پمپ بنزین‌ها هستند.

تضیمن می‌شود که شرط زیر برقرار است. $0 < d_1 < d_2 < \dots < d_n < L$

خروجی🔗

در صورتی که رسیدن به مقصد ممکن نیست، در تنها سطر خروجی -1 چاپ کنید. در غیر این‌صورت

در سطر اول خروجی، عدد صحیح و مثبت $k$ که نشان‌دهنده‌ی تعداد پمپ بنزین‌ها است.

در سطر دوم خروجی، $i_1, i_2, \dots, i_k\,$ را چاپ کنید که اندیس پمپ بنزین‌هایی که باید در آن توقف کنیم را نشان می‌دهد.

مثال🔗

ورودی نمونه ۱🔗

5 4 10
1 2 5 6 7

خروجی نمونه ۱🔗

2
2 4

ورودی نمونه ۲🔗

2 9 15
7 13

خروجی نمونه ۲🔗

1
1

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک دنباله از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. $q$ درخواست داده می‌شود. دو نوع درخواست داریم. در هر درخواست دو عدد صحیح $l$ و $r$ که $1 \leq l \leq r \leq n$ است داده می‌شود از شما می‌خواهیم همه‌ی اعداد $a_l, a_{l+1}, \dots, a_r\,$ را به $\varphi(a_l), \varphi(a_{l+1}), \dots, \varphi(a_r)\,$ سپس مجموع آن‌ها را بعد از تغییر چاپ کنید. منظور از $\varphi(k)$ تابع «[فی اویلر](https://fa.wikipedia.org/wiki/%D8%AA%D8%A7%D8%A8%D8%B9_%D9%81%DB%8C_%D8%A7%D9%88%DB%8C%D9%84%D8%B1)» است که تعداد اعداد طبیعی کوچکتر یا مساوی $k$ که نسبت به $k$ اول هستند را نشان می‌دهد. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد اعضای دنباله‌ی را نشان می‌دهد. $$1 \leq n \leq 100 \, 000$$ در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند آمده است. عدد $i$ ام ظاهر شده مقدار $a_i$ را نشان می‌دهد. $$1 \leq a_i \leq 100 \, 000$$ در سطر سوم ورودی، عدد صحیح $q$ آمده که تعداد درخواست‌ها را نشان می‌دهد. $$1 \leq q \leq 100 \, 000$$ در $q$ سطر بعدی، در هر سطر یک درخواست می‌آید. هر درخواست به صورت دو عدد $l$ و $r$ نشان داده می‌شود که $l$ و $r$ به ترتیب شروع و پایان بازه‌ی درخواست را نشان می‌دهند. $$1 \leq l \leq r \leq n$$ # خروجی به تعداد درخواست‌ها، مقدار مجموع زیربازه را بعد از تغییر گفته شده چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 12 3 4 18 6 6 1 5 3 4 1 5 1 3 2 5 3 3 ``` ## خروجی نمونه ۱ ``` 16 3 6 3 4 1 ```

تبدیل سخت

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

یک دنباله از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. $q$ درخواست داده می‌شود. دو نوع درخواست داریم. در هر درخواست دو عدد صحیح $l$ و $r$ که $1 \leq l \leq r \leq n$ است داده می‌شود از شما می‌خواهیم همه‌ی اعداد $a_l, a_{l+1}, \dots, a_r\,$ را به $\varphi(a_l), \varphi(a_{l+1}), \dots, \varphi(a_r)\,$ سپس مجموع آن‌ها را بعد از تغییر چاپ کنید.

منظور از $\varphi(k)$ تابع «فی اویلر» است که تعداد اعداد طبیعی کوچکتر یا مساوی $k$ که نسبت به $k$ اول هستند را نشان می‌دهد.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد اعضای دنباله‌ی را نشان می‌دهد. $1 \leq n \leq 100 \, 000$

در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند آمده است. عدد $i$ ام ظاهر شده مقدار $a_i$ را نشان می‌دهد. $1 \leq a_i \leq 100 \, 000$

در سطر سوم ورودی، عدد صحیح $q$ آمده که تعداد درخواست‌ها را نشان می‌دهد. $1 \leq q \leq 100 \, 000$

در $q$ سطر بعدی، در هر سطر یک درخواست می‌آید. هر درخواست به صورت دو عدد $l$ و $r$ نشان داده می‌شود که $l$ و $r$ به ترتیب شروع و پایان بازه‌ی درخواست را نشان می‌دهند.

$1 \leq l \leq r \leq n$

خروجی🔗

به تعداد درخواست‌ها، مقدار مجموع زیربازه را بعد از تغییر گفته شده چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

5
12 3 4 18 6
6
1 5
3 4
1 5
1 3
2 5
3 3

خروجی نمونه ۱🔗