Post
by Amikae » Fri Oct 31, 2008 4:28 pm
Задача 2. ТУБИ С БЕНЗИН
На няколко различни места по околовръстното шосе на Бургас, компанията
Лукойл е оставила по една туба с бензин. Известни са разстоянията между тубите,
както и количествата бензин във всяка от тях. Автомобил, с постоянен разход на
гориво и с резервуар, който е празен в началото (и е с неограничена вместимост),
трябва да тръгне от едно от местата, където има оставена туба и да направи пълна
обиколка, като има право да ползва бензин само от оставените туби. Напишете
програма CANS.EXE, която пресмята най-малкото общо количество на бензин в
тубите, което е необходимо, за да може да се осъществи обиколката и намира
мястото на тръгване.
Входните данни се четат от текстовия файл CANS.INP. На първия му ред е
записано едно цяло положително число N (не по-голямо от 1000), което задава броя
на тубите и цялото число C (със стойност между 1 и 1000), равно на разхода за
изминаване на единица разстояние. На следващия ред са записани N на брой цели
неотрицателни числа (всяко, не по-голямо от 1000), които задават количествата на
бензин в тубите според една избрана посока на обхождане на шосето, при която
тубите получават последователните номера от 1 до N. Във входния файл следва
още един ред, на който са записани разстоянията между двойките последователно
поставени туби – първото число задава разстоянието между първата и втората туба,
второто число – разстоянието между втората и третата и т.н., а последното число е
разстоянието между последната туба и първата. Тези разстояния са цели
положителни числа, не по-големи от 1000. Навсякъде във входния файл за
разделител между две числа от един ред е използвана една шпация.
Изходните данни трябва да бъдат записани като едно цяло число в текстовия
файл CANS.OUT. Ако не е възможно да се осъществи обиколката, това число
трябва да бъде равно на търсеното минимално количество бензин. В противен
случай, трябва да бъдат изведен номерът на тубата, от която може да започне и
успешно да се извърши обиколката. Ако съществуват повече от една възможности,
трябва да се изведе най-малкият възможен номер.
Пример
CANS.INP
3 1
1 1 1
1 1 1
CANS.OUT
1