Блог пользователя Twenty_Winter

Автор Twenty_Winter, история, 6 лет назад, По-русски

Прошедшие два дня обнажили интересную дилемму: либо учёба забирает у меня слишком много времени, либо же я настолько не адаптирован к трудностям некоторых задач. Тем не менее + 2 решённых задачи в копилку.

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

Вторая — Покупка факелов (необходимо посчитать минимальное число обменов палок на палки и палок на угли по некоторым правилам), — оказалась труднее. Казалось бы, принцип прост: посчитать необходимое для создания факелов количество палок и через него выразить необходимое количество обменов, однако количество палок углей и факелов могло выражаться девятизначными числами. Поэтому пришлось прибегнуть к длинной арифметике. Так как для привычного мне С++ не существует стандартных библиотек, её реализующих, то я прибег к помощи старого союзника — Python. Он поддерживает длинную арифметику и обеспечивает возможность быстрого решения задач, требующих таких вычислений.

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

Автор Twenty_Winter, история, 6 лет назад, По-русски

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

В качестве плана подготовки я выбрал темы (список может расширяться):

Рекурсия Комбинаторика Математика Математическое моделирование Структуры данных

Первой задачей стала задача на комбинаторику 1400D "Зигзаг". Её суть сводится к поиску в массиве данных двух пар одинаковых элементов. Эти пары расположены так, что первый элемент второй пары в массиве находится между элементами первой пары, а второй элемент первой пары — между элементами второй.

Первым пришедшим на ум решением стало классическое "в лоб": выбрать элемент А, после него выбрать элемент В, после него выбрать элемент равный А, а после него посчитать количество элементов равных В. Однако, это решение оказалось неспособно выдержать временной критерий, так как его асимптотическая оценка составляет n^4 (4 цикла, опирающихся на размер).

Таким образом, я встал перед выбором, модифицировать существующее или же искать абсолютно новый путь. Главные надежды возложены на проставление меток для одинаковых элементов.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится