Темы
Информатика(2656 задач)
--->
9 задач
<---
#1766
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача F
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Для заданного числа \(n\) найдите наименьшее положительное целое число с суммой цифр \(n\), которое делится на \(n\).
Входные данные
Во входном файле содержатся целое число \(n\) (1 ≤ \(n\) ≤ 1000).
Выходные данные
Выходной файл должен содержать искомое число. Ведущие нули выводить не разрешается.
Примеры
Входные данные
1
Выходные данные
1
Входные данные
10
Выходные данные
190
#1767
Темы:
[Рекуррентные последовательности]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача G
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется определить количество нечетных чисел в заданной строке треугольника Паскаля.
Треугольник Паскаля – это бесконечный треугольник из чисел, который имеет следующий вид:
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число – единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.
Таким образом, \(i\)-ая строка содержит \(i\) + 1 число. Если обозначить \(j\)-ый элемент \(i\)-ой строки как \(a_i\),\(j_,\) то выполняется равенство \(a_i\),\(j\) = \(a_i\) - 1,\(j\) - 1 + \(a_i\)-1,\(j\). Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами -1 и \(i\)) равными нулю.
Коля хочет узнать, сколько нечетных чисел в n-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.
Входные данные
Во входном файле содержится число \(n\) (0 ≤ \(n\) ≤ 2 ×\(10^9\)).
Выходные данные
Выходной файл должен содержать одно число – количество нечетных чисел в \(n\)-ой строке треугольника Паскаля.
Примеры
Входные данные
0
Выходные данные
1
Входные данные
5
Выходные данные
4
Входные данные
7
Выходные данные
8
#1768
Темы:
[Двумерные массивы]
[Линейный поиск]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача H
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.
Входные данные
Первая строка входного файла содержит числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 200). Следующие \(m\) строк содержат описание рисунка. Каждая строка содержит ровно \(n\) символов. Символ «.» обозначает пустой квадрат, а символ «#» – закрашенный.
Выходные данные
Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.
Если же этого сделать нельзя, выведите в выходной файл «NO».
Примеры
Входные данные
2 1 # .
Выходные данные
NO
Входные данные
2 2 .. ##
Выходные данные
YES .. ab
Входные данные
1 3 ###
Выходные данные
YES abb
Входные данные
3 1 . # #
Выходные данные
YES . a b
#1769
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2004,
Задача I
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, \(n\). Получились числа 1, 10, 11, 100, 101, 110, 111, …
После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число \(k\) и в каждой строке, идя слева направо, выделил красным цветом каждый \(k\)-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, \(k\) + 1, 2\(k\) + 1, … Например если \(k\) = 2, \(n\) = 56 то получились бы такие строки:
(красные нули выделены жирным шрифтом и подчеркнуты)
Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.
Входные данные
Во входном файле содержатся числа \(n\) и \(k\) (1 ≤ \(n\) < \(2^{31}\), 1 ≤ \(k\) ≤ 30).
Выходные данные
Выходной файл должен содержать одно число – количество красных нулей.
Примеры
Входные данные
5 1
Выходные данные
4
Входные данные
23 3
Выходные данные
20
Выбрано
:
|