● Codeforces Round #216 (Div. 2) - C. Valera and Elections

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

این کشور، n استان و n-1 جاده(مسیر بین 2 استان) دارد و از هر استانی می توان از طریق تعدادی جاده به استانی دیگر رفت. هر استان از 1 تا n شماره گذاری شده و هر جاده از دو حالت خارج نیست: یا "راه سالم" است و یا "راه مشکل دار".

از میان نامزدهای انتخابات، کسی انتخاب می شود که به این وعده عمل کند: "من حداقل k و همچنین k استانی را می یابم که با تعمیر مسیرهای آن k استان منتهی به استان شماره 1 (مثلاً استان شماره 1 پایتخت آن کشور بوده)، هیچ راه مشکل داری در کشور ما وجود نداشته باشد".

حال یکی از فامیل های رفیق تان که در این انتخابات کاندید شده، از شما کمک می خواهد که در عملی شدن این وعده به او کمک کنید.

input

5
1 2 2
2 3 2
3 4 2
4 5 2

output

1
5

● Bayan 2012-2013 Elimination Round - A. Duel

مسابقه برنامه نویسی بیان - انتخابی آبان 91

دوئل

در نوع جدیدی از بازی دوئل، n سرباز در یک صف قرار می گیرند و هر سرباز به سمت چپ ‘(‘ یا راست ‘)’ نشانه گیری کرده و آماده ی شلیک می شود. در هر ثانیه، اگر دو سرباز به سمت یکدیگر نشانه گرفته باشند و سرباز زنده ای میان آن دو نباشد، به همدیگر شلیک می کنند و هر دو کشته شده و به زمین می افتند. سربازانی که از مسابقه جان سالم به در ببرند، جوایز نفیسی دریافت می کنند.

برای مثال اگر جهت گیری اولیه سربازان به صورت ) ( ( ( ) ( ) ) ( ( باشد، در ثانیه اول سربازان چهارم و پنجم از سمت چپ و سربازان ششم و هفتم به هم شلیک خواهند کرد و در ثانیه دوم، سربازان سوم و هشتم به هم شلیک خواهند کرد و سایرین سالم خواهند ماند.

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

input

2
10
))(()()))(
6
()(())

output

4
0

● Codeforces Round #211 (Div. 2) - A. Soroban

در کشور ژاپن، چرتکه ای توسعه یافته به نام Soroban دارند که در مدارس ابتدایی استفاده آن را به دانش آموزان می آموزند تا جمع و تفریق را به خوبی یاد بگیرند. ما قصد نداریم در مورد آنها صحبت کنیم، بیایید نگاهی دقیق تر به ساختار این چرتکه بیاندازیم:

Soroban دارای تعدادی میله افقی و هر میله شامل 5 مهره است. نوار عمودی که یک مهره سمت چپ را از 4 مهره ی دیگر جدا می کند، نوار حساب نام دارد، این مهره تک نامیده می شود (طبق شکل) و مهره های سمت راست نوار حساب را ایچی می گویند. هر میله ی افقی رقمی از 0 تا 9 را نشان می دهد که با این الگوریتم، به سادگی می توان آنرا بدست آورد:

    ❶ ابتدا همه ی میله ها، رقم 0 را نشان می دهند. (مهره های ایچی، کاملاً راست و مهره ی تک، چپ) مثل ردیف اوّل در شکل.

    ❷ اگر مهره ی تک به سمت راست برود، 5 واحد اضافه می شود.

    ❸ به ازای هریک از مهره های ایچی که سمت چپ برود، 1 واحد اضافه می شود.

بنابراین در شکل، ردیف اوّل نشان دهنده ی رقم 0، ردیف دوّم نشان دهنده ی رقم 2 و ردیف سوّم نشان دهنده ی رقم 7 است که چرتکه عدد 720 را نشان می دهد.

کار شما نوشتن برنامه ای است که به ازای هر عددی، Soroban آن را نمایش دهد...

input

720

output

O-|-OOOO
O-|OO-OO
-O|OO-OO

● Codeforces Round #210 (Div. 2) - A. Levko and Table

میثم از دانش آموزان سال اوّل دبیرستان علامه حلی 5 است، او قبلاً اثبات کرده که به ازای هر عدد ثابتی مثل k ، می توان در هر مربع n×n طوری یک سری اعداد (که لزوما متمایز نیستند) درون آن قرار داد به طوری که جمع اعداد هر ستون و هر سطر مربع، k باشد. (بدیهیات را اثبات کرده!)

حال برای تمرین تکمیلی می خواهد برنامه ای بنویسد که با گرفتن n و k، جدول دلخواه را چاپ کند. طبق معمول کمک می خواهد!

input

4 7

output

2 1 0 4
4 0 2 1
1 3 3 0
0 3 2 2

● Codeforces Round #206 (Div. 1) - A. Vasya and Robot

قلی از دانش آموزان گروه مکانیک دبیرستان علامه حلی 5 است! برای سمینار سوّم، او رباتی ساخته است که قابلیت های زیر را دارد:

    ❶ یک بازوی راست و یک بازوی چپ دارد که می تواند به وسیله ی آنها شئی را بلند کند.

    ❷ اگرشئی را با بازوی راست بلند کند، به اندازه ی (وزن بازوی راست × وزن شئ) سنگین خواهد بود و اگرشئی را با بازوی چپ بلند کند، به اندازه ی (وزن بازوی چپ × وزن شئ) سنگین خواهد بود.

    ❸ اگر دوبار متوالی از بازوی راستش کار بکشد، به مقدار Q_r به سنگینی افزوده می شود و اگر دوبار متوالی از بازوی چپش کار بکشد، به مقدار Q_l به سنگینی افزوده می شود.

قبل از برگزاری سمینار، برای تست نحوه ی عملکرد و تأیید پروژه، n شئ با وزن های W₁ , W₂, ..., W_n در یک ردیف گذاشته اند به طوری که شئ n-ام در سمت چپ قرار گرفته است و ربات باید همه ی اشیاء را بلند کند. از قلی می خواهند طوری ربات را هدایت کند که کمترین انرژی را مصرف کند (هرچه مجموع سنگینی های وارد بر دو بازوی ربات بیشتر شود، انرژی بیشتری می سوزاند).

و مسلّم است که ربات نمی تواند شئی که در سمت چپ است را با دست راست بلند کند (و بلعکس) و نیز مجاز به برداشتن از اشیاء میانی نیست. قلی برای رساندن پروژه به سمینار، از کامپیوتری های مدرسه کمک می خواهد...

input

3 4 4 19 1
42 3 99

output

576

● Codeforces Round #207 (Div. 2) - A. Group of Students

تابستان 92 است! دبیرستان علامه حلی 5 تهران، برای ورودی های جدید (دوره 3) آزمونی برگزار کرد که برنامه نویس های قوی (رده الف) و ضعیف(رده ب) را دو دسته کند. از ما به عنوان بهترین برنامه نویس های حلی 5 تقاضا شده که نمره قبولی این آزمون را طوری تعیین کنیم که تعداد قبولی های رده الف از گنجایش کلاس آن بیشتر نشود و همین طور برای رده ب.

input

5
3 4 3 2 1
6 8

output

3

● Codeforces Round #205 (Div. 2) - D. Queue

دختر و پسرهای دبیرستانی برای سوارشدن به اتوبوس صف بسته اند، امّا اتوبوس راه می افتد اگر و تنها اگر پسرها زودتر از دخترها سوار شوند! پس باید تغییراتی در صف ایجاد شود، اینگونه که در هر ثانیه اگر پسری، دختری را جلوی خود دید جای آنها عوض می شود تا زمانی که هیچ دختری جلوی هیچ پسری نباشد؛ در اینجا دخترها را با F و پسرها را با M نمایش می دهیم. به ازای هر رشته ی ورودی شامل F و M ، حداقل زمان برای تشکیل رشته ای از تمام M ها در سمت راست و تمام F ها در سمت چپ را بر حسب ثانیه به دست آورید.

input

MMFF

output

3