Олимпиады_老虎机游戏

Олимпиады

Учебная работа >>> Дипломное проектирование Практика Олимпиады

16.10.2022 прошла индивидуальная олимпиада БГТУ

Поздравляем победителей:

1 место: Тихонович Никита Петрович, 3 курс, спец. ПОИТ гр. 4

2 место: Поздняков Максим Игоревич, 2 курс, спец. ПОИТ гр. 4

3 место: Турчинович Никита Александрович, 1 курс, спец. ИСиТ гр.2

Разбор задач

Задача А. Перестановки

Дано массив целых чисел. Переставьте числа в массиве так, чтобы сумма двух соседних элементов никогда не делилась на три.

ввод	вывод
9 1?0?2?2?0?2?0?0?0 ?	0?1?0?2?0?2?0?2?0?

Решение:

Для простоты предположим, что все входные числа равны 0, 1 или 2. Это не изменит результат, поскольку нужен только модуль, равный 3.

Очевидно, что два нуля или единица и двойка не могут быть соседними. Если общее количество нулей на два или более больше, чем количество единиц и двоек, то последовательность отсутствует. Точно так же, если нет нулей, но есть единицы и двойки, то придется разместить единицу и двойку вместе. Как только выясняем, что это возможно,? можем построить последовательность, вставив группы, состоящие только из единиц или двоек между нулями.

Задача B. Антенны

Для того, чтобы объединить в сеть?n?антенн, разбросанных по стране, которую можно представить в виде 2D-плоскости, необходимо установить радиус передачи каждой антенны равным одному и тому же неотрицательному вещественному числу?r. Дальность действия антенны определяется как множество всех точек, расстояние до которых до антенны не превышает?r. Если радиусы двух антенн имеют общую точку, эти антенны могут напрямую связываться. Кроме того, если антенны A и B могут обмениваться данными, а также антенны B и C, то антенны A и C также могут обмениваться данными через антенну B.

Для экономии ресурсов необходимо объединить антенны в сеть, т. е. сделать так, чтобы каждые две антенны могли обмениваться данными,?с??наименьшим?возможным радиусом?r.

ввод

вывод

1 1

2 2

0.7071068

Решение:

Две антенны могут общаться напрямую, если их расстояние не превышает 2r. Мы можем построить граф по антеннам и добавить ребра для всех пар антенн, которые ближе, чем 2r. Затем нужно проверить, связан ли граф, что можно сделать, например, с помощью dfs.

Оптимальное r, то есть минимальное r, при котором связан построенный граф, может быть найдено с помощью бинарного поиска. Для верхней границы мы можем поставить, например, 10⁹. Сложность O (n² log₂?10⁹)

Задача С. Зрительный контакт

N?человек стоят в очереди. Людям становится скучно, поэтому они поворачиваются и устанавливают зрительный контакт. Два человека A и B, стоящие в очереди, могут видеть друг друга, если они стоят рядом друг с другом или если между ними нет людей строго выше (>), чем человек A или человек B. Напишите программу, определяющую количество пар людей, которые устанавливают зрительный контакт.?

ввод

вывод

Решение:

Для начала предположим, что рост всех людей различен. Обратите внимание на любого человека А, стоящего в очереди. Если после человека А мы встречаем более высокого человека Б, то человек А точно не может видеть никого после человека Б.

Благодаря этому при прохождении очереди можно поддерживать стопку ?открытых подзадач?, где открытая подзадача — это человек, который уже встречался в очереди, но у которого еще есть возможность увидеть кого-то, с кем еще не установили контакт.. Должно быть очевидно, что подзадачи в стеке отсортированы в порядке убывания высоты (самая верхняя подзадача = самый низкий человек).

Когда сталкиваемся с новым человеком, этот человек может видеть всех в стеке, который короче, а также убирает этих людей из стека (закрывая их подзадачи). Если после этого стек не пуст, человек также может видеть первого человека, оставшегося в стеке.

Несмотря на то, что решение имеет два вложенных цикла, общая сложность равна O(N), потому что каждый человек входит в стек и выходит из него ровно один раз, а каждая итерация внутреннего цикла извлекает из стека один элемент.

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

Задача D. Тетрис

Тетрис — популярная компьютерная игра, в которую играют на поле, состоящем из?C?столбцов и неограниченного количества рядов. За один ход на поле выбрасывается одна из следующих семи фигур:

Бросая фигуру, игрок может вращать ее на 90, 180 или 270 градусов и перемещать ее влево или вправо, пока фигура полностью остается на поле. Затем фигура падает до тех пор, пока не остановится на дне поля или на уже занятых клетках. В нашем варианте тетриса фигура должна упасть так, чтобы все части фигуры оказались внизу поля или на уже занятых клетках. Другими словами, после того, как фигура упала, не может быть свободной клетки, такой, что какая-то клетка над ней занята.

Например, пусть поле имеет ширину в шесть столбцов с начальными высотами (количество уже занятых квадратов в каждом столбце) 2, 1, 1, 1,?0,??1. Затем фигуру номер 5 можно сбросить на поле пятью различными способами. :

Вам даны начальные высоты всех столбцов и фигура, которую нужно вбросить в поле.

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

ввод

вывод

6 5

2 1 1 1 0 1

?Решение:

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

Например, фигура номер 5 за четыре оборота дает следующие четыре последовательности: {1, 1, 1}, {1, 2}, {2, 1, 2} и {2, 1}.

Последовательность A соответствует последовательности B, если добавление некоторой константы ко всем элементам A дает последовательность B.

Например, последовательность {2, 1, 2} соответствует {5, 4, 5}, но не {4, 5, 4} или {5, 4}.

Обратите внимание, что фигура может быть вставлена в заданную позицию только в том случае, если последовательность высот в этой позиции соответствует кодировке фигуры. Поэтому, чтобы получить решение, просто нужно проверить все возможные положения всех вращений для данной фигуры и поля. Обратите внимание, что не у всех фигур есть 4 возможных поворота. Фигура 2 остается неизменной независимо от поворота, а фигуры 1, 3 и 4 имеют только два возможных поворота.

?Задача E. Паркинг

?В Минске появилась интересная парковка. Плату за парковку берут необычным способом — они дают скидку в зависимости?от??количества?машин.

Когда припаркован только один автомобиль, водитель платит?A?рублей за час. Когда припарковано две машины, каждый водитель платит по?B?рублей за час. Когда припарковано три машины, каждый водитель платит по?C?рублей за час.

Учитывая?A, B и C, а также интервалы, в которых припаркованы три автомобиля, определите, сколько нужно заплатить владельцу за все три машины.

ввод

вывод

5 3 1

1 6

3 5

2 8

33?

Решение:

Задача может быть решена моделированием. Нужно следить за тем, сколько машин находится на парковке. Для каждого часа от 0 до 100 мы: ?Складываем количество машин, прибывающих в течение этого часа?. Вычитаем количество машин, отправляющихся в течение этого часа. Плата за парковку зависит от количества припаркованных машин.

?Задача H. Число в квадратах

Задано целое число n, верните найменьшее число полных квадратных чисел, которые в сумме дают n.
Полный квадрат, также точный квадрат или квадратное число, — число, являющееся квадратом некоторого целого числа. Иными словами, квадратом является целое число, квадратный корень из которого извлекается нацело.
Например 1, 4, 9 и 16 являются полными квадратами, а 5 и 13 нет.

Input
На вход целое число (тестируйте на числах от 1 до 20)
Output
На выходе целое число?

Input	Output	Пояснение
12	3	12 = 4 + 4 + 4.
13	2	12 = 9 + 4.
8	2	8 = 4 + 4.

?Решение:

Создаем миссив размером (n+1) let n = 12, dp Array?

0	1	2	3	4	5	6	7	8	9	10	11	12
0	?	?	?	?	?	?	?	?	?	?	?	?

На 1 итерации заполняем массив с полным квардатом только 1

0	1	2	3	4	5	6	7	8	9	10	11	12
0	1	2	3	4	5	6	7	8	9	10	11	12

?На 2 обновляем с следующем полным квадратом 4?

0	1	2	3	4	5	6	7	8	9	10	11	12
0	1	2	3	1	2	3	4	2	3	4	5	3

На 3 обновляем с следующем полным квадратом 9?

0	1	2	3	4	5	6	7	8	9	10	11	12
0	1	2	3	1	2	3	4	2	1	2	3	3

Время: внешний цикл O (n * sqrt (n)) состоит из sqrt (n) итераций, а во внутреннем цикле примерно < n итераций.

Память: O(n).

? int numSquares(int n) {

??? vector<int> dp(n+1,INT_MAX);

??? dp[0]=0;

??? int count = 1;

??? while(count*count <= n) {

??? int sq = count*count;

??????? for(int i = sq; i < n+1; i++)? dp[i] = min(dp[i-sq] + 1,dp[i]);

??????? count++;

??? } return dp[n];

}

Задача G. Поискмладшихсоседей

У вас имеется массив целых чисел, вам необходимо вернуть массив чисел, в котором записаны количество элементов меньше каждого элемента масива справа.
Справа от 7 есть 2 меньших элемента (3 и 1).
Справа от 3 есть только 1 меньший элемент (1).
Справа от 9 находится 1 элемент меньшего размера (1).
Справа от 1 находится 0 меньших элементов.

Используйте массив [7,3,9,1] как начальное условие. Пример на Python print(counterSmall([7,3,9,1]))

Input

На вход масив чисел [7, 3, 9, 1]

Output
На выходе масив найденых чисел [2, 1, 1, 0]

Input	Output
[7, 3, 9, 1]	[2, 1, 1, 0]

Решение:

Пример, приведенный в описании задачи: [7, 3, 9, 1]

Выполним обычную сортировку слиянием для данного массива.

При обычной сортировке слиянием, мы рекурсивно разделяем массив сверху вниз, пока каждый? из подмассивов не будет иметь размер 1

[7, 3, 9, 1]

[7, 3] [9, 1]

[7] [3] [9] [1]

Теперь вернемся снизу вверх.

Мы объединяем [7] и [3] в результирующий массив.

Обычно мы просто должны сравнить первый элемент обоих подмассивов (7 и 3) и взять меньший элемент (3) поместите меньший элемент в ?объединенную? область

ВНИМАНИЕ: в этом случае мы знаем, что: перед сортировкой все элементы в левом подмассиве [7] изначально располагаются СЛЕВА от всех элементов в правом подмассиве [3] 7 > 3

Теперь мы нашли 1 экземпляр элемента (3), который расположен справа от 7 и меньше 7.

Мы можем увеличить на 1, результат ответа для 7.

Если мы повторим этот процесс несколько раз получим нужный ответ.

Продолжим наш первоначальный пример:

[7, 3, 9, 1]

[7, 3] [9, 1]

[7] [3] [9] [1]

Начальный результат: 7(0) 3(0) 9(0) 1(0) если мы поднимимся на один уровень снизу

3 меньше и правее 7 ==> увеличение счетчика для 7

1 меньше и правее 9 ==> увеличение счетчика для 9

[7, 3, 9, 1]

[7, 3] [9, 1]

Текущий результат: 7(1) 3(0) 9(1) 1(0)

Теперь нам нужно объединить:

левый подмассив, [3, 7] и правый подмассив [1, 9]

Все элементы в правом подмассиве изначально расположены справа от всех элементов в левом подмассиве

Обратите внимание, что 1 из правого подмассива меньше 3 из левого подмассива.

Это означает, что 1 расположен справа от 3 и меньше 3.

Поэтому мы должны увеличить количество меньших элементов для 3.

Обратите внимание, что 1 также меньше 7 и расположено справа от 7.

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

Из этого следует что: 1 < 3 < 7

Поэтому нам также нужно будет увеличить количество меньших элементов для 7

Это обновленное состояние:

7(1) 3(0) 9(1) 1(0) -------> 7(2) 3(1) 9(1) 1(0)

Теперь единственным элементом в правом подмассиве является 9. Все элементы в левом подмассиве [3,7] меньше 9, поэтому просто переместите их в ?объединенную? область, такая же, как и при обычной сортировкой слиянием.

[3, 7] [1, 9] ----------> [1,3,7,9]

Финальный результатов: 7(1) 3(0) 9(1) 1(0) -------> 7(2) 3(1) 9(1) 1(0)

Сортировка слиянием завершена.

Окончательный результат [2,1,1,0], как и в описании задачи.

Поскольку мы только что выполнили обычную сортировку слиянием и по ходу добавили некоторую проверочную логику, время выполнения такое же, как и при обычной сортировке слиянием, O(n log n)

private class ArrayValWithOrigIdx {

??????? int val;

??????? int originalIdx;

??????? public ArrayValWithOrigIdx(int val, int originalIdx) {

??????????? this.val = val;

??????????? this.originalIdx = originalIdx;

??????? }

??? }

??? public List<Integer> countSmaller(int[] nums) {

??????? if (nums == null || nums.length == 0) return new LinkedList<Integer>();

??????? int n = nums.length;

??????? int[] result = new int[n];

???????

?? ?????ArrayValWithOrigIdx[] newNums = new ArrayValWithOrigIdx[n];

??????? for (int i = 0; i < n; ++i) newNums[i] = new ArrayValWithOrigIdx(nums[i], i);

???????????

??????? mergeSortAndCount(newNums, 0, n - 1, result);

???????

??????? List<Integer> resultList = new LinkedList<Integer>();

??????? for (int i : result) resultList.add(i);

??????? return resultList;

??? }

???

??? private void mergeSortAndCount(ArrayValWithOrigIdx[] nums, int start, int end, int[] result) {

??????? if (start >= end) return;

??? ????

??????? int mid = (start + end) / 2;

??????? mergeSortAndCount(nums, start, mid, result);

??????? mergeSortAndCount(nums, mid + 1, end, result);

???????

??????? int leftPos = start;

??????? int rightPos = mid + 1;

??????? LinkedList<ArrayValWithOrigIdx> merged = new LinkedList<ArrayValWithOrigIdx>();

??????? int numElemsRightArrayLessThanLeftArray = 0;

??????? while (leftPos < mid + 1 && rightPos <= end) {

??????????? if (nums[leftPos].val > nums[rightPos].val) {

??????????????? ++numElemsRightArrayLessThanLeftArray;

??????????????? merged.add(nums[rightPos]);

??????????????? ++rightPos;

??????????? } else {

??????????????? result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

??????????????? merged.add(nums[leftPos]);

??????????????? ++leftPos;

??????????? }

??????? }

???????

??????? while (leftPos < mid + 1) {

??????????? result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

??????????? merged.add(nums[leftPos]);

??????????? ++leftPos;

??????? }

??????? while (rightPos <= end) {

??????????? merged.add(nums[rightPos]);

??????????? ++rightPos;

??????? }

??????? int pos = start;

??????? for (ArrayValWithOrigIdx m : merged) {

??????????? nums[pos] = m;

??????????? ++pos;

??????? }

??? }

13.10.2021 прошла индивидуальная олимпиада БГТУ

Поздравляем победителей:

1 место - Скородумов Иван, ПОИТ 3-5

2 место - Тихонович Никита, ПОИТ 2-4

3 место - Злобин Роман, ИСиТ 4-2

27.04.2021 прошла командная олимпиада БГТУ

Поздравляем команды:

1 место: Команда ?HouseOfFire?,

Таболич Артём Сергеевич, 2 курс, спец. ПОИТ гр. 5,

Мотолянец Екатерина Сергеевна, 2 курс, ИСИТ спец. гр. 1,

Филиппов Серафим Игоревич, 2 курс, ПОИТ спец. гр. 5

2 место: Команда ?BigO?,

Калоша Илья Валерьевич, 3 курс, спец. ИСИТ гр. 2,

Злобин Роман Юрьевич, 3 курс, спец. ИСИТ гр. 2,

Макеев Дмитрий Васильевич, 3 курс, ИСИТ спец. гр. 1

3 место: Команда ?IPatel?,

Кишко Иван Петрович, 2 курс, спец. ПОИТ гр. 5,

Скородумов Иван Иванович, 2 курс, спец. ПОИТ гр. 5,

Шуст Юрий Олегович, 2 курс, спец. ПОИТ гр. 4