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

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

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! مدتی پیش تصمیم گرفته بودم وارد بازار عرضه‌ی کتاب کنکور شوم! و این دقیقاً پس از آن بود که قیمت‌های سرسام آورش کمرم را شکسته بود! درحال حاضر$a_1$‌ شیمیِ خیلی قهوه ای و $a_2$ دیفرانسیلِ باج و $a_3$ هندسه یِ خوشخوار داریم. هر بار می‌توانیم یکی از دو کار را انجام دهیم: 1. دو تا از یک نوع را بفروشیم. 2. دو تا از انواع مختلف بدهیم و یکی از نوع دیگر پس بگیریم. اگر در آخر دقیقاً یکی از یک نوع بماند آن از کدام نوع ها می‌تواند باشد؟ # ورودی در تنها خط ورودی سه عدد $a_1$ , $a_2$, $a_3$ می آیدکه هرکدام تعداد یک نوع کتاب را معلوم می‌کند. $$0 \leq a_i \leq 1\ 000\ 000\ 000$$ # خروجی در تنها خط خروجی سه کلمه بنویسید و در $i$ امین کلمه معلوم کنید که آیا می‌توان طوری کار ها را انجام داد که در آخر تنها یکی از نوع $i$ بماند(و از انواع دیگر چیزی نمانده باشد). اگر ممکن بود `YES`، و در غیر این صورت ‍‍‍`NO` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 1 ``` ## خروجی نمونه ۱ ``` NO NO NO ``` ## ورودی نمونه ۲ ``` 1 1 2 ``` ## خروجی نمونه ۲ ``` NO NO YES ``` به راحتی می‌توان با این سری اعمال به یکی از نوع سوم رسید: (1,2) (3,3)

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! مدرسه‌ی حلی سه از $n$ دانش آموز تشکیل شده‌است. $n$ کتاب دیفرانسیل از موسسات متمایز بین آن‌ها پخش شده‌است به طوری که هر نفر یک کتاب دارد. کتابی که نفر $i$ام در اختیار دارد از موسسه‌ی $a_i$ام است. در حالی که نفر $i$ام فقط می‌تواند کتاب‌های موسسه‌ی $i$ را مطالعه کند. می‌خواهیم به هر کس کتاب متناسب او را بدهیم! برای اینکار هر بار می‌توانیم کتاب نفر $i$ ام را با نفر $j$ ام عوض کنیم اگر $j-i| \leq \frac{n}{2} + 1$| باشد. شما باید دنباله‌ای از جابه‌جایی‌ها بدهید که هر جابه‌جایی به صورت دو عدد $i$ و $j$ است و کتاب‌های نفر $i$ام و $j$ ام را باهم جابه‌جا می‌کند. پس از انجامِ به ترتیب جابه‌جایی‌ها، هر‌ کس باید کتاب متناسب با خودش را داشته باشد(یعنی نفر $i$ام کتاب موسسه‌ی $i$ام را داشته باشد). به علت کمبود زمان تعداد جابه‌جایی‌ها باید کوچکتر مساوی $\frac{3 \cdot n}{2} $ باشد. # ورودی در خط اول ورودی $n$ تعداد افراد آمده است سپس در خط بعد یک جایگشت از اعداد $1$ تا $n$ به عنوان آرایه‌ی $a$ آمده است. $$1 \leq n \leq 200\ 000$$ $$1 \leq a_i \leq n$$ # خروجی در خط اول خروجی $q$ تعداد جابه‌جایی‌ها بیاید. سپس $q$ خط در هر کدام دو عدد $i$ و $j$ باشد که بیانگر جابه‌جایی کتاب‌های $i$ ام و $j$ ام است.با این شرط که $j-i| \leq \frac{n}{2} + 1$| و $q$ کوچکتر مساوی $\frac{3 \cdot n}{2} $ باشد. اگر چند جواب وجود داشت یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 3 2 1 4 ``` ## خروجی نمونه ۱ ``` 1 3 1 ``` ## ورودی نمونه ۲ ``` 5 5 4 3 2 1 ``` ## خروجی نمونه ۲ ``` 4 1 3 3 5 1 3 2 4 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ---------- برنامه‌ای بنویسید که عدد $n$ و سپس یک دنباله $n$-تایی $a_1, a_2, a_3, ..., a_n$ را از ورودی بخواند. سپس به برنامه‌ی شما $q$ پرسش داده می‌شود که هر پرسش بصورت یک عدد $r$ است و برنامه‌ی شما باید نتیجه‌ی این پرسش را چاپ کند. نتیجه‌ی پرسش $r$ برابر مقدار زیر است: $$\sum _{i = 1} ^ r a_i \ xor\ (r - i)$$ برنامه‌تان را طوری بنویسید که پیش‌پردازش طولانی نداشته باشد و پاسخ هر پرسش را سریع بدهد؛ یعنی پیش از پرسش اول و پس از دریافت هر پرسش تا پایان خروجی دادن کمتر از ضریب ثابتی از $n$ دستور (مستقل از دیگر متغیرهای ورودی بجز $n$) انجام بشود. همچنین کل اجرای برنامه‌ی شما نباید بیش از ۲ ثانیه طول بکشد. **راهنمایی:** روش‌های مختلفی برای پیاده‌سازی بهینه وجود دارد؛ یکی از آن‌ها این‌چنین است: برای هر پرسش مقدار گفته‌شده را با یک حلقه ساده بدست آورید؛ در این روش تنها کاری که برای بهینه‌سازی زمان برنامه باید بکنید این است که پس از محاسبه‌ی نتیجه‌ی یک پرسش، این نتیجه را جایی ذخیره کنید که اگر در ادامه‌ دقیقاً همان پرسش دوباره مطرح شد، دوباره آن را محاسبه نکنید و مقداری که از قبل محاسبه شده بود را خروجی دهید. # ورودی در سطر اول ورودی دو عدد $n$ و $q$ آمده است و در سطر دوم $n$ عدد طبیعی آمده است که عدد $i$-ام نمایان‌گر $a_i$ است. سپس در $q$ سطر بعدی هر خط یک سوال بصورت یک عدد طبیعی آمده است که برابر $r$ است. $$1 \le a_i \le 1\ 000\ 000$$ $$1 \le r \le n \le 10\ 000$$ $$1 \le q \le 500\ 000$$ # خروجی در $q$ سطر هریک یک عدد چاپ کنید که پاسخ به یکی از پرسش‌های داده شده است. # مثال ## ورودی نمونه ``` 4 4 4 3 6 2 1 2 3 4 ``` ## خروجی نمونه ``` 4 8 14 17 ``` پاسخ پرسش‌ها به ترتیب: $4\ xor\ 0 = 4$ $(4 \ xor\ 1) + (3 \ xor\ 0) = 5 + 3 = 8$ $(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$