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

h1>Задача

Дано 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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *