Разбор задачи F. Марфа Геннадьевна на даче

Разбор задачи A. Правильная окраска.

Предположим, что . Тогда из соотношения найдём , и тогда найдём остальные числа тройки: , , ,

Далее нужно проверить, что 0 ≤ y₂, b₂ ≤ 1. Если это не так, то положим y₂ = 1 и повторим аналогичную процедуру. Если мы опять не получили решение, то положим b₂ = 1.

Докажем единственность решения. Предположим, что, когда мы положили r₂ = 1 и y₂ = 1, в обоих случаях выполняется неравенство 0 ≤ r₂, y₂, b₂ ≤ 1. Это означает, что и . Отсюда (r₁ + 1)y₃ ≤ (y₁ + 1)r₃ и (y₁ + 1)r₃ ≤ (r₁ + 1)y₃, поэтому (r₁ + 1)y₃ = (y₁ + 1)r₃. Следовательно, в обоих случаях r₂ = y₂ = 1, поэтому оба случая тождественны.

Пример решения:

var

c1, c2, c3: array[1..3] of extended;

k: extended;

i, j: integer;

ok: boolean;

begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);

 

ok := false;

for i := 1 to 3 do

read(c1[i]);

for i := 1 to 3 do

read(c3[i]);

 

for i := 1 to 3 do

begin

if (c3[i] > 0) then

begin

c2[i] := 1;

k := (c1[i] + 1)/c3[i];

ok := true;

for j := 1 to 3 do

begin

if (j <> i) then

begin

c2[j] := k*c3[j] - c1[j];

if not ((c2[j] >= -1e-10) and (c2[j] <= 1+1e-10)) then

ok := false;

end;

end;

if ok then

break;

end;

end;

 

for i := 1 to 3 do

write(c2[i]:0:5, ' ');

 

close(input);

close(output);

end.

 

Разбор задачи С. Коктейль

 

Предположим, что i-й сок будет "самым критичным" для коктейля. Тогда мы получим г коктейля. Поэтому ответ равен минимуму данного выражения по всем i от 1 до N.

Более точные рассуждения:

Допустим, что Марфа Геннадьевна приготовила K г коктейля. Тогда этот коктейль содержит г i-го сока. Учитывая ограниченные запасы каждого сока, делаем вывод, что должны выполняться неравенства:

Выражая K, получим:

Следовательно, ответ равен .

Разбор задачи D. Государство

 

Всего братья могут завоевать 2N−k клеток. Заметим, что то, какой игрок сделает последний ход, зависит от чётности числа 2N−k. Если это число нечётное, то последний ход сделает первый игрок, и тогда второй игрок победил. Если же это число чётное, то последний ход сделает второй игрок, и тогда первый игрок победил.

Поэтому если k чётное, то выиграл первый игрок, а если нечётное, то второй игрок.

 

Разбор задачи E. Y-хромосома

 

Сначала выберем объемлющий квадрат для буквы размером k×k квадратиков, 3≤k≤N. Это можно сделать (N−k+1)² способами.

Для каждого такого квадрата выбрать маленькую диагональ можно (k−2) способами. Таким образом, ответ равен .

Ответ можно привести к другому виду: .

 

Разбор задачи F. Марфа Геннадьевна на даче

Можно доказать, что для получения оптимального разреза можно отдать каждой подруге не более двух неполных связок (к тому же так будет удобнее забрать связки домой ☺). Поэтому все связки можно расположить друг за другом так, что каждой подруге достанутся куски связок, идущие друг за другом.

Следовательно, для получения оптимального разреза нужно расположить все N связок друг за другом и разрезать эту колбаску на M равных частей, делая разрезы там, где это необходимо.