Задача Кіндер. Олімпіада з інформатики

Задачі олімпіад з інформатики

Задача Kinder. Петрик П’яточкін вирішив подарувати своїм  K друзям на свято по кіндер-сюрпризу з іграшкою всередині.  Кожен кіндер-сюрприз містить одну  іграшку – машинку, ляльку або робота. Петрик хоче, щоб його друзі не посварились між собою, тому вони повинні отримати однакові іграшки.  У  крамниці  є  рівно C  кіндер-сюрпризів   з  машинками, D  з  ляльками  і R  з  роботами,  але невідомо, яка  іграшка знаходиться в якому   кіндер-сюрпризі. Яку найменшу  кількість    кіндер-сюрпризів  повинен придбати Петрик, щоб серед них гарантовано було хоча б K однакових з одним видом іграшки?

Технічні умови. Програма Kinder читає з клавіатури натуральні числа K, C, D, R 

(1≤ K, C, D, R ≤1000000)  і  виводить  на  екран  мінімальну  кількість  кіндер-сюрпризів  або 0,  якщо придбати неможливо.

Приклади. А)Введення  5 6 7 10    Виведення   13. Б) Введення 16 10 7 5  Виведення 0.

Пояснення.

Нехай  К=2    С=10   D=8   R=9.  У найгіршому випадку будемо виконувати

вибір кіндер-сюрпризів:     С=1       D=1    R=1   С= 1, отже, є дві  однокові іграшки. Тому відповідь  4 кіндер-сюрпризи .

Якщо найбільше з чисел C,D,R менше за K – відповідь 0

Інакше, ті числа, що менші за K додаються до відповіді повністю. Решта чисел додає до відповіді K-1. Після цього варто додати до відповіді 1 (саме цей подарунок і стане K-им)

Розв’язання.

program kinder;

var res,k,c,d,r,min,max,mid:longint;

begin

readln(k,c,d,r);

if c>d

   then max:=c

   else max:=d;

if max<r

   then max:=r;

if c<d

   then min:=c

   else min:=d;

if min>r

   then min:=r;

mid:=c+d+r-max-min;

if k<=min

   then begin

        res:=3*k-2;

        end

   else begin

        if k<=mid

           then begin

                res:=min+2*k-1;

                end

           else begin

                if k<=max

                   then res:=min+mid+k

                   else res:=0;

                end;

        end;

writeln(res);

end.

Задача Foto. Василько  отримав завдання розмістити на шкільному сайті фото з новорічного свята. Василько знав,  що  фото  слід «вписати»   в  заданий   прямокутник,  тобто   фото  зменшується (або збільшується)  таким  чином,  що  одна  з  його  сторін  стає  точно  рівною  відповідній  стороні заданого  прямокутника,  а  друга  сторона  підбирається   так,  аби  співвідношення  сторін отриманого  зображення  було  як можна  ближче  до  оригіналу. При  цьому  розміри  отриманого зображення  повинні  бути  найбільш  можливими,   але  не  повинні   при  цьому   перевищувати  розміри   прямокутника.   Всі   розміри  повинні  бути  натуральними  числами.  Зрозуміло,  що повертати зображення не можна. 

 Технічні  умови. Програма Foto  читає  з  пристрою  стандартного  введення  4  цілих  числа A,

B,С,D (1≤ A;B;C;D ≤ 10000), где A и B — ширина і висота початкового фото, а C и D — ширина і висота прямокутника,  в який це фото слід помістити. Програма виводить на екран 2 цілих числа

– ширину та висоту вже обробленого зображення.

Приклади

Введення                                Виведення

1280 720 640 480                   640 360

640 480 1280 720                   960 720

Пояснення. Розглянемо два випадки: 1) a=c. Звідси маємо, що d=b*c/a.

Переберемо усі числа проміжку [b-3;b+3] і спробуємо кожен із них як величину другої сторони. Аналогічно розглядається випадок b=d.

Розв’язання.

program fototask1;

var k,check1,check2:real;

    a,b,c,d,p:longint;

begin

Read(a,b,c,d);

k:=a/b;

if (round(k*d)<=c) then

   begin

   p:=trunc(k*d);

   If p=0 then inc(p);

   check1:=abs(k-(p+1)/d);

   check2:=abs(k-p/d);

   If check1>check2 then writeln(p,' ',d)

   else writeln(p+1,' ',d);

   end

else

   begin

   p:=trunc(c/k);

   If p=0 then inc(p);

   check1:=abs(k-c/(p+1));

   check2:=abs(k-c/p);

   if check1>check2 then writeln(c,' ',p)

   else writeln(c,' ',p+1);

   end;

end.

Задача  Balls2

На столі розкладено N червоних та   M синіх  кульок. Двоє  грають в  гру, хід  гравця полягає в

тому, щоб взяти дві довільні кульки  і покласти на стіл замість забраних  червону кульку, якщо

він забирав кульки різного кольору,  або кульку синього кольору, якщо забирав кульки одного

кольору. Гравці ходять по черзі, гра  триває поки  не залишиться 1 кулька.  Перемагає перший

гравець,  якщо  остання  кулька  виявилась  червоного  кольору,  якщо  ж   синього -  другий. 

Дізнайтеся  для заданої кількості  кульок, хто виграє при оптимальній грі обох гравців.

Технічні умови. Програма Balls2 читає  з клавіатури єдине число Т – кількість тестів (1 ≤  T 

≤500). В наступних  Т рядках  задано по два цілих числа   N і M 

(1 ≤  N +M,  0 ≤  N;M  ≤  10⁹)

Програма Balls2   виводить   для кожного тестового прикладу у новому рядку  1, коли виграє 1-

й гравець і 2,  коли виграє другий  

Приклад

Введення     Виведення

3                   1

1 0               2 

0 1                1  

1 1

Пояснення.

 Balls2

Нехай у нас є N червоних кульок та M синіх

Розглянемо усі можливі переходи:

1)    Взяти дві червоні кульки: переходимо у стан N-2, M+1

2)    Взяти дві сині кульки: переходимо у стан N, M-1

3)    Взятии різні кульки: переходимо у стан N, M-1

Як бачимо, парність N завжди залишається однаковою, а M – змінюється на протилежну.

З іншого боку, якщо в кінці гри M парне – переміг перший гравець, інакше – переміг другий.

За всю гру буде зроблено N+M-1 хід.

Отже парність числа M в кінці буде рівна (M+N-1+M)%2=(2M+N-1)%2=

=(N-1)%2, де % - операція взяття остачі від ділення.

Отже, якщо N парне, число M в кінці буде непарне, і виграє другий гравець. Інакше, виграє перший гравець.

Задача Queens. Ферзь – шахова фігура, яка ходить по горизонталі, вертикалі або діагоналі на довільну кількість  клітинок.  Клітинка  безпечна,  якщо  на  ній  не  стоїть ферзь  і  коли жоден ферзь  не може  в  ній опинитись  за  один  хід.  На  квадратній шахівниці  розміщені ферзі.  Порахуйте  на  ній  кількість  безпечних клітинок.

Технічні  умови.  Програма  Queens  читає  з  клавіатури  через  пропуск  два  числа –  розмір

шахівниці N  та  кількість ферзів K (1≤N≤10000, 1≤K≤100000). Далі програма читає K рядків по

два розділених пропуском натуральних числа i та j, не більших N – номери рядків і стовпчиків,

на яких стоїть відповідний ферзь. Рядки  і стовпчики нумеруються від 1 до N цілими числами.

Жодні  два  ферзі  не  стоять  на  одній  клітинці.  Програма  виводить  на  екран  єдине  число –

кількість безпечних клітинок.

 Приклад. Введення    3 2     3 2    2 3    Виведення    1

Пояснення.Queens. Розглянемо всі ферзі. Заведемо 4 масиви. Перший відповідає за номери горизонталей, які під биттям, другий – за номери вертикалей, третій – за номери діагоналей, нахилених вліво (задаються різницею координат x-y), четвертий – номери діагоналей, нахилених вправо (задаються різницею координат x+y). Тепер розглянемо всі клітинки і перевіримо, чи б’ють її по горизонталі, вертикалі і діагоналі (за допомогою описаних вище масивів). Якщо клітинку не б’ють – оновимо відповідь

Розв’язання.

program task;

type mas=array[-100000..100000] of byte;

var i,j,m,k,n,x,y:longint;

    s:longint;

    f:boolean;

    hor,ver,dia1,dia2:mas;

begin

fillchar(hor,sizeof(hor),0);

fillchar(ver,sizeof(ver),0);

fillchar(dia1,sizeof(dia1),0);

fillchar(dia2,sizeof(dia2),0);

read(n,m);

for i:=1 to m do

    begin

    read(x,y);

    hor[x]:=1;

    ver[y]:=1;

    dia1[x+y]:=1;

    dia2[x-y]:=1;

    end;

s:=n*n;

for i:=1 to n do

    for j:=1 to n do

        begin

        if (hor[i]>0) or

           (ver[j]>0) or

           (dia1[i+j]>0) or

           (dia2[i-j]>0)

             then dec(s);

        end;

writeln(s); end.