Задачи теоретической части

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры:

  1. четкость описания алгоритма,
  2. результативность (алгоритм в любом случае должен давать некоторый результат),
  3. корректность (алгоритм должен давать правильный ответ при любых корректных входных данных),
  4. оптимальность (следует привести по возможности наиболее оптимальный по количеству шагов алгоритм; из нескольких корректных алгоритмов больше баллов получит наиболее оптимальный).

Решения задач теоретической части оформляются в виде документа Microsoft Word в соответствии с техническими требованиями и загружаются для проверки в Виртуальном кабинете.

Задача 1. Цифры

Даны N цифр. Опишите эффективный алгоритм, который позволит составить из них 2 числа таким образом, чтобы их сумма была минимально возможной.

Задача 2. Строки

Даны N строк s1, s2, …, sn. Опишите эффективный алгоритм, позволяющий упорядочить их таким образом, чтобы конкатенация (склеивание) строк слева направо было минимальным в лексикографическом порядке.

Задача 3. Раскрасьте числа

Даны числа от 1 до N. Опишите эффективный алгоритм, раскрашивающий числа таким образом, чтобы если число A делится на число B, то числа A и B были окрашены в разный цвет. Число цветов должно быть минимально возможным.

Задача 4. Степени двойки

Все числа в массиве являются неотрицательными степенями двойки, не превосходящими 2015. Опишите алгоритм нахождения десяти подряд идущих элементов массива, среди которых нет одинаковых.

Задача 5. Стеклянные шары

Представьте, что вы находитесь в M-этажном здании. У вас есть B стеклянных шаров. Вам нужно найти самый низкий этаж, сбросив с которого шар, вы не сможете его разбить. Опишите эффективный алгоритм, позволяющий найти минимальное число бросков в худшем случае. Пример: если M=10, B=2, то минимальное число бросков – 4.

Задачи практической части

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

Для проверки принимаются только исходные тексты программ (файлы *.pas, *.c, *.cpp) в соответствии с техническими требованиями. Программы (исходные тексты) загружаются для проверки в Виртуальном кабинете, сразу компилируются и проверяются на наборе тестов, после чего участнику выдается результат. Допускается вносить изменения в программы произвольное количество раз и загружать программы для повторной проверки.

Внимание: загрузка работ будет возможна со 2 ноября (c 11:00 МСК). Загружается только исходный текст программы (файл *.pas, *.c, *.cpp) без архивирования.

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

Входные данные берутся из текстового файла input.txt, результат выполнения программы выводится в файл output.txt в установленном формате. Программа ничего не должна запрашивать для ввода с клавиатуры и не должна ничего выводить на экран.

Ограничения на время выполнения программы по каждому из тестов: 10 секунд. Программы, не укладывающиеся во время прохождения теста в установленные ограничения или выдающие ошибку, считаются не прошедшими данный тест.

Задача 1. Видимые точки

Георгий так любит математику, что видит её практически во всём. Вот и отдыхая на пляже, он взял (N+1)x(N+1) камушков и разложил их в целочисленных точках квадрата размером NxN, находящегося в первой четверти плоскости. Левый нижний угол квадрата находится в точке (0,0), правый верхний – в точке (N,N).  Камушек, находящийся в точке (x,y) будем называть видимым, если на прямой, проведенной из (0,0) в (x,y), не лежит ни один другой камушек. Георгий хочет найти количество видимых камушков. Помогите ему это сделать. Камушек, лежащий в точке (0,0), не считается видимым.

Вход: файл input.txt, в первой строке записано натуральное число N.

Ограничения: 1≤N≤105

Выход: файл output.txt, содержащий единственное число – количество видимых камушков.

Примеры:

input.txt

output.txt

2

5

4

13

5

21

Примечание:

Ниже проиллюстрирован пример с видимыми точками в квадрате 5x5:

Задача 2.

Когда Георгию становится скучно на уроках математики, он развлекает себя следующим образом: берет натуральное число n и получает из него единицу с помощью последовательных  делений без остатка. На каждом шагу Георгий делит текущее число на любой его натуральный делитель, отличный от единицы.

Например, если n=30, то существует несколько способов получить из него единицу. Например, 30→10→1 или 30→6→3→1, или 30→1. Всего это можно сделать 13 способами.

Георгий просит вас помочь подсчитать количество способов, которыми он может получить из числа n единицу. Два способа n→x1→…→xk→1 и n→y1→…→ym→1 считаются различными, если km или существует i такое, что xi≠yi.

Вход: файл input.txt, в первой строке записано натуральное число n.

Ограничения: 1≤N≤2≤109

Выход: файл output.txt, содержащий единственное число – количество способов получить из числа n единицу по модулю (109+7) (т. е. вывести остаток от деления количества способов получить единицу на 109+7).

Примеры:

input.txt

output.txt

1

1

9

2

30

13

Задача 3.

Помимо математики Георгий любит собирать замки из конструкторов. В магазин завезли n конструкторов. Конструкторы пронумерованы числами от 1 до n.

У Георгия есть 2 способа получить нравящийся конструктор:

  1. Купить его. Конструктор с номером i стоит ci рублей;
  2. Купить и объединить два конструктора, получив из них другой конструктор. Возможные способы компоновки конструкторов заданы тройками чисел (x, y, z). Купив конструкторы с номерами y и z, можно их объединить и получить один конструктор с номером x. Всего есть m доступных троек (xyz)

Георгий ограничен в средствах и просит вас помочь ему найти минимальную сумму денег, которую нужно будет потратить, чтобы собрать конструктор, из которых можно будет построить замок номер 1.

Вход: файл input.txt, в первой строке записаны два целых числа n и m. Во второй строке содержатся n чисел ci  – стоимости конструкторов. В следующих m строках содержится по 3 числа xiyizi – это означает, что конструктор номер xi может быть скомпонован из конструкторов yiи zi.  

Ограничения: 1≤ n≤ 104, 0 m 105, 0  ci  109, 1 xi,yi,zi n

Выход: файл output.txt, содержащий единственное число – минимальная сумма денег, которую потратит Георгий.

Примеры:

input.txt

output.txt

4 2

8 1 1 3

4 2 3

1 2 4

3

4 2

2 1 1 3

4 2 3

1 2 4

2

 

Примечание:

В первом тестовом примере, можно купить конструкторы номер 2 и 3, собрать из них детали для конструктора номер 4, затем купить ещё один конструктор номер 2 и собрать из имеющихся конструкторов конструктор номер 1. На это будет затрачено 1+1+1=3 рубля