SPAM занимается рассылкой рекламных газет и буклетов в разные города. По договоренности с почтой, каждая посылка должна содержать строго определенное количество (N, где 1 > N > 100) экземпляров рекламных изданий в сумме. Но есть еще проблема и принцип компании:
1) Два буклета не могут соприкасаться, из-за некачественного полиграфического покрытия они склеиваются и портятся. Газеты выполняют еще и роль прокладки между ними.
2) Каждая посылка должна быть уникальная, то есть отличаться от других порядком укладки или количеством различных типов изданий (буклет/газета). Это дополнительный рекламный ход компании, который состоит в том, что каждый клиент должен получать индивидуальную укладку или содержание посылки.
Необходимо заранее определить максимальное количество вариантов правильной комплектации посылки в зависимости от N.
Входные данные:
В начале файла "SPAM.IN" записано количество экземпляров изданий (некоторое N).
Выходные данные:
В первой строке файла "SPAM.OUT" нужно указать число возможных вариантов комплектации.
Пример 1.
Файл "SPAM.IN"
4
Файл "SPAM.OUT"
8
Пример 2.
Файл "SPAM.IN"
13
Файл "SPAM.OUT"
610
Решение g6_1043:
Без лишних слов перейдем к решению задачи.
Для N = 1 мы имеем ответ 2 (0 или 1). Для N = 2 - ответ 3 (00, 01, 10). Для N = 3 - 5 (000, 001, 010, 100, 101). Исследую эту закономерность, мы придем к тому, что она представляет собой последовательность чисел Фибоначчи. Действительно, в любом случае мы можем приложить к уже имеющейся последовательности газету, т.е. F(x) = F(x - 1). Кроме того, для предыдущей мы также могли приложить газету (таких комбинаций F(x - 2)) и теперь мы можем смело приложить буклет. Т.е. общее количество F(x) = F(x - 1) + F(x - 2). Как определить последовательность Фибоначчи разобрано в задаче #1025 - Домино
Задача g6_1044: Уникальная строка (отборочный тур на Самарскую областную олимпиаду 2000 г.)
Текстовый файл состоит из N строк (1
Входные данные:
Файл "US.IN" содержит строки. Список завершается "#". Этот символ находится отдельно, первым в последней строке и к списку не относится. Входные данные корректны, проверка на ошибки не требуется.
Выходные данные:
В файле "US.OUT" записывается уникальная строка.
Пример:
Файл "US.IN"
- Меня зовут Михаил, а Вас?
- Аваз.
- Меня зовут Михаил, а Вас?
- Аваз.
- Меня зовут...
#
Файл "US.OUT"
- Меня зовут...
Решение g6_1044:
Здорово я поизмачивался над этой задачей в свое время! Т.к. количество повторяющихся строк четно, то это неспроста. Здесь есть хитрость - а именно операция XOR (о ней более подробно можно прочитать в #1001 - Проблема с A и B).
Вот только единственная проблема - XOR можно делать только для строк одинаковой длины, но решается она просто - все строки дополняются каким-нибудь мусором до 255 символов (пробелы ставить не стоит - у жюри на таких умельцев есть тесты, я ставил рожицы улыбающиеся по Ctrl-B, а некоторые символ конца строки). Потом надо не забыть с конца строки срезать все эти символы, а то не поймут...
A xor B xor B xor C xor D xor C xor A = D - маленький пример
Задача g6_1045: День рождения Иванова (первоисточник неизвестен)
Иван Иванович Иванов пригласил на свой день рождения много гостей. Он написал на карточках фамилии всех гостей и разложил эти карточки на столе, полагая, что каждый гость сядет там, где обнаружит карточку со своей фамилией. Однако гости не обратили внимания на карточки и сели за стол в произвольном порядке. При этом Иван Иванович с удивлением обнаружил, что ни один гость не сел на предназначенное ему место, и задумался: а сколькими способами можно рассадить гостей так, чтобы ни один из них не сидел там, где лежала карточка с его фамилией? Помогите Ивану Ивановичу вычислить это число.
Считайте, что число гостей не превосходит 100 человек.
Входной файл: число гостей
Выходной файл: число способов
Решение g6_1045: предоставлено Ф.В. Меньшиковым
Общая идея. Пусть у нас есть N гостей. Посадим первого на не свое место. Это можно сделать N-1 способом. Теперь будем сажать того человека, на место которого сел первый. Его можно посадить или на место первого человека одним способом, или на другие места N-2 способами.
Если его посадили на место первого человека, теперь нужно оставшихся N-2 гостей рассадить на места этих же N-2 гостей, т.е. задача для N свелась к задаче для N-2.
Если же его посадили на другое место, то мы опять будем рассаживать того человека, чье место занял предыдущий посаженный человек, и опять будем в ситуации, когда одно свободное место соответствует уже рассаженному человеку, а остальные места - еще не рассаженным.
Обозначения.
Обозначим за count(N) число способов, каким можно посадить N гостей так, чтобы никто не сел на свое место. Из вышеизложенных рассуждений вытекает необходимость еще одного обозначения.
Обозначим за count'(N) число способов, которыми можно рассадить N гостей на N мест, если за каждым из N-1 гостей закреплено место, куда он не должен садиться, а один может садиться куда угодно.
Формулы перехода.
count(N) = (N-1)*count'(N-1) - сажаем первого человека на не свое место N-1 способом и получаем ситуацию, когда из N-1 человек N-2 имеют место, куда они не должны садиться, а один может садиться куда угодно.
count'(N) = count(N-1)+(N-1)*count'(N-1) = count(N-1)+count(N)
Назовем человека, не имеющего закрепленного за ним места, "свободным". Также назовем "свободным" место, за котором не закреплен человек.
Если мы рассаживаем "свободного" человека на "свободное" место единственным способом, то получаем, что нужно посадить N-1 человека на N-1 место, причем за каждым закреплено место, куда он не может садиться - это count(N-1).
Если же мы сажаем "свободного" человека на "несвободное" место N-1 способом, то получаем ситуацию, когда "свободным" стал человек, на чье место мы посадили предыдущего, а также сохранилось "свободное" место - это (N-1)*count'(N-1).
Начальные значения.
count(1)=0 - один человек, который не должен садиться на свое место.
count'(1)=1 - один человек, который может садиться на одно место.
Комментарии по реализации.
Число count(100) меньше числа 100! (это сколько вообще способов посадить гостей за стол). Число 100! меньше числа 100100, которое имеет 201 цифру. Итак, это задача на длинную арифметику, причем для хранения десятичной записи чисел достаточно массива из 200 цифр. Из операций длинной арифметики нужны только умножение длинного числа на короткое, сложение двух длинных чисел и вывод длинного числа.
Еще хочется отметить, что не следует использовать рекурсию для формальной реализации вышеприведенных формул - каждое count(i) и count'(i) нужно вычислять только один раз, а рекурсивный вариант будет вычислять одно и то же много раз, что неприемлемо для N=100. Массив значений count(i) и count'(i) можно тоже не заводить - просто помнить значения count(i-1) и count'(i-1), и после очередного шага обновлять их.
Алгоритм, опуская длинную арифметику, можно записать так:
var
n,i:integer;
count,counts,countprev,countsprev:number;
begin
readln(n);
set0(count);
set1(counts);
for i:=2 to n do begin
countprev:=count;
countsprev:=counts;
count:=countsprev;
mul(count,i-1);
counts:=countprev;
add(counts,count);
end;
show(count);
end.
Задача g6_1046: Упаковка простых.
Михаил Густокашин, Евгений Бровкин
В первой строке входного файла input.txt дано число N (N
Оптимизировать программу по времени исполнения.
Пример входного файла:
3
999999 1250001
1000000 1000005
1234567 1250001
Пример выходного файла:
17971
1
1109
Решение g6_1046:
Как искать простые числа более или менее быстро я советую прочитать вам разбор задачи 1036 - Хитрющая строка.
Недаром задача названа "Упаковка простых". Если каждый раз идти от min до max и если разница между ними большая, то программа будет тормозить ужасно. Следовательно простые надо посчитать один раз и не пересчитывать позже. Т.е. воспользоваться методом динамического программирования. Если у вас FP/GNU C, то никаких проблем быть не должно, а вот если у вас BP/TP/BC, то придется применить хитрость, т.к. 17971 longint число в памяти укладываться не хочет. Здесь уместно использовать обобщенную теорему Евгения Бровкина о разнице между простыми числами. Теорема Евгения Бровкина гласит:
Разница между двумя последовательными простыми числами до 60000 простого числа не превышает 255
Обобщенная Михаилом Густокашиным теорема о разнице между простыми числами, гласит:
Разница между двумя последовательными простыми числами в промежутке от 1000000 до 1250000 не превышает 255
Значит уместно один раз посчитать разницу между последовательными простыми числами, а затем пользоваться ею. Это можно сделать двумя способами:
Считать каждый раз в начале работы программы
Посчитать один раз и занести как константу Первым способ работает медленнее. Мы один раз пройдем от начала (999999) до конца (1250001) и будем при встрече простого числа записывать в очередной элемент массива разницу между этим числом и предыдущем. За первое число примем 1000000 - оно все равно не простое.
Теперь идем по массиву с первого элемента и последовательно восстанавливаем простые числа. Если число больше min и меньше max, то увеличиваем счетчик на 1. При превышении max выводим счетчик и начинаем считать заново для новых min и max.
Задача g6_1047: Бизнес-классики (XIII Всероссийская олимпиада по информатике)
Поле для игры в бизнес-классики представляет собой прямоугольник, состоящий из 3 * N клеток. В некоторых клетках лежит по одному рублю, в остальных - ничего нет. Играющий выбирает для начала игры одну из трех левых клеток и прыгает в нее. За один ход играющий перепрыгивает в одну из клеток, имеющих общую сторону с той, в которой он находится. При этом запрещено прыгать в те клетки, в которых он уже побывал. При очередном прыжке все деньги, собранные к этому моменту, удваиваются, а затем, если в новой клетке лежит рубль, то он прибавляется к имеющейся сумме денег. Считается, что в начале игры денег у играющего нет. Закончить прыжки надо в одной из трех правых клеток поля и при этом заработать как можно больше денег.
Требуется написать программу, которая по известному значению N и расположению рублей в клетках находит такую последовательность прыжков, при которой играющий заработает наибольшее количество денег. Если таких последовательностей несколько, то следует выбрать любую последовательность, количество прыжков в которой минимально.
Входные данные
В первой строке входного файла с именем CLASS.IN записано натуральное число N (1 Выходные данные
Выходной файл с именем CLASS.OUT должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов:
U - если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1;
D - если номер строки увеличился на 1;
L - если номер столбца уменьшился на 1;
R - если номер столбца увеличился на 1.
Символы во второй строке выходного файла должны быть выведены без пробелов.
Пример входного файла
4
1 1 1 0
1 1 1 0
1 1 1 1
Пример выходного файла для приведенного примера входного файла
1
DDRUURDDRUU
Решение g6_1047: предоставлено Е.В. Андреевой
Если, согласно информации о наличии или отсутствии рублей в клетках, искомую последовательность прыжков записать в виде набора нулей и единиц, то станет ясно, что размер выигрыша равен значению полученного двоичного числа. Так, в приведенном примере игрок заработает 1111111111002 = 409210 . Отсюда следует, что в большинстве случаев игроку выгодно побывать во всех клетках поля, в этом случае число разрядов двоичного числа будет максимальным, а количество прыжков равно 3N. Меньшее количество прыжков имеет смысл делать лишь если рублей на поле нет совсем (тогда выигрыш будет равен 0 для любой последовательности прыжков, а последовательность прыжков минимальной длины будет состоять из N клеток любой строки) или если первый столбец имеет вид 010 (тогда значение выигрыша выражается двоичным числом длины 3N-1 и игрок может впрыгивать в среднюю клетку, не уменьшая выигрыша). Во всех остальных случаях впрыгивать имеет смысл только в начальную клетку первой или третьей строки, иначе невозможно побывать во всех клетках поля, не нарушая правила игры.
Осталось определить способ обхода всех клеток поля, который будет соответствовать максимально возможному двоичному числу. В связи с тем что поле имеет всего три строки, каждые из k рядом стоящих столбцов могут быть пройдены одним из двух способов - вертикальной или горизонтальной "змейкой" (решение в примере соответствует прохождению всех столбцов поля вертикальной "змейкой"). А все поле целиком можно обойти, комбинируя эти два способа: например, первые k1 столбцов - вертикальной "змейкой", следующие k2 - горизонтальной, следующие k3 - опять горизонтальной - и т.д. - см. рис. 1.
Рис.1.
Пусть мы уже знаем оптимальный способ обхода первого столбца, первых двух столбцов, :, первых k - 1 столбцов. Тогда несложно определить оптимальный способ обхода первых k столбцов, сравнивая результаты следующих комбинаций обхода - обход горизонтальной "змейкой" всех первых k столбцов сверху вниз или снизу вверх или оптимальный обход первого столбца + горизонтальная "змейка" по следующим k - 1 столбцам или оптимальный обход первых двух столбцов + горизонтальная "змейка" по следующим k - 2 столбцам и т.д. Последний из рассматриваемых вариантов представляет собой оптимальный обход первых k - 1 столбцов и вертикальное прохождение k-го столбца. Наилучшая из рассмотренных комбинаций запоминается как оптимальный обход k первых столбцов и используется в дальнейшем. Такой способ решения относится к динамическому программированию.
Задача g6_1048: Оппозиция (XIII Всероссийская олимпиада по информатике)
В некоторой стране полиция выявила разветвленную сеть оппозиционной партии.
Партия сильно законспирирована и состоит из рядовых членов и руководителей различных уровней. Во главе партии стоит один главный руководитель - лидер партии. До начала арестов приказ лидера может быть доведен до любого члена партии. Все члены партии пронумерованы от 1 до N.
Каждый член партии знает только своего вышестоящего руководителя (ровно одного) и своих непосредственных подчиненных (руководитель не знает подчиненных своего подчиненного и наоборот).
Естественно, что с началом арестов членов партии она распадется на мелкие, не связанные друг с другом группы. Например, с арестом члена партии № 2 (см. рис. 2) партия разваливается на 4 группы.
Полицмейстер уверяет, что группа, состоящая из менее чем К членов партии, идеологически вырождается и не представляет угрозы для государства.
Стремясь не уронить престиж страны в глазах мирового общественного мнения, полицмейстер поставил задачу произвести минимальное количество арестов членов партии так, чтобы от нее остались только идеологически вырождающиеся маленькие группы.
Требуется
Написать программу, которая бы по входным данным, описывающим структуру подпольной партии, выводила количество арестов и номера членов партии, которых нужно арестовать.
Входные данные
Входной файл с именем ORG.IN содержит три строки. В первой записано число K (1
Выходные данные
Выходной файл с именем ORG.OUT состоит из двух строк. В первую строку необходимо поместить количество арестов, а во вторую - номера членов партии, подлежащих аресту. Эти номера разделяются одним пробелом. При наличии нескольких решений выведите одно из них.
Пример входного файла для структуры партии, представленной на рис. 2
3
14
1 1 2 2 3 2 3 6 6 6 7 4 7
Пример выходного файла для приведенного входного файла
4
6 2 7 8
Решение g6_1048: предоставлено Е.В. Андреевой
Описанная в условии задачи структура партии представляет собой дерево. Пусть для некоторого его поддерева справедливо следующее: каждая ветвь данного поддерева в отдельности содержит менее K элементов, а все поддерево в целом - K или более элементов (число элементов в поддереве равно сумме элементов в его ветвях плюс один элемент, соответствующий корневой вершине поддерева). Тогда очевидно, что удаление корневой вершины данного поддерева (то есть арест соответствующего члена партии) решает поставленную задачу в рамках рассмотренного поддерева оптимальным образом.
Действительно, удаление вершин, не принадлежащих данному поддереву, не может уменьшить избыточное число элементов в нашем поддереве, а удаление иной вершины поддерева, кроме корневой, возможно, и приведет к решению задачи для рассмотренного поддерева, но тогда непосредственный "начальник" неудаленной корневой вершины "идеологически обезвреженного" поддерева будет иметь по крайней мере на одного "подчиненного" больше, что может увеличить общее число удалений вершин (арестов).
В результате получаем следующий алгоритм решения задачи. Начиная с "листовых" вершин (соответствующих рядовым членам партии, не имеющим подчиненных), подсчитываем для каждой вершины дерева количество элементов в связанном с ней поддереве. Если количество элементов в поддереве оказалось больше или равно K, то его корневая вершина удаляется, данное поддерево исключается из рассмотрения и задача решается для оставшихся элементов дерева. Последним из рассмотренных элементов должна оказаться вершина № 1, обозначающая лидера партии. Так, в приведенном примере данный алгоритм предложит удалить вершины дерева с номерами 7, 6, 2 и 1. Алгоритм является линейным относительно количества членов партии, а его реализация зависит от выбора структуры данных для хранения исходного дерева.
Задача g6_1049: Телеметрия (XIII Всероссийская олимпиада по информатике)
Для космического корабля сконструирована телеметрическая система, содержащая N (1
Рис.3
С центрального пульта на систему могут подаваться команды управления. Каждая команда управления имеет вид:
номер группы + | -
При этом номер активного датчика в соответствующей группе увеличится или уменьшится на единицу. Попытка установить номер активного датчика в группе вне пределов [1..Pi ] ведет к аварийному останову контроллера.
В исходном состоянии для каждой из групп известен номер активного датчика.
Для комплексной проверки корабля требуется проводить съем показаний для всех возможных комбинаций активных датчиков, причем повторять уже использованные ранее комбинации активных датчиков запрещается. Общее количество комбинаций активных датчиков не превосходит 10 000.
После окончания проверки система должна оказаться в исходном состоянии.
Требуется
Разработать программу, которая осуществляла бы управление контроллером, реализующее требуемый опрос датчиков.
Входные данные
Входной файл с именем TELE.IN содержит следующие три строки. Первая строка содержит число N - количество групп датчиков. Вторая строка содержит N чисел P1 , P2 , :, PN , каждое из которых задает количество датчиков в соответствующей группе. Третья строка содержит N исходных номеров активных датчиков в группах. Числа во второй и третьей строках разделены пробелом.
Выходные данные
Выходной файл с именем TELE.OUT должен содержать следующие строки. В первую строку выводится сообщение Yes или No, в зависимости от того, возможно или нет реализовать управление контроллером, осуществляющее требуемую схему съема данных. При выводе сообщения Yes в последующих строках выдается последовательность команд управления. Каждая строка должна содержать по одной команде управления. При этом знак "+" соответствует увеличению на 1, а знак "-" - уменьшению на 1 номера активного датчика в этой группе.
Пример входного файла
2
2 3
2 1
Пример выходного файла, соответствующего приведенному входному файлу
Yes
1 -
2 +
2 +
1 +
2 -
2 -
Примечание. Будут отдельно оцениваться решения для частных случаев N = 1, N = 2, N = 3.
Решение g6_1049: предоставлено Е.В. Андреевой
Эта задача являлась, пожалуй, самой сложной на данной олимпиаде, как по выработке алгоритма решения, так и по его реализации, именно поэтому даже разбор случаев с N
При N > 1 решения не существует, если количество датчиков во всех группах нечетно, то есть произведение чисел P1 , P2 , :, PN нечетно. Так как если нам требуется перебрать все комбинации активных датчиков, то в каждой из групп датчиков количество команд "увеличить номер активного датчика" должно совпадать с количеством команд "уменьшить номер активного датчика", то есть общее количество команд, равное числу всевозможных комбинаций, должно быть четным. Если же существует хотя бы одна группа с номером i, в которой количество датчиков Pi четно, то решение построить можно. Для удобства далее будем считать, что i = N, а в начальный момент времени активным является первый датчик в каждой из групп, что не снижает общности рассмотрения. Для N = 2 задачу можно переформулировать следующим образом. В прямоугольнике размером P1
|