Страница: 1 2 3 4 5 6 >> Отображать по:
#32
Монетки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В Волшебной стране используются монетки достоинством A1, A2,…, AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

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

Сначала вводится число N (1≤N≤109), затем — число M (1≤M≤15) и далее M попарно различных чисел A1, A2,…, AM (1≤Ai≤109).

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

Выведите сначала K — количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один).

Оценка задачи

1 балл получат программы, правильно решающие задачу с дополнительными ограничениями Ai≤106, M≤10.

Примеры
Входные данные
5 2
1 2
Выходные данные
3
2 2 1
Входные данные
7 2
1 2
Выходные данные
-1
Входные данные
5 2
3 4
Выходные данные
0
#33
Сверим часы
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

В компании MacroHard в последнее время резко участились опоздания сотрудников. Проанализировав ситуацию, руководство решило, что это вызвано большим разбросом в показаниях наручных часов сотрудников. После дополнительного совещания руководящего состава было постановлено, что все сотрудники должны перевести часы на одно и то же время (не важно какое).

Все сотрудники компании носят исключительно электронные часы одного образца. Время на них отображается в формате HH:MM:SS (где HH — часы, MM — минуты, SS — секунды, всегда отображаются в виде двух цифр, 00≤HH≤23, 00≤MM≤59, 00≤SS≤59). Перевод часов осуществляется с помощью двух кнопок. Первая кнопка меняет поле редактирования следующим образом: после первого нажатия часы переходят из режима отображения времени в режим редактирования поля HH, после второго — в режим редактирования поля MM, после третьего — в режим редактирования поля SS, а после четвертого возвращаются в режим отображения времени и т.д. по циклу. Каждое нажатие второй кнопки приводит к увеличению редактируемого поля на единицу (в режиме отображения времени ничего не происходит). При переполнении секунд поле SS обнуляется, а MM увеличивается на единицу, при переполнении минут поле MM обнуляется, а HH увеличивается на единицу, а при переполнении часов просто обнуляется поле HH.

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

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

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

Первая строка входных данных содержит натуральное число N (1≤N≤200) — количество сотрудников компании. Последующие N строк содержат показания часов каждого из сотрудников в формате "HH:MM:SS".

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

Выведите одно число — минимальное суммарное количество нажатий.

Система оценки

1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤2.

Примеры
Входные данные
2
08:01:01
07:59:00
Выходные данные
7
#41
Быстрые шахматы
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

На шахматной доске (размером 8 Х 8 клеток) расставлены фигуры. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти последовательность ходов, после которой на доске останется одна фигура.<

Ладья ходит по горизонтали или вертикали на любое число клеток. Слон ходит по диагонали на любое число клеток. Ферзь ходит по горизонтали, вертикали или диагонали на любое число клеток. Эти фигуры не могут перепрыгивать через другие фигуры. Конь ходит на две клетки по горизонтали или вертикали и на одну клетку в перпендикулярном направлении (например, на 2 клетки вверх и на одну клетку вправо и т.п.), при этом он может перепрыгивать через другие фигуры.

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

В восьми строках входных данных записаны по 8 символов, описывающих шахматную доску: R — ладья, B — слон, K — конь, Q — ферзь, точка обозначает пустую клетку. На доске изначально стоит не менее двух и не более десяти фигур.

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

Выведите возможную последовательность в следующем формате. Для каждого хода указывается сначала клетка, с которой делается ход, затем двоеточие, затем клетка, на которую делается ход. Клетка задается столбцом и строкой: столбцы нумеруются слева направо строчными латинскими буквами a, b, c, d, e, f, g, h; строки — снизу вверх цифрами 1, 2, 3, 4, 5, 6, 7, 8.

Если решений несколько, приведите любое из них. Если решений нет, выведите NO SOLUTION

Примеры
Входные данные
........
........
.B......
........
........
....K...
........
........
Выходные данные
b6:e3
Входные данные
..K.....
..K.....
BR......
.B......
........
........
........
........
Выходные данные
c7:a6
b6:a6
b5:a6
a6:c8
#191
Шахматный детектив
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача A ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Дано изображение состоящее из черных, белых и серых клеток. Необходимо определить, может ли изображение быть шахматной доской (клетки доски могут состоять из нескольких маленьких клеток). 

Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

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

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

 

includegraphics{pics/chess.1} includegraphics{pics/chess.2}

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

Шахматная доска – это квадрат, разбитый на x2 (для некоторого x) равных квадратов – полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет – черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

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

В первой строке вводятся два целых числа: m и n – размеры фрагмента фотографии в пикселях ( 1\( le\)m, n\( le\)250).

Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i, j). Символ «.» (точка) означает белый пиксель, символ «*» – черный, символ «?» – серый.

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

Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите  слово «YES». После этого выведите m строк по n символов в каждой – изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае программа должна вывести слово «NO».

Примеры
Входные данные
4 5
*.?.?
.***.
.*?*.
.*?*.
Выходные данные
YES
*...*
.***.
.***.
.***.
Входные данные
4 5
..?..
.***.
.*?*.
.*?*.
Выходные данные
NO
#241
Тапочки
  
Темы: [Перебор]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

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

Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.

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

Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.

Примеры
Входные данные
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
Выходные данные
0
Страница: 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест