При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия.
Получение свидетельских показаний – непростая работа. Ситуация осложняется тем, что очень часто свидетели могут только приблизительно вспомнить номер автомобиля. При этом с большой вероятностью опрашиваемый может перепутать порядок цифр или букв в номере.
По полученному от свидетеля происшествия номеру, подсчитайте, сколько различных номеров может получиться из него перестановкой букв и/или цифр, а также выведите все такие номера.
Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.
В номере могут использоваться следующие буквы: «A», «B», «C», «E», «H», «K», «M», «O», «P», «T», «X», «Y» (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входных данных будут использоваться буквы латинского алфавита.
На вход программы поступает одна строка, которая представляет собой корректный автомобильный номер.
В первой строке выведите число k – количество номеров, которые могут получиться из заданного перестановкой букв и/или цифр.
В последующих k строках выведите все такие номера в произвольном порядке.
X772KX
9 X277XK X277KX X727XK X727KX X772XK X772KX K277XX K727XX K772XX
Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".
Организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). Считается, что никакие два таракана не могут прийти к финишу одновременно.
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".
Если завершить бега так, чтобы у каждого из болельщиков сыграла ровно одна из двух ставок, можно, то следует вывести номера тараканов в том порядке, в котором они окажутся в итоговой таблице результатов (сначала номер таракана, пришедшего первым, затем номер таракана, пришедшего вторым и т. д.) в одну строку через пробел. Если таких вариантов несколько, выведите любой из них.
Если требуемого результата добиться нельзя, выведите одно число 0.
Пример
| Входные данные | Выходные данные |
| 3 2 2 1 2 3 1 2 3 2 |
3 2 1 |
| 3 4 1 2 1 3 1 2 3 1 1 2 2 3 1 2 3 2 |
0 |
Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1\) + \(a_2\) +...+ \(a_n\) и \(a_1\) . \(a_2\) . ... . \(a_n\) не зависит от порядка выполнения в них действий и, следовательно, не меняется при произвольной расстановке в этих выражениях скобок.
В отличие от сложения и умножения, деление – операция не ассоциативная. Так, значение выражения вида \(a_1\)/\(a_2\)/ ... /\(a_n\) может меняться при расстановке в нем скобок.
Рассмотрим выражение вида
\(p_1\)/\(p_2\)/ ... /\(p_n\),
где все \(p_i\) – простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений.
Например, выражение 3/2/2 после расстановки скобок может принять два значения: 3/4 = (3/2)/2 и 3 = 3/(2/2).
В первой строке вводится число \(n\) ( 1\( \le\)n\( \le\)200). Следующая строка содержат \(n\) натуральных чисел – \(p_1\), \(p_2\),..., \(p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).
В первой строке выведите количество возможных значений, которые может принять выражение \(p_1\)/\(p_2\)/ ... /\(p_n\) при заданных \(p_i\) после расстановки в нем скобок. Во второй строке выведите количество целых чисел среди этих значений.
3 3 2 2
2 1
В одном магическом королевстве есть \(N\) городов, каждые два из которых соединены дорогой. Эти дороги были построены в давние времена Светлыми и Темными силами. Дороги, которые были построены Светлыми силами, вымощены белыми камнями, а те, что построены Темными – черными. Поскольку магические чары охраняют дороги, ни одно доброе существо не может пройти по дороге, вымощенной черными камнями, и ни одно злое – по белой дороге.
Когда-то давно люди решили избрать своих правителей и изгнали верховных магов из королевства. Однако недавно верховные маги Светлых и Темных сил договорились вернуть королевство под свой контроль. Для этого они хотят направить в некоторые города королевства магов, которые возьмут эти и смежные с ними города под свой контроль.
Точнее, если светлый маг будет направлен в некоторый город, то он возьмет под свой контроль этот город и все города, которые напрямую соединены с ним белыми дорогами. Аналогично, черный маг помимо города, в который он направлен, будет контролировать все города, напрямую соединенные с ним черными дорогами. Для захвата королевства требуется установить контроль над всеми городами.
Однако, при разработке плана захвата обнаружилось две трудности. Во-первых, выяснилось, что маг согласен принять участие в операции только если все маги, которые будут направлены в королевство, будут представлять ту же силу, что и он. То есть либо все участвующие в захвате маги должны быть светлыми, либо все они должны быть темными. Во-вторых, общее число магов, которые могут быть направлены в королевство не должно превышать K. Единственная надежда верховных магов заключается в том, что K достаточно велико, \(2^K\) >= \(N\).
Выясните, светлых или темных магов следует использовать для захвата королевства, а также в какие города их следует направить.
В первой строке вводятся целые числа \(N\) и \(K\) ( \(2 \le N \le 256\), \(2^K\) \(\ge\) \(N\), \(K \le N\)).
Следующие \(N\) строк содержат по \(N\) целых чисел каждая. На \(i\)-ой позиции \(i\)-ой из этих строк расположено число 0, которое означает, что город не соединен дорогой сам с собой. Для всех \(j \neq i\) число на \(j\)-ой позиции \(i\)-ой из этих строк равно 1, если \(i\)-ый город соединен с \(j\)-ым белой дорогой, и равно 2, если они соединены черной дорогой. Числа в строках разделены пробелами.
Гарантируется, что входные данные корректны, то есть если \(i\)-ый город соединен с \(j\)-ым белой дорогой, то и \(j\)-ый соединен с \(i\)-ым белой дорогой, аналогично в случае черных дорог.
Если захватить королевство при заданных условиях невозможно, выведите единственное число 0. В противном случае в первой строке выведите 1, если удастся захватить королевство с использованием светлых магов, и 2, если требуется использовать черных магов. В следующей строке выведите число L\( \le\)K – количество использованных магов. Третья строка должна содержать \(L\) целых чисел – номера городов, в которые следует направить магов. Заметьте, что вам не требуется минимизировать \(L\). Если решений несколько, выведите любое.
8 3 0 1 1 1 1 2 2 2 1 0 1 1 2 1 2 2 1 1 0 1 2 2 1 2 1 1 1 0 2 2 2 1 1 2 2 2 0 2 1 1 2 1 2 2 2 0 2 1 2 2 1 2 1 2 0 2 2 2 2 1 1 1 2 0
1 3 1 5 2
Найдите количество чисел \(Z\), удовлетворяющих неравенству \(A\) ≤ \(Z\) ≤ \(B\), таких, что в записи \(Z\) в двоичной системе счисления используется ровно 2 единицы. Например, если \(A\)=10; \(B\)=20; то таких чисел 5 (это числа \(10=1010_2\); \(12=1100_2\); \(17=10001_2\); \(18=10010_2\); \(20=10100_2\)).
На вход программы поступают два числа, записанных через пробел — \(A\), \(B\) ( 0 ≤ \(A\), \(B\) ≤ \(10^9\))
Выведите одно число – количество чисел \(Z\).
10 20
5