یک سوال ساده


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

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

یک عدد به شما داده شده است. به تعداد آن عدد برای ما جمله‌ی "man khoshghlab hastam" را چاپ کنید بلکه به خوش‌قلب شدن، قدمی دیگر نزدیک شده باشید.

ورودی🔗

در تنها سطر ورودی یک عدد nn به شما داده شده است که نماینگر تعداد دفعاتی است که باید جمله‌ی فوق را چاپ کنید. 1n100 1 \le n \le 100

خروجی🔗

خروجی شامل nn سطر می‌باشد که هر کدام از این سطر ها باید شامل عبارت "man khoshghlab hastam" باشد.

مثال🔗

ورودی نمونه🔗

3
Plain text

خروجی نمونه🔗

man khoshghlab hastam
man khoshghlab hastam
man khoshghlab hastam
Plain text

اسم‌ها


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

کریم یک کودک ۵ ساله است که به اسم متغیرها خیلی توجه می‌کند.

کریم یک پدربزرگ دارد که از «واج آرایی» متنفر است. او اسم‌هایی را دوست دارد که در آن‌ها تعداد حرف‌های مختلف زیاد باشد. برای مثال karim پنج حرف مختلف (همه‌ی حرف هایش مختلفند) و abbas سه حرف مختلف دارد. (حرف های a و b و s)

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

ورودی🔗

خط اول ورودی شامل عدد nn است. در nn خط بعدی هر خط شامل یک اسم پیشنهادی است. هر اسم رشته‌ای با حداکثر ۲۰ حرف از حروف کوچک انگلیسی می‌باشد.

خروجی🔗

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

ورودی نمونه🔗

4
ali
karim
abbas
mohammad
Plain text

خروجی نمونه🔗

5
Plain text

خیلی قهوه ای یا باج یا خوش‌خوار!


  • محدودیت زمان: ۰.۵ ثانیه
  • محدودیت حافظه: ۱۲۸ مگابایت

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

مدتی پیش تصمیم گرفته بودم وارد بازار عرضه‌ی کتاب کنکور شوم! و این دقیقاً پس از آن بود که قیمت‌های سرسام آورش کمرم را شکسته بود! درحال حاضرa1a_1‌ شیمیِ خیلی قهوه ای و a2a_2 دیفرانسیلِ باج و a3a_3 هندسه یِ خوشخوار داریم. هر بار می‌توانیم یکی از دو کار را انجام دهیم:

  1. دو تا از یک نوع را بفروشیم.
  2. دو تا از انواع مختلف بدهیم و یکی از نوع دیگر پس بگیریم.

اگر در آخر دقیقاً یکی از یک نوع بماند آن از کدام نوع ها می‌تواند باشد؟

ورودی🔗

در تنها خط ورودی سه عدد a1a_1 , a2a_2, a3a_3 می آیدکه هرکدام تعداد یک نوع کتاب را معلوم می‌کند.

0ai1 000 000 0000 \leq a_i \leq 1\ 000\ 000\ 000

خروجی🔗

در تنها خط خروجی سه کلمه بنویسید و در ii امین کلمه معلوم کنید که آیا می‌توان طوری کار ها را انجام داد که در آخر تنها یکی از نوع ii بماند(و از انواع دیگر چیزی نمانده باشد). اگر ممکن بود YES، و در غیر این صورت ‍‍‍NO را چاپ کنید.

مثال🔗

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

1 1 1
Plain text

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

NO NO NO
Plain text

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

1 1 2
Plain text

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

NO NO YES
Plain text

به راحتی می‌توان با این سری اعمال به یکی از نوع سوم رسید: (1,2) (3,3)

هر که بامش بیش درسش بیش‌تر!


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

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

مدرسه‌ی حلی سه از nn دانش آموز تشکیل شده‌است. nn کتاب دیفرانسیل از موسسات متمایز بین آن‌ها پخش شده‌است به طوری که هر نفر یک کتاب دارد. کتابی که نفر iiام در اختیار دارد از موسسه‌ی aia_iام است. در حالی که نفر iiام فقط می‌تواند کتاب‌های موسسه‌ی ii را مطالعه کند.

می‌خواهیم به هر کس کتاب متناسب او را بدهیم! برای اینکار هر بار می‌توانیم کتاب نفر ii ام را با نفر jj ام عوض کنیم اگر jin2+1j-i| \leq \frac{n}{2} + 1| باشد.

شما باید دنباله‌ای از جابه‌جایی‌ها بدهید که هر جابه‌جایی به صورت دو عدد ii و jj است و کتاب‌های نفر iiام و jj ام را باهم جابه‌جا می‌کند. پس از انجامِ به ترتیب جابه‌جایی‌ها، هر‌ کس باید کتاب متناسب با خودش را داشته باشد(یعنی نفر iiام کتاب موسسه‌ی iiام را داشته باشد). به علت کمبود زمان تعداد جابه‌جایی‌ها باید کوچکتر مساوی 3n2\frac{3 \cdot n}{2} باشد.

ورودی🔗

در خط اول ورودی nn تعداد افراد آمده است سپس در خط بعد یک جایگشت از اعداد 11 تا nn به عنوان آرایه‌ی aa آمده است. 1n200 0001 \leq n \leq 200\ 000 1ain1 \leq a_i \leq n

خروجی🔗

در خط اول خروجی qq تعداد جابه‌جایی‌ها بیاید. سپس qq خط در هر کدام دو عدد ii و jj باشد که بیانگر جابه‌جایی کتاب‌های ii ام و jj ام است.با این شرط که jin2+1j-i| \leq \frac{n}{2} + 1| و qq کوچکتر مساوی 3n2\frac{3 \cdot n}{2} باشد. اگر چند جواب وجود داشت یکی را چاپ کنید.

مثال🔗

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

4
3 2 1 4
Plain text

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

1
3 1
Plain text

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

5
5 4 3 2 1
Plain text

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

4
1 3
3 5
1 3
2 4
Plain text

بسی پرسش


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

برنامه‌ای بنویسید که عدد nn و سپس یک دنباله nn-تایی a1,a2,a3,...,ana_1, a_2, a_3, ..., a_n را از ورودی بخواند. سپس به برنامه‌ی شما qq پرسش داده می‌شود که هر پرسش بصورت یک عدد rr است و برنامه‌ی شما باید نتیجه‌ی این پرسش را چاپ کند. نتیجه‌ی پرسش rr برابر مقدار زیر است:

i=1rai xor (ri)\sum _{i = 1} ^ r a_i \ xor\ (r - i)

برنامه‌تان را طوری بنویسید که پیش‌پردازش طولانی نداشته باشد و پاسخ هر پرسش را سریع بدهد؛ یعنی پیش از پرسش اول و پس از دریافت هر پرسش تا پایان خروجی دادن کمتر از ضریب ثابتی از nn دستور (مستقل از دیگر متغیرهای ورودی بجز nn) انجام بشود. همچنین کل اجرای برنامه‌ی شما نباید بیش از ۲ ثانیه طول بکشد.

راهنمایی:

روش‌های مختلفی برای پیاده‌سازی بهینه وجود دارد؛ یکی از آن‌ها این‌چنین است: برای هر پرسش مقدار گفته‌شده را با یک حلقه ساده بدست آورید؛ در این روش تنها کاری که برای بهینه‌سازی زمان برنامه باید بکنید این است که پس از محاسبه‌ی نتیجه‌ی یک پرسش، این نتیجه را جایی ذخیره کنید که اگر در ادامه‌ دقیقاً همان پرسش دوباره مطرح شد، دوباره آن را محاسبه نکنید و مقداری که از قبل محاسبه شده بود را خروجی دهید.

ورودی🔗

در سطر اول ورودی دو عدد nn و qq آمده است و در سطر دوم nn عدد طبیعی آمده است که عدد ii-ام نمایان‌گر aia_i است. سپس در qq سطر بعدی هر خط یک سوال بصورت یک عدد طبیعی آمده است که برابر rr است.

1ai1 000 0001 \le a_i \le 1\ 000\ 000 1rn10 0001 \le r \le n \le 10\ 000 1q500 0001 \le q \le 500\ 000

خروجی🔗

در qq سطر هریک یک عدد چاپ کنید که پاسخ به یکی از پرسش‌های داده شده است.

مثال🔗

ورودی نمونه🔗

4 4
4 3 6 2
1
2
3
4
Plain text

خروجی نمونه🔗

4
8
14
17
Plain text

پاسخ پرسش‌ها به ترتیب:

4 xor 0=44\ xor\ 0 = 4

(4 xor 1)+(3 xor 0)=5+3=8(4 \ xor\ 1) + (3 \ xor\ 0) = 5 + 3 = 8

(4 xor 2)+(3 xor 1)+(6 xor 0)=6+2+6=14(4 \ xor\ 2) + (3 \ xor\ 1) + (6 \ xor\ 0) = 6 + 2 + 6 = 14

(4 xor 3)+(3 xor 2)+(6 xor 1)+(2 xor 0)=7+1+7+2=17(4 \ xor\ 3) + (3 \ xor\ 2) + (6 \ xor\ 1) + (2 \ xor\ 0) = 7 + 1 + 7 + 2 = 17