Криптография (max20 баллов)
 Скачать 46 Kb.
|
|
Криптография (max=20 баллов) При подготовке данного комплекта задач жюри столкнулось со следующей проблемой: нужно было передавать по электронной почте тексты задач. Как известно, электронная почта ненадёжна, сообщения передаются открытым текстом, и существует опасность, что кто-нибудь их перехватит. Членам программного комитета вовсе не хотелось, чтобы задачи стали известны участникам раньше начала соревнования, поэтому они прибегли к методам криптографии. Жюри разработало совершенно новый способ шифрования текста, но он пока не запатентован и поэтому держится в секрете. Впрочем, одну тайну мы вам всё же откроем, новый алгоритм основан на работе с простыми числами и, в частности, использует вычисление n-го по счёту простого числа. Несколько членов программного комитета, независимо друг от друга, разработали программы, производящие такие вычисления, но эти программы выдают разные ответы. Каждый уверен, что он написал свою программу правильно, поэтому жюри встало в тупик и не может продолжать свою работу. Вы должны помочь жюри и спасти соревнования. Напишите программу, вычисляющую n-е по счёту простое число, и, самое главное, она должна работать правильно! Исходные данные В первой строке находится ровно одно целое число k, задающее количество чисел в списке. За ним следуют k целых чисел, по одному в строке. Все числа положительные и не превосходят 15000. Результат Для каждого числа n из списка вы должны вывести n-е по счёту простое число. Ответ для каждого числа должен находиться в отдельной строке. Пример
Подсказка Простое число — это целое положительное число, которое имеет ровно два различных положительных делителя, т.е. 1 не является простым числом. Охота на зайцев(max=20 баллов) Хороший охотник убивает двух зайцев одним выстрелом. Конечно же это может быть легко сделано, поскольку через любые две точки можно провести прямую. Но убить трёх и более зайцев одним выстрелом — намного более сложная задача. Чтобы стать лучшим охотником в мире, нужно уметь убить максимально возможное количество зайцев. Представим зайца точкой на плоскости. Точка задаётся целочисленными координатами x и y. Вам нужно найти максимальное число зайцев, которые могут быть убиты одним выстрелом, то есть максимальное количество точек заданного множества, лежащих точно на одной прямой. Никакие два зайца не находятся в одной точке. Исходные данные Первая строка ввода содержит целое число N (3 ≤ N ≤ 200) — количество зайцев. Каждая из следующих N строк содержит x и y координаты (в таком порядке), разделённые пробелом (−2000 ≤ x, y ≤ 2000). Результат Выведите максимальное число зайцев, находящихся на одной прямой. Пример
Произведение цифр(max=15 баллов) Ваша задача — найти минимальное положительное целое число Q такое, что произведение цифр числа Q в точности равняется N. Исходные данные Целое число N (0 ≤ N ≤ 109). Результат Выведите целое число Q. Если такого числа не существует, выведите −1. Пример
Демократическая реформа (max=25 баллов) Вступление В одном из островных государств Карибского бассейна все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей. Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается «за», если «за» голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается «против». После проведения голосования в группах подсчитывалось количество групп, высказавшихся «за» и «против», и вопрос решался положительно в том и только том случае, когда групп, высказавшихся «за», оказывалось более половины общего количества групп. Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов! Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь трех сторонников в каждой из первых двух групп, и она сможет провести решение всего шестью голосами «за», вместо девяти, необходимых при общем голосовании. Задача Вам надо написать программу, которая определяет по заданному разбиению избирателей на группы минимальное количество сторонников партии, достаточное, при некотором распределении их по группам, для принятия любого решения. Исходные данные В первой строке записано нечётное число K — количество групп избирателей (1 ≤ K ≤ 101). Во второй строке через пробел записаны K нечётных чисел, которые задают количество избирателей в группах. Население острова не превосходит 9999 человек. Результат Выведите минимальное количество сторонников партии, способное решить исход голосования. Пример
|