+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جو شرکت رهنما خیلی صمیمی است؛ بدین منظور در این شرکت همه، از پیر تا جوان، همدیگر را به اسم کوچک صدا می‌زنند. در پی استخدامات بی‌رویه واحد منابع انسانی، به تازگی رهنما با مشکلی اساسی تشابه اسمی مواجه شده‌است. متاسفانه وقتی کسی در شرکت صدا می‌زند «باقر» از آنجایی که تعداد زیادی «باقر» در شرکت مشغول کار‌ هستند، نمی‌توان فهمید که منظورش کدام «باقر» است. بدین منظور مدیر منابع انسانی تصمیم می‌گیرد که برای هر شخص دقیقا یک کلاه‌رنگی بخرد به طوری که همه کسانی که اسم کوچک مشابهی دارند کلاهی با رنگ متفاوت داشته باشند. با اینکار تا حدودی مشکل حل می‌شود؛ بدین صورت که از این به بعد کارکنان شرکت به جای اینکه اسم‌کوچک شخص را صدا بزنند، از ترکیب «اسم کوچک + رنگ» استفاده می‌کنند. مثلا وقتی می‌گوییم «باقر صورتی» می‌دانیم تنها یک «باقر صورتی» داریم و دیگر ابهامی وجود ندارد. حال مدیر منابع انسانی رهنما از شما خواسته تا با گرفتن نام افراد، حداقل تعداد رنگ‌های مختلف لازم را بدست آورید تا به هر فرد بتوان ترکیب «اسم کوچک + رنگ» یکتایی را متناظر کرد. **برای فهم بهتر به نمونه‌ها و توضیحشان دقت کنید.**  # ورودی در خط اول $n$ که تعداد کارکنان شرکت رهنما است به شما داده می‌شود. در $n$ خط بعدی در هر خط دو رشته متشکل از حروف کوچک الفبای انگلیسی که طول هر یک حداکثر ۱۵ حرف است به شما داده می‌شود که با فاصله از هم جدا شده و به ترتیب، نام و نام خانوادگی کارمند $i$ ام را نشان می‌دهند. **تضمین می‌شود که هیچ دو نفری در رهنما وجود ندارند که نام و نام خانوادگی‌شان دقیقا یکی باشد.** $$ 1 \le n \le 100$$ # خروجی در تنها خط خروجی حداقل تعداد رنگ‌های مختلف لازم را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 bagher bagherian bagher naderian nader bagherian nader naderian steve jobs ``` ## خروجی نمونه ۱ ``` 2 ``` توضیح نمونه ۱: با دو رنگ مختلف می‌توان مشکل تشابه اسمی را حل کرد به این‌صورت که به دو باقر و دو نادر کلاه ناهمرنگ بدهیم. ## ورودی نمونه ۲ ``` 5 bagher bagherian bagher borna bagher naderian alfred nobel alfred hitchcock ``` ## خروجی نمونه ۲ ``` 3 ``` ## ورودی نمونه ۳ ``` 3 freddie mercury brian may roger taylor ``` ## خروجی نمونه ۳ ``` 1 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا تصمیم گرفت که دیوار رنگ و رو رفته‌ی شرکت را دوباره رنگ کند، قبل از اینکه نقاش کارش را شروع کند، بچه‌ها به این نتیجه رسیدند که می‌توانند قبل از اینکه نقاش دیوار را دوباره سفید کند روی آن نقاشی کنند! از این رو مهدی در حالی که این شعر را میخواند روی دیوار یک مربع کشید: یه خونه می‌کشم... بعد از کشیدن مربع، پارسا تصمیم گرفت که یک لیوان را به سمت مربع پرت کند؛ او فکر می‌کرد که توی تغییر دکوراسیون شرکت قرار است شرکت را با وسایلش خراب کنند و طرحی نو دراندازند!! برای همین به نظرش آمد که در این وضعیت خراب کردن هر چیزی به شرکت کمک می‌کند.(او حتی این کار را جزو ساعت کاری‌اش هم حساب می‌کرد!) علی‌رقم هشدار‌های صاحب لیوان، پارسا این کار را کرد و دقیقاً قبل از اینکه لیوان به دیوار برسد و بترکد، نقاش رنگ سفید را روی دیوار ریخت تا شروع به رنگ زدن کند که این کار باعث پاک شدن مربع مهدی شد. حالا مهدی جای مربع و پارسا نقطه‌ی ترکیدن لیوان را می‌داند ولی نمی‌دانند که لیوان داخل یا روی مربع ترکید یا بیرون آن؛ چرا که اگر داخل یا روی مربع ترکیده باشد، مهدی وگرنه پارسا باید خرده‌لیوان‌ها را جمع کند! حال شما با گرفتن اطلاعات از این دو، بازنده را مشخص کنید. # ورودی در سطر اول ورودی دو عدد صحیح $x$ و $y$ می‌آید که نمایانگر مختصات گوشه‌ی بالا چپ مربع می‌باشد. در سطر دوم یک عدد صحیح $r$ می‌آید که نمایانگر طول ضلع مربع می‌باشد. در سطر سوم دو عدد صحیح $dx$ و $dy$ می‌آید که نمایانگر مختصات جایی است که لیوان ترکیده است. $$ -100 \le x, y, dx, dy \le 100 $$ $$ 1 \le r \le 1000 $$ دقت کنید که مختصات دکارتی می‌باشد؛ یعنی زمانی لیوان داخل یا روی مربع است که شروط زیر برقرار باشد: $$ x \le dx \le x + r $$ $$ y - r \le dy \le y $$ # خروجی در یک سطر کسی که باید خرده‌لیوان‌ها را جمع کند چاپ کنید. اگر این شخص پارسا بود "Parsa" و اگر مهدی بود "Mahdi" چاپ کنید. . # مثال ## ورودی نمونه ۱ ``` 0 5 5 0 0 ``` ## خروجی نمونه ۱ ``` Mahdi ``` ## ورودی نمونه ۲ ``` 0 5 5 5 6 ``` ## خروجی نمونه ۲ ``` Parsa ``` ## ورودی نمونه ۳ ``` 0 5 5 -5 3 ``` ## خروجی نمونه ۳ ``` Parsa ``` ## ورودی نمونه ۴ ``` 0 5 5 3 3 ``` ## خروجی نمونه ۴ ``` Mahdi ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پگاه خود را به عنوان هم‌سفر مینو معرفی کرد. حال آن‌ها می‌خواهند با قطار گشتِ محشر را آغاز کنند. قطار آن‌ها $n$ واگن دارد که به ازای هر $1 \leq i \leq n$ دقیقا یکی از واگن‌ها $i$ کوپه دارد. کوپه‌های قطار به ترتیب از چپ به راست با $1$ تا $\frac{n \times (n+1)}{2} $ شماره‌گذاری شده‌اند. عدد یک واگن برابر شماره‌ی چپ ترین کوپه‌ی آن واگن است. می‌دانیم واگن‌ها به ترتیبی بهم متصل شده‌اند که تعداد واگن‌هایی که عدد آن‌ها فرد است، بیشینه می‌باشد. چینش واگن‌های این قطار چگونه است؟ # ورودی تنها ورودی عدد $n$ تعداد واگن‌های قطار است. $$ 1 \leq n \leq 100\ 000 $$ # خروجی در خروجی $n$ عدد چاپ کنید که تعداد کوپه‌های هر واگن از چپ به راست است. اگر چند چینشِ خوب برای واگن‌ها وجود داشت یکی از آن‌ها را به دل‌خواه خروجی دهید. # مثال ## ورودی نمونه ``` 5 ``` ## خروجی نمونه ``` 2 1 3 4 5 ``` **توضیح نمونه:** عدد واگن‌ها در چینش ۵ ۴ ۳ ۱ ۲ به ترتیب ۱۱ ۷ ۴ ۳ ۱ است و بین همه‌ی چینش‌های مختلف ‌‌‌‌$n$ واگن بیشینه‌ی تعداد واگن‌هایی که عدد آن‌ها فرد است‌ ‌۴ می‌باشد.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، دیگر حوصله اعدادی که بیشتر از یک رقم دارند را ندارد. به همین خاطر به هر عدد چند رقمی که بر بخورد آن را به شیوه خاص خودش تبدیل به یک عدد تک رقمی می‌کند. به این شکل که عدد مورد نظر را با عدد حاصل از مجموع ارقام آن جایگزین می‌کند و به یک عدد جدید می‌رسد. سپس همین کار را با عدد جدید انجام می‌دهد و تا جایی که به یک عدد تک‌رقمی برسد به این کار ادامه می‌دهد. بعد از مدتی مهدی متوجه شد که با این کار نه تنها راحت تر نشده است، بلکه بیشتر درگیر اعداد شده است. در نتیجه از شما خواسته است در یک رقمی کردن عددها به او کمک کنید.  # ورودی در تنها سطر ورودی یک عدد $n$ می‌آید که نشان دهنده عددیست که باید آن‌ را تک رقمی کنید. $$ 1 \le n \le 10 ^{18} $$ # خروجی در تنها خط خروجی باید عدد تک‌رقمی حاصل از تبدیل $n$ به یک عدد تک‌رقمی طبق روش مهدی چاپ شود. # مثال ## ورودی نمونه ۱ ``` 14 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 123456 ``` ## خروجی نمونه ۲ ``` 3 ``` در مرحله اول عدد 123456 تبدیل به عدد 6 + 5 + 4 + 3 + 2 + 1 = 21 می‌شود. در مرحله دوم عدد 21 تبدیل به عدد 1 + 2 = 3 می‌شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** اخیرا آقای ماهر دستگاهی اختراع کرده که طبق ادّعایش می‌تواند زمین‌های ناهموار را هموار کند. اگر ادّعای او درست باشد، اختراع وی، عصر جدیدی را در صنعت صاف‌سازی رقم خواهد زد. حال بزرگان این صنعت جمع شده‌اند تا ببیند ادّعای آقای ماهر درست است یا نه! آقای ماهر برای این که درست بودن دستگاهش را به دیگران ثابت کند، می‌خواهد یک کوهستان را با استفاده از دستگاهش هموار کند. کوهستانی که او برای این کار انتخاب کرده است، به شکل یک مستطیل $n \times m$ است. یعنی کوه‌ها در $n$ سطر قرار دارند و هر سطر شامل $m$ کوه است. (کوه‌های هر سطر و هر ستون در یک خط قرار گرفته‌اند) هر کوه ارتفاعی صحیح و نامنفی نیز دارد؛ ارتفاع کوه $j$ام از سطر $i$ام کوهستان را با $A_{i, j}$ نشان می‌دهیم. دستگاه آقای ماهر در هر مرحله ۴ ورودی می‌گیرد و قسمتی از کوهستان را طبق آن ۴ ورودی هموارتر می‌کند. ورودی‌هایی که دستگاه می‌گیرد در یکی از دو قالب زیر هستند: 1. R $l$ $r$ $k$ 2. C $l$ $r$ $k$ در حالت اوّل، ارتفاع هر کوهی که در یکی از سطرهای $l$ تا $r$ (شامل این دو سطر) باشد، تقسیم بر $k$ خواهد شد($1\leq l \leq r \leq n$). در حالت دوم نیز همین اتّفاق برای هر کوهی که در یکی از ستون‌های $l$ تا $r$ (شامل این دو ستون) وجود دارد می‌افتد($1 \leq l \leq r \leq m$). چنان چه ارتفاع جدید هر کوه عددی ناصحیح باشد، بر اثر عوامل طبیعی از ارتفاع کوه آن قدر کاسته می‌شود تا به اوّلین عدد صحیح کوچکتر از خودش برسد! مثلن اگر ارتفاع کوهی $9$ باشد و عملیاتی با $k=4$ روی آن اعمال شود، ارتفاع آن ابتدا برابر $2.25$ می‌شود و سپس تبدیل به $2$ می‌شود. امّا اگر عملیاتی به ازای $k=3$ روی آن اعمال شود،‌ ارتفاعش برابر $3$ می‌شود. آقای ماهر در زمینه‌ی محاسبات ماهر نیست؛ لذا ارتفاع کوه‌های کوهستان و عملیاتی که قرار است با دستگاه انجام دهد را به شما می‌گوید؛ در ازای این داده‌ها نیز می‌خواهد ارتفاع نهایی کوه‌ها را در صورتی که دستگاه درست کار کند، به او بگویید. # ورودی در سطر اوّل ورودی دو عدد $n$ و $m$ می‌آیند. در هر یک از $n$ سطر بعد، $m$ عدد آمده است. عدد $j$ام در $i$امین سطر برابر $A_{i, j}$ است. سپس در یک خط عدد $q$ می‌آید که تعداد درخواست‌هاست. در هر یک از $q$ سطر بعد، یکی از ورودی‌های سوال در قالبی که گفته شد قرار دارد. $$1 \leq n, m \leq 1\ 000$$ $$1 \leq q \leq 10\ 000$$ $$1 \leq k, A_{i, j} \leq 1\ 000\ 000\ 000$$ # خروجی در خروجی ارتفاع نهایی کوه‌ها را چاپ کنید. خروجی شما باید از $n$ سطر تشکیل شده باشد که هر کدام از آن‌ها شامل $m$ عدد هستند. .عدد $j$ام از سطر $i$ام برابر با ارتفاع نهایی کوه $j$ام از سطر $i$ام کوهستان خواهد بود. # مثال ## ورودی نمونه ۱ ``` 2 3 1 2 3 4 5 6 1 C 2 3 2 ``` ## خروجی نمونه ۱ ``` 1 1 1 4 2 3 ``` ## ورودی نمونه ۲ ``` 3 3 10 20 3 15 1000 60 16 10 20 4 R 2 3 4 C 1 2 2 R 1 2 3 R 2 2 5 ``` ## خروجی نمونه ۲ ``` 1 3 1 0 8 1 2 1 5 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بازی $minesweeper$ به این صورت است که از یک جدول $m \times n$ ساخته شده است که بعضی از خانه‌های آن بمب هستند و سایر خانه‌ها تعداد بمب‌هایی را که در ۸ خانه مجاور آن‌ها قرار دارد، نشان‌می‌دهند. در این سوال خانه‌های حاوی بمب به شما داده می‌شود و برنامه‌ی شما باید جدول را چاپ کند. # ورودی در خط اول ورودی دو عدد $n$ و $m$ داده میشود که به ترتیب نشان دهنده‌ی تعداد سطر و ستون‌های جدول است. سپس در خط بعد یک عدد $k$ که تعداد بمب‌های واقع در جدول را نشان می‌دهد. در نهایت در هر یک از $k$ خط بعدی در هر خط یک زوج عدد که مکان بمب‌ها را نشان می‌دهند به عنوان ورودی به برنامه داده میشوند. در هر زوج ابتدا شماره سطر و سپس ستون مربوطه نمایش داده می‌شود؛ جدول را طوری فرض کنید که ستون‌های آن از چپ به راست با اعداد ۱ تا $m$ و سطرهای آن از بالا به پایین با اعداد طبیعی ۱ تا $n$ شماره‌گذاری شده‌اند. $$ 1 \le m,n \le 100 $$ $$1 \le k \le n \times m$$ # خروجی برنامه باید در خروجی یک جدول $m \times n$ را چاپ کند. به این صورت که به ازای بمب‌ها نماد `*` و برای سایر خانه‌های جدول نیز عدد متناظر با آن را چاپ کنید. بین هر دو عنصر متوالی در یک سطر، یک فاصله ($space$) چاپ‌کنید که آن‌ها را از هم جدا کند. # مثال ## ورودی نمونه ``` 4 3 5 1 1 4 2 1 3 3 2 4 3 ``` ## خروجی نمونه ``` * 2 * 2 3 2 2 * 3 2 * * ```