1

Тема: Олімпіадна задача 9 клас

Задача за 2010 рік з інформатики не знаю як зробити  якщо можна зробіть у pascal abc або pascal turbo або в АЛГО
БУДУ ДУЖЕ ВДЯЧНИЙ
3. Купівля квитків


Ім'я вхідного файлу: Input.txt.
Ім'я вихідного файлу: Output.txt.
Максимальний час роботи на одному тесті: 5 секунд.
Максимальний об'єм використаної пам'яті: 4 Мбайти.

За квитками на прем'єру нового мюзиклу зібралася черга з N осіб, кожна з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків просувався дуже повільно, від чого «клієнти» черги впадали у відчай. Найкмітливіші швидко примітили, що, як правило, декілька квитків у одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поряд, віддавати гроші першому з них, щоб він купив квитки на всіх.
Але для боротьби зі спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 особи, які стоять поряд.
Відомо, що на продаж і особі з черги одного квитка касир витра¬чає Аі секунд, на продаж двох квитків – Ві секунд, трьох квитків – Сi секунд.
Завдання. Напишіть програму, яка визначить мінімальний час, за який можна було б обслужити всіх покупців.
Зверніть увагу, що квитки на групу людей, що об'єднались, завжди купує перший із них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).
Вхідні данні. Перший рядок вхідного файлу містить єдине число N – кількість покупців в черзі (1N5000). У кожному з наступних N рядків записано трійку натуральних чисел Аі, Bi, Сi. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються, починаючи від каси.
Вихідні данні. Вихідний файл містить одне число – мінімальний час у секундах, за який можна було б обслужити всіх покупців.
Приклад вхідних і вихідних даних:

Input.txt    Output.txt
5                    12
5 10 15   
2 10 15   
5 5 5   
20 20 1   
20 1 1   
2                    4
3 4 5   
1 1 1   

Наперед дякую

2

Re: Олімпіадна задача 9 клас

Допоможіть будь-ласка

3

Re: Олімпіадна задача 9 клас

Що ніхто не може розвязати?

Re: Олімпіадна задача 9 клас

vladnembo написав:

Що ніхто не може розвязати?

А можливо ніхто не хоче розв`язувати тому, що ви навіть не сказали, чи є якісь напрацювання чи ні.
Більшість юзерів, які просять розв`язати задачі, навіть не розуміють елементарних речей, а все писати за вас, ніхто не хоче.

5

Re: Олімпіадна задача 9 клас

у мене э ідея для розвязування-
Ідея розв'язання. Розв'яжемо задачу методом динамічного програмування. Нехай Time[1..N] – масив, у якому зберігатиметься мінімальний час, тоді Time [і] – мінімальний час обслуговування перших і покупців.
Розглянемо варіант, коли в черзі один покупець. Очевидно, що для N = 1, мінімальним часом буде А [1], отже, Time[1] = А [1].
Для N=2 можливі два варіанти: перший – кожен з двох покупців купує квитки окремо, тоді загальний час придбання квитків дорівнює А[1] + А[2], і другий, коли вони об'єднаються, щоб купити квитки разом, тоді час становитиме В[1] секунд. Зрозуміло, що вибирати потрібно варіант з меншим часом. Отже, для N =2 мінімальний час становитиме
Time[2]=min(А[1] + А[2],В[1]),
де min – функція знаходження найменшого з двох чисел.
При N = 3 можливі три випадки:
-    третій покупець купує квиток самостійно, тоді мінімальний час – це найменший час купівлі для двох (Time[2]) і час купівлі третім самостійно
(А[3] – Time[2] + А[3]);
-    третій і другий домовилися про купівлю квитків разом (В[2]), тоді перший купує самостійно (А [1]) і загальний час купівлі становитиме А[1] + В[2];
-    всі троє домовилися про спільну купівлю, тоді перший в черзі купує три квитки (С[1]).

З усіх можливих варіантів виберемо мінімальний час. Отже,
Time[3] = min_3(Time[2] + А[3],А[1] + В[2],С[1]),
де min_3 – функція знаходження найменшого з трьох. Якщо ж за¬стосуємо раніше згадану функцію знаходження найменшого з двох чисел min, то маємо:
Time[3] = min(Time[2] + А[1],min(A[1] + В[2],С[1])).
Запишемо аналогічну формулу для черги з чотирьох людей (N = 4):
Time[4] = min_3(Time[3] + А[4],Time[2] + В[3],Time[1] +С[2]),
де Time[3] + А[4] – четвертий купує самостійно, Time[2] + В[3] – чет¬вертий з третім об'єдналися, Time[1] + С[2] –  четвертий, третій і дру¬гий об'єдналися.
Тепер можемо записати загальну формулу:
Time[і] = min_3(Time[і -1] + А[і],Time[і -2] + В[і -1],Time[і -3] +С[і - 2])
або
Time[і] =min(Time[і-1] + А[і],min(Time[і-2] + В[і-1], Time[і-3]+С[i-2])).
Розглянемо  покрокове заповнення  масиву Time для  першого наведеного в умові тесту:
1) Time[1] = А[1] = 5;
2)     Time[2] = min(А[1] + А[2],В[1])=min(5 + 2,10) = 7;
3)     Time[3] = min_3(Time[2] + А[3],А[1] + В[2],С[1]) = min_3(7+5, 5+10, 15) = 12;
4) Time[4] = min_3(Time[3] + А[4],Time[2] + В[3],Time[1]+С[2]) = =min_3(12+20, 7+5, 5+15) = 12;
5) Time[5] = min_3(Time[4] + А[5], Time[3] + В[4], Time[2] + С[3]) =
= min_3(12 + 20, 12 + 20, 7 + 5) = 12.

Re: Олімпіадна задача 9 клас

Тоді, що саме у вас не виходить ?

7

Re: Олімпіадна задача 9 клас

Щось або я не зрозумів умови задачі, або...

значить N*min(A,B/2,C/3)+max(A,B,C)>=tmin>=N*min(A,B/2,C/3).
А точніше, якщо min(A,B/2,C/3)=А, то tmin=N*A,
min(A,B/2,C/3)=B/2, то Якщо N ділиться на 2, то tmin=N*В/2, якщо не ділиться, то tmin=(N-3)*В/2+min(B+A,C)
Те саме для min(A,B/2,C/3)=C/3, для остачі 0 -> tmin=N*C/3, 1-> tmin=(N-4)*C/3+min(C+A,2*B), 2->  tmin=(N-2)*C/3+min(2*A,B)

8 Востаннє редагувалося Voron (10.01.2013 01:01:18)

Re: Олімпіадна задача 9 клас

На мою думку вам потрібен алгоритм Дейкстри - http://uk.wikipedia.org/wiki/Алгоритм_Дейкстри
Суть така, створюємо масив значень часу за який ми можемо дійти до певної людини у черзі.
Починаємо з першої людини, дивимось за скільки часу ми можемо дійти до 1, 2, 3-ої людини за нею, порівнюємо ці значення зі значеннями які вже є в масиві, якщо час менший записуємо в масив. По закінчені циклу отримаємо мінімальний час обслуговування черги.
Графічно робота алгоритму для вашого прикладу виглядала б десь так: http://clip2net.com/clip/m40453/thumb640/1357768012-2013-01-09-234645_499x102_scrot-5kb.png
Враховуючи ліміт пам'яті, масив потрібно брати з 4 елементів (поточна людина + 1, 2 та 3-тя за нею)

Подякували: Ярослав1