Время на выполнение заданий – 180 минут.
Максимальный балл - 100
Задача 1 (40 баллов)
Решение
Для начала заметим, что 1 фунт равен 16*7000 гранам, поэтому цены фунтов после ввода стразу можно привести в соответствие с рецептом, разделив на это число. Цена грана может быть нецелым числом!
Теперь нетрудно найти стоимость N ингредиентов для 7 порций:
SUM := 0;
для i от 1 до N:
SUM := SUM + цена *количество.
Разделив полученное число на 7, получим стоимость одной порции.
Любая замена ингредиентов может увеличить или уменьшить стоимость салата.
Для решения задачи нужно найти и применить "выгодные" замены.
Выгодность замены можно вычислить как разницу между ценой ингредиента (цена * количество) и ценой возможной замены (цена замены * требуемое количество замены).
Требуемое количество замены рассчитывается по формуле
требуемое количество замены = количество / заменяемое количество
(пример: если 5 граммов ингредиента можно заменить на один грамм "замены", то для 20 граммов ингредиента понадобится 4 грамма "замены"; это верно и для гранов, и для фунтов, и для тонн).
Программа может выглядеть, например, так (на языке программирования Паскаль):
program Salat;
const FUNT = 16*7000{гранов};
var
N: integer; { количество ингредиентов }
CENY: array [1..200] of real; { цены ингредиентов - 1 фунта, 1 грана }
KOLICH: array [1..200] of real; { количества ингредиентов в салате по рецепту }
ZAMENY: array [1..200] of real; { номера ингредиентов, которыми можно заметить... }
SKOLKO: array [1..200] of real; { сколько граммов... можно заменить на один грамм... }
CenaSalata, CenaBezZameny, CenaZameny, Vygoda : real;
OPT: array [1..200] of real; { количества ингредиентов в оптимизированном салате }
NomerZameny, i: integer;
begin
readln(N);
CenaSalata := 0;
for i:=1 to N do begin
readln(CENY[i], KOLICH[i], ZAMENY[i], SKOLKO[i]);
CENY[i]:=CENY[i]/FUNT; { цена одного грана }
CenaSalata := CenaSalata + KOLICH[i]*CENY[i];
OPT[i] := KOLICH[i]
end;
writeln ( "Цена продуктов для одной порции салата: ", CenaSalata/7,
" Цена продуктов для семи порций салата: ", CenaSalata);
{ ползадачи решено! :) }
{ вычисляем выгодность замен и применяем их, если это имеет смысл: }
K:=0;
for i:=1 to N-1 do
if ZAMENY[i]>0 then begin
CenaBezZameny := CENY[i]*KOLICH[i];
NomerZameny := ZAMENY[i];
CenaZameny := CENY[NomerZameny]*KOLICH[i]/SKOLKO[i];
Vygoda := CenaZameny - CenaBezZameny;
if Vygoda>0 then begin
CenaSalata := CenaSalata-Vygoda;
{ + запомнить, что поменялось в рецепте! }
OPT[i] := OPT[i] - KOLICH[i];
OPT[NomerZameny] := OPT[NomerZameny] + KOLICH[i]/SKOLKO[i]
end end;
{ и вывод результатов второй половины задачи }
writeln ("Минимальная цена набора продуктов для семи порций салата: ", SUM);
for i:=1 to N-1 do writeln ("Ингредиент ", i, ": ", OPT[i]);
end.
Ответ на вопрос
Если рецепты неволшебных салатов нас тоже устраивают (например, можно заменить клубнику малиной, а потом ВСЮ малину огурцами), то
1. Все замены сделать в одном цикле невозможно (например, после замены малины огурцами, в рецепте снова появится малина, заменившая клубнику).
2. Кроме того, из того, что замена выгодна, не следует, что она имеет смысл, и наоборот (например, морковь не следует заменять более дешевым картофелем, а лучше заменить более дорогой свеклой, которая потом заменится совсем дешевой солью).
Такая задача требует совсем другого, рекурсивного алгоритма решения.
Указания по оцениванию | Баллы |
Программа (алгоритм на языке программирования из школьной программы) составлена | +30 |
Алгоритм составлен, но не на языке программирования | +25 |
Предложены алгоритм и программа, логически не соответствующие друг другу | +25 (оценивается только алгоритм) |
Правильный ответ на вопрос: потребуются существенные изменения | +5 |
Правильный ответ на вопрос обоснован примерами возникающих проблем. Или указано, что понадобится рекурсия. | +5 |
Ошибки в алгоритме: | |
Ввод данных принципиально не соответствует условию задачи | -5 |
Выводимая информация принципиально не соответствует требуемой | -5 |
Граны и фунты не переведены друг в друга или переведены неправильно | -5 |
Испорченный массив данных при разработке альтернативного рецепта (не использован дополнительный массив) | -5 |
Перепутаны деление и умножение при вычислении количества заменяющего ингредиента | -5 |
Ошибки в границах циклов | по -2 |
Прочие существенные ошибки в логике решения задачи | по -2 |
Лишние циклы или вычисления (например, перевод в граммы или из граммов) | -2 |
Ошибки, касающиеся примененного языка программирования (например, неописанные переменные в программе на Паскале) | от -1 до -5 |
Алгоритм записан/нарисован небрежно, его понимание требует заметных усилий | -5 |
Грамматические ошибки в текстах (не в алгоритме) | -5 |
Итоговая оценка меньше 0 или больше 40 заменяется на 0 или 100, соответственно.
Задача 2 (40 баллов)
Составьте программу (алгоритм), которая читает из стандартного входного файла число - цену (в копейках) одной порции Волшебного Салата и печатает эту же цену в рублях и копейках. В случае нецелого числа копеек цену следует округлить "вверх", чтобы полученной суммы денег наверняка хватило на порцию.
Справится ли Ваша программа с ценами в сотни миллиардов копеек?
Что придется изменить в Вашей программе, чтобы продать ее в Тунис, где используются динары и миллимы (1 динар = 1000 миллимов)?
Могли бы Вы написать программу для копеек так, чтобы для продажи в Тунис в ней достаточно было изменить всего три константы? Константы какого типа (или каких типов)?
Решение
Ввод вещественного числа - конечно, не проблема.
Введя, сразу округлим число копеек, иначе в случае, скажем, 13 р. 99,1 к. получить 14 рублей из 13 будет сложнее:
копейки := ОкруглитьВверх(копейки).
Проблема в том, что нам нужно не просто округлить, а округлить непременно вверх, а встроенные функции большинства языков программирования округляют либо вниз, либо «математически».
Можно, конечно, зная особенности таких функций, решить задачу разными способами, но хотелось бы, чтобы решение было не только корректным, но и понятным.
Простое решение с использованием любой функции округления:
округленно := ОкруглитьКакНибудь(копейки);
если округленно<копейки то округленно := округленно+1;
Теперь решим, есть ли в цене рубли:
рубли := ОкруглитьВниз(округленно/100);
Округлить вниз не труднее, чем вверх. Кроме того, во многих языках программирования есть деление нацело, и на Паскале, например, для "integer округленно" достаточно написать
рубли := округленно div 100;
Если рублей больше нуля, распечатаем их, иначе просто пропустим.
Теперь разберемся с копейками:
копейки := округленно mod 100;
или копейки := округленно - рубли*100;
Не печатать копейки, если их нет, было бы неправильным решением, так как в случае нулевой цены программа не напечатает вообще ничего, и о нулевой цене никто не догадается.
Поэтому мы напечатаем копейки, если хотя бы одно из двух утверждений "копеек не 0" и "рублей 0" истинно:
если копейки > 0 или рубли = 0 то напечатать копейки;
Собираем все вместе и на Паскале получается примерно такая программа:
program rubokop;
var
cena : real;
okrugleno, rubli, kopeyki : integer;
begin
read(cena);
okrugleno := round(cena);
if okrugleno <cena then okrugleno := okrugleno +1;
rubli := okrugleno div 100;
if rubli>0 then write (rubli, " p. ");
kopeyki := okrugleno mod 100;
if kopeyki>0 or rubli=0 then write (kopeyki, " к.")
end.
Ответы на вопросы:
1. Справится, если сотни миллиардов могут быть представлены в типе данных, используемом в алгоритме для целых чисел.
Если алгоритм реализован на Паскале с типом integer, то ответ - не справится.
Если алгоритм записан без привязки к конкретной системе программирования, то ответ - справится.
2. Придется везде заменять константу 100 на 1000, обозначения рублей и копеек на тунисские обозначения динаров и миллимов.
3. Нужно определить и потом заменять три константы - целую или вещественную (для пересчетов рубли-копейки) и две строковые или символьные (для обозначения рублей и копеек).
Указания по оцениванию | Баллы |
Программа (алгоритм на языке программирования из школьной программы) составлена | +25 |
Алгоритм составлен, но не на языке программирования | +20 |
Предложены алгоритм и программа, логически не соответствующие друг другу | +20 (оценивается только алгоритм) |
Обоснованный ответ на вопрос 1 | +5 |
Правильный ответ на вопрос 2 | +5 |
Правильный ответ на вопрос 3 | +5 |
Неправильные ответы на вопросы | по -2 |
Использование обозначений "м." и "д." в ответе на вопросы | -2 |
Ошибки в алгоритме: | |
Ввод данных принципиально не соответствует условию задачи | -2 |
Выводимая информация принципиально не соответствует требуемой | -2 |
Округление вверх реализовано неправильно | -2 |
Количество рублей или копеек вычисляется неправильно | -10 |
Можно подобрать пример, когда в результате окажется 0 рублей | -5 |
Можно подобрать пример, когда в результате окажутся рубли и 0 копеек | -5 |
Прочие существенные ошибки в логике решения задачи | по -2 |
Лишние вычисления | -2 |
Ошибки, касающиеся примененного языка программирования (например, неописанные переменные в программе на Паскале) | от -1 до -5 |
Алгоритм записан/нарисован небрежно, его понимание требует заметных усилий | -5 |
Грамматические ошибки в текстах (не в алгоритме) | -5 |
Итоговая оценка меньше 0 или больше 40 заменяется на 0 или 40, соответственно.
Задача 3 (20 баллов)
Ответ: 0
Решение
При каждом ходе робота сумма координат (номер по вертикали и номер по горизонтали) клеток, откуда и куда он сделал шаг, меняется с четной на нечетную или с нечетной на четную. Чтобы посетить по одному разу все клетки, ему нужно сделать 255 ходов, значит, он окажется на клетке другой четности, чем та, с которой он стартовал. Но ему нужно попасть в противоположный угол, который имеет такую же четность суммы координат, как начальная клетка. Значит, за 255 ходов сделать это никак не возможно.
