+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- محمد مهدی تصمیم گرفته تا بازی کند! او در این بازی یک عدد تصادفی از ۱ تا ۱۰۰۰ مثل $n$ انتخاب کرده و $q$ تا از مقسوم علیه‌های آنرا به روزبه می‌گوید. حال روزبه تصمیم گرفته تا عدد محمد مهدی را حدس بزند. روزبه برای اینکه عدد را حدس بزند می‌خواهد بداند که چند عدد وجود دارند که می‌توانند حدس محمد مهدی باشند. به او کمک کنید. # ورودی خط اول ورودی عدد $q$ آمده است. $(1 \leq q \leq 100)$ در خط دوم $q$ عدد که با فاصله از هم جدا شده‌اند و برخی از مقسوم علیه‌های $n$ هستند آمده است. # خروجی در خروجی تعداد اعدادی که می توانند حدس محمدمهدی باشند را چاپ کنید. دقت کنید ممکن است محمدمهدی اشتباه کرده‌باشد و حدسی وجود نداشته‌باشد. # مثال ## ورودی نمونه ۱ ``` 4 2 3 5 7 ``` ## خروجی نمونه ۱ ``` 4 ``` ---------- ## ورودی نمونه ۲ ``` 1 1 ``` ## خروجی نمونه ۲ ``` 1000 ``` # توضیحات در مثال اول، محمد مهدی یکی از اعداد ۲۱۰، ۴۲۰، ۶۳۰ یا ۸۴۰ را انتخاب کرده‌است. در مثال دوم، محمد مهدی می‌تواند همه‌ی اعداد ۱ تا ۱۰۰۰ را انتخاب کرده‌باشد!

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر شماست. بنابراین به ما تاکید کرد که حتما سوالی ساده به عنوان سوال اول به شما بدهیم. از آنجایی که ایشان حق بزرگتری به گردن ما دارند، ما حرفشان را اطاعت می‌کنیم: یک عدد به شما داده شده است. به تعداد آن عدد برای ما جمله‌ی "man khoshghlab hastam" را چاپ کنید بلکه به خوش‌قلب شدن، قدمی دیگر نزدیک شده باشید. # ورودی در تنها سطر ورودی یک عدد $n$ به شما داده شده است که نماینگر تعداد دفعاتی است که باید جمله‌ی فوق را چاپ کنید. $$ 1 \le n \le 100 $$ # خروجی خروجی شامل $n$ سطر می‌باشد که هر کدام از این سطر ها باید شامل عبارت "man khoshghlab hastam" باشد. # مثال ## ورودی نمونه ``` 3 ``` ## خروجی نمونه ``` man khoshghlab hastam man khoshghlab hastam man khoshghlab hastam ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل و طماع است، به پارک رفته است. پارک از بالا به شکل یک صفحه ی مختصات دکارتی است. رادزینکا در یک نقطه از پارک به مختصات $x$ و $y$ نشسته است و به افق خیره شده است(به طرف مثبت $y$ها). دوست رادزینکا که در مختصات $x_1$ و $y_1$ قرار دارد او را صدا میزند. رادزین میخواهد سرش را برگرداند، به او نگاه کرده و جوابش را بدهد. اما به دلیل تنبلی زیاد میخواهد سرش را در جهتی بچرخاند که کمترین مقدار چرخش را داشته باشد. به او کمک کنید که جهت درست را انتخاب کند # ورودی در سطر اول ورودی $x$ و $y$ آمده است محل نشستن رادزین را نشان میدهد. در سطر دوم دو عدد $x_1$ و $y_1$ آمده است که نشان دادن محلی است که دوست رادزینکا در آن قرار دارد. تضمین میشود در تست ها زاویه‌ی چرخش از چپ و راست متفاوت است. $$ -1000 \le x, y, x_1, y_1 \le 1000$$ # خروجی اگر باید به جهت راست حرکت کند "Right" و اگر باید در جهت چپ سرش را بچرخاند "Left" را خروجی دهید. # مثال ## ورودی نمونه ``` 2 2 3 1 ``` ## خروجی نمونه ``` Right ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** برای کنترل جهان باید از کنترل کولر شروع کرد! "رادزینکا دوبرامیل ویچشسلافوویچ" قرار شده‌است که در عمارت، انتخاباتی برگزار شود تا شخص منتخب خانه را اداره کند. آقای خطری، یکی از اعضای خانه است که میخواهد برای این کار نامزد بشود. او مردی به شدت منطقی بوده و معتقد است که کولر باید خاموش باشد! انگیزه‌ی شرکت او در انتخابات هم همین است... هنگام ثبت‌نام نامزد از او خواسته شد تا نام انتخاباتی خود را وارد کند. او که احساس می‌کرد که اسم «خطری» رای‌دهندگان را خواهد ترساند تصمیم گرفت که نام دیگری را وارد کند. او دستش را برروی صفحه کلید گذاشت (تکنولوژی در عمارت بالاست) و تعدادی کلید را فشار داد تا اسم انتخاباتی‌اش را وارد کند. می‌دانیم که صفحه کلید تنها شامل حروف و دکمه‌ی CapsLock می‌باشد و ابتدا CapsLock خاموش بوده است. با گرفتن دکمه‌هایی که آقای خطری زده است بگویید که نام انتخاباتی او چیست. اگر CapsLock روشن باشد، حروف بزرگ نوشته خواهند شد و اگر خاموش باشد حروف کوچک نوشته خواهند شد. همچنین با زدن دکمه‌ی CapsLock، وضعیت CapsLock برعکس خواهد شد. # ورودی در سطر اول ورودی عدد $n$ آمده‌ است که نمایانگر تعداد دکمه‌هایی است که آقای خطری وارد کرده است. سپس در $n$ سطر بعدی، در هر سطر، دکمه‌ای که آقای خطری زده است آمده است. این دکمه یا یکی از حروف کوچک انگلیسی است و یا دکمه‌ی CapsLock که دکمه‌ی CapsLock در ورودی به صورت "CAPS" آمده است. تضمین می‌شود که حداقل یک دکمه از حروف زده شده است. $$ 3 \le n \le 100 $$ # خروجی در تنها سطر خروجی نام انتخاباتی آقای خطری را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 10 d CAPS a n g CAPS e r CAPS y ``` ## خروجی نمونه ۱ ``` dANGerY ``` ## ورودی نمونه ۲ ``` 3 z j u ``` ## خروجی نمونه ۲ ``` zju ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گروه اسنپ بعد از اسنپ فود در حال ساخت یک استارتاپ جدید است. در حال حاضر تمام کارهای این استارتاپ انجام شده اما انتخاب نامی مناسب برای این استارتاپ ذهن همه‌ی بچه‌های اسنپ را مشغول کرده‌است. بدین منظور $n$ نفر از بچه‌ها، هر کدام نامی برای این استارتاپ پیشنهاد داده‌اند که قرار است محسن از بین این نام‌ها یک نام را انتخاب می‌کند. محسن عقیده دارد که زیبایی یک نام برابرست با تعداد حرف‌های مختلفی که در این نام به کار رفته‌است. حال ما به شما $n$ اسم پیشنهادی بچه‌ها را می‌دهیم و از شما ‌می‌خواهیم که بیشترین زیبایی بین این اسم‌ها را چاپ کنید. # ورودی خط اول ورودی شامل عدد $n$ است. در $n$ خط بعدی هر خط شامل یک اسم پیشنهادی است. هر اسم رشته‌ای با حداکثر ۲۰ حرف از حروف کوچک انگلیسی می‌باشد. # خروجی در تنها خط خروجی یک عدد چاپ کنید که برابر تعداد حروف مختلف در اسم انتخابی خواهد بود. # ورودی نمونه ``` 4 ali karim abbas mohammad ``` # خروجی نمونه ``` 5 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خلیل آقا یک راننده شریف اسنپی است. خلیل آقا به دلیل علاقه زیادی که به سکه دارد پس از هر روز کار تمام پول‌های دریافتی خود را تبدیل به سکه می‌کند و در یک ستون می‌چیند. پس از $n$ روز در روز $n + 1$ ام وی تصمیم می‌گیرد که همه این $n$ ستون را هم ارتفاع کند. او هر مرحله می‌تواند یک سکه از یک ستون بردارد و روی ستون دیگری قرار دهد، به او بگویید که حداقل چند مرحله لازم است. # ورودی سطر اول ورودی شامل عدد $n$ است که نمایانگر تعداد ستون‌های سکه‌ی خلیل است. در سطر $i$م از هریک از $n$ سطر بعدی یک عدد طبیعی حداقل ۰ و حداکثر $10^4$ آمده است که ارتفاع ستون‌ها را نشان میدهد. تضمین می‌شود که خلیل می‌تواند با حرکت گفته‌شده همه ستون‌ها را هم ارتفاع کند. $$1 \le n \le 10^4$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمینه دقایقیست که خلیل می‌تواند در آن ستون‌هایش را هم ارتفاع کند. # ورودی نمونه ``` 4 1 2 3 6 ``` # خروجی نمونه ``` 3 ``` خلیل می‌تواند یک سکه از ستون آخر به ستون دوم ببرد و ۲ سکه از ستون آخر به ستون اول تا ارتفاع همه‌ی ستون‌ها برابر ۳ شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزد با مهارت، در دزدی به مهارت بالا رفتن و جانگولربازی (‌jungular play) نیاز دارد؛ چرا که بعد از پیدا کردن دوربین های فروشگاه و ورود به آن، او دریافت که تیله‌ها در طبقه‌ی آخر است. او در طبقه‌ی اول فروشگاه بوده و باید به طبقه‌ی آخر یعنی طبقه‌ی $n$ ام برود. هر طبقه دو پنجره دارد. یکی در سمت راست طبقه و یکی در سمت چپ طبقه(هر طبقه را یک پاره خط افقی فرض کنید که پنجره‌ها در دو لبه‌ی آن قرار دارد). اگر دزد در طبقه‌ی $k$ باشد، تنها می‌تواند به طبقه‌ی $k+1$ برود. اگر برای مثال او در طبقه‌ی $k$باشد، دو روش برای رفتن به طبقه‌ی بعدی وجود دارد: ۱. از پنجره‌ی سمت راست طبقه‌ی $k$ ام خارج شده و از طریق پنجره‌ی سمت راست، به طبقه‌ی $k+1$ وارد شود. ۲. از پنجره‌ی سمت چپ طبقه‌ی $k$ ام خارج شده و از طریق پنجره‌ی سمت چپ، به طبقه‌ی $k+1$ وارد شود. متاسفانه در بعضی از طبقات، پلیس وجود دارد. در هر طبقه حداکثر یک پلیس وجود دارد. در طبقه‌ی اول و آخر پلیس وجود ندارد. هر پلیس چون خسته است(ساعت کاری شون زیاده!)، تنها می‌تواند مراقب یکی از پنجره‌های طبقه‌ای که در آن است، باشد؛ یعنی دزد نمی‌تواند از آن پنجره وارد آن طبقه شود و در عین حال نمی‌تواند در آن طبقه از پنجره‌ای که پلیس مراقب آن است، خارج شود و به طبقه‌ی بالا برود. یعنی اگر مثلا پلیسی در طبقه‌ی $k$ ام باشد و مراقب پنجره‌ی راست باشد و دزد بخواهد از طبقه‌ی $k-1$ ام به طبقه‌ی $k+1$ ام برود، باید از پنجره‌ی چپ طبقه‌ی $k-1$ ام خارج شده و از طریق پنجره‌ی چپ، به طبقه‌ی $k$ ام وارد شود. سپس باید دوباره از پنجره‌ی سمت چپ طبقه‌ی $k$ ام استفاده کرده و از طریق پنجره‌ی چپ، به طبقه‌ی $k+1$ ام وارد شود. دقت کنید که اگر در طبقه‌ای هیچ پلیسی نباشد، از هر دو پنجره‌ی آن می‌توان خارج و از هر دو پنجره‌ی آن می‌توان به آن وارد شد. دزد مکان پلیس‌ها و پنجره‌ای را که هر کدام مراقبش هستند، می‌داند. او به شما این اطلاعات را می‌دهد و شما می‌خواهد که به او بگویید که آیا می‌تواند به طبقه‌ی آخر برود یا خیر. # ورودی در هر ورودی، تعدادی تست آمده‌است که برنامه‌ی شما باید به آن‌ها به ترتیب پاسخ دهد. در سطر اول هر ورودی یک عدد $t$ آمده است که نمایانگر تعداد تست‌هایی است که باید در این ورودی جواب داده شوند. سپس در هر تست: در سطر اول هر تست دو عدد $n$ و $k$ آمده‌ است که نمایانگر تعداد طبقات و تعداد پلیس‌‌ها در این تست است. در $k$ سطر بعدی، در سطر i، ابتدا $a_i$ که نمایانگر طبقه‌ی حضور پلیس $i$ ام است،آمده است. سپس یک عدد آمده است که نمایانگر پنجره ایست که پلیس $i$ ام مراقب آن است که این عدد یا 0 است و یا 1: 0: به معنای اینکه پلیس $i$ ام مراقب پنجره‌ی راست است. 1: به معنای اینکه پلیس $i$ ام مراقب پنجره‌ی چپ است. $$ 3 \le n \le 100\ 000 $$ $$ 0 \le k \le n-2 $$ $$ 2 \le a_i \le n-1 $$ مجموع $n$ در تست‌های هر ورودی از $ 200\ 000 $ بیشتر نیست. # خروجی در تنها سطر خروجی هر تست یکی از دو کلمه‌ی زیر را خروجی دهید: + No: به معنای دزد نمی‌تواند به طبقه‌ی آخر برسد + Yes: به معنای اینکه دزد می‌تواند به طبقه‌ی آخر برسد # مثال ## ورودی نمونه ``` 3 5 1 2 0 5 3 3 0 2 1 4 0 4 2 2 1 3 1 ``` ## خروجی نمونه ``` Yes No Yes ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بد خواه، بدِ مردم را میخواهد. از این رو بر آن شده است که مردم را سرگرم کند و وقتشان را تلف کند تا به کار های مهم زندگی نرسند. او ابتدا مردم را به یک اتاق دعوت می‌کند. سپس کیسه ای را با $m$ توپ سیاه و $n$ توپ سفید پر میکند. سپس از شخصی میخواهد تا دو توپ از کیسه بیرون بیاورد. اگر دو توپ هم رنگ بودند، یک توپ سفید جدید در داخل کیسه بیاندازد و اگر همرنگ نبودند، یک توپ سیاه جدید داخل کیسه بیاندازد. سپس دو توپ خارج شده را دور بیاندازد. آن شخص باید اینقدر این کار را تکرار کند تا دقیقاً یک توپ داخل کیسه باقی بماند. بعد از اینکه بد خواه از کسی خواهش کرد که او این کار را انجام دهد، قبل از این که آن شخص شروع به انجام کار کند بدخواه از آن اتاق بیرون رفته و وقتی که دقیقا یک توپ در کیسه باقی مانده بود به اتاق برمیگردد. دقت کنید که بدخواه از ترتیب بیرون آوردن توپ‌ها بی اطلاع است و تنها $n$ و $m$ را میداند. از آنجایی که بدخواه دنبال سرگرم کردن مردم است، میخواهد رنگ توپ داخل کیسه را پیش‌بینی کند. اما از آنجایی که ذاتاً آدم بی‌هنریست، توانایی انجام این کار را ندارد. از این رو بر آن شده است که از شما کمک بگیرد و از شما می‌خواهد که رنگ توپ را فقط با دانستن $n$ و $m$ برای او پیش بینی کنید یا به او بگویید امکان پیش‌بینی وجود ندارد زیرا امکان دارد توپ باقی‌مانده سفید یا سیاه (بسته به ترتیب بیرون آوردن توپ‌ها) باشد تا او بتواند با انجام حرکات موزون مردم را سرگرم کند تا ناتوانی او در پیش‌بینی را فراموش کنند. # ورودی سطر اول ورودی شامل دو عدد $m$ و $n$ است که به ترتیب نشان دهنده‌ ی تعداد توپ‌های سیاه و تعداد توپ‌های سفید اند. $$ 1 \le m,n \le 1000\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک کلمه باشد: + $white$ : به معنای اینکه توپ آخر سفید است. + $black$ : به معنای اینکه توپ آخر سیاه است. + $no prediction$ : به معنای اینکه امکان پیش‌بینی وجود ندارد. # مثال ## ورودی نمونه ۱ ``` 2 2 ``` ## خروجی نمونه ۱ ``` white ``` ## ورودی نمونه ۲ ``` 3 6 ``` ## خروجی نمونه ۲ ``` black ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، باید درس تربیت بدنی را پاس کند. رادزینکا در دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا (Tziolkovsky Kaluga State Pedagogical University) تحصیل میکند. همانطور که می‌دانید آزمون درس تربیت بدنی در این دانشگاه بسیار سخت گیرانه گرفته می‌شود، بصورتی که همه‌ی دانشجوها مقدار زیادی تمرین می‌کنند تا بتوانند از آن آزمون سخت گذر کنند. رادزینکا بدلیل تنبلی‌اش، قاعدتاً نمی‌تواند از پس این آزمون برآید. پس تلاش‌می‌کند که هرگونه حقه‌ای به کار گیرد تا بدون تلاش این درس یک واحدی را پاس کند. آزمون نهایی تربیت بدنی در این ترم، دوی استقامت است. دانشجویان باید $a$ متر دور زمین دو‌ و میدانی دانشگاه بدوند. این زمین $n$ متر طول دارد و شامل یک خط شروع است. کنار زمین $n$ خط کشیده شده‌است که هر دو تای آن ۱ متر با هم فاصله دارند و کنار هر خط فاصله‌ی نقطه‌ی شروع تا آن خط را نوشته است. بعنوان مثال، در کنار نقطه‌ی شروع، یک خط است که در کنار آن ۰ نوشته شده است. یک متر پیش از نقطه‌ی شروع نیز یک خط هست که در کنار آن مقدار $n - 1$ نوشته شده است. رادزینکا با کمی دقت متوجه شد که می‌تواند به جای $a$ متر، به مقدار باقی‌مانده‌ی $a$ پس از تقسیم بر $n$ متر ($a\ mod\ n$ متر) بدود و به جایی برسد که در نهایت باید آنجا متوقف شود! استاد تربیت بدنی این ترم، کاستاماروف لفانتونویچ (Kostomarov Lev Antonovich)، بسیار دقیق و سخت‌گیر است و برای تقلب جریمه‌های سنگینی می‌گذارد. اگر فردی که باید $x$ متر بدود به هر دلیلی این کار را انجام ندهد، باید بار دیگر امتحان بدهد و این‌بار $x^x$ متر بدود! رادزینکا هنگام دادن آزمون، با خیال راحت $a\ mod\ n$ متر می‌دود تا به کنار خط هدفش برسد. اما کاستاماروف دقیق‌تر از این حرف‌ها است و متوجه تقلب او می‌شود. پس با داد و بیداد، رادزینکا را به نقطه‌ی شروع می‌فرستد و به او می‌گوید که این بار باید $a^a$ متر بدود. رادزینکای سرخورده، به نقطه‌ی شروع می‌رود و دوباره دو را شروع می‌کند، و به کنار خط $a^a\ mod\ n$ می‌رود؛ اما باز هم کاستاماروف مچش را می‌گیرد و با چک و لگد، او را دوباره به نقطه ی شروع می‌برد که دوی ماراتن $(a^a)^{a^a}$ متری‌اش را آغاز کند. اکنون رادزینکا گیج شده و نمی‌تواند محاسبه کند که کجا باید توقف کند! شما مقدار $(a^a)^{a^a} \ mod \ n$ را به او بگویید تا یک بار دیگر برای فریب کاستاماروف تلاش کند. # ورودی در تنها سطر ورودی دو عدد $a$ و $n$ آمده است که با یک فاصله از هم جدا شده‌اند و به ترتیب نمایانگر مقدار اولیه‌ی دویدن در امتحان و طول زمین دو و میدانی دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا است. $$1 \le a \le 1000$$ $$2 \le n \le 1000$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که نمایانگر خطی است که رادزینکا پس از ۲ بار تقلب، در انتهای امتحان باید کنارش بایستد. # مثال ## ورودی نمونه ۱ ``` 2 1000 ``` ## خروجی نمونه ۱ ``` 256 ``` ## ورودی نمونه ۲ ``` 2 5 ``` ## خروجی نمونه ۲ ``` 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مصطفی که آدمی کاری است، باید بر جلسه‌ی شرکت نظارت کند. در این جلسه $n$ نفر شرکت دارند و همگی پشت یک میز دایره‌ای نشسته‌اند. هر کس یا در بخش فنی شرکت است و یا در بخش علمی. یک بازه از افراد پشت سر هم (دور میز دایره‌ای) باحال هستند اگر تعداد افراد علمی آن‌ها بیشتر از تعداد افراد فنی آن‌ها باشد. مصطفی میخواهد بداند چند تا از بازه‌های افراد پشت میز باحال هستند. توجه داشته‌باشید که دو بازه‌ی متفاوت می‌توانند شامل افراد یکسانی شوند. (در حالتی که هر دو بازه شامل کل دایره باشند) برای مثال در حالتی که تنها ۲ نفر علمی دور دایره هستند، ۴ بازه‌ی باحال وجود دارد. # ورودی در سطر اول ورودی عدد $n$ آمده است که نمایانگر تعداد افراد پشت میز است. در سطر بعدی $n$ عدد بدون فاصله از هم آمده است که عدد $i$م اگر یک باشد یعنی نفر $i$م پشت میز علمی و اگر صفر باشد یعنی فنی است. میز به شکل دایره است یعنی نفر $n$م در کنار نفر اول نشسته است. $$ 1 \le n \le 100\ 000 $$ # خروجی در تنها سطر خروجی باید تعداد حالات باحال چاپ شود. # مثال ## ورودی نمونه ``` 5 10001 ``` ## خروجی نمونه ``` 5 ``` بازه های باحال در مثال بالا: ۱. نفر ۱م ۲. نفر ۵م ۳. نفر ۱م و ۵م ۴. نفر ۱م و ۲م و ۵م ۵. نفر ۱م و ۴م و ۵م