BOOKS
Важным событием в жизни молодого издательства стало ежегодное участие во Франкфуртской международной книжной ярмарке. Полученная информация о новых тенденциях в издательском деле и проведённые переговоры о правах переиздания на произведений предвещает большой прорыв в этом направлении. При этом сильная конкуренция требует, чтобы уровень подготовки текста был на высоте.
Было решено, что издательство произведений каждого из авторов планируется проводить в нескольких томах, а сами произведения печататься в строго заданном порядке. При этом печать одного произведния в двух томах не допускается.
В каждом издании необходимо минимизировать максимальное число страниц в томах. До недавнего времени это решалось просто, но после издания романа Марселя Пруста в 14 томов и объёмом в более чем 9 млн. слов издательство всерьёз задумалось над возникшей проблемой. Вам необходимо в срочном порядке решить эту задачу.
Формат входного файла(BOOKS.IN):
N K
A[1] A[2] ... A[N]
N - число произведений
K - число томов, на которое требуется разбить
N, K, A[i] - натуральные числа, 1 < N <= 10^4, 1 < K <= N, A[i] <= 10^5.
Формат выходного файла(BOOKS.OUT):
M
M - число страниц самого большого из томов
Пример входного и выходного файлов:
BOOKS.IN:
8 4
10 20 25 25 21 3 20 3
BOOKS.OUT:
46
PLATES
На некотором заводе в своё время была внедрена технология производства оптических пластин с автоматической записью информации. В то время массовое производство не требовалось, и поэтому пластины технологически изготовлялись по одной штуке. Но с ростом популярности спрос требовал экспоненциального роста производительности. В связи с этим пластины стали изготавливаться в виде большого оптического листа. Это квадратный лист стороной в 2^n клеток и числом в 2^(2n) пластин, пронумерованный слева-направо сверху вниз от 1 до 2^(2n).
После получения листа производится запись информации в массовом порядке, и далее разбивается лист на отдельные пластины, т.е. преобразуется лист в очередь пластин. Было решено, что эта операция делается с минимальным числом изломов. Исходный лист сначала ломается пополам и слаживается справа налево:
Далее происходит такое же сложение снизу вверх. Действия повторяются до тех пор, пока не будет получена стопка из одиночных пластин. В такой стопке пластины нумеруются снизу вверх, начиная с 1. Например, для n=1 получаем такое преобразование:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
-> 1 4 16 13 ... 5
Данная операция достаточно хитрая. Вам необходимо написать программу, позволяющию по заданному номеру входной последовательности определить порядковый номер в выходной.
Формат входного файла(PLATES.IN):
N K
N - порядок степени пластины, т.е. число клеток стороны листа будет 2^N.
K - номер пластины на листе.
N, K - натуральные числа, 1 <= N <= 15, 1 <= K <= 2^(2*N).
Формат выходного файла(PLATES.OUT):
M
M - порядковый номер в выходной последовательности.
Пример входного и выходного файлов:
PLATES.IN:
2 7
PLATES.OUT:
10
PAINTING
Раскраска заготовок для мозаики производится следующим образом:
Задаются параметры прямоугольной раскраски - M и N. Это длина и ширина прямоугольника закраски. Внутри самого прямоугольника все цвета должны быть разными. Вся плоскость закраски разбивается на эти прямоугольники полностью так, что прямоугольники находятся рядом друг с другом и соприкасаются с 4-мя по граням, и с 4-мя по вершинам.
Прямоугольники все одинаковые по цветам и размерам.
Все цвета нумеруются натуральными числами от 1 до M*N и по номерам могут располагаться в прямоугольнике в произвольном порядке. Для случая M=3 и N=2 может быть получена такая раскраска:
126126126126...
534534534534...
126126126126...
534534534534...
...............
Всё было бы хорошо, однако на плоскости уже кто-то зарисовал некоторые клетки в произвольном порядке.
Требуется раскрасить плоскость таким образом, чтобы использовалось минимальное число цветов.
Формат входного файла (PAINT.IN):
N
X[1] Y[1] C[1]
X[2] Y[2] C[2]
...
X[N] Y[N] C[N]
N - количество закрашенных клеток
X[i], Y[i] - координата закрашенной i-й клетки, C[i] - её цвет.
N, X, Y, C - натуральные числа
(X[i], Y[i]) != (X[j], Y[j])
Формат выходного файла(PAINT.OUT):
M
M - количество необходимых цветов для закраски
FAST FOOD
Чебурашка съедает пирожное за A секунд. Крокодил Гена – за B секунд.
С мороженым Чебурашка разбирается за C секунд, а Гена – за D секунд.
Всего у наших героев M пирожных и N порций мороженого. Одно пирожное или одно мороженое Гена и Чебурашка одновременно есть не могут, но могут что-то частично съесть, отложить чтобы съесть потом либо отдать на съеденье своему другу.
Необходимо написать программу, позволяющую определить, за какое минимальное время Чебурашка и Гена могут съесть всё, что у них есть.
Формат входного файла:
A B C D M N
A – время на поедание пирожного Чебурашкой
B - время на поедание пирожного Геной
C– время на поедание мороженого Чебурашкой
D - время на поедание мороженого Геной
M – количество пирожных
N – количество порций мороженого
0 < A,B,C,D < 10^5
0 ≤ M,N < 10^4
A,B,C,D,M,N – целые числа.
Формат выходного файла:
T – время в секундах с точностью до 0.01
Пример входного файла(IN.TXT):
30 60 20 50 21
Пример выходного файла(OUT.TXT):
52.50
PENGUINS
Сообщество пингвинов, проводя археологические раскопки, наткнулось на большой склад льдин. Все они были аккуратно уложены, отполированы и представляли собой выпуклые многоугольники. Это был не первый такой случай в их истории и согласно логике пингвинов, это не имело никакой информационной ценности. Поэтому было решено это хозяйство оприходовать в на собственные нужды. В данный момент льдины использовались только как плавучие островки безопасности. При чём по обоснованным исследованиям лучших умов давно была выведена аксиома, что островок наиболее безопасен тогда и только тогда, когда он представляет собой круг. Естественно, большие островки ценятся больше малых, поэтому при их создании из льдин нужно сделать так, чтобы радиус островков был максимален. Что от вас и требуется – попробовать почувствовать себя пингвином, определяющим максимальный радиус островка из вытачиваемой льдины.
Формат входного файла:
N – количество точек многоугольника (натуральное число, не более 100)
X1Y1
X2Y2
...
XNYN
Xi,Yi– точки многоугольника в порядке сторон льдины (1)-(2), (2)-(3), … (N)-(1); целые числа, по модулю не превосходящие 10000.
Формат выходного файла:
R – радиус островка – натуральное число (результат округлить к наиближайшему целому числу).
Пример входного файла(IN.TXT):
4
0 0
100 200
200 200
200 -70
Пример выходного файла(OUT.TXT):
83
DIVIDE
Научившись находить остаток от деления, Петя решил опробовать свои знания на практике. Он загадал число S и начал находить остатки деления его на произвольные числа Ai. Увлекшись этим делом, Петя вскоре заметил, что загаданное число S не хочет делиться ни на одно из вновь придуманных чисел Ai. И мало того, что оно не делится, оно ещё и как будто издевается – каждый из получаемых остатков получался наибольшим из возможных.
Наутро после бессонной ночи Петя никак не мог вспомнить исходное число S. Но остались записи вычислений с числами Ai. После такого нервного перенапряжения Петя решить обратную задачу по нахождению минимального Sиз возможных не в состоянии. И видеть большие многозначные числа тоже. Помогите ему в нахождении числа S, но покажите максимум последние(младшие) 3 цифры, удалив лидирующие нули.
Формат входного файла:
N – число делителей ( натуральное число 1 < N < 15000 )
A1A2 … AN – используемые делители числа S(натуральные числа 1 < Ai < 10^4)
Формат выходного файла:
B1…BM – младшие цифры числа S(M = {1,2,3}).
Пример входного файла(IN.TXT):
3
2 3 4
Пример выходного файла(OUT.TXT):
11
STROKES
Для рисования больших штриховых линий в конструкторский отдел поступило два специальных прибора. Они обладали гибкими настройками и интуитивно понятным интерфейсом и позволяли рисовать линии с произвольными длинами штрихов. Но в один прекрасный день, в день истечения срока гарантии, эти приборы дали сбой. Первый из них стал рисовать только линии со штрихом длиной A и промежутком B, а второй со штрихом C и промежутком D. При чём они рисовали сразу всю линию и остановить их было невозможно.
Каждый раз, когда нужно было рисовать новую линию со штрихом E и промежутком F, коллективу отдела приходилось долго размышлять на тему, как это сделать с помощью имеющихся приборов. В конечном итоге было принято решение обратиться за помощью к целой бригаде программистов. Как вы догадались, вы член этой бригады, и на вас возложена вся ответственность за восстановление работоспособности коллег.
Программа должна определять минимальное количество проходов приборами для рисования заданной линии. Если это невозможно, то вывести в ответ 0.
Формат входного файла:
A B C D E F
A – штрих первого прибора
B – промежуток первого прибора
C – штрих второго прибора
D – промежуток второго прибора
E – требуемый штрих
F – требуемый промежуток
Формат выходного файла:
N – количество проходов приборами
Пример входного файла(IN.TXT):
2 7 4 14 6 3
Пример выходного файла(OUT.TXT):
3
Door Security
Для обеспечения тактической безопасности своих помещений корпорация Fearsoft внедрила новый пропускной режим и обновила общую систему охраны. Согласно новой концепции каждый из сотрудников имеет при себе пропускную пластиковую карточку, с помощью которой фиксируется то множество дверей, через которое он может пройти. Открытие остальных дверей для него недоступно.
При использовании такой системы на практике каждая дверь оборудовалась замком, в который прошивалось то множество карточек, которым было позволено его открыть. В процессе установки определились с правами сотрудников и заказали всё множество замков и карточек, при чём с запасом.
Казалось бы, проблемы безопасности корпорацию не должны были волновать. И они уже даже подумывали о переименовании. Но в одну прекрасную полнолунную ночь сторож обнаружил страшную пропажу: со склада исчезло ровно N штук пластиковых карточек. К этому времени накладные заказанных карточек давно ушли в лету и определить, какие из карточек были украдены, – невозможно. А сторожу по его профессиональной принадлежности известно, какие карточки есть и к каким замкам они подходят. Сторож может воспользоваться только своей карточкой и открыть самую главную входную дверь. Ждать утра крайне опасно, так как злоумышленники могут в любой момент появиться и завладеть всем имуществом корпорации.
В такой сложнейшей ситуации сторож принимает решение о монтаже на большой входной двери дополнительных замков, при чём таким образом, чтобы никто не смог до утра проникнуть в помещение. Это единственный реальный шанс обеспечения надёжного светлого будущего…
Помогите сторожу выбрать наименьшее количество замков для монтажа. Если это невозможно – сообщите об этом как можно скорее.
Формат входного файла:
N M K
A[1] B[1,1] B[1,2] … B[1,A[1]]
A[2] B[2,1] B[2,2] … B[2,A[2]]
…
A[K] B[K,1] B[K,2] … B[K,A[K]]
N – количество пропавших карточек.
M – количество замков.
K – количество карточек.
A[i] – число замков, которое можно открыть карточкой.
B[i,j] – номера замков, которые можно открыть данной карточкой.
A[i] > 0
B[i,j] > 0
K >= N
Формат выходного файла:
M
M – минимальное число замков, которое нужно повесить для полной защиты.
M = 0 в случае, если это невозможно.
SNAKE COMBAT
Согласно преданиям старины далёкой, в некотором царстве, некотором государстве повадился Змей Горыныч жителей убивать да выжигать. И стали люди выход искать. Призвал царь всех богатырей и повелел Змея извести.
В ту пору главным богатырём был Добрыня Никитич. И решился он один Змея победить. Выехал в чистое поле, вызвал Змея на поединок и давай сражаться. Но, как оказалось, Добрыня мог срубить Змею одним ударом только некоторое число голов, а после каждого удара некоторое число голов у Горыныча вырастало. При чём бой осложнялся тем, что богатырь не мог срубить меньшее число голов никаким образом.
Согласно всем преданиям, Добрыня победил Горыныча. Но все предания различаются тем, сколько было голов у Змея, сколько вырастало и сколько Добрыня мог голов за один раз срубить. В связи с этим вам ставится задача не только помочь победить Змея наибыстрейшим образом, но и отличить правдивые предания от ложных.
Формат входного файла:
N – начальное число голов Змея
AB – число голов, сколько мог отрубить Добрыня (только 2 числа)
M – сколько голов вырастало после каждого удара
N, A, B, M – натуральные числа, меньшие 30000.
Формат выходного файла:
K – минимальное число ударов для победы или 0, если победить невозможно
Пример входного файла(IN.TXT):
3
7 1
3
Пример выходного файла(OUT.TXT):
3
SMART WAR
Пентагон после изобретения smart-бомб всерьёз задумался над созданием более грозного оружия – smart-помех. Согласно господствующей доктрине, данные помехи должны определённым образом воздействовать на программное обеспечение противника и выводить его из строя.
Спецслужбы стран знали об этом проекте, но технические характеристики и поведение smart-помех были неизвестны.
После завершения одной из финальных стадий проекта на полигон были приглашены представители со всех стран мира. Испытания оказались успешными: все устройства международных делегаций оказались неработоспособными!
В ходе исследований над одним из таких устройств было выяснено, что данная помеха изменяет байты памяти атакуемого программного обеспечения так, что если содержимое ячейки в 16 с/с содержит символ 'A', то в значение ячейки записывается код 'A' согласно American Standard Code for Information Interchange - т.е. на 4116.
Для обеспечения безопасности отечественного программного обеспечения исследовательской лаборатории БЭМС ТС БелГУТа было поручено создание кода, позволяющего работать в условиях жёсткого воздействием smart-помех. Согласно поставленной задаче требуется создавать надёжный код, а он надёжен тогда и только тогда, когда на него не может воздействовать smart-помеха.
Вам для проверки уже созданного кода требуется написать программное обеспечение, позволяющее определить, надёжен код или нет.
Формат входного файла:
N – число байт кода ( натуральное число до 10000 )
A1A2A3A4 … AN - проверяемый код (числа в 16 с/с только с цифрами ‘0123456789abcdef’ и лидирующими нулями)
Формат выходного файла:
result – строка, содержащая либо ‘reliable’ (код надёжен) или ‘reliable’ (ненадёжен)
Пример входного файла(IN.TXT):
3
01 a3 fa
Пример выходного файла(OUT.TXT):
unreliable
BBT’s Sarcasm
Встретились как-то Пенни и Шелдон, и они разговорились:
- Привет! Как дела на работе?
- Круто! Надеюсь, что буду работать официанткой до конца своих дней!
- Это был сарказм?
- Нет.
- А это был сарказм?
- Да.
- А это был ...
И тут вмешался Леонард, который никогда не говорит сарказмов.
Помогите Шелдону восстановить истинность первого высказывания.
Формат входного файла:
N – число ответов на вопрос ( от 0 до 1000000 включительно );
Q - вопрос (любые буквы до перевода каретки)
A1 - ответ 'yes' или 'no'
A2
...
AN
Формат выходного файла:
Q is X
где X - 'true' или 'false' (в случае истинности начальоного утверждения 'true', ложности 'false')
Пример входного файла:
I hope I'm a waitress for my whole life
yes
no
yes
yes
Пример выходного файла:
I hope I'm a waitress for my whole life is false
Comments (0)
You don't have permission to comment on this page.