Данная олимпиада в этом году посвящается Никлаусу Вирту — швейцарскому ученому, профессору, создателю языка Паскаль, человеку-новатору в сфере языков программирования.
Инструкция по участию в олимпиаде: участие в олимпиаде
(1): Троичная уравновешенная система счисления
Система оценивания: Максимальный балл: 100 (50 баллов — за первую программу, 50 баллов — за вторую программу. 10 баллов за каждый пройденный тест, всего 5 тестов)
Троичная уравновешенная система счисления — система счисления с основанием 3, используя для своей записи цифры 0, 1 и -1. Цифра -1 будет обозначаться как $. Первые 10 чисел в такой системе счисления будут выглядеть следующим образом:
0 = 1*0 = 0
1 = 1*1 =1,
1$ = 1*3+(-1)*1 = 2,
10 = 1*3+0*1 = 3,
11 = 1*3+1*1 = 4,
1$$ = 1*9+(-1)*4+(-1)*1 = 5,
1$0 = 6,
1$1 = 7,
10$ = 8,
100 = 9,
101 = 10.
В 1840 году ее предложил французский математик и изобретатель механических устройств для вычислений Леон Лаланн.
Напишите две программы:
- Программа, которая по входной строке — число в обычной троичной системе счисления, выводит это число в троичной уравновешенной системе счисления.
- Программа, которая среди N десятичных чисел выводит троичную уравновешенную запись максимального числа. Программа сначала получает на вход число N(2<=N <=1000000), а затем сами числа. Программа должна вывести максимальное число в последовательности в троичной уравновешенной системе счисления.
(2): Артикул в Интернет-магазине
Система оценивания: Максимальный балл: 100 (50 баллов — за первую программу, 50 баллов — за вторую программу. 10 баллов за каждый пройденный тест, всего 5 тестов)
Вера любит покупать товары в Интернет-магазине. Специально для нее сотрудники магазина собрали для нее артикулы ее любимых товаров в один файл — articul.txt, а цены за эти товары в файл price.txt. Первый артикул в файле articul соответствует первой цене из файла price. Но у Веры ограниченное количество денег — всего N рублей. (1<=N<=1000000). Вера любит все товары, поэтому если ей хватает денег на несколько товаров, то она возьмет как можно больше товаров.
Напишите две программы:
- По входному числу N рублей и по входному числу M — артикулу, программа должна вывести «Да», если за N рублей можно купить товар M, а также вывести остаток(сколько рублей останется у Веры после покупки), или вывести «Нет», если N рублей не хватит на покупку. Если в программу был введен номер артикула, которого нет в файле, программа также должна вывести «Нет».
- По входному числу N рублей вывести максимальное количество товаров, которая Вера может купить на эту сумму. Программа должна вывести количество товаров и артикулы этих товаров. Если денег не хватит ни на один товар, необходимо вывести «НЕТ».
(3): Не хочу выходить к доске
Система оценивания: Максимальный балл: 100 (100 баллов — за программу, 10 баллов за каждый пройденный тест, всего 10 тестов)
Гена не хочет выходить к доске, так как не готов к уроку. Для объективности, учитель хочет случайным образом выбрать тех, кто будет отвечать домашнее задание на уроке. Для выбора ученика учитель написал программу, которая случайным образом выбирает уникальный номер ученика из журнала. Но учитель каждый раз меняет номера учеников, поэтому каждый раз ученики узнают свои номера только перед уроком. Гена решил схитрить и написать программу, которая генерирует последовательность из уникальных N чисел, но не включает в последовательность номер Гены, а после генерации программа выбирает случайным образом номер ученика(из последовательности, сгенерируемой Геной), который будет отвечать ДЗ.
Напишите программу, которая получает на вход два числа: N(1 <= N <= 50) — количество учеников, M (1 <= M <= 50) — номер Гены в журнале. Программа должна сначала вывести последовательность в случайном порядке из N чисел(от 1 до N включительно), исключая из последовательности число M, а затем случайным образом выбирает из этой последовательности номер ученика.
Пример работы программы (Работа программы может отличаться, так как в этой задаче идет работа со случайными числами):
Примечание: При генерации случайных чисел учите, что программа учителя и программа Гены генерирует все УНИКАЛЬНЫЕ числа. Повторяющихся чисел в последовательности быть не должно.
(4): Чистота чисел
Система оценивания: Максимальный балл: 100 (50 баллов — за первую программу, 50 баллов — за вторую программу. 10 баллов за каждый пройденный тест, всего 5 тестов)
Алексей давно увлекается математикой и разработал свою теорию чистоты чисел. Теория чистоты чисел гласит, что существую такие числа, которые помогают в математических расчетах(по мнению Алексея, математики с ним не согласны). Алексей считает, что чистые числа — это числа, у которых в качестве делителей нет полных квадратов(кроме числа 1) и числа не должны быть простые. Например, число 10 — чистое, так 10 — не простое число, и у делителей числа 10 нет полных квадратов(2,5,10 — не полные квадраты, число 1 исключается), а число 11 — не чистое, так как является простым. Напишите две программы:
- Среди N чисел найти и вывести все чистые числа. Если в последовательности таких нет, то вывести «НЕТ».
- Среди N чисел найти три числа с наименьшей суммой, из которых можно составить треугольник. Вывести эти числа в порядке возрастания. Если в последовательности нет таких чисел или из таких чисел нельзя составить треугольник, то необходимо вывести «НЕТ».
В программу вводится число N, а затем N натуральные числа. Программы должны вывести числа, удовлетворяющие двум условиям задачи.