Програмування 2010

2.  Найбільший добуток (25 балів)

Ідея розв'язання. Найбільш очевидний спосіб – це перебирати всі можливі трійки чисел і вибрати з них ту, що має максимальний добуток. Але цей спосіб має декілька недоліків. По-перше, 1000000 елементів не поміститься в пам'яті; по-друге, оскільки для перебору потрібно організувати три вкладених цикли, то таке розв'язання спрацює приблизно для N<100, оцінка такого алгоритму дорівнює N³; по-третє, елементи послідовності за модулем можуть досягати 30000, а їх добуток може вийти за межі типу LongInt.

Розглянемо більш цікаве розв'язання. Якби всі числа були додатними або всі від'ємними, то, очевидно, нам потрібно було б знайти три найбільших числа, що легко організувати під час зчитування даних з файлa. Єдине, на що потрібно звернути увагу, – це переміщення значень максимальних елементів «зверху донизу»: нехай max_1 – перший максимум, а max_2 і max_3 – відповідно другий та третій максимуми, тоді якщо на деякому кроці ми зчитали із файла число х, яке більше за max_1, то його потрібно надати max_1, попереднє значення max_1 потрібно перемістити в max_2, а значення max_2 – в max_3. Якщо ж ми зчитали число, що більше за max_2, але менше за max_1, то його потрібно надати max_2, а попереднє значення max_2 потрібно перемістити в max_3. Якщо ж зчитане число більше за max_3, але менше за max_2, то надати його max_3. Фрагмент програми буде таким:

program zad;

var

A: array [1..100] of integer;

i,j, par,N : integer;

input, output: Text;

begin

  Assign (input,'input.txt');

  Reset (input);

  read (input,N);//

  for I:=1 to N do // запись данных в масив

  read (input,A[i]);

  for I:=1 to N-1 do // сортировка за убыванием

   for j:=i+1 to N do

     if A[i]< A[j] then

             begin

              par:=A[j];

              A[j]:=A[i];

              A[i]:=par;

             end;

  Assign (output,'output.txt');

  Rewrite (output);         

     if A[n]*A[N-1]> A[1]*A[2] then Write (output,A[n],' ',A[N-1],' ' ,A[1]) else Write (output,A[1],' ',A[2],' ',A[3],' ');

    Close(input);

    Close(output);

end.

3. Купівля квитків (30 балів)

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