Олимпиада по программированию 2012

Регламент

  • 15:00–15:05 — Регистрация и получение заданий.
  • 15:06–16:59 — Работа над задачами, досрочная сдача задач по желанию участников.
  • 17:00 — Срок обязательной сдачи задач.

Участник имеет право досрочно сдать свои задачи. В этом случае он объявляет о своём намерении, фиксируется время сдачи. После сдачи, участник не должен вносить какие-либо изменения в программный код. Баллы начисляются за каждую правильно решенную задачу. Задача считается решенной верно, если на всех тестовых наборах получается верный результат. Побеждает тот, кто наберёт максимальное количество баллов. При равном количестве баллов побеждает тот участник, кто раньше набрал победную сумму баллов.

Ввод данных с клавиатуры в программе реализовывать не обязательно, данные могут задаваться внутри программы за счёт передачи начального значения в переменные или с помощью явного перечисления элементов массива.

Задания

Задача №1 (3 балла)

В виде числовой переменной задано некоторое натуральное число (длиной до 10 цифр). Составить из всех цифр данного числа новое число, такое чтобы его абсолютное значение оказалось наименьшим из возможных. Вывести полученное число на экран. Пример исходных данных:

int n = 23042012;

Корректный результат:

10022234

Задача №2 (4 балла)

Заданы две строки символов, в каждой из которых не более 50 символов. Найти и вывести на экран наибольшую по количеству символов общую подстроку, содержащуюся в обеих строках. Если существует несколько подстрок наибольшей длины, то вывести любую из них. Пример исходных данных:

char str1[] = "Наконец-то наступила весна в наших краях";
char str2[] = "Весна в самом разгаре";

Наибольшая общая подстрока:

есна в

Задача №3 (4 балла)

Задана матрица 7 на 4 из целых чисел из отрезка [0;9]. Найти и вывести на экран хотя бы одну квадратную подматрицу размера 3 на 3, сумма элементов в которой была бы больше 40, но меньше 50. Либо сообщить, что такой подматрицы не существует. Пример исходных данных:

int [] m = {
{ 0, 1, 3, 9, 5, 6, 1 },
{ 2, 7, 4, 0, 6, 5, 8 },
{ 1, 3, 9, 1, 4, 9, 2 },
{ 8, 6, 3, 5, 1, 7, 0 }
};

Корректный результат:

2 7 4
1 3 9
8 6 3

Задача №4 (7 баллов)

Числовыми координатами своих вершин заданы два треугольника на плоскости. Известно, что фигуры расположены таким образом, что их стороны имеют ровно две точки пересечения, а область пересечения фигур (их общая часть) также является треугольником. Вычислить и вывести на экран площадь этого треугольника.

Задача №5 (7 баллов)

Задан набор из 7 точек на плоскости, каждая из которых представлена парой своих числовых координат. Определить и сообщить на экран, можно ли используя точки из данного набора как вершины, построить хотя бы один прямоугольник.