سوالات حلی نت ششم

دانلود فایل پی دی اف

(با تشکر فراوان از وبلاگ انفورماتیک)

توضیح سوال اول

امروز روز تولد خیگول، برادر کوچک خیکول است. ننه خیکول تصمیم می‌گیرد که برای این جشن شیرینی بپزد. او می‌داند که برای پخت هر شیرینی k ماده‌ی اولیه مصرف می‌شود که این میزان برای ماده‌ی i ام، ai گرم است. همچنین می‌داند که در خانه از ماده‌ی i ام bi گرم وجود دارد. حالا شما باید برنامه‌ای بنویسید که با داشتن این اطلاعات، حداکثر تعداد شیرینی ممکنی که می‌توان پخت را حساب کند. بدیهی است که تمام شیرینی‌ها باید به صورت کامل پخته شوند و در نهایت ممکن است مقداری از مواد اولیه بی‌استفاده بمانند.

ورودی:در سطر اول ورودی عدد صحیح k آمده است. (k <= 50) در سطر بعدی k عدد صحیح و مثبت a1 تا ak به ترتیب آمده اند و در سطر سوم k عدد b1 تا bk آمده اند.(ai,bi <= 1,000,000,000)

خروجی:در تنها سطر خروجی عدد مورد نظر را چاپ کنید.

ورودی نمونه

5

2 3 5 2 1

10 11 100 4 4

خروجی نمونه

2

------------------------------------------------------------------------------------------------------

توضیح سوال دوم

میشائیل شوماخر عاشق بازی کامپیوتری شده است. در قوانین آخرین نسخه‌ی این بازی آمده است:

پیست مسابقه دارای یک نقطه‌ی شروع، یک نقطه‌ی پایان، و چند نقطه‌ی سوختگیری است. مسیر خاصی در نقشه تعیین نشده و بازیکن می‌تواند آزادانه در پیتس براند و در نقاط سوختگیری باک ماشینش را پر کند. تنها هدف بازی، رسیدن از نقطه‌ی شروع به نقطه‌ی پایانی است‎!‎

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

میشائل: میکا‎!‎ میکا‎!‎ کمک‎!‎ من از بازی خسته شدم‎.

میکا: بگو ببینم اندازه‌ی باک بنزین ماشینت چقدره؟‎

میشائل: مگه مهمه؟ صبر کن... نوشته ‎1000 لیتر‎.

میکا: 1000‎ لیتر؟‎!‎ خب، معلومه که می‌گی بازی آسونه‎!‎

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

ورودی:در اولین خط ورودی N‎، تعداد نقاط پیست می‌آید. نقطه‌ی اوّل همان نقطه‌ی شروع، نقطه‌ی آخر همان نقطه‌ی پایان، و بقیّه‌ی نقاط، محل‌های سوختگیری هستند‎.پس از آن، در خط ‎i+1 اُم دو عدد اعشاری می‌آید که نشان‌دهنده‌ی مختصات نقطه‌ی iام در صفحه است‎. تمام اعداد ورودی نامنفی، و کوچکتر از ‎1000‎ هستند.

خروجی:در تنها خط خروجی، کمترین اندازه‌ی ممکن برای باک را، با ‎دقیقاً‎ یک رقم اعشار بنویسید.

ورودی نمونه

‎5

‎7.0 10

‎5.1 11

‎3 2.23

‎1 12.1

‎12 1‎

خروجی نمونه

9.1

------------------------------------------------------------------------------------------------------

توضیح سوال سوم

در کشور خیکولند، n شهر وجود دارد که بین تعدادی از آنها جاده احداث شده است. بر اثر حوادث طبیعی، امکان دارد که این جاده ها خراب شوند. می خواهیم در هر شهر شرکتی برای تعمیر جاده تاسیس کنیم. میدانیم S شرکت تعمیر جاده، با شماره های 0 تا S-1 وجود دارد ولی صنف تعمیرکنندگان جاده، قوانین عجیبی برای احداث شرکت دارد:

1- در هر شهر باید دقیقا یک شرکت احداث شود. (طبیعتاً میتوان از یک شرکت در چند شهر استفاده کرد)

2- باید بین دو شهر i و j جاده وجود داشته باشد اگر و تنها اگر مجموع شماره شرکت های واقع در این دو شهر بر S بخشپذیر شود!

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

ورودی:در خط اول به ترتیب S و n آمده است. در ادامه یک جدول n در n از صفر و یک وجود دارد. بین شهرهای i و j جاده وجود دارد اگر و تنها اگر در خانه i و j جدول یک نوشته شده باشد. (n,S <= 1000)

خروجی:در صورتیکه می‌توان با توجه به قوانین بالا شرکت ها را تاسیس کرد Yes و درغیر اینصورت No (حروف اول بزرگ و بقیه حروف کوچک) چاپ کنید.

ورودی نمونه

2 3

0 1 0

1 0 1

0 1 0

خروجی نمونه

No

توضیح سوال چهارم

ستاد هِلوکوخ

همان طور که حتما می‌دانید خیکوله امسال هم در درس ریاضی مردود شده است. او شنیده است که در جنگل‌های دور افتاده‌ی شمال خیکولند٬ کوهستانی وجود دارد که در یکی از غارهای آن هِلوکوخ استاد بزرگ ریاضی زندگی می‌کند و توانایی آن را دارد که از چوب درخت هم ریاضیدان بسازد. او که انگیزه‌ی زیادی برای قبولی در سال آینده دارد به هر نحوی شده خود را به هلوکیخ می‌رساند و از او می‌خواهد که به او ریاضی بیاموزد. هِلوکوخ برای قبول خیکوله شرطی می گذارد. او به خیکوله دو عدد a و b را می‌دهد و از او می‌خواهد که جمع اعداد فیبوناچی a اُم تا b اُم را بدست بیاورد که عدد فیبوناچی n ام به صورت زیر تعریف می‌شود:

Fn = Fn-1 + Fn-2

F0 = 1 , F1 = 1

ورودی:در تنها سطر ورودی دو عدد صحیح a و b آمده‌اند (1 <= a<= b <= 1000000000)

خروجی:شما در تنها سطر خروجی باید باقی‌مانده‌ی عبارت Fa+Fa+1+…+Fb بر ۱۰۰۰۰۰۰۰۰۷ را چاپ کنید.

ورودی نمونه

2 5

خروجی نمونه

18

-----------------------------------------------------------------------------------

توضیح سوال پنجم

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

هدف هر دزد فرار از دست تمام پلیس ها است و هدف پلیس دستگیری حداقل یکی از دزدهاست. یک دزد در صورتی دستگیر می شود که با یک پلیس در یک لحظه در یک تقاطع باشد.

دزدها از شما خواسته اند برنامه ای بنویسید که محل قرارگیری اولیه دزدها و پلیس ها را بگیرد و اعلام کند که آیا همگی آنها می توانند از دست پلیس ها فرار کنند یا خیر!

ورودی:در خط اول n و m به ترتیب تعداد پلیس ها و دزدها آورده شده است. در n خط بعدی، در هر خط دو عدد صحیح می آید که مختصات پلیس ها را بیان می کند و به همین ترتیب در m خط بعد از آن مختصات دزدها آمده است. (n,m <= 1000)

تمامی مختصات‌ها کمتر از 109 است و فاصله تمام خیابان های افقی و عمودی با هم برابر است.

خروجی:اگر همگی دزدها میتوانند فرار کنند در خروجی Yes و در غیر اینصورت No (با رعایت بزرگی و کوچکی حروف) چاپ کنید.

ورودی نمونه

3 1

-1 0

1 0

0 1

0 0

خروجی نمونه

Yes

منبع:rivalry.blog.ir