انجمن انفورماتیک ایران انجمن انفورماتیک ایران انجمن انفورماتیک ایران
گزارش کامپیوتر شماره 234, ویژه مرداد و شهریور ماه 96 منتشر شد. شنبه  ٢٧/٠٨/١٣٩٦ ساعت ١٥:٣٣
 

برگزاری اولین مسابقه برنامه‌نویسی دانش‌آموزی ایران
دانشگاه صنعتی شریف- 14 و 15 آذر 1386

دکتر یحیی تابش
پست الکترونیک: tabesh@sharif.edu


اولین مسابقه برنامه‌نویسی دانش‌آموزی ایران به ابتکار دانشگاه صنعتی شریف و با هماهنگی با سازمان آموزش و پرورش شهر تهران روزهای 14 و 15 آذر 1386 در دانشگاه صنعتی شریف برگزار شد. در این مسابقه 74 تیم از دبیرستان‌ها و پژوهش‌سراهای تهران و حومه، و تیم‌هایی نیز از دبیرستان‌های شهرهای اصفهان، مشهد، کاشان، و کرمانشاه شرکت کردند.
مسابقه به صورت تیمی برگزار شد و دانش‌آموزان در تیم‌های سه نفر در این رقابت شرکت کردند. هر تیم سه نفره یک دستگاه کامپیوتر که به شبکه متصل بود در اختیار داشت، و در شروع مسابقه 11 مسأله به آنان داده شد. دانش‌آموزان می‌بایست پس از حل هر مسأله و طراحی الگوریتم‌های لازم، به یکی از زبان‌های پاسکال، ++ C و یا جاوا برنامه لازم را نوشته و پس از اطمینان از درستی آن را از طریق شبکه برای داوران ارسال کنند. داوران پس از بررسی در صورت درستی برنامه، امتیاز مربوطه را اعطا می‌کردند ولی در غیر اینصورت عدم درستی برنامه به اطلاع آنان رسانده می‌شد تا نسبت به تصحیح و ارائه مجدد آن اقدام کنند. البته در ارائه مجدد در صورت درستی برنامه نمره کامل اعطا نمی‌شود و جریمه‌ای به امتیاز آن تعلق می‌گیرد.
حضور دانش‌آموزان در اولین مسابقه بسیار چشمگیر و در مجموع رضایت‌بخش بود. دانش‌آموزان با اهداف این مسابقه که توجه به پرورش تفکر خلاق، و هنر حل مسأله، و آشنایی با روش‌های برنامه‌نویسی بود آشنا شدند و امید است برگزاری این مسابقه توجه دانش‌آموزان علاقه‌مند را به هنر حل مسأله و برنامه‌نویسی جلب نماید، و علاوه بر آن مشارکت در یک فعالیت تیمی و گروهی نیز برای آنان تجربه بسیار ارزنده‌ای را به دنبال دارد.

امید است با ادامه این فعالیت در سال‌های آینده بیش از پیش موجب پیشرفت علمی و تکنولوژیکی دانش‌آموزان کشورمان را فراهم کنیم.
به پیوست اسامی 10 تیم برتر مسابقه و متن مسائل مسابقه آورده شده است.

* * *

تعداد سؤالات حل کرده

نام تیم شرکت‌کننده

رتبه

7
7
6
6
6
5
5
5
3
3

فرزانگان تهران
علامه حلی تهران (تیم سوم)
علامه حلی تهران (تیم اول)
هاشمی‌نژاد مشهد
طباطبایی (تیم سوم)
علامه حلی تهران (تیم دوم)
طباطبایی (تیم پنجم)
طباطبایی (تیم چهارم)
اژه‌ای اصفهان
علامه حلی شهریار (تیم دوم)

1
2
3
4
5
6
7
8
9
10

مسأله 1: معدل‌گیری
پس از چند هفته امتحانات پی‌در‌پی، امروز کارنامه بچه‌های مدرسه به آن‌ها تحویل داده شد! همه نمرات و ضرایب هر درس در کارنامه مشخص شده است، اما معدل در کارنامه درج نشده است. بچه‌های مدرسه در محاسباتشان همیشه اشتباه می‌کنند، بنابراین از شما خواسته‌اند، برنامه‌ای بنویسید که معدل هر یک از کارنامه‌ها را به‌دست آورد.

ورودی
ورودی شامل اطلاعات تعدادی کارنامه است. هر کارنامه شامل سه خط است، در خط اول یک عدد طبیعی n ، تعداد دروس، آمده است. می‌دانیم n بین 2 و 25 است (خود این مقادیر هم می‌تواند بشود). در خط دوم n عدد صحیح بین 0 تا 10 آمده است که ضرایب دروس 1 تا n هستند. در خط سوم نیز n عدد صحیح بین تا 0 تا 20 آمده است که نمرات دروس 1 تا n هستند.
پس از آخرین کارنامه یک خط اضافه آمده است که فقط شامل عدد 0 است.

خروجی
به ازای هر کارنامه در ورودی، یک خط درخروجی چاپ کنید که معدل کارنامه را گرد شده به دقیقاً 2 رقم اعشار نمایش می‌دهد. توجه کنید که مثلاً اگر جواب دقیقاً 19 باشد شما باید در خروجی “19.00” چاپ کنید.

ورودی نمونه

ورودی نمونه

4
2 3 1 4
17 19 18 20
3
10 1 10
15 20 14
2
5 5
19 18
0

خروجی نمونه

خروجی نمونه

18.90
14.76
18.50

مسأله 2: سربازها
در یک پادگان احتمالاَ نظامی، n سرباز در یک ردیف ایستاده‌اند. با صدای سوت، هریک از این سربازها ۹۰ درجه می‌چرخد؛ بعضی به راست و بعضی به چپ. از این‌جا بازی شروع می‌شود.
در هر مرحله، اگر دو سرباز روبه‌روی هم ایستاده باشند، هردو عقبگرد می‌کنند. توجه کنید که در هر مرحله ممکن است چند سرباز با هم عقب‌گرد کنند، ولی یک سرباز حداکثر یک بار عقب‌گرد می‌کند.
می‌توان نشان داد که پس از تعدادی مرحله بازی تمام می‌شود؛ یعنی دیگر هیچ دو سربازی روبه‌روی هم نیستند. برنامه‌ای بنویسید که تعداد مراحل بازی را مشخص کند.

ورودی
در هر سطر ورودی، رشته‌ای از کاراکترهای "<" و ">" آمده است. هریک از این کاراکترها مشخص کننده یک سرباز است. کاراکتر < به معنی گردش به راست و کاراکتر > به معنی گردش به چپ (در هر مرحله، دو سربازی که به‌صورت >< هستند، به‌صورت <> می‌شوند). فاصله‌ای میان کاراکترها نیست.

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

محدودیت‌ها
طول رشته ورودی (یعنی همان n ) حداکثر ۱۰۰۰۰ است.

ورودی نمونه

ورودی نمونه

><<><  
><<>  

خروجی نمونه

خروجی نمونه

3
2

  توضیح ورودی اول: بازی به این صورت انجام می‌شود:

><<><  
<><<>  
<<><>  
<<<>>  

مسأله 3: جستجو
متنی به شما داده شده است که شامل چندین خط می‌باشد. شما باید در این متن چند کلمه را جستجو کنید. کلمات جستجو شده فقط شامل حروف کوچک یا بزرگ الفبایی انگلیسی هستند، اما خود متن ممکن است شامل هر نوع کاراکتری باشد.
به یک زیر رشته از حروف وقتی "کلمه جدا" گفته می‌شود که هر دو شرط زیر رخ دهد:

  1.   سمت چپ آن یا هیچ کاراکتری وجود نداشته باشد (به عبارت دیگر، اولین حرف آن، اولین حرف خط هم باشد)، یا آنکه کاراکتر سمت چپ آن فاصله (" ") باشد.
  2.   سمت راست آن یا هیچ کاراکتری وجود نداشته باشد (به عبارت دیگر، آخرین حرف آن، آخرین حرف خط هم باشد)، یا آنکه کاراکتر سمت راست آن یکی از حروف (" ") یا (" ? ") یا (" ! ") یا (" . ") یا (" , ") یا (" ; ") باشد.

شما باید به ازای هر کلمه جستجو شده تمام موارد ظاهر شدن آن به صورت یک کلمه جدا در متن را گزارش کنید.

ورودی
ورودی شامل چند آزمون است. هر آزمون به شکل زیر است:
در اولین خط L (150 ≥ L≥ 1) ورودی تعداد خط‌های متن می‌آید. سپس L خط می‌آید که همان متنی است که می‌خواهیم در آن جستجو کنیم. سپس در یک خط Q (100≥Qی≥1) می‌آید و سپس Q کلمه می‌آید که فقط شامل حروف ( a تا z ) و ( A تا Z ) است.
تعداد کل کاراکتر‌های روی هر خط حداکثر 150 کاراکتر است. طول هر کلمه حداکثر 20 حرف است.

خروجی
به ازای هر آزمون یک بلوک از خروجی باید چاپ کنید. هر بلوک شامل تعدادی خط است که هر خط نتیجه جستجوی یکی از کلمات است. هر خط به شکل زیر است:
اگر کلمه مورد نظر هیچ جای متن به شکل جدا یافت نشد، در خروجی فقط خط “No occurrences found.” را دقیقاً چاپ کنید. در غیر این صورت تمام ظاهر شدن‌ها را به ترتیب مکان یافت شدن‌شان در متن چاپ کنید. هر ظاهر شدن را به شکل «مکان_در_خط:خط» چاپ کنید و بین آن‌ها یک کاراکتر فاصله بگذارید. توجه کنید که در انتهای هیچ خطی نباید کاراکتر فاصله بگذارید. پس از هر بلوک (حتی بلوک آخر) یک خط خالی بگذارید.

ورودی نمونه

ورودی نمونه

4
only 40 minutes left.
WOW, I submitted the find problem.
wrong answer?!?!?! Why? Hmmm.....
Yes. Bring me some soda :)
8
answer
soda
bring
Wow
submit
Yes
only
Soda

4
aaaaa abcdabcd;;; .abcd! abcd.
abc
aaa
aaaabcd
5
aaa
aaaa
abc
abcd
abcdabcd

0

خروجی نمونه

خروجی نمونه

(3:7)
(4:20)
No occurrences found.
No occurrences found.
No occurrences found.
(4:1)
(1:3)
No occurrences found.

3:1)
No occurrences found.
(2:1)
(1:26)
(1:7)

مسأله 4: نمودار
نمودار هیستوگرام تعدادی داده عددی، نموداری است که شامل تعدادی ستون مستطیلی است. هر ستون متناظر با یک بازه از اعداد، مثلاٌ [1, 3] است. ارتفاع هر ستون متناسب با تعداد داده‌های درون بازه متناظر آن ستون است. در این مسأله شما باید برنامه‌ای بنویسید که نمودار هیستوگرام تعدادی داده را رسم کند. داده‌ها در بازه [A , B] قرار دارند و نمودار خروجی باید شامل دقیقاٌ D ستون باشد. البته D در ورودی داده شده است و می‌دانیم B-A بر D بخشپذیر است. ارتفاع هر ستون در این نمودار دقیقاَ برابر تعداد داده‌هایی است که در بازه متناظر آن ستون قرار دارند. اگر داده‌ای در مرز دو بازه قرار داشت فقط در درون سمت چپی محسوب می‌شود. برای روشن شدن بیشتر مسأله به ورودی و خروجی نمونه توجه کنید. اعداد تکراری ممکن است به عنوان داده بیایند. خود A و B هم ممکن است به عنوان داده بیایند.

ورودی
ورودی شامل تعدادی آزمون است و پس از آخرین آزمون خطی با چهار عدد صفر آمده است. هر آزمون به این شکل است:
در خط اول ورودی به ترتیب N , D , A و B آمده‌اند. در N سطر بعدی اعدادی که باید نمودار آن‌ها کشیده شود آمده‌اند. پس از هر آزمون (حتی آزمون آخر) یک خط خالی بگذارید. تمام داده‌ها در بازه [ A , B ] قرار دارند.

خروجی
قبل از چاپ نمودار در هر آزمون، ابتدا خطی شامل: " Case #x " در خروجی بنویسید که در این عبارت به جای x شماره آزمون را بنویسید ( x لزوماً یک رقمی نیست!!). سپس خروجی را مانند آنچه در خروجی نمونه آمده است چاپ کنید. توجه کنید که باید پس از هر آزمون (حتی آزمون آخر) یک خط خالی چاپ کنید.

محدودیت‌ها

50 ≥N≥ 2 , 20 ≥D≥ 2
-1000≤A<B≤10000

ورودی نمونه

ورودی نمونه

10 4 0 20
1
4
4
3
5
12
19
19
20
10

7 10 0 10
0
1
5
9
9
9
10

0 0 0 0

خروجی نمونه

خروجی نمونه

Case #1:
 
|#
|# #
|# ##
|####
+----

Case #2:
| #
| #
| #
|## # #
+----------

مسأله 5: آزمایشگاه شیمی
مسئول آزمایشگاه شیمی مدرسه ‌ای می‌خواهد تمام مواد لازم برای آزمایش‌های این هفته را فهرست کند. بنابراین او از هرکدام از گروه‌های پژوهشی فعال خواسته است که مقدار مواد لازم برای آزمایش خود را (به گرم) در یک خط نوشته و به او ایمیل کنند. اکنون او اطلاعات درون تمام ایمیل‌ها را درون یک فایل قرار داده و می‌خواهد لیست نهایی خرید را تهیه کند. تنها کاری که لازم است انجام شود این است که مقادیر مورد نیاز برای هر ماده را جمع بزند و سپس مواد را به ترتیب الفبایی چاپ کند. برنامه‌ای بنویسید که این کار را برای او انجام دهد. منظور از ترتیب الفبایی همان ترتیبی است که کلمات در لغت‌نامه می‌آیند.

ورودی
ورودی شامل چندین آزمون است. ساختار هر آزمون به شکل زیر است:
در اولین خط عدد  n(1≤n≤30)   ، تعداد آزمایش‌ها ،  آمده است. سپس n خط آمده است که هر خط اطلاعات مربوط به یک آزمایش است.  در ابتدای هر خط عدد    k (1≤k≤20) ، تعداد مواد مورد نیاز و در ادامه k جفت آمده است که به ترتیب نام و جرم ماده مورد نظر است. جرم هر ماده عددی طبیعی و کوچکتر یا مساوی 10000 است و نام یک ماده یک دنباله از حروف بزرگ لاتین با طول حداکثر 20 است. ممکن است یک ماده خاص بیش از یک بار در یک آزمایش مورد استفاده قرار گیرد که در این صورت از آن ماده به اندازه مجموع جرم‌هایش در آن آزمایش نیاز داریم. پس از آخرین آزمون یک خط شامل عدد 0 آمده است. در ورودی حداکثر 50 آزمون وجود دارد. برای درک بهتر ساختار ورودی و خروجی، به ورودی و خروجی نمونه توجه کنید!

خروجی
به ازای هر آزمون، ابتدا یک خط شامل “Test #x:” بنویسید که x شماره این آزمون است. سپس هر کدام از مواد مورد نیاز را در یک خط و به ترتیب الفبایی بنویسید. حتماً پس از هر آزمون (حتی آزمون آخر!) یک خط خالی در خروجی بگذارید.

ورودی نمونه

ورودی نمونه

5
3 HCL 1000 KCL 100 NAOH 50
1 CACOH 45
1 XE 25
1 CACOH 20
3 NAOH 45 CL 40 CACOH 100

2
2 GOOGERD 10 ALMINIUM 20
3 HCL 10 HCL 20 HCL 30

4
3 AA 10 A 20 AA 10
3 AB 40 AB 10 AA 20
4 AAA 30 ABA 50 AAA 1000 AB 500
1 AAABA 10000
0

خروجی نمونه

خروجی نمونه

Test #1:
CACOH 165
CL 40
HCL 1000
KCL 100
NAOH 95
XE 25
 
Test #2:
ALMINIUM 20
GOOGERD 10
HCL 60

Test #3:
A 20
AA 40
AAA 1030
AAABA 10000
AB 550
ABA 50

مسأله 6: جاده‌ها
در هنگام بازجویی اداره پلیس از یک فرد مظنون، او ادعا کرده است که در یک روز مشخص چهار جاده به طول‌های a ، b ، c و d را که به شکل زیر قرار دارند, به ترتیب پیموده است. در این مسأله به این نوع چهارضلعی «راست» گفته می‌شود. به عبارت دقیقتر به یک چهارضلعی راست گفته می‌شود اگر دو خاصیت زیر را داشته باشد:

  1.   دو ضلع موازی داشته باشد (که به آن‌ها قاعده می‌گوییم و به دو ضلع دیگر ساق می‌گوییم)
  2.   دو زاویه روبرو نداشته باشد که هر دو حاده (کمتر از 90 درجه) باشند.

توجه کنید که طبق این تعریف مستطیل‌ها راست‌اند اما متوازی‌الاضلاع‌هایی که مستطیل نباشند، راست نیستند.
اکنون اداره پلیس می‌خواهد بداند که آیا شکلی با این مشخصات وجود دارد یا نه. مظنون ترتیب پیمایش جاده‌ها را نیز مشخص کرده است.
در هر خط ورودی به ترتیب چهار عدد طبیعی a ، b ، c و d آمده‌اند. همه اعداد ورودی از 1000 کمترند. به ازای هر خط ورودی یک خط در خروجی چاپ کنید. اگر چهارضلعی راستی وجود دارد که b و d قاعده‌های آن و a و c ساق‌های آن باشد، در خروجی عبارت “ YES ” را در یک سطر بنویسید. در غیر این صورت “ NO ” بنویسید. آخرین خط ورودی شامل چهار عدد صفر است. تعداد خطوط ورودی از 10000 کمتر است.
تذکر: همانطور که در ورودی نمونه دیده می‌شود لزومی ندارد که b از d کوچکتر باشد تا جواب “ YES ” باشد.

ورودی نمونه

ورودی نمونه

3 3 5 7
4 9 4 5
4 5 4 8
4 5 3 7
2 7 3 7
1 10 100 20
6 18 9 7
0 0 0 0

خروجی نمونه

خروجی نمونه

YES
YES
YES
NO
NO
NO
YES

 

مسأله 7: پله‌بازی
یک صفحه m در n را در نظر بگیرید که خانه‌های آن مانند صفحه بازی مار و پله با اعداد 1 تا mn شماره‌گذاری شده‌اند. فردی در ابتدا خانه 1 ایستاده است و می‌خواهد با تعدادی حرکت به خانه mn برود. k نردبان نیز وجود دارند که هر نردبان میان دو خانه متفاوت جدول قرار دارد. در هر حرکت فرد می‌تواند یکی از این دو کار را بکند:

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

تعداد راه‌های متفاوت برای پیمودن جدول چقدر است؟

ورودی
ورودی شامل چندین نمونه از مسأله است.
هر نمونه شامل تعدادی خط است. در اولین خط 3 عدد طبیعی m ، n و k به ترتیب آمده‌اند.
m≤10,n≤10,k≤20 . در k خط بعدی در هر خط یک جفت عدد طبیعی آمده است که دو سر یک نردبان را نشان می‌دهند، هر دو از mn کمترند و اختلافشان حداقل 2 است. پس از آخرین نمونه ورودی، خطی شامل “0 0 0” آمده است. دو سر هیچ نردبانی از جدول یکی نیستند، به عبارت دیگر تمام اعدادی که بعد از خط اول می‌آیند متمایزند. بدین ترتیب نردبان تکراری هم در ورودی وجود ندارد.

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

ورودی نمونه

ورودی نمونه

2 4 1
1 3

3 3 3
7 9
2 8
6 4

4 3 5
1 4
2 7
11 3
9 5
10 12
0 0 0

خروجی نمونه

خروجی نمونه

2
5
11

مسأله 8 :تعادل
کامران با دوستانش کَل انداخته است و قصد دارد یک بشقاب نسبتاً بزرگ را روی یک سوزن نگه دارد. او فیزیک بلد است و می‌داند برای اینکه این کار ممکن باشد، باید مرکز ثقل بشقاب روی سوزن باشد، وگرنه بشقاب تعادل نخواهد داشت و می‌افتد. مکان سوزن را دوستانش تعیین می‌کنند (و ممکن است وسط بشقاب نباشد). خوشبختانه بشقاب مورد نظر Nتا حفره دارد و کامران سه تیله فلزی در اختیار دارد و می‌تواند تیله‌هایش را در حفره‌های بشقاب بگذارد. هدف کامران این است که وقتی دوستانش مکان سوزن را نسبت به بشقاب تعیین کردند، او تیله‌های خود را طوری در حفره‌ها بچیند که مرکز ثقل بشقاب بر روی سوزن بیفتد و بشقاب تعادلش را حفظ کند.
کامران می‌تواند از هر سه تیله استفاده نکند و مثلاً فقط دو تا را بر بشقاب بگذارد، ولی حق ندارد از هیچ یک از تیله‌ها استفاده نکند. در ضمن در یک حفره حداکثر یک تیله جا می‌شود و نمی‌تواند دو تیله را در یک حفره بگذارد.

ورودی
ورودی شامل چند آزمون است. در سطر اول هر آزمون، عدد N و سوزنX و سوزنY به همین ترتیب می‌آید. سپس در N سطر بعدی مختصات مکان حفره iاُم به صورت xi و yi داده می‌شود. تمامی مختصات بر حسب سانتی‌متر هستند و نسبت به وسط بشقاب داده می‌شوند. (وسط بشقاب نقطه (0,0) است). تمام نقاط هم از یکدیگر مجزا هستند و هیچ حفره‌ای با سوزن هم مکان نیست. در آخر ورودی ۳ تا صفر نوشته شده است.

خروجی
برای هر آزمون باید یک خط چاپ کنید. اگر فلانی بتواند تعادل را با گذاشتن تیله برقرار کند، باید بنویسید ”YES“ و در غیر این صورت بنویسید ”NO“.

چند نکته دیگر:

  • 1<K است؛ تعداد حفره‌ها حداقل دو تاست
  • تمامی اعداد ورودی، اعداد صحیح هستند.
  • محاسبه مرکز ثقل چنین است:

که در آن xi و yi مختصات تیله iاُم است و mi وزن تیله iاُم می‌باشد و مختصات مرکز جرم xcm و ycm است.

  •   مواظب تقسیم باشید! تقسیم اعداد int فقط جزء صحیح جواب را به شما می‌دهد!

ورودی نمونه

ورودی نمونه

4 1 0
2 1
-1 -3
2 2
3 -1
6 0 0
1 1
2 3
2 4
3 1
2 2
4 1
3 100 -100
200 0
0 -200
1 1
0 0 0

خروجی نمونه

خروجی نمونه

YES
NO
YES

مسأله 9: قایق سواری
احمد، یکی از دوستان شما، طرحی برای ایجاد یک مسیر قایق‌رانی به ذهنش رسیده است. او پس از جستجوی فراوان دو منطقه تفریحی (الف) و (ب) پیدا کرده است که میان آن‌ها یک مسیر دریایی نسبتاً کوتاه وجود دارد. احمد می‌داند که اکثر شرکت کنندگان در یکی از مناطق (الف) یا (ب)، علاقه دارند به منطقه دیگر نیز سری بزنند. بنابراین او یک پایگاه در هر یک از (الف) و (ب) ساخته است و اکنون می‌خواهد بداند چند تا قایق باید بخرد. احمد می‌داند که هر منطقه تفریحی برنامه مجزایی برای کار خود دارد.
او می‌خواهد پس از اتمام یک برنامه شرکت‌کنندگان را توسط قایق به منطقه دیگر ببرد، بنابراین او جدول زمان اتمام برنامه‌های تفریحی هر منطقه را با پرس‌و‌جو به‌دست آورده است. منطقه (الف) A برنامه دارد و منطقه (ب) B برنامه دارد.
(1≤A,B≤ی1500)
احمد برای اینکه بتواند بیشترین سود ممکن را بکند، می‌خواهد بلافاصله پس از اتمام هر برنامه قایقی آماده در منطقه انجام آن برنامه داشته باشد که به شرکت کنندگان در آن برنامه تخصیص می‌یابد (اگر قایق در آن لحظه آماده نباشد مشتری‌ها پراکنده می‌شوند و احمد می‌خواهد این اتفاق هیچوقت نیفتد)
می‌دانیم همیشه دقیقاً L دقیقه طول می‌کشد تا قایق مسیر را بپیماید. از طرفی به خاطر هزینه زیاد سوخت احمد نمی‌خواهد هیچ قایقی بدون مسافر حرکت کند.
اکنون او می‌خواهد بداند کمترین تعداد قایقی که لازم دارد تا کاملاَ برنامه‌ای که در ذهنش است را اجرا کند چند تاست. (به عبارت دیگر حداقل تعداد قایقی را می‌خواهد بداند که با برنامه‌ریزی مناسب برای آن قایق‌ها بتواند پس از اتمام هر برنامه‌ای یک قایق آماده در آن منطقه داشته باشد). برنامه‌ای بنویسید که این عدد را به‌دست آورد.

ورودی
ورودی شامل تعدادی آزمون است که هر کدام آن‌ها بدین شکلند:
هر زمانی در ورودی به شکل “hh:mm” آمده است (دقیقاً 5 کاراکتر دارد). این زمان‌ها بین 00:00 تا 23:59 قرار دارند و زمان اتمام هیچ دو برنامه‌ای از یک منطقه یکسان نیست.
در سطر اول (1≤L≤2000) ,L آمده است. در سطر بعد A آمده است. سپس در A سطر بعدی، زمان اتمام برنامه‌های منطقه (الف) آمده است. در سطر بعدی B و در B سطر بعدی زمان اتمام برنامه‌های منطقه (ب) آمده است. زمان اتمام برنامه‌ها در هر یک از مناطق بر حسب زمان مرتب شده است. پس از آخرین آزمون سطری شامل یک عدد صفر آمده است.

خروجی
به ازای هر آزمون یک خط در خروجی که شامل جواب مسأله است چاپ کنید.

ورودی نمونه

ورودی نمونه

45
1
08:00
1
08:00

 

45
2
08:00
12:00
1
08:45

120
2
09:00
10:00
4
08:00
11:00
14:00
20:00

0

خروجی نمونه

خروجی نمونه

2
1
3

مسأله 10: گوی‌ها
n گوی دور دایره‌ای به محیط ۱۰۰ متر قرار دارند. مکان هریک از این گوی‌ها براساس نقطه‌ای خاص روی محیط دایره، که آن را نقطه صفر می‌نامیم، عددی صحیح و نامنفی و کوچکتر از ۱۰۰ است. در ابتدا مکان گوی‌ها متفاوت است. در لحظه صفر این گوی‌ها با سرعت ثابت ۱ ‌متر بر ثانیه در جهت مثبت یا منقی مثلثاتی شروع به حرکت می‌کنند. اگر دو گوی به یکدیگر برخورد کنند، هریک از آن‌ها جهت حرکت خود را تغییر داده و با همان سرعت ۱ متر بر ثانیه حرکت می‌کند. برنامه‌ای بنویسید که بتواند در هر لحظه موقعیت گوی‌ها را مشخص کند.

ورودی
ورودی شامل تعدادی آزمون است و پس از آخرین آزمون یک خط می‌آید که تنها شامل یک عدد صفر است.
هر آزمون به این شکل است: در سطر اول, n ، تعداد گوی‌ها آمده. در n سطر بعد، در هر سطر یک عدد صحیح نامنفی کوچکتر از ۱۰۰ و یک کاراکتر + یا – آمده که به‌ترتیب مشخص کننده مکان اولیه گوی (نقطه دلخواهی از دایره را صفر می‌نامیم و نقاط دایره را در جهت مثبت مثلثاتی شماره‌گذاری می‌کنیم) و جهت حرکت آن (+ به معنی مثبت مثلثاتی و – به معنی منفی مثلثاتی) هستند آمده‌اند.
سطر ( ۲ + n )ام شامل عدد m ، تعداد درخواست‌ها است. در هر یک از m سطر بعدی عددی نامنفی و حقیقی با حداکثر یک رقم اعشار آمده است.

خروجی
به ازای هر آزمون در ورودی، ابتدا عبارت ": Case #x " را بنویسید و سپس جواب آزمون را به شکل زیر چاپ کنید:
خروجی باید شامل m بلوک باشد که پس از هر بلوک یک خط شامل "---" چاپ می‌شود.
در هر بلوک، n عدد چاپ کنید، که هر کدام از آن‌ها به تنهایی در یک سطر قرار گرفته است. این اعداد نشان دهنده مکان گوی‌ها در لحظه مورد نظر است. این اعداد باید تا دقیقاً سه رقم اعشار نوشته شوند. پس از جواب هر آزمون (حتی آزمون آخر) یک خط خالی چاپ کنید.

محدودیت‌ها
1≤m≤200 , 1≤n≤100
همچنین هریک از زمان‌های داده شده عددی نامنفی و کوچکتر از ۱۰۰۰۰ است.

ورودی نمونه

ورودی نمونه

4
0 +
65 -
10 -
13 -
3
2.1
6.0
20.0
 
0

خروجی نمونه

خروجی نمونه

Case #1:
2.100
62.900
7.900
10.900
---
4.000
59.000
6.000
7.000
---
90.000
45.000
93.000
20.000
---
 

مسأله 11: برج‌های هانوی
مسأله «برج‌های هانوی» از سه میله با نام‌های A و B و C تشکیل می‌شود که n عدد دیسک با قطرهای مختلف (و ارتفاع‌های یکسان) در میله‌ها قرار دارند. در ابتدای کار تمام دیسک‌ها به‌صورت مرتب شده بر اساس قطرشان (طوری‌که کم‌قطرترین دیسک بالاترین و بزرگ‌ترین دیسک پایین‌ترین باشد) روی میله A قرار دارند.

C:\Documents and Settings\aideen\Desktop\hanoi.GIF

یک حرکت «مجاز» در این مسأله برداشتن بالاترین دیسک از یک میله (میله مبدأ) و قرار دادن آن در میله‌ای دیگر (میله مقصد) است به‌طوری که هیچ‌گاه یک دیسک روی دیسکی با قطر کوچک‌تر قرار نگیرد. با این وصف، یک حرکت را می‌توان با دو حرف بزرگ انگلیسی نمایش داد که حرف اوّل میله مبدأ و حرف دوم میله مقصد است. برای مثال حرکت AB یعنی برداشتن بالاترین دیسک میله A و قرار دادن آن روی تمام دیسک‌های میله B (در صورت وجود). دقّت کنید که حرکت AB تنها زمانی مجاز است که میله A حداقل یک دیسک داشت باشد و به‌علاوه یا میله B خالی باشد یا قطر بالاترین دیسک میله A (که جابه‌جا می‌شود) از قطر بالاترین دیسک میله B کمتر باشد.
با شروع از حالتی که تمام دیسک‌ها به‌صورت مرتب در میله A قرار دارند (نظیر شکل بالا)، بازی هنگامی تمام می‌شود که یا تمام دیسک‌ها به همین ترتیب در میله B قرار بگیرند (و میله‌های A و C خالی باشد) یا تمام دیسک‌ها به همین ترتیب در میله C قرار بگیرند (و میله‌های A و B خالی باشند).
هوشنگ برای حل کردن این معما، الگوریتم زیر را در پیش می‌گیرد. او ابتدا یک جایگشت از تمام ۶ حرکت موجود در نظر می‌گیرد (مثلاً جای‌گشت CA , AB , BC, BA , AC , CB از چپ به راست)، سپس در هر مرحله سمت‌چپ‌ترین حرکت مجاز از حرکات این جایگشت را انجام می‌دهد. علاوه بر این، او هیچ‌وقت دوست ندارد یک دیسک را در دو حرکت متوالی جابه‌جا کند و از این رو اگر یک حرکت (بعد از حرکت اوّل) از مقصد حرکت بعدی آغاز شود، او این حرکت را غیرمجاز تلقّی می‌کند. برای مثال اگر جای‌گشت نمونه گفته‌شده را روی میله‌های شکل در نظر بگیریم، اوّلین حرکت هوشنگ AB خواهد بود (چرا که CA به‌دلیل خالی بودن میله C غیرمجاز است) و حرکت دوم او AC خواهد بود: CA غیر مجاز است چون C هنوز خالی است؛ AB غیر مجاز است چون دیسک با قطر ۲ را نمی‌توان روی دیسک با قطر ۱(که در حرکت اوّل به B منتقل شده) قرار داد؛ BC نیز غیر‌مجاز است چرا که دیسک رویی B در حرکت قبل تکان خورده و هوشنگ دوست ندارد یک دیسک را در ۲ حرکت متوالی تکان بدهد، مشابهاً BA نیز غیر مجاز است و از این رو سمت‌چپ‌ترین حرکت مجاز AC است!
می‌توان اثبات کرد که الگوریتم هوشنگ همیشه پایان می‌یابد! آن‌چه از شما خواسته می‌شود این‌ است که با دانستن تعداد دیسک‌ها و استراتژی هوشنگ (جایگشتی از ۶ حرکت ممکن)، مشخص کنید که هوشنگ چند جابه‌جایی انجام می‌دهد تا بازی تمام شود.

ورودی
در سطر اوّل ورودی، تعداد آزمون‌ها داده می‌شود. سپس هر آزمون در ۲ خط داده می‌شود که خط اوّل تنها یک عدد را داشته و در خط دوم یک جایگشت از حرکات ممکن به‌صورت ۶ رشته دو حرفی (معتبر و دو به دو متمایز) داده می‌شود.

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

محدودیت‌ها
می‌دانیم 1≤n≤س30 و جواب خروجی هیچ آزمونی بیش‌تر از 10 به توان 18 نخواهد بود.

ورودی نمونه

ورودی نمونه

2
3
AB BC CA BA CB AC
2
AB BA CA BC CB AC


خروجی نمونه

خروجی نمونه

7
5