Страница: 1 2 >> Отображать по:

#113684

Бактерии

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача A ]

У юного биолога Антона в красивой стеклянной колбе живут \(n\) бактерий.

Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если \(p\) — некоторое простое число, то Антон умеет в домашних условиях получать вещество \(C_pH_{2p \ + \ 1}OH\), которое, будучи добавленным в колбу, уменьшает число бактерий ровно в \(p\) раз. Если же число бактерий не делилось на \(p\), то результат действия вещества не определен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество \(C_pH_{2p \ + \ 1}OH\) только когда число бактерий делится на p.

Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (\(C_{20}H_{25}N_{30}\)). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат.

Антон хочет, чтобы в колбе стало \(m\) бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.

Входные данные

Во входном файле содержатся два натуральных числа \(n\) и \(m\) (\(1 \le n, m \le 10^9\) ) — изначальное и желаемое число бактерий в колбе у Антона.

Выходные данные

Если получить ровно m бактерий невозможно, выведите в выходной файл слово «Impossible».

Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ, которая позволяет его достичь, в следующем формате: добавление вещества \(C_pH_{2p \ + \ 1}OH\) кодируется числом \(p\), добавление вещества \(C_{20}H_{25}N_{30}\) — числом \(0\). Числа должны быть разделены пробелами и/или переводами строк.

Если существует несколько кратчайших последовательной добавлений веществ, оставляющих \(m\) бактерий, выведите любую из них.

Пояснения к примеру

В первом примере Антону требуется добавлять в колбу вещества три раза: сначала добавить \(C_2H_5OH\), уменьшая число бактерий в два раза, то есть оставляя \(6\) бактерий; затем добавить \(C_{20}H_{25}N_{30}\), возводя число бактерий в квадрат, то есть увеличивая его до \(36\); и наконец, добавить снова \(C_2H_5OH\), деля число бактерий на два и делая его равным \(18\).

Примеры

Входные данные

12 18

Выходные данные

2 0 2

Входные данные

56 6

Выходные данные

Impossible

#113685

Шахматная головоломка

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача B ]

Борис очень любит различные шахматные головоломки. У него есть младший брат Вова. Борис очень любит задавать простые головоломки Вове, а в награду, если тот их решит, давать ему конфету. Но Вова, к сожалению, не очень любит шахматы, зато любит программирование.

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером \(8 \times 8\) клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

Напомним, что конь бьет те клетки, которые отстоят от его текущего положения на две клетки по горизонтали и одну клетку по вертикали, или на две клетки по вертикали и одну по горизонтали.

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.

Входные данные

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от «a» до «h», обозначающая номер столбца в котором находится конь, потом цифра от «1» до «8», обозначающая номер строки.

Выходные данные

В первую строку выведите положение ладьи в аналогичном формате, во вторую строку выведите положение слона.

Гарантируется, что требуемая расстановка всегда существует

Примеры

Входные данные

a1

Выходные данные

b1
c3

#113686

Шоколад

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача C ]

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник \(n \times m\), который полностью состоит из маленьких шоколадных долек — прямоугольников \(2 \times 1\).

Петя делит шоколадку на две части, разламывая ее вдоль некоторой прямой, параллельной одному из краев шоколадки. Ни Петя, ни Маша не любят ломаные дольки, поэтому Петя хочет разломать шоколадку так, чтобы ни одна долька не была повреждена.

Помогите Пете поделиться шоколадкой с Машей.

Входные данные

В первой строке входного файла два целых числа \(n\) и \(m\) (\(1 \le n, \ m \le 20;\) хотя бы одно из чисел \(n\) и \(m\) — четно). Далее следуют \(n\) строк по \(m\) чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от \(1\) до \(\frac{n \cdot m}{2}\), и никакие две дольки не имеют одинаковые номера.

Выходные данные

В выходной файл выведите «Yes», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «No»

Примеры

Входные данные

2 3
1 1 2
3 3 2

Выходные данные

Yes

#113687

Луна

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача D ]

Начинающий астроном Даша наконец-то обзавелась цифровым фотоаппаратом. Конечно, фиксировать звездное небо нажатием кнопки, а уже затем производить исследования — гораздо удобней.

Разрешающая способность матрицы фотоаппарата оказалась не слишком высокой, да и на фотографиях ночного неба можно различить только два цвета: черный и белый. Впрочем, в этом есть и свои плюсы: Даша сделала уже огромное число снимков, а память все еще не закончилась. Теперь Дашу интересует положение Луны на каждом из снимков.

Будем считать, что Луна на снимке выглядит как круг с центром в точке изображения \(C\) и целым неотрицательным радиусом r, то есть как множество белых точек, расстояние от центров которых до точки \(C\) не больше \(r\). Луна полностью поместилась на снимке.

Также некоторые достаточно яркие звезды могут присутствовать на снимке в виде отдельных белых точек. Таких точек не больше \(25\). Объектов, отличных от Луны и звезд, на снимке не изображено.

Напишите программу, которая по изображению найдет наибольший возможный радиус круга, который соответствует Луне, а также ее возможное положение.

Входные данные

В первой строке ввода записаны целые числа \(w\) и \(h\) — горизонтальное и вертикальное разрешение снимка, соответственно
(\(1 \le w, \ h \le 50\)). В следующих \(h\) строках записано по \(w\) символов «.» (черная точка) или «*» (белая точка).

Выходные данные

В первой строке выведите натуральное число — максимальный радиус изображения Луны. Во второй строке выведите координаты (столбец, затем строку) центра изображения Луны с данным радиусом. Столбцы и строки нумеруются с единицы, слева направо и сверху вниз, соответственно.

Если центров может быть несколько, выведите любой. Гарантируется, что корректный ответ существует.

Примеры

Входные данные

7 8
.*.*...
.*****.
.*****.
*******
.*****.
.*****.
...*...
......*

Выходные данные

3
4 4

Входные данные

5 4
.....
.....
..*..
.*...

Выходные данные

0
3 3

#113688

Ожерелье

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2010, Задача E ]

Юная любительница ювелирных изделий Октябрина к празднику 4-го ноября хочет подарить своей лучшей подруге Тракторине ожерелье из \(n\) черных и розовых жемчужин.

Чтобы ожерелье не было скучным, Октябрина хочет расположить жемчужины таким образом, чтобы как его ни повернуть, левая половина ожерелья не была симметрична правой. Более формально — у него не должно быть оси симметрии.

Ось симметрии делит ожерелье на непрерывные части, содержащие одинаковое число жемчужин. При этом, если ось проходит через какую-то жемчужину, то она относится к обеим частям, если же ось проходит между двух жемчужин, то эти жемчужины находятся в разных частях. Таким образом, следующие ожерелья имеют ось симметрии:

Ваша задача — помочь Октябрине найти необходимую расстановку жемчужин.

Входные данные

Первая и единственная строка входного файла содержит единственное число \(n \ (2 \le n \le 1000\)) — требуемое количество жемчужин в ожерелье.

Выходные данные

Если искомой расстановки не существует, выведите в выходной файл единственное число \(−1\), иначе выведите \(n\) целых чисел — расстановку жемчужин. Розовой жемчужине соответствует число \(0\), черной — число \(1\).

Пояснение к примеру

Растановка жемчужин в первом примере:

Примеры

Входные данные

Выходные данные

0 0 1 0 1 1

Входные данные

Выходные данные

-1

Страница: 1 2 >> Отображать по:

Выбрано

Отменить

Добавить в контест