ماشین محاسبه‌گر🔗

time limit per test: 0.5 seconds

memory limit per test: 50 megabytes

اولین ماشین‌های محاسبه‌گر تنها قادر به انجام عملیات‌های جمع و تفریق بودند. تاجران آن زمان که اصلا حوصله جمع و تفریق نداشتند ترجیح میدادند محاسبات خود را برای این ماشین ارسال کنند. تاجران محاسبات خود را بر روی کارت‌های مخصوصی می‌نوشتند و آن را به ماشین میدادند. پس از مدت کوتاهی حاصل عبارت بر روی کارت دیگری چاپ می‌شد. تاجران اصفهانی که به هوش و ذکاوت فراوان معروف بودند برای آنکه بتوانند بیش‌ترین بهره را از کارت‌ها ببرند تصمیم گرفتند پرانتز‌های موجود در عبارت را که در نتیجه نهایی تأثیری ندارند از عبارت حذف کنند. آنها از شما کمک درخواست کرده‌اند که این کار را برای آنها انجام دهید.

برای ساده سازی فرض‌ کنید به جای اعداد و ارقام موجود در عبارات حروف بزرگ انگلیسی وجود دارند.

ورودی🔗

ورودی شامل یک خط می‌باشد که عبارت در آن نوشته شده است. در عبارت ممکن است فضاهای خالی (white space) وجود داشته باشند. طول ورودی حداکثر شامل ۲۵۵ کاراکتر است.

خروجی🔗

خروجی عبارتی است که هیچگونه پرانتز اضافی و فضای خالی در آن وجود ندارد. توجه کنید که ترتیب عملوند‌ها و عملگر‌ها در ورودی و خروجی باید یکسان باشد.

مثال ۱🔗

ورودی

(A-B+C)-(A+(B – C))-(C-(D-E))

خروجی

A-B+C-(A+B-C)-(C-(D-E))

مثال ۲🔗

ورودی

((A) - (  (B)))

خروجی

A-B

رشته ی دوست داشتنی🔗

time limit per test: 1 seconds

memory limit per test: 64 megabytes

مردم شهر استرینگ آباد علاقه ی زیادی به بازی با رشته های مختلف دارند. آن ها برای رشته هایی از مدل های خاص اسم های خاص میگذارند. برای مثال به رشته هایی که با حرف a شروع میشوند ، رشته های کوچولو میگویند. از جمله رشته های معروفی که به چشم میخورد و بسیار مورد علاقه ی مردم است ، رشته ی دوست داشتنی نام دارد. به رشته ای دوست داشتنی گفته میشود که از دو طرف یکسان خوانده شود مانند aba یا cnnc. حال آن ها میخواهند با یک سری عملیات رشته های مختلف را با کمترین هزینه به یک رشته ی دوست داشتنی تبدیل کنند. 2 عمل مجاز وجود دارد برای تغییر رشته ها:

۱. جابجایی دو حرف از رشته که هزینه ای در بر نخواهد داشت.

۲. تغییر دادن یک حرف از رشته به حرف دیگر که هزینه ای برابر 1 واحد پول کالین خواهد داشت.

حال از شما خواسته شده رشته ای دوست داشتنی ارائه دهید که با کمترین هزینه از رشته ی ورودی به دست می آید.

ورودی🔗

در تنها خط ورودی یک رشته از حروف کوچک انگلیسی با طول کم تر از $10^5$ داده شده است

خروجی🔗

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

مثال🔗

ورودی

abc

خروجی

aba

خاک برداری🔗

time limit per test: 2 seconds

memory limit per test: 100 megabytes

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

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

فرض کنید، گلدان‌ها با شماره‌های ۱ تا $N$ که $1 \leq N \leq 100$ به ترتیب در یک سطر قرار گرفته باشند و مقدار اولیه خاک هر گلدان را به ترتیب $A_i$ می‌نامیم. هم چینن مقدار خاک جدید مورد نیاز هر گلدان را به ترتیب $B_i$ می‌نامیم. فرض کنید خاک موجود در گلدان‌ها در طی این چند سال تغییری نکرده باشد و همه $A_i$ و $B_i$ها در بازه صفر تا ۱۰ باشند.

می‌دانیم به هر یک از سه طریق زیر می‌توان مقدار خاک یک گلدان را تغییر داد.

• می‌تواند ۱ واحد خاک بخرد و آن را در هریک ار گلدان‌ها که بخواهد بریزد. هزینه این عمل به طور ثابت برابر $X$ است.

• می‌تواند ۱ واحد از خاک یک گلدان دلخواه را با هزینه ثابت $Y$ از گلدان مورد نظر برداشته و دور بریزد.

• می‌تواند یک واحد خاک را از گلدان $i$ به گلدان $j$ منتقل کند. هزینه این عمل برابر $Z \times |i-j|$ خواهد بود.

می‌خواهیم خاک هر گلدان مقدار مورد نیاز جدید شود. حداقل هزینه مورد نیاز برای انجام این کار با توجه به مقادیر ورودی چقدر است؟

ورودی🔗

در خط اول ورودی ۴ عدد $N, X, Y, Z$ می‌آیندکه با یک فاصله از هم جدا شده‌اند.

$1 \leq X,Y,Z \leq 1000$

در خط‌های $2, ..., N+1$ در هر خط دو عدد می‌آید به طوری که در خط $i+1$ام، به ترتیب دو عدد $A_i$ و $B_i$ می‌آیند که با یک فاصله از هم جدا شده‌اند.

خروجی🔗

در تنها سطر خروجی حداقل هزینه‌ای که با آن می‌توان به حالت مورد نظر رسید را چاپ کنید.

مثال🔗

ورودی نمونه

4 10 200 1
1 4
2 3
3 2
4 0

خروجی نمونه

210

رکورد بیشترین پرواز🔗

time limit per test: 3 seconds

memory limit per test: 128 megabytes

سینا می‌خواهد رکورد بیشترین تعداد پرواز با هواپیما را بشکند. او می‌خواهد در طول $k$ روز، هر روز از یک شهر به شهر دیگر پرواز کند و در نهایت در شهری که نمایندگی گینس در آن‌جا حضور دارد، رکورد خود را به ثبت برساند. مشکلی که سینا با آن برخورد کرده کمبود بودجه است. بنابراین او می‌خواهد با صرف کمترین هزینه این رکورد را به ثبت برساند.

روش کار سینا به این صورت است که در روز اول از بین شهرهایی که از شهر ۱ به آن‌ها پروازی وجود دارد، شهری مانند $a$ را انتخاب کرده و به آن شهر می‌رود. سپس در روز دوم از شهر $a$ پروازی را به مقصد شهر $b$ انتخاب می‌کند و این کار ادامه پیدا می‌کند تا در نهایت در روز $k$ام به شهر مقصد که نمایندگی گینس در آن‌جا است، یعنی شهر $n$ام برسد. مشکل دیگری که سینا دارد این است که قیمت پرواز از شهر $x$ به شهر $y$ در روزهای مختلف ممکن است متفاوت باشد، اما یک دنباله متناوب است. بنابراین اگر دوره تناوب این دنباله برای پرواز از $x$ به $y$ برابر $d$ باشد، قیمت روز $d+1$ام با روز اول برابر است و به همین ترتیب برای سایر روزها. حال شما باید به سینا کمک کنید تا برنامه سفرش را با کمترین هزینه پیدا کند.

ورودی🔗

ورودی شامل تعدادی مورد تست است. خط اول هر مورد تست، به ترتیب مقادیر $n$ و $k$ ( $2 \le n \le 10$ و $1 \le k \le 1000$ ) داده می‌شود. در ادامه در $n(n-1)$ خط بعدی برنامه پروازها از شهری به شهر دیگر داده شده است. $n-1$ خط اول برنامه پرواز از مبدأ شهر ۱ به مقصد شهرهای ۲ تا $n$، $n-1$ خط بعدی برنامه پرواز از شهر ۲ به شهرهای ۱ تا $n$ بجز ۱ و .... هر خط برنامه پرواز شامل عدد $d$ (دوره تناوب دنباله قیمت پرواز از مبدأ به مقصد) و $d$ عدد صحیح نامنفی که قیمت بلیت هواپیما در روز اول تا $d$ام است. قیمت ۰ به معنای آن است که در این روز پروازی از مبدأ به مقصد وجود ندارد. ورودی با مقدار ۰ برای $n$ و $k$ خاتمه می‌یابد.

خروجی🔗

به ازای هر مورد تست، در خروجی کمترین هزینه برای انجام این سفر را در یک خط چاپ کنید. در صورتی که انجام این سفر ممکن نباشد، عبارت No Solution را چاپ کنید.

مثال🔗

ورودی

3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 700
1 80
0 0

خروجی

460
No Solution

کارخانه شکلات سازی🔗

time limit per test: 2 seconds

memory limit per test: 64 megabytes

در کشور "شکلاتسان" کارخانه‌های شکلات سازی زیادی وجود دارد. هر کارخانه تعدادی دستگاه شکلات سازی دارد که هر کدام در هر دقیقه $r$ شکلات از نوعی که برای دستگاه تعریف شده است، تولید می‏کند. دولت شکلاتسان برای متمرکز کردن تولید شکلات‌ها می خواهد یک کارخانه شکلات سازی بزرگ تاسیس کند که:

۱. هیچ دو دستگاه شکلات ساز برای یک نوع شکلات نباشند.

۲. بیشترین تولید شکلات در دقیقه را داشته باشد.

دولت از شما که برنامه نویس خفن(!)ی هستید خواسته تا تولیدات کل در دقیقه کارخانه‌ای را که می‌خواهد تاسیس کند حساب کنید.

ورودی🔗

در خط اول ورودی عدد طبیعی $n \leq10^3$ تعداد کارخانه‌های موجود می‌آید. سپس مشخصات هر کدام از این کارخانه‌ها به این صورت می‌آید که ابتدا یک عدد طبیعی $m \leq10^3$ تعداد دستگاه‌های این کارخانه و سپس در $m$ خط بعدی هر کدام، $t$ نامِ شکلاتی که دستگاه تولید می‌کند و $1\leq r \leq100$ تعداد شکلاتی که در هر دقیقه تولید می‌کند به ترتیب می‌آیند.

توجه کنید $t$ از حروف کوچک انگلیسی تشکیل شده و <space> در بین آن قرار ندارد و $|t|\leq30$.

خروجی🔗

در تنها خط خروجی تولیدات کل در دقیقه کارخانه جدید را چاپ کنید.

مثال🔗

ورودی

2
2
hoby 4
kitkat 1
5
hiss 2
hoby 2
diamond 4
twix 10
hiss 3

خروجی

22

ورودی

4
1
nesquik 5
2
nesquik 6
metro 2
1
snickers 10
1
snickers 10

خروجی

18

ژله‌ی ایرانی🔗

time limit per test: 1 seconds

memory limit per test: 100 megabytes

> این سوال به دلیل وجود نقص در Test Case ها حذف شده است

افراسیاب $n$ ژله‌ که به شکل مکعب‌های $1 \times 1 \times1$ هستند با شماره‌های ۱ تا $n$ خریده است. ژله $i$ام دارای وزن $W_i$ کیلوگرم است. می‌دانیم یک ژله قابلیت تحمل وزن تا حداکثر $C_i$ کیلوگرم را دارد. می‌خواهیم برای دسر، تعدادی از این ژله‌ها را روی یکدیگر بچینیم. از آن‌جا که در ایران باستان هرچه ژله بلندتر بود ارزش بیشتری داشت، افراسیاب قصد دارد با قرار دادن تعدادی ژله بر روی هم بلندترین ژله‌ي ممکن را بسازد. برنامه‌ای بنویسید که با دریافت وزن و قدرت تحمل ژله‌ها، طول بلندترین برج ژله‌ای را به دست آورد.

ورودی🔗

در خط اول ورودی عدد $n$ و س‍پس در $n$ خط بعد، درهر خط ابتدا عدد $W_i$ و سپس $C_i$ داده می‌شود.

خروجی🔗

در تنها سطر خروجی طول بلندترین برج ژله‌ای که افراسیاب می‌تواند با این ژله‌ها بسازد را به دست آورید.

محدودیت‌ها🔗

$0 \leq W_i, C_i \leq 10^9 , \, n \leq 10^9$

مثال🔗

ورودی نمونه ۱

4
10 10
3 5
10 1
9 7

خروجی نمونه ۱

3

ورودی نمونه ۲

2
10 5
9 4

خروجی نمونه ۲

1

مناطق پرسیتی🔗

time limit per test: 1 seconds

memory limit per test: 50 megabytes

در شهر زیبای پرسیتی خیابان‌ها به گونه‌ای طراحی شده‌اند که از نمای ماهواره به شکل یک شبکه مربعی می‌باشند.

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

ورودی🔗

ورودی شامل یک خط می‌باشد که دو عدد به صورت $X$ و $Y$ که با فاصله از هم جدا شده‌اند، منطقه مورد نظر را مشخص می‌کنند. ابتدا $X$ و سپس $Y$ وارد می‌شود.

$1 \leq X, Y \leq 10^4$

خروجی🔗

در صورتی که منطقه مورد نظر دارای شماره باشد، خروجی شماره منطقه می‌باشد و اگر آن منطقه شماره‌ای نداشت عبارت "no solution" در خروجی چاپ می‌شود.

مثال ۱🔗

ورودی

5 3

خروجی

11

مثال ۲🔗

ورودی

3 2

خروجی

no solution

مثال ۳🔗

ورودی

2 0

خروجی

2

شرکت بروبچ و شرکا🔗

time limit per test: 3 seconds

memory limit per test: 128 megabytes

شرکت ساختمانی بروبچ و شرکا، از کنار هم جمع شدن تعدادی دوست تشکیل شده که هر روز صبح اول وقت هر کدام با وانت خود به محل کار مشترک که یک ساختمان در حال تکمیل است، و با نام «ساختمون» شناخته می‌شود، می‌روند.

اخیراً بروبچ با دو مشکل جدید مواجه شده‌اند. اولین مشکل از زمانی پیش آمده که سهمیه‌بندی سوخت شروع شد، بروبچ به این نتیجه رسیدند که برای کاهش مصرف سوخت بهتر است از یک وانت برای انتقال چند نفر استفاده کنند. مثلاً ممکن است چند نفر از بروبچ با وانت خود به منزل یکی بروند، آنجا وانت خود را پارک کنند و همه با یکی از وانت‌ها به ساختمون بروند. همچنین همسایگان ساختمون از شلوغی زیاد اطراف ساختمون و پیدا نشدن جای پارک شکایت کرده‌اند و بروبچ در پارک کردن وانت خود در اطراف ساختمون دچار مشکل شده‌اند.

شما باید به آن‌ها کمک کنید تا بهترین روش برای رفتن به ساختمون را با کمترین میزان مصرف سوخت پیدا کنند. فرض بر این است که میزان مصرف سوخت متناسب است با میزان مسافتی که ماشین‌ها طی می‌کنند. همچنین وانتی که در ساختمون پارک کند تا پایان روز همان‌جا باقی می‌ماند.

ورودی🔗

ورودی شامل یک مورد تست است. در خط اول عدد صحیح $n$ که تعداد راه‌های ارتباطی ممکن برای جابه‌جایی آمده است. $n$ خط بعدی هر یک اطلاعات مربوط به یکی از راه‌های ارتباطی است که شامل دو نام و یک عدد صحیح مثبت است. نام‌ها یا نام دو نفر از بروبچ یا کلمه Sakhtemoon است و عدد صحیح فاصله بین آن‌ها است. راه‌ها دو طرفه فرض می‌شود. حداکثر اعضای بروبچ ۲۰ نفر و حداکثر طول نام هر یک ۱۰ است. در خط انتهایی عدد صحیح $s$ که حداکثر تعداد ماشین‌هایی است که می‌توانند در نزدیکی ساختمون پارک شوند. می‌توانید فرض کنید از منزل هر یک از اعضای بروبچ به ساختمون مسیری وجود دارد و مسأله جواب دارد.

خروجی🔗

خروجی از یک خط تشکیل شده و در آن جمع مسافتی که وانت‌ها طی می‌کنند می‌آید.

مثال🔗

ورودی

10
A B 32
A Sakhtemoon 57
A D 43
B Sakhtemoon 19
B C 82
C Sakhtemoon 65
C E 90
C D 109
Sakhtemoon E 24
E D 79
3

خروجی

183

ورودی

10
A B 32
A Sakhtemoon 57
A D 43
B Sakhtemoon 19
B C 82
C Sakhtemoon 65
C E 90
C D 109
Sakhtemoon E 24
E D 79
1

خروجی

255