Подразделы

Другие разделы

Дата и время

25/04/2024 21:12:39

Авторизация

Задачи заочного тура личного первенства 2010

A. Как я провел лето

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Попытавшись записать видеоролик с летними впечатлениями на DVD-диск, чтобы потом показать его своим друзьям, Петя обнаружил, что размер файла оказался больше, чем осталось места на диске. Он решил так уменьшить разрешение видеоролика, чтобы он поместился на диск.

Пете известно, что размер файла с видеороликом в зависимости от разрешения можно рассчитать по формуле `S=k*W*H`, где `W` и `H` – размеры кадра в пикселях, а `k` – коэффициент, учитывающий продолжительность видеоролика и используемый кодек. Кроме того ширина кадра должна быть кратна 4, а высота – кратна 2. Поэтому при пропорциональном сжатии кадра его ширина округляется вверх до ближайшего числа, кратного 4, а высота округляется вверх до ближайшего четного числа, и добавляются черные пиксели справа или внизу для получения кадра с соответствующими размерами.

Напишите программу, которая поможет Пете определить максимальные размеры кадра в сжатом видеоролике, при котором его размер не будет превышать `S_2` мегабайт.

Первая строка ввода содержит 4 целых числа – размеры кадра в исходном видеоролике `W_1`, `H_1` (`100\ ≤\ W_1,\ H_1\ ≤\ 10^5`, `W_1\ mod\ 4\ =\ 0`, `H_1\ mod\ 2\ =\ 0`), размер исходного видеоролика в мегабайтах `S_1` и ограничения на размер после сжатия `S_2` (`100\ ≤\ S_2\ <\ S_1\ ≤\ 10^6`).

Вывести два целых числа `W_2`, `H_2` – размеры кадра в сжатом видеоролике.

Пример ввода

512 400 1400 700

Пример вывода

360 282

B. Монеты

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Среди `n` монет (`2\ ≤\ n\ ≤\ 1000`) могут быть фальшивые, они имеют одинаковый вес и легче настоящих. Про одну из монет известно, что она является настоящей. Необходимо за минимальное количество взвешиваний на чашечных весах без гирь определить количество настоящих монет.

Вы должны написать функцию с именем calc, возвращающую количество настоящих монет среди `n` монет.

int calc(int n); // С/С++
function calc(n:integer):integer; // Pascal

Для выполнения взвешивания ваша функция должна вызывать функцию compare.

int compare(int k, int left[], int right[]); // С/С++
function compare(k:integer; left, right:array of integer):integer; // Pascal

В качестве аргументов необходимо указать количество и номера монет, которые нужно положить на левую и правую чашу весов. Можно класть на чаши только одинаковое количество монет и нельзя указывать один и тот же номер монеты дважды. Нумерация монет начинается с 1. Монета с номером 1 является настоящей. Функция возвращает значение 0, если веса монет на обоих чашах равны, значение `-1`, если вес монет на левой чаше меньше, чем на правой, или значение 1, если вес монет на левой чаше больше.

Пересылаемое на проверку решение должно содержать только функцию calc, вспомогательные функции, команды #include (в C/C++) и глобальные переменные. В функциях не должен выполняться ввод или вывод.

Пример программы на С/C++

int calc(int n)
{ int left[1000],right[1000],i,k=1;
  left[0]=1;
  for(i=2; i<=n; ++i)
  { right[0]=i;
    if(compare(1,left,right)==0) ++k;
  }
  return k;
}

Пример программы на Pascal

var left,right:array[1..1000] of integer;
function calc(n:integer):integer;
var i,k:integer;
begin
  k:=1;
  left[1]:=1;
  for i:=2 to n do
  begin
    right[1]:=i;
    if compare(1,left,right)=0 then
      inc(k);
  end;
  calc:=k;
end;

Решение участника, который определит количество настоящих монет за наименьшее количество взвешиваний, получает оценку 100 баллов. Решение, которое определяет количество настоящих монет за `n-1` взвешивание или больше, получает оценку 0 баллов. Остальные решения получают оценку пропорционально достигнутым результатам по сравнению с лучшим решением.

C. Головоломка "9 квадратов"

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Квадрат `3\ times\ 3` сложен из квадратных фишек `1\ times\ 1`. Фишки пронумерованы числами от 1 до 9. Начальное расположение фишек показано ниже. Фишки каждого квадрата `2\ times\ 2` можно поворачивать на угол, кратный 90 градусов.

1	2	3
4	5	6
7	8	9

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

Ввод содержит три строки, содержащих по три целых числа от 1 до 9 – требуемое расположение фишек.

В первой строке вывести одно целое число `K` – минимальное количество ходов. Во второй строке вывести последовательность ходов через пробел. Поворот левого верхнего квадрата `2\ times\ 2` на 90 по часовой стрелке обозначается A1, на 180 градусов – A2, а на 90 против часовой стрелки – A3, для поворотов правого верхнего используются обозначения B1, B2 и B3, левого нижнего – C1, C2 и C3, правого нижнего – D1, D2 и D3. Если существует несколько решений с наименьшим количеством ходов, то можно вывести одно из них (любое).