+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرمحمد مسئول اهدای کاکتوس به شرکت‌کنندگان مسابقه است. $n$ دسته از شرکت‌کنندگان به ترتیب به امیرمحمد رجوع میکنند و از او طلب کاکتوس می‌کنند. دسته $i$ام شامل $a_i$ نفر است. اگر افراد آن دسته حداکثر **۳ نفر** باشند امیرمحمد به اندازه تعداد نفراتشان به آن‌ها کاکتوس می‌دهد؛ در غیر این صورت تنها یک کاکتوس به کل دسته می‌دهد. به شما تعداد افراد هر دسته داده می‌شود. شما باید به ازای هر دسته، تعداد کاکتوس‌هایی راکه امیرمحمد به آن‌ها می‌دهد را با چاپ کردن کارکتر ‍‍`*` نشان دهید. # ورودی در خط اول ورودی عدد طبیعی $n$ داده میشود که نشانگر تعداد دسته افراد مراجعه کننده به امیرمحمد است. در خط بعدی $n$ عدد طبیعی داده می‌شود که عدد $i$ام نشانگر تعداد افراد دسته $i$ام است. $$1 \le n, a_i \le 100$$ # خروجی خروجی برنامه شما شامل $n$ خط است که باید در خط $i$ام باید به اندازه تعداد کاکتوس‌هایی که امیرمحمد به دسته $i$ام میدهد '$*$' چاپ کنید. ## ورودی نمونه ۱ ``` 5 1 5 2 4 3 ``` ## خروجی نمونه ۱ ``` * * ** * *** ```

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

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیر هر روز برای رفتن به محل کارش از مترو استفاده می‌کند. یک بلیت مترو یک بارکد نه در نه است که هر خانه آن سیاه یا سفید است. متاسفانه بعضی از خانه‌های بلیت امیر کمرنگ شده و معلوم نیست که چه رنگی بودند. هر بارکد را با یک جدول از اعداد صفر و یک نشان می‌دهیم؛ عدد یک نشان‌دهنده رنگ سیاه و صفر نشان‌دهنده رنگ سفید است. هر بارکد چهار مربع سه در سه که محیط آن سیاه و درونش سفید است، دارد. چهار مربع را می‌توانید در گوشه‌های شکل زیر مشاهده کنید: ``` 111###111 101###101 111###111 ######### ######### ######### 111###111 101###101 111###111 ``` توجه کنید که مربع‌های سه در سه گوشه همه بارکدها، باید **دقیقا** مانند شکل بالا باشند و در غیر این صورت قابل استفاده در مترو نیستند. حال یک بارکد به شما داده شده است؛ اگر رنگ یک خانه معلوم نبود آن را با عدد دو نشان می‌دهیم. شما باید به امیر بگویید که این بارکد چند حالت مختلف می‌تواند داشته باشد؛ توجه کنید که بارکد امیر ممکن است در هیچ حالتی درست نباشد و در آن صورت جواب صفر است (بارکد در صورتی نامعتبر است که یکی از مربع‌های سه در سه گوشه نتوانند به شکل گفته شده باشند). # ورودی ورودی شامل ۹ خط است که هر خط شامل ۹ کاراکتر است که بدون فاصله آمده‌اند. هر کاراکتر یکی از ارقام ۰ تا ۲ است. این ارقام به ترتیب نشان‌دهنده رنگ سفید، رنگ سیاه و خانه با رنگ نامعلوم هستند. # خروجی در تنها خط خروجی تعداد بارکدهای ممکن را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 111011111 101011101 111011111 111000100 111110011 011010001 111010111 101212101 111002111 ``` ## خروجی نمونه ۱ ``` 8 ``` در این نمونه هر یک از خانه‌های ۲، دو حالت می‌توانند داشته باشند، پس جواب برابر با $2^3 = 8$ است. ## ورودی نمونه ۲ ``` 121101111 101011101 111011111 110110011 122210101 111100111 111010111 101110101 111000111 ``` ## خروجی نمونه ۲ ``` 8 ``` در این نمونه ۴ تا دو داریم که ۲ موجود در سطر اول، باید حتما سیاه شود. بنابر این جواب برابر با $2^3 = 8$ است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نقطه‌بازی یک بازی قدیمی است. این بازی معمولا بین دو بازیکن در یک صفحه $N \times M$ که شامل $N$ ردیف است که در هر ردیف $M$ نقطه است، انجام می‌شود. ردیف‌ها را از بالا به پایین با ۱ تا $n$ و ستون‌ها را از چپ به راست با ۱ تا $m$ نامگذاری می‌کنیم. بازی به این صورت است که هر کس در نوبت خود بین دو نقطه‌ی مجاور که قبلا بین آنها پاره‌خطی کشیده نشده است ، پاره‌خطی می‌کشد. هر گاه حرکت کسی منجر به ساخت تعدادی مربع $1 \times 1$ شود، به تعداد مربع‌ها امتیاز می‌گیرد و **همچنین حرکت بعدی را نیز باید خودش انجام دهد**. بازی وقتی تمام می‌شود که نشود پاره‌خطی کشید. همانطور که می‌دانید یک برنامه‌نویس بیشتر از هر چیز به تفریح و سرگرمی نیاز دارد. به همین منظور ناصر و یاسر که دو تا از خوب‌های شرکت رهنما هستند، تصمیم می‌گیرند با هم نقطه‌بازی کنند. از آنجایی که ناصر اعتقاد دارد که معمولا شروع کننده بازی‌، برنده بازی است **همواره** حرکت اول را او انجام می‌دهد. بعد از پایان بازی یک مسئله ذهن ناصر را مشغول می‌کند؛ آیا کسی می‌تواند بدون دیدن برگه بازی و صرفا با دانستن پاره‌خط‌های کشیده شده نتیجه بازی را بفهمد. ما از شما می‌خواهیم به ناصر کمک کنید و برنامه‌ای بنویسید تا صرفا با گرفتن حرکات، نتیجه نهایی را برای ما محاسبه کند. **برای فهم بیشتر، شکلی که برای ورودی نمونه دوم کشیده شده را نگاه کنید.** # ورودی در خط اول $n$ و $m$ که ابعاد صفحه هستند داده می‌شود. در $ 2\times n \times m - n - m $ خط بعدی در هر خط چهار عدد مانند $(x_{1} , y_{1} , x_{2} , y_{2})$ به شما داده می‌شود که به معنای این است که نقطه‌ی سطر $x_{1}$ و ستون $y_{1}$ به نقطه سطر $x_{2}$ و ستون $y_{2}$ با یک پاره‌خط متصل شد. همچنین تضمین می‌شود که ناصر و یاسر تنها حرکات مجاز انجام می‌دهند.(یعنی همواره پاره‌خط بین دو نقطه‌ی مجاور است که تا به حال بین آنها خطی کشیده نشده است.) همچنین داریم: $$ 2 \le n , m \le 200 $$ $$ 1 \le x_{1} , x_{2} \le n$$ $$ 1 \le y_{1} , y_{2} \le m$$ # خروجی در یک خط دو عدد (که با فاصله از هم جدا شده‌اند) چاپ کنید که عدد اول امتیاز ناصر و عدد دوم امتیاز یاسر باشد. ## ورودی نمونه ۱ ``` 2 2 1 1 1 2 1 2 2 2 2 2 2 1 2 1 1 1 ``` ## خروجی نمونه ۱ ``` 0 1 ``` ## ورودی نمونه ۲ ``` 2 3 1 1 2 1 1 2 2 2 1 2 1 3 1 1 1 2 2 1 2 2 2 2 2 3 1 3 2 3 ``` ## خروجی نمونه ۲ ``` 1 1 ``` شکل زیر نمایانگر بازی ورودی نمونه دوم است: 

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در هر دور از مسابقه *LIFFCode*، چهار شرکت‌کننده با هم مسابقه می‌دهند و حق استفاده از سه زبان انتخاب شده را دارند. مهارت شرکت‌کننده $i$ام در زبان $j$ام، $a_{ij}$ است. هر شرکت‌کننده سوال مسابقه را با زبانی که بیشتر از همه در آن مهارت دارد، حل می‌کند. در نهایت هم شرکت‌کننده‌ای برنده می‌شود که مهارتش در زبانی که استفاده کرده از سایرین بیشتر باشد. حال شما باید با گرفتن اطلاعات مهارت هر یک از شرکت‌کننده‌ها، برنده مسابقه را قبل از شروع آن مشخص کنید. # ورودی ورودی شامل ۴ خط است که خط $i$ام ورودی شامل ۳ عدد طبیعی است که نشانگر مهارت شرکت‌کننده $i$ام در سه زبان برنامه نویسی مختلف است. **تمام اعداد ورودی متمایز و کوچکتر مساوی ۱۰۰ هستند.** # خروجی در تنها خط خروجی باید شماره شرکت‌کننده برنده را چاپ کنید. ## ورودی نمونه ۱ ``` 1 4 15 3 5 8 9 7 2 12 13 14 ``` ## خروجی نمونه ۱ ``` 1 ``` شرکت‌کننده اول از زبان سومش با مهارت ۱۵، شرکت‌کننده دوم هم از زبان سومش با مهارت ۸، شرکت‌کننده سوم از زبان اولش با مهارت ۹ و شرکت‌کننده چهارم از زبان سومش با مهارت ۱۴ استفاده می‌کند.و در نهایت چون مهارت شرکت‌کننده اول بیشتر بوده، او برنده می‌شود. ## ورودی نمونه ۲ ``` 90 92 91 80 93 81 99 10 11 51 98 97 ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- احمد رشته $S$ که از حروف کوچک انگلیسی تشکیل شده را دوست دارد. جواد به بهانه تولد احمد، $n$ رشته را آماده کرده و می‌خواهد یکی از آن‌ها را برای تولد احمد به او هدیه دهد. جواد می‌داند احمد فقط رشته‌هایی را دوست دارد که رشته $S$ زیردنباله آن باشد. حال جواد از شما می‌خواهد تا تعداد رشته‌هایی را که احمد دوست دارد را به دست بیاورد. تعریف می‌کنیم رشته $T$ زیردنباله رشته $S$ است؛ اگر و تنها اگر با حذف تعدادی از کاراکترهای $S$ (این تعداد می‌تواند صفر باشد)، بتوان آن را به رشته $T$ تبدیل کرد. # ورودی در خط اول ورودی رشته $s$ داده میشود. در خط دوم ورودی عددطبیعی $n$ داده می‌شود. در هریک از $n$ خط بعدی یکی از رشته‌هایی که جواد آماده کرده است ورودی داده می‌شود. $$1 \le n \le 100$$ اندازه همه‌ی رشته‌های ورودی حداکثر ۱۰۰ است. # خروجی در تنها خط خروجی تعداد رشته‌هایی که احمد دوست دارد را چاپ کنید. ## ورودی نمونه ۱ ``` cod 4 coding crocodile doc acetaminofencodeina ``` ## خروجی نمونه ۱ ``` 3 ``` احمد کلمات اول و دوم و چهارم را دوست دارد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علی که پسری تنبل و بازی‌گوش است، تمام عید را صرف خوش‌گذرانی در منزل و بازی کردن بود. متاسفانه معلم علی ایمیل زده که **از همین شنبه** کلاس‌های آنلاین را برگزار می‌کند و تا آن‌موقع همه دانش‌آموزان باید پیک‌های شادی خود را کامل کنند و برای وی ارسال کنند. علی که وقت کافی برای حل پیک‌شادی خود ندارد و دوستانش منتظرش هستند که در بازی *FortCode*، آنلاین شود تا باهم بازی کنند، از شما می‌خواهد که برنامه‌ای برای او بنویسید تا با گرفتن یک معادله درجه یک، آن را برایش حل کنید. شما با دریافت معادله درجه یک،‌ باید آن‌را حل کنید و در صورتی که پس از ساده‌سازی، ضریب $x$ برابر با صفر شد، عبارت `invalid` را چاپ کنید در غیر اینصورت اگر پاسخ شما برابر $\frac{p}{q}$ باشد، باید عبارت `p q` را بنویسید به طوری که $p$ و $q$ نسبت به هم اول باشند و همچنین $q$ عددی طبیعی باشد. برای اطلاع بیشتر از نحوه دادن معادله بخش ورودی و مثال‌ها را بخوانید. # ورودی در خط اول ورودی ابتدا عدد $n$ می‌آید که بیانگر تعداد کاراکترهای رشته معادله می‌باشد. در خط دوم یک رشته شامل $n$ کاراکتر می‌آید که بیانگر یک معادله درجه یک برحسب $x$ می‌باشد. موارد زیر نیز رعایت شده‌اند: + در صورتی که ضریب $x$، ۱ و یا ۱- باشد، ضریب ۱ نمایش داده نمی‌شود. + در رشته ورودی هیچ **فاصله‌ای** وجود ندارد. + رشته ورودی شامل دقیقا یک کاراکتر $=$ می‌باشد. + حداقل یک $x$ در ورودی وجود دارد و ضریب هیچ $x$‌ای صفر نمی‌باشد. + رشته با علامت $+$ شروع نمی‌شود و درصورتی که ضریب یا عدد بلافاصله بعد از علامت $=$ مثبت باشد، علامت $+$ نمایش داده نمی‌شود. + در رشته عبارات $++$ و $--$ و $+-$ و $-+$ وجود ندارند. همچنین ضریب $x$ و تمامی اعداد در بازه $[-10^9, 10^9]$ می‌باشند. $$3 \le n \le 1000$$ # خروجی در تنها خط خروجی، در صورتی که ضریب $x$ پس از ساده‌سازی برابر با صفر بود، عبارت `invalid` را چاپ کنید در غیراینصورت پاسخ را به صورت `p q` چاپ کنید به طوری $p$ و $q$ نسبت به هم اول باشند و همچنین $q$ عددی طبیعی باشد. # مثال ## ورودی نمونه ۱ ``` 7 3x+5=-4 ``` ## خروجی نمونه ۱ ``` -3 1 ``` پس از ساده سازی به کسر $\frac{-9}{3}$ می‌رسیم اما $-9$ و $3$ نسبت به هم اول نیستند، پس عبارت `-3 1` را چاپ می‌کنیم. ## ورودی نمونه ۲ ``` 9 5x=4x+x+0 ``` ## خروجی نمونه ۲ ``` invalid ``` پس از ساده‌سازی، ضریب $x$ صفر می‌شود پس عبارت `invalid` را چاپ می‌کنیم.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شرکت *beeptunes*، در حال راه‌اندازی یک سیستم هوش مصنوعی برای پیشنهاد موسیقی به کاربرهاست. اکنون بخش هوش این سیستم به انتها رسیده، اما هنوز رابط درستی بین داده‌های موجود و بخش هوش سیستم وجود ندارد! دو نوع داده جهت سیستم پیشنهاد موسیقی قابل استفاده است: 1. داده‌های مربوط به هر کاربر. این داده‌ها شامل نام کاربری، سن، شهر و لیست نام آلبوم‌هاییست که این کاربر خریداری کرده است. 2. داده‌های مربوط به هر آلبوم. این‌داده‌ها شامل نام آلبوم، نام خواننده، سبک و تعداد ترک‌های موسیقی این آلبوم هستند. برای این سیستم هوش مصنوعی، خود این داده‌ها بصورت خام اهمیتی ندارند. این سیستم داده‌ها را بطور خاصی درخواست می‌کند و باید آن‌ها را در اختیارش قرار دهیم. درخواست‌ها به صورت‌های زیر ممکن است باشند: 1. درخواست تعداد آهنگ‌هایی که یک کاربر از یک خواننده خریده‌است. 2. درخواست تعداد آهنگ‌هایی که یک کاربر از یک سبک خریده‌است. 3. درخواست تعداد آهنگ‌هایی که کاربرهای با یک سن خاص، از یک خواننده خریده‌اند. 4. درخواست تعداد آهنگ‌هایی که کاربرهای با یک سن خاص، از یک سبک خریده‌اند. 5. درخواست تعداد آهنگ‌هایی که کاربرهای با یک شهر خاص، از یک خواننده خریده‌اند. 6. درخواست تعداد آهنگ‌هایی که کاربرهای با یک شهر خاص، از یک سبک خریده‌اند. البته این سیستم خیلی هم باهوش نیست و ممکن است در سوال‌هایی که می‌پرسد نام کاربری، یا نام خواننده و یا هریک از فیلدهای مسئله اشتباه باشد و واقعاً در بین داده‌های سایت موجود نباشد. حال به سراغ شما آمده‌ایم تا این رابط را برای ما بنویسید! برنامه‌ای بنویسید که داده‌های شرکت را **بصورت Yaml** دریافت کند، سپس به درخواست‌های از انواع مختلف پاسخ بدهد. برای آشنایی با فرمت *Yaml* می‌توانید به مثال‌های سوال (و البته اینترنت!) مراجعه کنید. دقت کنید که ورودی‌های این سوال حالت خاص و بسیار ساده‌ای از *Yaml* می‌باشد. # ورودی در خط اول ورودی عدد $n$‌ آمده‌است که نمایانگر تعداد داده‌های از نوع کاربر است. سپس این $n$ داده بصورت *Yaml* می‌آیند. پس از آن، در خط بعدی عدد $m$ آمده‌است که نمایانگر تعداد داده‌های از نوع آلبوم است. سپس این $m$ داده بصورت *Yaml* می‌آیند. در این *Yaml*ها، فیلدهای نام کاربری، سن، شهر و لیست آلبوم‌ها برای هر کاربر به همین ترتیب می‌آیند و با کلیدهای زیر مشخص می‌شوند: + `name` + `age` + `city` + `albums` همچنین فیلدهای نام آلبوم، نام خواننده، سبک و تعداد ترک‌های یک آلبوم به همین ترتیب می‌آیند و با کلیدهای زیر مشخص می‌شوند: + `name` + `singer` + `genre` + `tracks` در فیلدهای `age` و `tracks` حتماً یک عدد بین ۱ تا ۳۰ می‌آید و در دیگر فیلدها رشته‌های متشکل از حداکثر ۱۰ کاراکتر از حروف کوچک انگلیسی می‌آید. و فرمت اعداد و رشته‌ها و فواصل، دقیقاً به شکل ورودی‌های نمونه خواهد بود. هر تب نیز با ۲ تا فاصله (*space*) مشخص می‌شود. سپس در خط بعدی عدد $q$ آمده‌ است که نمایانگر تعداد درخواست‌هایی است که برنامه شما باید به آن‌ها پاسخ دهد. سپس در هریک از $q$ سطر بعدی، ابتدا شماره نوع درخواست و سپس توضیح آن می‌آید که به یکی از ۶ شکل زیر است: + 1 `user` `singer` + 2 `user` `genre` + 3 `age` `singer` + 4 `age` `genre` + 5 `city` `singer` + 6 `city` `genre` **دقت کنید که ممکن است هریک از اطلاعات داخل پرسش‌ها (از قبیل نام کاربر، نام خواننده، ...) در ورودی موجود نباشد.** $$1 \le n, m, q \le 100$$ تضمین می‌شود که نام‌های کاربری و نام آلبوم‌ها، متفاوت هستند. همچنین تضمین می‌شود تمامی نام‌های آلبوم‌های خریده شده توسط کاربرها درست هستند و چنین آلبوم‌هایی وجود دارند. همچنین تمامی رشته‌های موجود در داده‌ها از حروف کوچک انگلیسی تشکیل شده‌اند و بین ۱ تا ۱۰ کاراکتر دارند. و تمامی اعداد موجود در داده‌ها بین ۱ تا ۳۰ هستند. تضمین می‌شود که آلبوم‌ها و کاربرهای مختلف، نام‌های مختلف دارند. همچنین هیچیک از کلیدهای توضیحی (مانند `name` و `albums` و ...) بعنوان نام کاربر، آلبوم، خواننده، سبک و یا شهر در ورودی نمی‌آیند. # خروجی به ازای هر درخواست، برنامه‌ی شما باید یک عدد خروجی دهد که برابر با پاسخ آن درخواست است. # مثال ## ورودی نمونه ۱ ``` 1 - name: ali age: 12 city: bushehr albums: - bidad - blaze 2 - name: bidad singer: shajarian genre: classic tracks: 10 - name: blaze singer: ghorbani genre: pop tracks: 9 1 1 ali ghorbani ``` ## خروجی نمونه ۱ ``` 9 ``` ## ورودی نمونه ۲ ``` 2 - name: gholi age: 18 city: tehran albums: - tekunbede - barf - hoyad - name: mehdi age: 20 city: mashhad albums: - eclipse - barf - hoyad 4 - name: eclipse singer: malmsteen genre: classic tracks: 10 - name: barf singer: beeptunes genre: pop tracks: 22 - name: tekunbede singer: beeptunes genre: pop tracks: 14 - name: hoyad singer: hoyad genre: persian tracks: 5 12 1 gholi hoyad 1 gholi beeptunes 2 gholi rock 2 mehdi pop 3 20 beeptunes 4 18 malmsteen 4 19 malmsteen 5 tehran malmsteen 5 mashhad malmsteen 6 tehran pop 6 ghazvin rock 1 mehdi shajarian ``` ## خروجی نمونه ۲ ``` 5 36 0 22 22 0 0 0 10 36 0 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیر از خواب بیدار شده اما هنوز کمی خسته است. او $T$ دقیقه دیگر فرصت استراحت دارد و چون خسته است تصمیم می‌گیرد کمی چرت بزند. هر چرت دارای دو مشخصه $t_i$ و $e_i$ است که به ترتیب مدت زمان چرت و مقدار انرژی دریافتی از چرت را مشخص می‌کند؛ توجه کنید که ممکن است او بعد از یک چرت خسته‌تر باشد یا به عبارت دیگر، $e_i$ صفر و یا حتی منفی باشد! هم‌چنین امیر به ازای هر دقیقه از $T$ دقیقه که چرت نمی‌زند، یک واحد از انرژی‌اش کم می‌شود و در زمان صفر هم، صفر واحد انرژی دارد. امیر می‌خواهد یک $i$ انتخاب کند و به ترتیب چرت‌های $1$ تا $i$ را بزند بطوری که در دقیقه‌ی $T$ همه‌ی چرت‌هایش تمام شده باشد و بیدار باشد؛ حال شما به او بگویید که با این شرایط در زمان $T$، حداکثر چقدر انرژی می‌تواند داشته باشد. توجه کنید که $i$ می‌تواند صفر باشد و به ازای $i$ انتخابی جمع چرت‌ها باید کم‌تر مساوی $T$ باشد. # ورودی خط اول ورودی شامل دو عدد $n$ و $T$ است. سپس در $n$ خط دیگر ورودی، در هر خط به ترتیب دو عدد $t_i$ و $e_i$ می‌آیند. $$1 \le n \le 10^5$$ $$1 \le T \le 10^9$$ $$1 \le t_i \le 10^4$$ $$-10^4 \le e_i \le 10^4$$ # خروجی بیشینه انرژی امیر را در زمان $T$ چاپ کنید. توجه کنید که این عدد ممکن است منفی باشد. # مثال ## ورودی نمونه ۱ ``` 3 5 1 1 2 3 1 -2 ``` ## خروجی نمونه ۱ ``` 2 ``` در این مثال امیر، $i$ را ۲ انتخاب می‌کند و چرت‌های ۱ و ۲ را می‌زند؛ بنابراین بعد از ۳ دقیقه (که هر دو چرتش تمام شده)، ۴ واحد انرژی دارد؛ سپس دو دقیقه چرت نمی‌زند و ۲ واحد انرژی‌اش کم می‌شود؛ بنابراین در نهایت ۲ واحد انرژی دارد. ## ورودی نمونه ۲ ``` 2 10 5 -3 4 -3 ``` ## خروجی نمونه ۲ ``` -7 ``` در این مثال هم $i = 2$ بهترین حالت است و پس از این که امیرمحمد ۹ دقیقه چرت می‌زند ۶- واحد انرژی دارد و پس از یک دقیقه انرژی‌اش ۷- می‌شود.

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا بچه‌ای شلخته و نامنظم است که اتاقش شبیه شهر ارواح است**!** در یکی از روزهای مه‌آلود بهاری، مادر رادزینکا خواست تا اتاق او را جاروبرقی بکشید که ناگهان با انبوه لنگه جوراب‌های پخش و پلای او روبرو شد. مادر که به خشم آمده بود، شروع به جفت‌ کردن جوراب‌های هم‌رنگ کرد و تصمیم گرفت هر جورابی که اضافه آمد را دور بریزد و جوراب‌های جفت‌ شده‌ را در کمد قرار دهد، بلکه اتاق اندکی خلوت شود. از آن‌جایی که جوراب‌های رادزینکا ورزشی است، بر روی هر لنگه یک عدد نوشته شده است.جوراب‌ها به ترتیب با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند. مادر رادزینکا دوست دارد به نحوی جوراب‌ها را جفت کند که چهار شرط زیر (به همین ترتیب اولویت) رعایت شود: + دو لنگه‌ای که با هم جفت می‌شوند، رنگ یکسانی داشته باشند. + تعداد جوراب‌های جفت شده بیشینه شود تا کمترین تعداد جوراب دور ریخته شود. + اگر قرار است $k$ جفت انتخاب کند، آن‌ $k$ جفت را به گونه‌ای انتخاب کند که جمع اعداد موجود بر روی جوراب‌ها کمینه شود (مادر رادزینکا از اعداد بزرگ خوشش نمی‌آید). + در جفت کردن ایده‌آل مادر رادزینکا، با رعایت کامل سه شرط بالا، تلاش می‌شود شماره جوراب‌های جفت شده تا حد امکان به هم نزدیک‌تر باشند. به عبارت دیگر، مجموع اختلاف اعداد جوراب‌های جفت شده کمینه شود (رادزینکا از اختلاف زیاد اعداد جوراب‌هایش ناراحت می‌شود) از آن‌جایی که مادر رادزینکا مشغول تمیز کردن خانه است،‌ زمان کافی برای جفت کردن جوراب‌ها با شرایط دلخواهش را ندارد. به او کمک کنید تا این کار را انجام دهد. # ورودی در خط اول ورودی عدد $n$ آمده است که نشان‌دهنده تعداد لنگه جوراب‌های موجود در اتاق رادزینکا است. در خط دوم $n$ عدد آمده است که $i$ امین عدد نشان‌دهنده رنگ‌ جورابی است که بر روی آن عدد $i$ نوشته شده است. $$1 \le n \le 200$$ رنگ جوراب‌ها عددی بین ۱ تا ۱۰۰ است. # خروجی در اولین خط خروجی عدد $k$ را خروجی دهید که نشان‌دهنده بیشینه تعداد جفت‌هاست. در $i$امین خط از $k$ خط بعدی به ترتیب دو عدد $a$ و $b$ را خروجی دهید که نشان‌دهنده اعداد جوراب‌هایی است که مادر رادزینکا در مرحله $i$ام جفت می‌کند. دقت کنید که $a$ کوچکتر از $b$ باشد. همچنین به‌خاطر وسواس مادر رادزینکا در برقراری نظم و ترتیب، جفت‌ها را طوری خروجی دهید که بر اساس عدد کوچکتر، مرتب شده باشند. یعنی اگر جفت $x$ قبل از جفت $y$ ظاهر شده است، جورابی که در بین چهار لنگه این دو جفت شماره کمینه را دارد، در جفت $x$ باشد. # مثال ## ورودی نمونه ۱ ``` 5 1 2 1 2 3 ``` ## خروجی نمونه ۱ ``` 2 1 3 2 4 ``` ## ورودی نمونه ۲ ``` 8 1 4 1 1 4 1 4 1 ``` ## خروجی نمونه ۲ ``` 3 1 3 2 5 4 6 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- با بوجود آمدن زبان‌های برنامه‌نویسی متنوع بسیار با نام‌های غیر قابل توصیف، "حاج اصغر" نیز تصمیم گرفت برای خود زبانی طراحی کند و آن را "ذله" (یا Zelle) نامید. او نحوه‌ی برنامه‌نویسی با زبانش را به جهانیان ارائه کرد تا همه بتوانند از زبان زیبایش استفاده کنند. هر برنامه به زبان "ذله" به شکل زیر است: + یک برنامه شامل تعدادی "محدوده" یا "scope" است. در ابتدای هر scope یک سطر که شامل آکولاد باز (یا `{`) می‌شود آمده‌است و در انتهای آن یک سطر که شامل آکولاد بسته (یا `}`) می‌شود آمده‌است. یک محدوده می‌تواند شامل تعدادی محدوده شود؛ به این صورت که کل محدوده‌ی داخلی بین شروع و پایان محدوده‌ی خارجی قرار داشته باشد. برای مثال، برنامه‌ی زیر ۳ محدوده دارد که یکی شامل ۲ تای دیگر می‌شود: { { } { } } + در هر محدوده تعدادی متغیر می‌توان تعریف کرد که در آن‌ها می‌توان یک مقدار عددی نگه‌داشت. هر متغیر بصورت زیر تعریف می‌شود: set name = value ; که name برابر نام متغیر است و value یک عبارت است که نمایانگر مقدار اولیه‌ی در این متغیر است. برای مثال: set a = 24 + 18 - 10 ; یک متغیر به‌نام a تعریف می‌کند و مقدار آن‌ را برابر ۳۲ قرار می‌دهد. نام یک متغیر باید رشته‌ای شامل تنها حروف کوچک انگلیسی باشد. همچنین نام یک متغیر نباید برابر set یا print باشد. اگر متغیر در محدوده‌ای تعریف شود، تنها در آن محدوده و تنها در سطر‌های بعد از تعریفش قابل استفاده است. (دقت کنید که اگر محدوده‌ای باشد که این محدوده شاملش شود و پس از تعریف این متغیر شروع شده باشد، این متغیر در آن محدوده نیز تعریف شده‌است. همچنین دقت کنید که وقتی محدوده‌ای که متغیر در آن تعریف‌شده است تمام شود، متغیر در سطر‌های بعدی آن تعریف شده نیست.) می‌توان مقدار یک متغیر را پس از تعریف آن بصورت زیر تغییر داد: name = value ; که name نام متغیری است که باید تغییر کند و value عبارتی‌است که حاصلش مقدار جدید این متغیر است. برای مثال: set a = 2 ; set b = 5 ; a = a - b ; هنگام تعریف یک متغیر، نباید نام متغیر دیگری که در همین محدوده تعریف شده‌است برابر با نام متغیر جدید باشد. اگر یک متغیر در محدوده‌ی دیگری که شامل محدوده‌ی کنونی می‌شود تعریف شده باشد مشکلی ندارد که نام این دو متغیر برابر باشند. در این حالت وقتی که دو متغیر هم‌نام موجود است، هرکجا به متغیری به آن نام اشاره شود متغیری که دیرتر تعریف شده‌است (یعنی در محدوده‌ی کوچک‌تری تعریف شده‌است) در نظر گرفته می‌شود. برای مثال، برنامه‌ی زیر درست نیست: { set a = 5 ; set a = 6 ; } اما برنامه‌ی زیر درست است: { set a = 5 ; { set a = 6 ; } } + دستور print نیز یک عبارت را در خروجی برنامه می‌نویسد. نحوه‌ی کار با این دستور به شکل زیر است: print value ; که value عبارتی‌است که حاصلش باید در یک سطر از خروجی نوشته شود. برای مثال: print a + b - c ; + هر برنامه باید یک scope اصلی داشته باشد که بقیه برنامه درون آن قرار بگیرد و قبل و بعد از این scope هم دستور یا scope دیگری وجود نداشته باشد. + یک عبارت در زبان "ذله" شامل تعدادی عدد/متغیر است که بینشان عملگر جمع یا تفریق به صورت + یا - ، همراه با فاصله آمده است. اعداد داخل یک عبارت همه صحیح و مثبت هستند. + در پایان هر خط دستوری یک کاراکتر ; با فاصله می‌آید. همچنین نباید در عبارت هنگام تعریف یک متغیر از آن و یا متغیری هم‌نام با آن استفاده کرد. حال جهانیان از دیدن این زبان زیبا به وجد آمده‌اند و تعداد زیادی برنامه به زبان "ذله" نوشته‌شده است. اما حاج اصغر حواسش به این موضوع نبود که باید برای این زبان یک کامپایلر نیز بنویسد! حال او این وظیفه را به شما محول کرده است؛ شما باید برنامه‌ای بنویسید که با ورودی گرفتن یک کد که به زبان "ذله" نوشته‌شده، بگوید که آیا مشکلی در این برنامه وجود دارد و اگر وجود نداشت، بگوید گه این برنامه در خروجی چه مقادیری را می‌نویسد. # ورودی ورودی از تعدادی خط تشکیل شده است که برنامه را می‌سازند. می‌توانید فرض کنید برنامه ورودی حداکثر از ۱۰۰ خط تشکیل شده که هر خط شامل یک دستور، آکولاد باز و یا آکولاد بسته است. همچنین ممکن است برای خواناتر شدن در برنامه از کاراکتر های فاصله (space یا tab) اضافه استفاده شده باشد و یا سطری خالی از دستور در برنامه باشد. همچنین می‌توانید فرض کنید در عبارت های داخل برنامه از حداکثر ۱۰ عدد/متغیر استفاده شده است و در طول اجرای برنامه مقدار قدر مطلق هیچ متغیری بیشتر از $10^6$ نمی‌شود. حداکثر طول نام متغیر ها ۱۰ کاراکتر است. # خروجی اگر در برنامه ورودی قواعد زبان برنامه نویسی ذله رعایت نشده بود باید عبارت "Zelle Error" در یک خط چاپ شود و اگرنه مقدار های مربوط به دستور های print باید به ترتیب در خط های جداگانه چاپ شوند. # مثال ## ورودی نمونه ۱ ``` { set a = 3 ; { print a ; set b = a + a + a ; print b - 5 ; } } ``` ## خروجی نمونه ۱ ``` 3 4 ``` ## ورودی نمونه ۲ ``` { set a = 3 ; { print a ; set b = a + a + a ; } print b - 5 ; } ``` ## خروجی نمونه ۲ ``` Zelle Error ``` ## ورودی نمونه ۳ ``` { set a = 3 ; set b = 5 ; print a ; print b ; a = a + b ; b = a - b ; a = a - b ; print a ; print b ; } ``` ## خروجی نمونه ۳ ``` 3 5 5 3 ```