حدس عدد

یک سوال ساده

بازگشت از بوستان

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** برای کنترل جهان باید از کنترل کولر شروع کرد! "رادزینکا دوبرامیل ویچشسلافوویچ" قرار شده‌است که در عمارت، انتخاباتی برگزار شود تا شخص منتخب خانه را اداره کند. آقای خطری، یکی از اعضای خانه است که میخواهد برای این کار نامزد بشود. او مردی به شدت منطقی بوده و معتقد است که کولر باید خاموش باشد! انگیزه‌ی شرکت او در انتخابات هم همین است... هنگام ثبت‌نام نامزد از او خواسته شد تا نام انتخاباتی خود را وارد کند. او که احساس می‌کرد که اسم «خطری» رای‌دهندگان را خواهد ترساند تصمیم گرفت که نام دیگری را وارد کند. او دستش را برروی صفحه کلید گذاشت (تکنولوژی در عمارت بالاست) و تعدادی کلید را فشار داد تا اسم انتخاباتی‌اش را وارد کند. می‌دانیم که صفحه کلید تنها شامل حروف و دکمه‌ی 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 ```

صفحه‌کلید انتخاباتی

استارتاپ جدید

راننده

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزد با مهارت، در دزدی به مهارت بالا رفتن و جانگولربازی (‌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 ```