e-olymp 107. Компакт-диски

Задача взята с сайта e-olymp.com.

Задача

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков — 30 грн., а один диск стоит 2 грн. Какую минимальную сумму нужно истратить для покупки [latex] n [/latex] таких дисков?

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

Количество дисков [latex] n (n ≤ 1000)[/latex].

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

Вывести минимальную сумму в гривнах для покупки [latex] n [/latex] дисков.

Тесты

Входные данные (число [latex] n [/latex]) Выходные данные (минимальная сумма, грн.)
1. 17 30
2. 7 14
3. 123 136
4. 24 38
5. 173 200
6. 108 116
7. 136 160

 

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

Решение

Для решения этой задачи мы должны вывести минимальную сумму для покупки[latex] n [/latex] дисков. Следует отметить, что для заданного числа [latex] n [/latex] дисков нам надо определить минимальную сумму, при этом мы можем покупать упаковку с большем количеством дисков, чем нужное нам [latex] n [/latex], если при этом итоговая сумма покупки получится меньше. Таким образом, мы аналитически определили, что если [latex]n\mod100 > 65[/latex] то экономней будет приобрести большую упаковку на 100 дисков за 100 грн., чем несколько более маленьких упаковок по 30 грн., и соответственно при [latex]n\mod20 > 15 [/latex] лучше приобрести одну упаковку на 20 дисков за 30 грн., чем по одному за 2 грн.

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olymp 128. Счастливые билеты

Задача взята с сайта e-olymp.com.

Задача

Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N[/latex].

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

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

В единственной строке задано натуральное число [latex] N (N ≤ 27). [/latex]

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

Единственное число — количество счастливых билетов.

Тесты

Входные данные (число [latex] N [/latex]) Выходные данные (число билетов)
1. 1 9
2. 27 1
3. 0 1
4. 10 3969
5. 3 100

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

Решение
Любой шестизначный номер можно представить как 2 трехзначных номера.

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

Когда в цикле встречается подходящая комбинация, счетчик [latex]c[/latex] увеличивается на 1. Так как номер шестизначный, а счетчик [latex]c[/latex] подсчитывает удачные комбинации для трехзначного числа первой части, то и для трехзначного числа второй части он будет соответствовать. Следовательно, окончательное число комбинаций будет равно [latex]c \cdot c[/latex].

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olimp 248. Юный садовод

Задача взята с сайта e-olymp.com.

Условие задачи

Мама попросила Васю полить все молодые деревца в саду. Вася знает, что пока деревья маленькие, их надо очень хорошо поливать. А вот сколько поливать — неизвестно. Но Вася — очень умный мальчик. Он внимательно прочитал весь учебник ботаники для средней школы и выяснил, что полив прямо пропорционален количеству листьев на дереве. Для хорошего роста деревьев достаточно выливать под дерево ежедневно по одному литру воды на каждый лист.

К счастью Васи оказалось, что листья на деревьях растут ярусами, причем на верхнем ярусе два листа, на втором — четыре, на следующем — шесть, и так далее, на каждом последующем ярусе на два листа больше по сравнению с предыдущим. А на самой верхушке растет еще один листик. Хитрый Вася послал младшую сестренку Машеньку подсчитать количество ярусов на каждом дереве, а Вас просит написать программу, которая для каждого дерева вычислит количество литров воды для его полива.

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

Количество ярусов [latex] n  (0 ≤ n ≤ 1000) [/latex] на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

Входные данные Выходные данные
1. 2 7
2. 5 31
3. 0 1
4. 70 4971

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

Решение

Как можно было заметить, по условию нашей задачи, на каждом следующем уровне на 2 листа больше чем на предыдущем. Поэтому для ее решения мы можем воспользоваться формулой суммы [latex]n[/latex]-первых членов арифметической прогрессии, и в конце расчетов добавить к полученной сумме единицу (тот самый листик с верхушки). Тогда подставив [latex] d = 2 , a_1 = 2, n = n [/latex]. Мы получим формулу [latex] S_n = \frac{2a_1 + (n — 1)d}{2} \cdot n \to n^2 + n [/latex].

 

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olymp 4853. Кратчайший путь

Условие:

Задан неориентированный граф. Найдите кратчайший путь от вершины $start$ до вершины $end$.

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

В первой строке находится два целых числа $n$ и $m$ $ (1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $start$ и $end$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $start$ и $end$ нет, то выведите $-1$. Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты:

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

Решение:

Поскольку нам необходимо найти кратчайшее расстояние между вершинами реализуем поиском в ширину. Запомним посещенные вершины в массиве [latex]used[/latex], родительские вершины в массиве [latex]parent[/latex], а план посещений в списке [latex]plan[/latex].
Изначально в списке [latex]plan[/latex] находится единственная вершина $start$. Каждый шаг начинается с того, что мы берем первую вершину из списка [latex]plan[/latex], отмечаем ее как посещенную, удаляем из списка и после посещаем все ее соседние вершины, которые еще не были посещены.
Когда очередь опустеет, обход в ширину обойдёт все достижимые из [latex]point[/latex] вершины, причём до каждой дойдёт кратчайшим путём. После того, как кратчайший путь найден — мы с помощью массива «предков» восстанавливаем его.

 

try online

e-olymp 2162. Палиндром

Ссылка на оригинальную статью

Ссылка на рабочий код

Ссылка на e-olymp

Задача
Палиндром — это строка, которая одинаково читается слева направо и справа налево. Составьте программу, которая проверяет, является ли заданный текст палиндромом. Не забудьте, что при чтении пробел никак не произносится.

Входные данные
Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки

Выходные данные
Вывести «Yes», если текст является палиндромом, и «No», если не является.

Тесты

Входные данные Выходные данные
a roza upala na lapu azora Yes
my gym Yes
palindrom No
character No

Код

Решение
Со входного потока считываем строку. Так как пробелы не должны учитываться, то легче будет работать со строкой без пробелов. Поэтому, пользуясь пространством имен StringTools, заменим все вхождения пробелов на пустые строки (инчае говоря, удалим все пробелы). Флаг ok в конце будет использован для вывода соответствующего сообщения. В цикле поочередно проверяем на равенство противоположные элементы строки. В случае единого несовпадения устанавливаем флаг в false и останавливаем цикл. Выводим сообщение в выходной поток.

Ю 4.1

Задача взята отсюда
Условие
Задача. Разделение по знаку. В массиве С(n) подсчитать количество отрицательных и сумму положительных элементов.
Тесты

Входной массив Кол-во отрицательных элементов Сумма положительных элементов
1,2,-3,4,-5 2 7
25,-13,100,-1024,1,0,-24,36 3 162
-17,45,-2,80,-11,-20,-14,10,12,-3 6 147

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

В ходе решении данной задачи я использую цикл for, в котором сначала считываются, а затем обрабатываются данные. Переменная-счётчик k нужна для того, чтобы узнать кол-во отрицательных элементов. А если встречаются неотрицательные элементы, то подсчитывается их сумма в переменной s. Для проверки выполнения программы можно воспользоваться ссылкой.

2.1.2 Переполнение

Ссылка на manual

Ссылка на код демонстрации

По причинам производительности компилятор Haxe не осуществляет переполнения. Задача проверки на переполнения лежит на конечной платформе. Вот несколько примеров поведения при переполнении на разных платформах:

  • С++, Java, C#, Neko, Flash: 32-битное целое число со знаком с обычным поведением при переполнении
  • PHP, JS, Flash 8: нет типа int, потеря точности случится в случае достижения лимита float($2^{52}$)

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

Пример поведения при переполнении продемонстрирован в коде ниже. Переменная i, выходя за пределы Int, приобретает отрицательное значение, а затем при декременте на единицу — крайнее положительное значение

Заметка: данный код следует выполнять в среде HaxeDevelop, так как на Try Haxe! он (код) приобретает другое поведение

e-olymp 2166: Анаграммы

Ссылка на задачу на e-olymp.

Условие

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

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

Два слова заданы в отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают $255$.

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

Следует вывести «$YES$», если введенные слова являются анаграммами друг друга и «$NO$» если нет.

Тесты

Входные данные Выходные данные
sharm
marsh
YES
ananas
nnaass
NO

Код.

Решение.

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

Ссылка на решение задачи на сайте Try Haxe!

e-olymp 2164. Шифр Юлия

Задача

Юлий Цезарь использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через [latex]k[/latex] позиций по кругу. Необходимо по заданной шифровке определить исходный текст.

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

В первой строке дана шифровка, состоящая из не более чем 255 заглавных латинских букв. Во второй строке число [latex]k (1[/latex] [latex]\leq[/latex] [latex]k[/latex] [latex]\leq[/latex] [latex]10)[/latex].

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

Требуется вывести результат расшифровки.

Тесты

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

1

WORD
2 ZABC

3

WXYZ

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

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

Каждая буква строки является элементом массива [latex]cipher[/latex]. Чтобы расшифровать строку нужно от значения [latex]i[/latex]-го элемента массива отнять [latex]k[/latex], тем самым сдвинуть символ на [latex]k[/latex] единиц по алфавиту, и заменить первоначальный символ на полученный результат. В случае если разница символа [latex]i[/latex]-го элемента и числа [latex]k[/latex] не входит в множество заглавных латинских букв, требуется от символа «Z» отнять оставшееся кол-во шагов [latex]k[/latex] (то есть не считая те которые уже были пройдены от изначального символа символа до крайнего символа «A»), и заменить первоначальный символ на полученный результат. Можно не беспокоиться о том, что символ вернется к «Z» более чем один раз так как условие исключает этот вариант ([latex]k<=10[/latex] при 26-ти символах латинского алфавита).

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

А137д

Задача

Даны натуральное число [latex]n[/latex], действительные числа [latex]a_1, … , a_n[/latex] . Вычислить:

[latex]-a_1, a_2, -a_3, … , (-1)^na_n[/latex]

Тесты

[latex]n[/latex] [latex]a_1, … , a_n[/latex] [latex]-a_1, a_2, -a_3, … , (-1)^na_n[/latex] Комментарий
4 3 -2 -3 6 -3 -2 3 6 Пройден
5 40 -30 0 34.5 0.2 -40 -30 0 -34.5 0.2 Пройден
3 126 -486.95 -20.0985 -126 -486.95 20.0985 Пройден

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

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

Для начала вводим число [latex]n[/latex]. Задаем цикл для ввода ряда чисел [latex]a_1, … , a_n[/latex]. Если [latex]n[/latex] — чётное число, умножаем введенное [latex]a[/latex] на [latex]-1[/latex]. Выводим результат.

Решение задачи на Try Haxe !

Решение этой задачи на С++ и Java.