1 Відповідь від vladnembo

(7 відповідей, залишених у Pascal/Delphi)

у мене э ідея для розвязування-
Ідея розв'язання. Розв'яжемо задачу методом динамічного програмування. Нехай 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.

Перейти до форуму: Pascal/Delphi

2 Відповідь від vladnembo

(7 відповідей, залишених у Pascal/Delphi)

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

Перейти до форуму: Pascal/Delphi

3 Відповідь від vladnembo

(7 відповідей, залишених у Pascal/Delphi)

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

Перейти до форуму: Pascal/Delphi

4 Тема від vladnembo

(7 відповідей, залишених у Pascal/Delphi)

Задача за 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   

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

Перейти до форуму: Pascal/Delphi