Ограничение по памяти: 256 мебибайт
В этой задаче требуется расшифровать английский литературный текст, зашифрованный по специальному алгоритму. Для шифровки текст записывается в кодировке ASCII. Все символы, кроме символов переводов строки, имеют коды от 32 до 126 включительно; перевод строки в системе Linux кодируется одним символом с кодом 10. Шифровка проходит в два этапа.
На первом этапе выбирается случайный ключ k = k0 k1 ... k len-1 длиной len (от 1 до 8 символов); символы в ключе могут иметь произвольные коды от 0 до 255. После этого из исходного текста a0a1a2 ... ап-1 получается промежуточный текст b0b1b2 ... bп-1 по следующему правилу: ai = bi Θ кi mod len. Здесь и Θ v — побитовая операция «исключающего или»: коды символов и и v представляются в двоичном виде, а результат — это символ, код которого получается побитовым применением двоичной операции Θ к и и v. Например, ‘а’ Θ ‘Н’ = ‘)’: код символа ‘а’ равен 9710 = 011000012, код символа ‘Н’ равен 7210 = 010010002,
011000012 Θ 010010002 = 001010012 = 4110, а 41 – это код символа ‘)’ (круглая закрывающая скобка).
На втором этапе выбирается одно число shift от 0 до 255. После этого из промежуточного текста b0b1b2 ... bп-1 получается зашифрованный текст c0c1c2 ... cп-1 по следующему правилу:
ci = (bi + shift) mod 256. Здесь сложение означает, что к коду символа bi прибавляется число shift. Например, ‘)’ + 7 = ‘0’: код символа ‘)’ равен 4110, значит, получается символ с кодом
4110 + 710 = 4810.
Требуется по заданному зашифрованному тексту c0c1c2 ... cп-1 восстановить исходный текст a0a1a2 ... ап-1. Необходимо помнить, что исходный текст — это отрывок литературного текста на английском языке.
Ваша программа должна реализовывать функцию solution (n, а, с). Здесь п — длина текста (50 000 ≤ п ≤ 100 000), а c – зашифрованный текст, заданный как массив символов. Эта функция должна записать исходный текст в первые п элементов массива а.
Обратите внимание, что размер посылаемой программы не должен превышать 262 144 байта. Для сбора статистики — и локально, и на сервере жюри — ваша программа может читать пример литературного текста из файла sample. txt.
Подзадача 1 (баллы: 30)
len = 8, shift =0.
Подзадача 2 (баллы: 30)
shift = 0.
Подзадача 3 (баллы: 40)
Дополнительные условия отсутствуют.
Замечание
Обратите внимание, что тестирование проводится под операционной системой Windows, однако во входном файле, а также в выданном вам примере, в качестве перевода строки используется один символ с кодом 10.
Выданный grader считывает данные, считая файл бинарным. Если вы хотите как-либо обрабатывать sample. txt в обход grader, его тоже лучше открывать как бинарный файл.
8. Описание заданий для восьмого интернет-тура
На восьмом туре было предложено 4 задачи: задача A «Построить граф», задача B «А где матроид?», задача C «Планеты и звезды» и задача D «Двойной шифр». Тексты задач представлены ниже.
Задача A. Мечты корпорации
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мебибайт
Некоторая Корпорация для своего бизнеса решила составить карту мира. Для этого она использовала спутник, который способен делать снимки произвольного прямоугольника со сторонами, параллельными сторонам будущей карты.
Решить поставленную задачу не так просто, поскольку в разных странах существуют устройства, которые засвечивают снимки, если попадают в кадр. Корпорации требуется локализовать все эти устройства, поскольку она может делать снимки произвольных прямоугольников и узнавать, насколько каждый из них засвечен.
Формат входных данных
Требуется написать программу, которая будет взаимодействовать с управляющим модулем спутника через стандартный ввод и вывод. После того, как программа-решение выведет очередной набор данных, необходимо вызвать функцию flush(output) в Pascal или fflush(stdout) в С/С++, поскольку из-за использования буферизации проверяющая программа может не получить эти данные.
Первой строкой входных данных ваша программа получает три целых числа n, w и h — количество устройств на карте и её размеры. Далее ваша программа может делать запросы, каждый из которых состоит из четырёх целых чисел — координат левого-нижнего и правого-верхнего углов. В ответ ваша программа получит строку с числом x, соответствующим количеству устройств, засветивших этот снимок, а значит, попавших в кадр.
Разрешается сделать не более 120·n снимков.
1 ≤ n≤ 500, 1≤w,h≤ 109.
Известно, что нет двух устройств с совпадающими координатами.
Формат выходных данных
Когда определены все n позиций устройств, необходимо вывести —1 —1 —1 —1 вместо координат очередного снимка, а затем вывести n пар чисел — координаты устройств.
Система оценки
На каждом тесте ваше решение будет оцениваться из максимального числа баллов для данного теста. Если решение не завершилось корректно с указанными ограничениями, либо если решение не выдало верный ответ, оценка за тест будет равна 0. Если решение вывело верный ответ и использовало не более 60·n снимков, оно получит полный балл. Решения, использующие более 60·n, но не более 120·n снимков, получат число баллов, линейно убывающее с возрастанием количества снимков от полного балла за тест до половины.
Примеры
Задача B. Дорожные работы
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мебибайт
В Республике Икс издавна действует двухпартийная система. Каждый год граждане, имеющие избирательные права, голосуют за партию, которой они больше доверяют — партии Демократов или партии Консерваторов, и в течение последующего года вся реальная власть сосредотачивается в руках избранной партии.
В последние М лет между партиями разразилась нешуточная война по перестройке дорожной сети республики «под себя». Партия Демократов стремится построить как можно больше государственных дорог, чтобы истратить побольше бюджетных денег на их «обслуживание», а партия Консерваторов стремится сделать платными как можно большее число дорог. Движение на всех дорогах Республики Икс двустороннее.
Известно, что в течение одного года правления партии Демократов удалось построить ровно одну новую дорогу, которая поначалу являлась бесплатной, а партии Консерваторов — ввести плату за проезд по одной из бесплатных на текущий момент дорог, при этом деньги на содержание этой дороги выделяются уже не из бюджета, а из средств, вырученных за проезд.
Президент Республики, не имеющий в настоящее время реального политического влияния, решил привлечь внимание общественности к проблеме дорог. Он назвал дорожную сеть удобной (для простых граждан), если из любого города можно доехать до любого, используя только бесплатные дороги, но при этом количество бесплатных дорог а, соответственно, и бюджетных средств на их содержание, полученных сбором налогов с граждан Республики, должно быть минимально возможным.
Требуется написать программу, которая определяет, была ли дорожная сеть удобной по завершении i-го года «дорожной войны».
Формат входных данных
В первой строке входных данных заданы два числа — N (1 ≤ N ≤ 1000), число городов в Республике Икс, и М (1 ≤ М ≤ 100 000) – продолжительность порядком затянувшейся «дорожной войны». Далее следуют М строк, первый символ каждой из которых — это F, если в данный год у власти была партия Демократов, и R — если партия Консерваторов, а далее в строке следуют два числа — номера городов ui и vi — пара городов, дорога между которыми стала объектом пристального внимания соответствующей партии (была построена новая дорога, если у власти была партия Демократов, и одна из существующих дорог была сделана платной, если у власти была партия Консерваторов). Вполне возможна ситуация, когда между двумя городами окажется более одной дороги, или будет построена дорога из города в себя — мало ли, что там удумает партия Демократов.
Гарантируется, что входные данные корректны, то есть, все числа ui и vi лежат в пределах от 1 до N, и если известно, что в какой-то год дорога между двумя городами была сделана платной, то это значит, что перед началом года была хотя бы одна бесплатная дорога между этими городами.
Формат выходных данных
Для каждого года выведите в отдельной строке YES, если дорожная сеть по завершении соответствующего года была удобной, и NO в противном случае.
Пример
Задача C. Подпоследовательности
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мебибайт
Андрей очень любит решать задачи по олимпиадному программированию. Недавно ему на глаза попалась задача, в которой надо было выбрать из последовательности максимальную возрастающую подпоследовательность. Он эту задачу не решил, однако его друг рассказал ему решение. Андрей решил, что теперь он может решить и более сложную задачу — выбрать из последовательности К непересекающихся непустых возрастающих подпоследовательностей так, чтобы сумма их длин оказалась наибольшей. Однако справиться с этой задачей не смог ни он, ни его друг.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
