+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پویان یک نوجوان تپل است که تصمیم گرفته است با ورزش شطرنج، وزن خود را کاهش دهد. پویان یک زمین شطرنج و مهره‌های آن را از بزرگان شطرنج قرض گرفت تا به ورزش بپردازد. اما متوجه شد که تعداد مهره‌های شطرنجی که به او داده‌اند درست نیست، تعداد برخی مهره‌ها بیشتر و تعداد برخی کمتر از تعداد لازم است. میدانیم که یک مجموعه مهره‌های شطرنج باید شامل: + یک شاه + یک وزیر + دو رخ + دو فیل + دو اسب + هشت سرباز باشد. پویان میتواند مهره‌هایش را کم یا زیاد بکند تا تعدادشان درست بشود. با ورودی گرفتن تعداد مهره‌هایی که پویان از هر نوع دارد، بگویید پویان از هر نوع چه تعداد باید تهیه یا حذف بکند که مجموعه مهره‌هایش درست بشود. # ورودی در تنها سطر ورودی ۶ عدد آمده است که به ترتیب برابر تعداد شاه‌ها، وزیرها، رخ‌ها، فیل‌ها، اسب‌ها و سرباز‌های مهره‌های پویان است. # خروجی تنها سطر خروجی باید شامل ۶ عدد باشد که برابر تعداد مهره‌هایی از انواع گفته‌شده است که پویان باید تهیه یا حذف بکند، به همان ترتیب ورودی. اگر پویان باید $x$ تا از مهره‌ای تهیه بکند باید عدد $x$ در جایگاه مربوط به آن مهره بیاید و اگر باید $x$ تا از مهره‌ها را حذف بکند باید عدد $-x$ در این جایگاه بیاید. # مثال ## ورودی نمونه ``` 0 2 2 2 3 7 ``` ## خروجی نمونه ``` 1 -1 0 0 -1 1 ```

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پویان یک نوجوان تپل است که تصمیم گرفته است با درست کردن و خوردن معجون، وزن خود را کاهش دهد. پویان دستورالعمل ساخت تعدادی معجون را از بزرگان عرصه‌ی کاهش وزن دریافت کرده و قصد دارد آن‌ها را بسازد. هر معجون از ترکیب تعدادی چاشنی است که هر چاشنی یا یکی از مواد اولیه‌ی آشپزی است و یا نوعی معجون است. (که در صورت معجون بودن دستورالعمل خود را دارد.) برای ساخت یک معجون باید همه‌ی معجون‌های داخل چاشنی‌های آن را در ظرف‌های جدا آماده کرده، سپس یک ظرف خالی جدید برداشته و این معجون‌ها را در آن ریخته و مواد اولیه‌ی آشپزی را نیز اضافه کرده و با هم مخلوط کرد. نمیتوان معجون‌ها را در یکی از ظرف‌های خودشان باهم مخلوط کرد. پس از استفاده از چاشنی موجود در یک ظرف، ظرف خالی شده و میتوانیم از آن برای مخلوط کردن چاشنی‌های دیگر استفاده کنیم. برای مثال فرض کنید A (یک معجون) با ترکیب B (یک معجون) و namak (یک ماده‌اولیه) بوجود می‌آید. باید در ابتدا معجون B را در یک ظرف جدا درست کرد و یک ظرف خالی برداشته و در آن B و namak را قاطی کرده تا A در آن ظرف بوجود بیاید. حال ظرفی که قبل شامل B‌ بوده خالی است و میتوان از آن استفاده دیگر کرد! واضح است که تعداد ظرف‌های مورد نیاز پویان برای ساخت معجون، به ترتیب ساخت معجون‌های قبلی‌اش بستگی دارد. با ورودی گرفتن دستورالعمل، بگویید در ترتیبی که در آن از کمترین تعداد ظرف استفاده میشود، این کمترین تعداد ظرف چقدر است. **به ورودی‌های مثال‌ و توضیحاتشان توجه کنید!** # ورودی در سطر اول ورودی عدد $n$ آمده است که برابر تعداد معجون‌ها است. در $i$مین سطر از هریک از $n$ سطر بعدی ابتدا نام $i$مین معجون و سپس دستورالعمل آن آمده‌ است. در ابتدای دستورالعمل عدد $k_i$ آمده که نمایانگر تعداد چاشنی‌های معجون $i$م است و پس از آن نام آن $k_i$ چاشنی آمده است. نام معجون‌ها بصورت کلمات حداکثر ۲۰ کاراکتری از حروف بزرگ انگلیسی در ورودی آمده‌اند. نام مواد اولیه آشپزی بصورت کلمات حداکثر ۲۰ کاراکتری از حروف کوچک انگلیسی در ورودی آمده‌اند. معجون‌ها اسامی مختلفی دارند و تضمین میشود هر معجونی در دستورالعمل ساخت دقیقن یک معجون دیگر استفاده میشود بجز معجون نهایی که در دستورالعمل ساخت هیچ معجونی استفاده نمیشود. همچنین میتوان همه‌ی معجون‌ها را ساخت؛ یعنی دنباله‌ی وابستگی از یک معجون به خودش وجود ندارد. تنها یک معجون نهایی وجود دارد که از آن در ساخت معجون‌های دیگر استفاده نمیشود. $$2 \le k_i \le 10$$ $$1 \le n \le 1000$$ # خروجی تنها سطر خروجی باید شامل تنها یک عدد باشد که برابر با کمترین تعداد ظرف است که پویان میتواند با استفاده از آن معجون‌ را درست کند. # مثال ## ورودی نمونه ۱ ``` 3 SOUP 3 CHIZ namak aab SABZI 2 piaz gharch CHIZ 2 morgh SABZI ``` ## خروجی نمونه ۱ ``` 2 ``` در این نمونه برای ساخت SOUP در ۲ ظرف، چنین میکنیم: ۱. با ترکیب piaz و gharch در ظرف شماره ۱، SABZI را میسازیم. ۲. با ترکیب morgh و SABZI در ظرف شماره ۲، CHIZ را میسازیم. (اکنون ظرف شماره‌ی ۱ با برداشتن SABZI از داخلش، خالی شد.) ۳. با ترکیب CHIZ و namak و aab‌ در ظرف شماره ۱،‌ SOUP را میسازیم. ## ورودی نمونه ۲ ``` 5 MILKSHAKE 4 bastani shir TAM MIVE MIVE 5 golabi moz havij khiar anbe TAM 2 CHIZ CHOCOLATE CHIZ 2 goody darchin CHOCOLATE 2 sharbat cocoa ``` ## خروجی نمونه ۲ ``` 3 ``` برای ساخت MILKSHAKE دلخواهمان،‌ حق انتخاب داریم که اول MIVE را درست کنیم و یا اول TAM‌ را، که پس از آن با ترکیبشان با shir و bastabi یک MILKSHAKE بسازیم. اگر اول MIVE را درست کنیم، به ۴ ظرف نیاز پیدا خواهیم کرد ولی اگر اول TAM را بسازیم و سپس MIVE را، با ۳ ظرف میتوانیم به هدف خود برسیم.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پویان یک نوجوان تپل است که تصمیم گرفته است با سخت کار کردن در مغازه تیله فروشی، وزن خود را کاهش دهد. مغازه‌ی ای که پویان در آن کار میکند تیله‌ها را در $n$ اندازه مختلف عرضه میکند و هر تیله میتواند دارای *پر* باشد یا نباشد. پس در این مغازه میتوان $2n$ نوع تیله مختلف یافت. مغازه‌ی پویان، $m$ مشتری ثابت دارد که هر روز به مغازه سر میزنند و به تیله‌ها نگاه میکنند. هریک از این مشتری‌ها یکسری از انواع تیله‌ها را دوست میدارد و اگر هیچیک از تیله‌های موردعلاقه‌ی او در مغازه یافت نشود، او ناراحت از مغازه به بیرون میرود. همچنین هریک از این مشتری‌ها اگر تیله‌ی پردار از یک اندازه‌ای را دوست داشته باشد، هیچگاه تیله پردار از اندازه‌ی دیگری را دوست نخواهد داشت. (یعنی بین تیله‌های مورد علاقه‌ی هر مشتری حداکثر یکیشان پردار است.) پویان میخواهد از هر اندازه‌ی تیله تنها یک نوع (پردار و یا بدون پر) را انتخاب کند و تنها تولید آن را ادامه دهد، بدون اینکه هیچیک از این مشتری‌های ثابت را برنجاند. یعنی باید حداقل یک تیله مورد علاقه‌ی هریک از این مشتری‌ها در فهرست تولید وجود داشته باشد. در ضمن، پویان میخواهد که تعداد تیله‌های پردار داخل فهرست تولید کمینه شود. با ورودی گرفتن فهرست علاقه‌ی مشتریان اگر پویان میتواند با شرایط گفته شده و بدون ناراحت کردن مشتری‌هایش تولید تیله‌ها را ادامه دهد، حالتی از فهرست تولید را خروجی دهید که تعداد تیله‌های پردار داخل آن‌ها کمینه است. # ورودی در سطر اول ورودی عدد $n$ آمده است که نمایانگر تعداد اندازه‌های مختلف برای تیله‌‌های مغازه‌ی پویان است. در سطر دوم ورودی عدد $m$ آمده است که نمایانگر تعداد مشتری‌های ثابت مغازه‌ی پویان است. سپس در $i$مین سطر از هریک از $m$ سطر بعدی، فهرست انواع تیله‌هایی که مشتری ثابت $i$م دوست میدارد توصیف میشود. در ابتدای سطر عدد $k_i$ آمده که برابر تعداد انواع تیله‌هاییست که این مشتری دوست میدارد. سپس $k_i$ نوع تیله بصورت دو عدد *اندازه* و *پردار بودن* توصیف شده اند. اندازه عددی طبیعی و حداکثر برابر $n$ است و *پردار بودن* اگر برابر ۱ بود، یعنی این مشتری تیله‌ی پردار از این اندازه را دوست میدارد و اگر برابر ۰ بود، یعنی تیله بی‌پر از این اندازه را دوست میدارد. (ممکن است مشتری از یک اندازه هم تیله‌ی پردار و هم تیله‌ی بی‌پر را دوست داشته باشد. این در دو توصیف مختلف در این سطر، گفته میشود. یکی برای تیله‌ی پردار با این اندازه و دیگری برای توصیف تیله‌ی بی‌پر با این اندازه.) تضمین میشود هر مشتری حداکثر یک نوع تیله‌ی پردار را دوست دارد و هیچگاه یک نوع تیله دوبار در فهرست علایق یک مشتری ظاهر نمیشود. $$1 \le n, m \le 2000$$ $$1 \le k_i \le 3000$$ $$\sum_{i = 1}^m k_i \le 3000$$ # خروجی اگر نمیتوان بدون ناراحت کردن مشتری‌های ثابت فهرست تیله‌ها را انتخاب کرد، خروجی باید تنها شامل کلمه‌ی IMPOSSIBLE شود. اگر میتوان از هر اندازه یک نوع پردار یا بی‌پر انتخاب کرد بطوری که مشتری‌ها ناراحت نشوند، یک حالت از این انتخاب کردن‌ها را خروجی دهید که تعداد تیله‌های پردارش کمینه است. تنها سطر خروجی باید شامل $n$ عدد باشد که هرکدام برابر ۰ یا ۱ است. اگر $i$مین عدد برابر ۱ بود یعنی تیله‌ی با اندازه‌ی $i$ در فهرست داده شده از این به بعد پردار تولید خواهد شد و اگر برابر ۰ بود یعنی تیله‌ی با اندازه‌ی $i$ در فهرست داده شده از این به بعد بدون پر تولید خواهد شد. # مثال ## ورودی نمونه ۱ ``` 1 2 1 1 0 1 1 1 ``` ## خروجی نمونه ۱ ``` IMPOSSIBLE ``` ## ورودی نمونه ۲ ``` 5 3 1 1 1 2 1 0 2 0 1 5 0 ``` ## خروجی نمونه ۲ ``` 1 0 0 0 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پویان یک نوجوان تپل است که تصمیم گرفته است بوسیله‌ی دوچرخه‌ سواری، وزن خود را کاهش دهد. پویان در حیاط بزرگ خانه‌شان ایستاده است. میتوان حیاط آن‌ها را از بالا مانند یک صفحه دوبعدی نامتناهی مختصات دکارتی تصور کرد. پویان در ابتدا روی نقطه‌ی $(0, 0)$ حیاطشان ایستاده و میخواهد دوچرخه‌ سواری را شروع کند. دوچرخه‌ی او او میتواند با بردار $(x_1, y_1)$ یا $(x_2, y_2)$ ویا قرینه‌ی آن‌ها حرکت کند؛ یعنی از نقطه‌ی $(x, y)$ میتواند به نقاط $(x + x_1, y + y_1)$ یا $(x - x_1, y - y_1)$ یا $(x + x_2, y + y_2)$ یا $(x - x_2, y - y_2)$ برود. پویان نمیخواهد دوچرخه‌ سواری اش در نقطه‌ی $(0, 0)$ به پایان برسد. (بخاطر حرف مردم!) ولی او میخواهد نقطه‌ی پایان دوچرخه‌ سواری اش تا جای ممکن به نقطه‌ی $(0, 0)$ نزدیک باشد. با ورودی گرفتن بردار‌های $(x_1, y_1)$ و $(x_2, y_2)$، کمترین فاصله‌ای که نقطه‌ی پایان پویان میتواند از $(0, 0)$ داشته باشد را خروجی دهید. فاصله‌ را منهتنی در نظر میگیریم؛ یعنی فاصله بین دو نقطه‌ی $(x, y)$ و $(x', y')$ برابر $|x - x'| + |y - y'|$ است. # ورودی در تنها سطر ورودی چهار عدد صحیح $x_1$ و $y_1$ و $x_2$ و $y_2$ آمده‌اند. تضمین میشود هیچیک از این بردار ها برابر $(0, 0)$ نیستند. $$-100\ 000 \le x_1, y_1, x_2, y_2 \le 100\ 000$$ # خروجی تنها سطر خروجی باید شامل تنها یک عدد باشد که برابر با کمترین فاصله‌ی ممکن برای نقطه‌ی پایان دوچرخه‌ سواری با مبدأ مختصات است. # مثال ## ورودی نمونه ``` 13 4 17 5 ``` ## خروجی نمونه ``` 2 ```