12 грудня 2010 р. ІІ етап Всеукраїнської учнівської олімпіади з інформатики для 8-11 класів

1. Зернини

Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.

У банці знаходяться білі та чорні зернини. Кожного разу з банки виймають навмання дві зернини. Якщо вони однакового кольору, то їх викидають, а до банки кладуть чорну зернину (чорних зернин у достатній кількості). Якщо ж зернини різного кольору, то чорну викидають, а білу повертають до банки. Ці дії повторюють, доки не залишиться одна зернина.

Завдання Напишіть програму, яка за відомою кількістю чорних та білих зернин визначає колір останньої зернини.

Вхідні данні. У єдиному рядку записані два числа – кількість білих та чорних зернин.

Вихідні данні. Єдиний рядок вихідного текстового файлу має містити колір зернини, що залишилася: white – якщо зернина біла, black – якщо зернина чорна.

Приклад вхідних і вихідних даних:

Input.txt	Output.txt
4 3	black

Авторський Розв'язок  Pascal

На розв'язання задачі впливає тільки непарність білих зернинок, оскільки після кожного кроку кількість білих зернинок або не зміниться або зменшиться на 2:

If Odd(White) then write('white') else write('black')

Program zerninu;

var a,b:integer;

begin

readln(a,b);

if odd(a) then write ('white') else write('black');

readln;

end.

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

Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.

Максимальний час роботи на одному тесті: 5 секунд.

Дано N цілих чисел.

Завдання. Необхідно вибрати з N цілих чисел три таких числа, добуток яких максимальний.

Вхідні данні. Перший рядок вхідного файлу містить одне число N –  кількість чисел у послідовності (3£ N £10⁶). У друго­му рядку записано саму послідовність: N цілих чисел, які за модулем не перевищують 30000.

Вихідні данні. У вихідний файл виведіть три шуканих числа в довільному порядку. Якщо існує декілька різних трійок чисел, які дають максимальний добуток, то виведіть довільну з них.

Приклад вхідних і вихідних даних:

Input.txt	Output.txt
9	9 10 9
3 5 1 7 9 0 9 –3 10
3	–5 –30000 –12
–5 –30000 –12

Ідея розв'язання. Найбільш очевидний спосіб – це перебирати всі можливі трійки чисел і вибрати з них ту, що має максимальний добуток. Але цей спосіб має декілька недоліків. По-перше, 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. Фрагмент програми буде таким:

Read(x);

if x>max_1 then

    begin

         max_3:=max_2;

max_2:=max_1;

max_1:=x

         end

    else if x>max_2 then

         begin

             max_3:=max_2;

max_2:=x

end

    else if x>max_3 then max_3:=x;

Оскільки в послідовності можуть бути додатні та від'ємні числа, а добуток двох від'ємних чисел є число додатне, то потрібно шукати ще й два найменших числа min_1 та min_2. Після завершення зчитування даних та визначення трьох найбільших та двох найменших чисел потрібно порівняти добутки min_1*min_2 та max_2*max_3.

Авторський Розв'язок  Pascal

Program maks;

var k,n,x,max1,max2,max3,min1,min2:longint;

begin

read(n);

k:=1;

while  k<=n do

begin

 read(x);

if x > max1 then

begin

max3:=max2;

max2:=max1;

max1:=x ;

end

else if x>max2 then

  begin

  max3:=max2;

  max2:=x;

  end

else if x>max3 then max3:=x;

if x<min1   then

begin

min2:=min1;

min1:=x;

end

else

if x<min2 then  min2:=x;

k:=k+1;

end;

if( min1*min2) >(max2*max3) then write(max1,' ',min1,' ',min2)

else write(max1,' ',max2,' ',max3);

readln;

end.

3. Купівля квитків

Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.

Максимальний час роботи на одному тесті: 5 секунд.

Максимальний об'єм використаної пам'яті: 4 Мбайти.

За квитками на прем'єру нового мюзиклу зібралася черга з N осіб, кожна з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків просувався дуже повільно, від чого «клієнти» черги впадали у відчай. Найкмітливіші швидко примітили, що, як правило, декілька квитків у одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поряд, віддавати гроші першому з них, щоб він купив квитки на всіх.

Але для боротьби зі спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 особи, які стоять поряд.

Відомо, що на продаж і особі з черги одного квитка касир витра­чає А_і секунд, на продаж двох квитків – В_і секунд, трьох квитків – С_i секунд.

Завдання. Напишіть програму, яка визначить мінімальний час, за який можна було б обслужити всіх покупців.

Зверніть увагу, що квитки на групу людей, що об'єднались, завжди купує перший із них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).

Вхідні данні. Перший рядок вхідного файлу містить єдине число N – кількість покупців в черзі (1£N£5000). У кожному з наступних N рядків записано трійку натуральних чисел А_і, B_i, С_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

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