e-olymp 2812. Уголок

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

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

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ j-ой из этих строк равен [latex]’X'[/latex] (большая буква икс), если клетка вырезана, и ‘[latex].[/latex]’ (точка) в противном случае.

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

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные Выходные данные
2 2
..
..
4
2 3
..X
.X.
1
5 4
….
X.XX
….
X..X
..XX
12

Код программы

Решение

Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем его правдой, если доска на точке не имеет дырки (когда вводится точка),и ложью в противном случае. Далее, проверяем существуют ли не пустые клетки и добавляем +1 к сумме уголков. Выводим сумму.

Ссылки

e-olymp
Ideone
 

e-olymp 7492. Будильник

Задача

Алиса любит свой цифровой будильник. Она устанавливает его каждый вечер. Прошлой ночью Алисе приснились ее часы. К сожалению, единственное, что она помнит — так это количество отображаемых сегментов на часах. Алиса хочет узнать, какое время показывали ее часы во сне.

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные Выходные данные
23 00:02
28 Impossible
0 Impossible
15 01:12

Код программы

Решение

Перебираем i и j (от 0 до 24 и 60 соответственно). a=seg[i/10] (для десятков) и a=seg[i%10] (для остальных чисел) то же самое делаем для j. Тем самым, мы перебираем все возможные варианты количества сегментов. Если a==n (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим [latex]Impossible[/latex].

Ссылки

e-olymp
Ideone

e-olymp 247. Несчастливый автобус

Задача

Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя — очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит «двойка» …

Помогите Вите составить список автобусов, которые он считает «несчастливыми» автобусами.

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

В первой строке записано число [latex]N (0 ≤ N ≤ 100000)[/latex] — количество автобусов, далее указаны номера автобусов [latex]m_i (0 ≤ m_i ≤ 2^{31}-1)[/latex] по одному в строке.

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

Выведите количество «несчастливых» автобусов.

Тесты

Входные данные Выходные данные
2
0
3
1
3
1
2
4
1
4
2
1
3
5
2
5
1
2
3
7
4
3

Решение

В двоичном коде число заканчивается на [latex]1[/latex] тогда и только тогда, когда остаток от деления на [latex]2[/latex] равен [latex]1[/latex] . Для определения предпоследнего символа , в каждом числе отбрасываем последний символ двоичного представления путем деления нацело на [latex]2[/latex] и проверяем нечетность. Подсчитываем все нужные варианты

Ссылки

e-olymp
Ideone

e-olymp 109. Нумерация

Задача

Для нумерации [latex]m[/latex] страниц книги использовали [latex]n[/latex] цифр. По заданному [latex]n[/latex] вывести [latex]m[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]n[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Вывести количество страниц в книге.

Тесты

Входные данные Выходные данные
27 18
15 12
9 9
49 29
50 0

Решение

Для решения этой задачи я описал [latex]3[/latex] переменные: n, mи minus, где n- количество цифр, использованных для нумерации страниц, m — количество страниц и minus — «счетчик», для определения количества цифр в числе [latex]a[/latex]. Использовал [latex]2[/latex] вложенных цикла, где счетчик [latex]a[/latex] — определяет разрядность числа страницы [latex]b[/latex]. Внутри вложенного циклы перед вычитанием minusиз n поставил проверку на выполнения условий: если n == 0, значит мы закончили считать страницы и если [latex]n — minus < 0[/latex], значит на следующей итерации мы запишем в [latex]n[/latex] отрицательное значение, значит во входных данных была ошибка.

Ссылки

e-olymp
Ideone

e-olymp 918. Какая четверть?

Задача

Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex] , если однозначно определить четверть невозможно.

Тесты

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

Выходные данные
[latex]x[/latex] [latex]y[/latex] Четверть
12 31 1
-10 18 2
-15 -25 3
13 -13 4
0 0 0

 

Решение

Четверти координатной плоскости

В прямоугольной системе координат на плоскости выделяют 4 четверти: 1, 2, 3, 4.
1-й четветри соответствуют точки, имеющие обе ([latex]x[/latex] и [latex]y[/latex]) положительные координаты.
2-ая четверть: [latex]x \lt 0[/latex], [latex]y \gt 0[/latex].
3-ая четверть: [latex]x \lt 0[/latex], [latex]y \lt 0[/latex].
4-ая четверть: [latex]x \gt 0[/latex], [latex]y \lt 0[/latex].
Точка с координатами ([latex]0[/latex];[latex]0[/latex]), находится в начале координат.
Если точка лежит на оси [latex]«Oy»[/latex], то её абсцисса равна [latex]0[/latex].
Если точка лежит на оси [latex]«Ox»[/latex], то её ордината равна [latex]0[/latex].

Ссылки

e-olymp
Ideone

e-olymp 2262. Явная формула

Задача

Дано 10 булевых переменных  [latex] x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10} [/latex]. Вычислите количество пар и троек, у которых хотя бы одна переменная установлена в [latex]1[/latex]. Установим [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = 1[/latex]  если это количество нечетно и [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = 0[/latex]  если количество четно.
Рассмотрим явную формулу, которая реализует функцию [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}):[/latex] [latex]f( x_{1},\:x_{2},\:x_{3} ,\:x_{4},\:x_{5},\:x_{6},\:x_{7},\:x_{8},\:x_{9},\:x_{10}) = [/latex] [latex] \left( x_{1}\vee x_{2} \right) \oplus \left( x_{1}\vee x_{3} \right) \oplus \left( x_{1}\vee x_{4} \right)\oplus \left( x_{1}\vee x_{5} \right)
\oplus \left( x_{1}\vee x_{6} \right) \oplus \left( x_{1}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{8} \right) \\
\oplus \left( x_{1}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{3} \right)
\oplus \left( x_{2}\vee x_{4} \right) \oplus \left( x_{2}\vee x_{5} \right) \oplus \left( x_{2}\vee x_{6} \right) \\
\oplus \left( x_{2}\vee x_{7} \right) \oplus \left( x_{2}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{4} \right) \oplus \left( x_{3}\vee x_{5} \right) \\
\oplus \left( x_{3}\vee x_{6} \right) \oplus \left( x_{3}\vee x_{7} \right) \oplus \left( x_{3}\vee x_{8} \right)
\oplus \left( x_{3}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{5} \right) \\
\oplus \left( x_{4}\vee x_{6} \right) \oplus \left( x_{4}\vee x_{7} \right) \oplus \left( x_{4}\vee x_{8} \right)
\oplus \left( x_{4}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{6} \right) \\
\oplus \left( x_{5}\vee x_{7} \right) \oplus \left( x_{5}\vee x_{8} \right) \oplus \left( x_{5}\vee x_{9} \right)
\oplus \left( x_{5}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{7} \right) \oplus \left( x_{6}\vee x_{8} \right) \\
\oplus \left( x_{6}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{10} \right) \oplus \left( x_{7}\vee x_{8} \right)
\oplus \left( x_{7}\vee x_{9} \right) \oplus \left( x_{7}\vee x_{10} \right) \oplus \left( x_{8}\vee x_{9} \right) \\
\oplus \left( x_{8}\vee x_{10} \right) \oplus \left( x_{9}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{3} \right)
\oplus \left( x_{1}\vee x_{2}\vee x_{4} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{5} \right) \\ \oplus \left( x_{1}\vee x_{2}\vee x_{6} \right)
\oplus \left( x_{1}\vee x_{2}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{8} \right) \oplus \left( x_{1}\vee x_{2}\vee x_{9} \right)
\oplus \\ \left( x_{1}\vee x_{2}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{4} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{5} \right)
\oplus \left( x_{1}\vee x_{3}\vee x_{6} \right) \oplus \\ \left( x_{1}\vee x_{3}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{3}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{3}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{5} \right) \\
\oplus \left( x_{1}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{4}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{4}\vee x_{9} \right) \oplus \\ \left( x_{1}\vee x_{4}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{6} \right)
\oplus \left( x_{1}\vee x_{5}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{1}\vee x_{5}\vee x_{9} \right) \\
\oplus \left( x_{1}\vee x_{5}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{1}\vee x_{6}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{6}\vee x_{9} \right) \\ \oplus \left( x_{1}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{1}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{1}\vee x_{7}\vee x_{10} \right) \oplus \\ \left( x_{1}\vee x_{8}\vee x_{9} \right)
\oplus \left( x_{1}\vee x_{8}\vee x_{10} \right) \oplus \left( x_{1}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{4} \right)
\oplus \left( x_{2}\vee x_{3}\vee x_{5} \right) \\ \oplus \left( x_{2}\vee x_{3}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{7} \right)
\oplus \left( x_{2}\vee x_{3}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{3}\vee x_{9} \right) \oplus \\ \left( x_{2}\vee x_{3}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{5} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{7} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{8} \right) \\ \oplus \left( x_{2}\vee x_{4}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{4}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{4}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{6} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{7} \right) \\
\oplus \left( x_{2}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{5}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{2}\vee x_{6}\vee x_{8} \right) \\ \oplus \left( x_{2}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{2}\vee x_{7}\vee x_{8} \right) \oplus \left( x_{2}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{2}\vee x_{7}\vee x_{10} \right) \\ \oplus \left( x_{2}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{2}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{2}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{5} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{6} \right) \\
\oplus \left( x_{3}\vee x_{4}\vee x_{7} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{4}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{4}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{6} \right) \\ \oplus \left( x_{3}\vee x_{5}\vee x_{7} \right)
\oplus \left( x_{3}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{5}\vee x_{10} \right)
\oplus \left( x_{3}\vee x_{6}\vee x_{7} \right) \\ \oplus \left( x_{3}\vee x_{6}\vee x_{8} \right) \oplus \left( x_{3}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{7}\vee x_{8} \right) \\ \oplus \left( x_{3}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{3}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{3}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{3}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{3}\vee x_{9}\vee x_{10} \right) \\ \oplus \left( x_{4}\vee x_{5}\vee x_{6} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{7} \right)
\oplus \left( x_{4}\vee x_{5}\vee x_{8} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{5}\vee x_{10} \right) \\
\oplus \left( x_{4}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{4}\vee x_{6}\vee x_{8} \right) \oplus \left( x_{4}\vee x_{6}\vee x_{9} \right)
\oplus \left( x_{4}\vee x_{6}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{7}\vee x_{8} \right) \\ \oplus \left( x_{4}\vee x_{7}\vee x_{9} \right)
\oplus \left( x_{4}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{4}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{4}\vee x_{8}\vee x_{10} \right) \\
\oplus \left( x_{4}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{7} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{8} \right)
\oplus \left( x_{5}\vee x_{6}\vee x_{9} \right) \oplus \left( x_{5}\vee x_{6}\vee x_{10} \right) \\ \oplus \left( x_{5}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{5}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{5}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{5}\vee x_{8}\vee x_{9} \right)
\oplus \left( x_{5}\vee x_{8}\vee x_{10} \right) \\ \oplus \left( x_{5}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{7}\vee x_{8} \right)
\oplus \left( x_{6}\vee x_{7}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{7}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{9} \right) \\
\oplus \left( x_{6}\vee x_{8}\vee x_{10} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{6}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{6}\vee x_{9}\vee x_{10} \right) \\ \oplus \left( x_{7}\vee x_{8}\vee x_{9} \right) \oplus \left( x_{7}\vee x_{8}\vee x_{10} \right)
\oplus \left( x_{7}\vee x_{9}\vee x_{10} \right) \oplus \left( x_{8}\vee x_{9}\vee x_{10} \right) \\
[/latex]

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

Содержит [latex]10[/latex] чисел  [latex] x_{1},\ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10} [/latex].  Каждое из них равно [latex]0[/latex]  или  [latex]1[/latex].

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

Вывести единственное значение [latex]f( x_{1}, \ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10}).[/latex]

Тесты

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

Решение

Рассмотрим все возможные пары и тройки разных переменных из этих десяти (всего существует [latex]45[/latex] пар и  [latex]120[/latex] троек).  Данная формула реализует функцию [latex]f( x_{1},\ x_{2},\ x_{3} ,\ x_{4},\ x_{5},\ x_{6},\ x_{7},\ x_{8},\ x_{9},\ x_{10}) [/latex].   В указанной формуле бинарные операции обозначаются  «[latex]\vee[/latex]»  и  «[latex]\oplus[/latex]»,  где «[latex]\vee[/latex]»  —  логическое или ,  а «[latex]\oplus[/latex]»  —  исключающее или

Ссылки

e-olymp
Ideone