Ще ти разясня условието (тъй като половината ти пост е само повтарянето му ;р). Нищо не трябва да въвеждаш. Всички данни са въведени във файла CANS.INP, от който трябва да се чете. Това, че числата са отделени със шпации, ще ти укаже как да четеш числата (да кажем, че за смисловото решение това не е важно).
Имаш един ред с общи данни - броят на тубите и разхода за 1км.
После имаш един ред с количеството бензин във всяка туба. Всичко това сложно обяснение за посоката означава просто, че тубите са номерирани от 1 до N и ти трябва да използваш тази номерация в отговора. На третия ред са разстоянията между така номерираните туби.
Задачата е да намериш туба, от която като тръгнеш, бензинът да ти стигне за цялото шосе. Ако това не е възможно от никоя туба, трябва да напишеш минималното количество бензин, нужно за цялата обиколка (това е съвсем очевидно как се смята).
Ще разясня примера: имаш 3 туби и 1км харчи 1л бензин.
В всяка от трите туби имаш по 1л бензин и между тубите има по 1км разстояние.
При тази постановка е очевидно, че от която и туба да тръгнеш, бензинът ще ти стигне. Ето защо отговорът е тубата с най-малък номер (както е указано в условието, ако има няколко възможности), която е номер 1.
Пример, в който няма решение:
3 2
1 2 1
1 1 1
тук е същото, но 1км харчи 2л бензин. Ще стигнеш донякъде само ако тръгнеш от туба номер 2 - бензинът ще стигне до туба номер 3. Но оттам до туба номер 1 бензинът не стига. Следователно в този вариант задачата няма решение и ти трябва да напишеш като отговор числото 6 - това са литрите бензин, които ще ти трябват, за да обходиш пистата от три километра (тук доста подсказвам как се пресмята това количество бензин).
Задачата е доста улеснена от факта, че единствения ти възможен маршрут е кръгов, т.е. трябва само да събираш количества бензин. Можеше тубите да са свързани по произволен начин и щеше да е доста по-интересно
В момента задачата се решава с прости цикли, а още по-лесното е, че решението изисква най-малкият номер на туба, от която ще стане обиколката, та можеш да спреш веднага като го намериш
Та сега вече можеш ли да направиш алгоритъм
).
?
Никъде не можеш да намериш и хинт кога смятат да го качат ...