e-olymp 7233. Отрезки

Задача

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

Входные данные:

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

Выходные данные:

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Тесты

Входные данные Выходные данные
1 4
1 1
2 2
3 3
4 4
9

Код

 

 

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

e-olymp 7213. Шашка на кубе

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

Входные данные

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

Выходные данные

Вывести искомое количество способов.

Тесты

l m вывод
3 3 1
3 4 0
3 5 25
51 199 4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3 199 11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

e-olymp 9066. Кружок стрельбы

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

Входные данные

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

Выходные данные

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

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
 1 5
1 3 3
5 1 2
8 2 3
10 1 2
11 3 2
2
2 6
1 3 5
4 2 2
7 4 3
10 1 2
11 3 2
13 4 3
1

Код

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

  • Условие задачи на e-olymp
  • Код на Ideone
  • Засчитанное решение на e-olymp 

e-olymp 6261. Устройство для анализа бюллетеня

Задача

Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет $ \frac{100p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

Входные данные

Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем «Invalid».

Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

Выходные данные

Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘%‘. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите «12.35» для 12.345).

Тесты

Входные данные

Выходные данные

1 4 7
Loudy
Apples
Dogman
Miller
.X..
X…
….
..X.
..XX
..X.
..X.
Dogman 42.86%
Loudy 14.29%
Apples 14.29%
Miller 0.00%
Invalid 28.57%
2 4 10
Loudy
Apples
Dogman
Miller
X………………..
X…………………..
X………………
X………………….
X…………..
x………………………..
X……………….
X……………
X..x
xxxx
Loudy 70.00%
Apples 0.00%
Dogman 0.00%
Miller 0.00%
Invalid 30.00%

Код программы

Решение

Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

e-olymp 976. Флойд — существование

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

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

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

   Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути.
  • Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

 

link

e-olimp 6124. Стек неограниченного размера

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы.  Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Пояснение: Размер стека должен быть ограничен только размером доступной оперативной памяти.

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

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

Отрицательные стороны:

Конструктор срабатывает для каждого узла достаточно медленно, решение уступает в скорости связному списку массивов.
Ссылка на задачу. Ссылка на засчитанное решение.

Код программы:

М16. Freshly Pressed Juice

Формулировка задачи

Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.

Тесты

[latex]V[/latex] [latex]n[/latex] [latex]Menu[/latex] [latex]Recipe[/latex] Комментарий
150 2 Apple 10 60 200

Cherry 20 70 50
Sorry, we are closed for today Объем фруктов на складе меньше 300.
80 8 Dragonfruit 123 50 10

Aplle 10 60 200

Cherry 40 80 100

Coconut 20 5 30

Pineapple 80 90 50

Raspberry 70 95 30

Blackberry 130 95 30

Strawberry 60 95 40

Grape 20 95 120

Orange 10 80 200

Melon 10 98 300

Banana 20 30 120
Apple 80 800 В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее.
80 14 (см. тест № 2) Banana 40.000000

Raspberry 30.000000

Pineapple 10.000000

3700
Корректно
110 1 (см. тест №2) Melon 110 1100 Корректно

Анализ задачи

  1. Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
  2. Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].

Алгоритм решения

    • Объявить структуру [latex]fruit[/latex] с переменными:
      • name
      • specific_cost
      • percentage
      • amount
    • Необходимо
      1. считывать информацию о фрукте;
      2. сортировать фрукты по некоторому параметру

      Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.

  1. Дальнейшее решение распадается на несколько подзадач:
    1. Сортировка элементов вектора в порядке убывания стоимости единицы объема.
    2. Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
    3. Составление коктейля наименьшей стоимости при заданном объёме порции.

    Был намечен следующий алгоритм действий:

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

Программный код

Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.

Подробности реализации

Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.

  1. После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
  2. Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
  3. Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
  4. Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
  5. В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].