Результаты олимпиады
В пятницу 9 октября на базе факультета информационных технологий состоялась индивидуальная олимпиада по программированию студентов БГТУ.
Всего в олимпиаде приняли участие 20 студентов ФИТ. Для решения жюри подготовило 8 задач. Тройка лучших студентов станет участниками соревнований ¼ финала студенческого командного чемпионата мира по программированию, который состоится в начале ноября в БГУ.
1-е место
Юшкевич А.В., 2 курс, спец.ПОИТ, гр.3
Андрей смог решить три задачи: «Колбы», «Касса» и «Вычисления».
2-е место
Зайцев А.Н., 1 курс, спец. ПОИТ, гр.4
Молодой, но подающий надежды участник олимпиады решил три задачи «Колбы», «Касса» и «Радистка Кэт».
3-е место разделили две команды
Мартынюк А.В., 1 курс, спец. ПОИТ,гр.4
Коровкин А.И., 2 курс, спец. ПОИТ, гр.3
Участники решили по три задачи .
Достойные результаты показали Хорхалев Вадим, Юрашевич Дмитрий, Максим Сычев (несмотря на получасовое опоздание решил две задачи), Латкович Никита и Дима Кравчук (своего рода лидер, Дима послал решения по пяти задачам, к сожалению не все они были верны).
Минимум одну задачу решили 9 участников.
Разберем несколько задач олимпиады. Одна из самых легких была задача Колбы
Условие задачи:
У преподавателя химии Ивана Михайловича имеется 10 колб с соляной кислотой и известен объем кислоты в каждой из них. За одно «касание» можно взять только одну колбу и часть кислоты (или всю) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество «касаний» Иван Михайлович может уравнять объемы кислоты во всех колбах. Каждая колба может вместить любое количество соляной кислоты.
Ввод:
Выходной файл содержит 10 целых чисел, каждое записано в отельной строке – объем кислоты в каждой из колб. Все числа целые от 1 до 100.
Вывод:
Выходной файл должен содержать одно целое число – минимальное число «касаний», за которое можно уравнять объемы кислоты во всех колбах.
Примеры:
| Ввод | Вывод |
| 302623456789 | 2 |
Примечание: В данном примере можно из первой колбы перелить 20 во вторую, оставляя в первой 10. Затем из второй колбы разлить кислоту по всем остальным колбам так, чтобы в каждой из колб оказалось по 10.
Решение
Считаем входные данные. Запишем объемы воды в колбах в массив и подсчитаем среднее значение всех объемов в колбах. Если в какой-то колбе налито больше среднего, то обязательно придется дотронутся до этой колбы, чтобы вылить из нее излишки воды. Оказывается, что достаточно дотронуться только до таких колб. Таким образом, задача сводится к нахождению среднего арифметического значения массива и подсчета числа элементов, которые больше среднего арифметического.
Следующая задача Касса
Условие задачи:
Студент Артем стоит в очереди кассы «Гиппо». Так как сейчас обеденное время, пока работает только первая касса. Всего в очереди N человек, включая Артема , и он последний. Каждый человек расплачивается на кассе за 1 минуту и уходит из магазина. Также, каждые M минут с обеда возвращается очередной кассир и открывает следующую кассу. Когда открывается i-я касса часть людей из конца очереди в (i − 1)-ю кассу в том же порядке переходит в очередь в i-ю кассу. Причем, если количество людей в (i − 1)-й кассе было K, то количество людей, которое перейдет в i-ю кассу равно целой части от K/2. Например, если в момент открытия 4 -ой кассы в 3-ей было 5 человек, то в 4-ю перейдет 2 человека, если было 6 человек перейдет 3 человека. Переход из одной очереди в другую происходит мгновенно. Определите, через сколько минут Артем сможете уйти из «Гиппо».
Ввод:
Входной файл содержит два целых числа N и M , разделенных пробелом (1 ≤ N ≤ 109 ,1 ≤ M ≤ 109).
Вывод:
Выведите одно целое число — через сколько минут Артем уйдете из магазина.
Примеры:
| Ввод | Вывод |
| 5 10 | 5 |
| 5 2 | 3 |
| 15 3 | 7 |
Примечание:
3-й тест :
• 1 касса — 15 человек
Через 3 минуты:
• 1 касса — 6 человек
• 2 касса — 6 человек
Через 6 минут :
• 1 касса — 3 человека
• 2 касса — 2 человека
• 3 касса — 1 человек (Артем)
Решение
Пусть cur – количество людей в последней очереди. Если M>= cur, то новая касса откроется после ухода последнего клиента. res += cur.
Иначе до открытия новой кассы уйдет M человек. res += M, cur -= M, cur /= 2. Но очевидно, что если в очереди остался 1 человек, действиеcur /= 2 не нужно. Поэтому этот случай стоит проверить отдельно.
Следующая задача Радистка Кэт
Условие задачи:
Скоро будет республиканский этап соревнования радистов. В соревновании дается N точек на местности, заданные координатами на плоскости. Выигрывает тот, кто быстрее других соединит каждые две точки проводами. Радистка Кэт очень хочет выиграть это соревнование, для этого ей надо двигаться быстро.Чтобы двигаться быстро она не должна таскать с собой лишний провод. Помогите Кэт узнать длину провода, которую она должна принести с собой на соревнование.Чтобы соединить точки (x1,y1) и (x2,y2), ей понадобиться провод длины |x1− x2|+ |y1− y2|.Так как длина может быть очень большой, выводите остаток от ее деления на 109+ 7.
Ввод:
Первая строка содержит целое число N — количество точек на плоскости (1 ≤ N ≤ 200000).В следующих N строках содержатся по два целых числа xi,yi — координаты точек на плоскости(−109 ≤ xi,yi≤ 109).
Вывод:
Выведите единственное целое число — ответ к задаче.
Примеры:
| Ввод | Вывод |
| 3 1 12 23 3 | 8 |
| 4 — 1 51 63 52 3 | 22 |
Примечание:
Первый тест:8 = (|1 −2|+ |1 − 2|)+ (|1 − 3|+ |1 − 3|) + (|2 − 3| + |2 − 3|)
Решение
Cамое очевидное решение за O(n2) — перебрать каждую пару точек. Но, нужно более быстрое решение.Посчитаем отдельно для X и отдельно для Y.
Пусть в массиве a[] лежат значения соответствующей координаты. Отсортируем его.Теперь для каждогоa[i] нужно найти сумму (a[i]-a[0])+(a[i]-a[1])+…+(a[i]-a[i-1]).Преобразуем в: i*a[i]-(a[0]+a[1]+…+a[i-1]). Для быстрого подсчета второго слагаемого будем в переменной curподдерживать сумму всех элементов от (0 до i-1). Ответ на задачу – сумма ответов для X и Y со сложность O(nlogn).
Одна из самых простых задач Вычисления.
Условие задачи:
Это простая задача на вычисления. Вам задана последовательность из Nчисел. Проделайте следующие действия, пока у вас не останется одно число:
• вычислите сумму каждых двух последовательных чисел, замените текущую последовательность на последовательность этих сумм
• вычислите произведение каждых двух последовательных чисел, замените текущую последовательность на последовательность этих произведений
Действия нужно выполнять именно в таком порядке: сложение, умножение, сложение, умножение и т.д. Так как в результате вычислений могут получиться очень большие числа, производите все вычисления по модулю 10 9 + 7.
Ввод:
Первая строка входного файла содержит одно целое число N (1 ≤ N ≤ 1000). Следующая строка содержит N целых неотрицательных чисел, не превышающих 10 9.
Вывод:
Выведите одно целое число, которое получится в результате.
Примеры:
| Ввод | Вывод |
| 6 4 9 3 8 5 7 | 161425 |
Примечание:
сложение: 13, 12, 11, 13, 12
умножение: 156, 132, 143, 156
сложение: 288, 275, 299
умножение: 79200, 82225
сложение: 161425
Решение
Для решения задачи возьмём целый тип данных long long. Затем в каждой интерации необходимо выполнять два цикла: суммирования соседних и произведения соседних (каждый раз выполняя корректировку суммы или произведения на P = 1000000007). Число элементов должно уменьшатся на один поле каждого цикла. Продолжаем пока не останется одно число.
Всем большое спасибо за участие! Будем рады видеть вас снова! Удачи!
Автор: доц. Пацей Н.В.
