Напишите программу, которая по изображению поля для игры в «Крестики-нолики» определит, могла ли такая ситуация возникнуть в результате игры с соблюдением всех правил.
Напомним, что игра в «Крестики-нолики» ведется на поле 33. Два игрока ходят по очереди. Первый ставит крестик, а второй – нолик. Ставить крестик и нолик разрешается в любую еще не занятую клетку поля. Когда один из игроков поставит три своих знака в одной горизонтали, вертикали или диагонали, или когда все клетки поля окажутся заняты, игра заканчивается.
Вводится три строки по три числа в каждой, описывающих игровое поле. Число 0 обозначает пустую клетку, 1 – крестик, 2 – нолик. Числа в строке разделяются пробелами.
Требуется вывести слово YES, если указанная ситуация могла возникнуть в ходе игры, и NO в противном случае.
1 1 1 1 1 1 1 1 1
NO
2 1 1 1 1 2 2 2 1
YES
1 1 1 2 0 2 0 0 0
YES
0 0 0 0 1 0 0 0 0
YES
1 1 1 2 2 2 0 0 0
NO
Вася и Петя играют в следующую игру. Они взяли некоторую последовательность символов и дальше получают из нее новые последовательности, отбрасывая несколько первых символов исходной последовательности (разрешается в том числе не отбрасывать ни одного символа, но не разрешается отбрасывать сразу все символы). Каждый называет по одной такой последовательности. Выигрывает тот, чья последовательность будет идти раньше в алфавитном порядке.
Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.
Напишите программу, которая по данной последовательности определит, что нужно назвать Васе, чтобы не проиграть Пете.
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.
В выходной файл выведите выигрышную последовательность.
Примеры
| Входные данные | Выходные данные | Комментарии |
| 4 MAMA | A | Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A |
| 4 ALLO | ALLO | Выигрышной является исходная строка |
| 5 BBABB | ABB |
|
Дано верное равенство вида a1+a2+…+aN=b1+b2+…bM, где a1,a2,…,aN,,b1,b2,…,bM – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c1+c2+…+cN=d1+d2+…+dM, где c1,c2,…,cN,d1,d2,…,dM — целые числа, и при этом c1 получено округлением числа a1 до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c2 получено округлением a2, …, cN – округлением aN, d1 – округлением b1, …, dM – округлением bM. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.
Во входном файле задано сначала число N, затем N чисел a1, a2, …, aN, затем число M, затем числа b1, b2, …, bM. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a1+a2+…+aN=b1+b2+…bM.
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c1,c2,…,cN, а затем числа d1,d2,…,dM. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.
Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.
Комментарии к примерам тестов
1. Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
2. Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
3. Здесь верными являются как ответ 1=1, так и 0=0.
3 0.15 -3.000 2.7 1 -0.15
1 -3 2 0
2 1.7 2.5 3 1 2.000 1.20
2 2 1 2 1
1 0.5 1 0.5
0 0
Ученику второго класса рассказали правила, как нужно выполнять арифметические действия, чтобы вычислить значение арифметического выражения, состоящего из чисел, скобок и знаков арифметических операций + (сложение) и * (умножение). После этого ему дали упражнения — несколько задач, в которых требуется расставить порядок выполнения действий. Помогите ему.
Правила вычисления выражения, рассказанные ученику, звучат так. Если в выражении вообще нет скобок, то сначала выполняются все операции умножения слева направо, а затем — операции сложения также слева направо. Если же в выражении есть скобки, то находится самая левая пара скобок (открывающая и закрывающая), содержащая внутри себя бесскобочное выражение, которое может быть вычислено по вышеописанным правилам. Дальше это выражение (вместе со скобками) мысленно удаляется из выражения и заменяется числом – результатом. Если в выражении остались скобки, то процедура повторяется.
Напишите программу, которая для корректного выражения будет определять порядок выполнения арифметических действий. Поскольку сами числа в этой задаче нам будут не существенны, мы заменим их на знаки #.
Во входном файле записана одна строка, состоящая из символов #, +, *, (, ). Длина строки не превышает 250 символов. Строка соответствует правильному арифметическому выражению.
В выходной файл нужно вывести ту же строку, заменив знаки операций + и * в ней натуральными числами, задающими порядок выполнения действий в соответствии с описанными правилами.
#+#*#
#2#1#
#+#+(#+#)
#2#3(#1#)
#+(#+#*#)*#+#
#4(#2#1#)3#5#
#+#+#+#+#+#+#+#+#+#+#
#1#2#3#4#5#6#7#8#9#10#
#+#+(#+(#+#))+(#+#)
#4#5(#2(#1#))6(#3#)
Васю угостили конфетами, а он решил частью конфет поделиться со своим младшим братом Петей. Однако он хочет разделить конфеты не поровну, а по-братски.
Для этого Вася решил сыграть сам с собой в следующую игру. Он разложил конфеты на столе в несколько кучек, которые расположил в ряд. Если кучек не меньше двух, то из первой и последней в этом ряду кучек он выбирает ту, в которой меньше конфет. Пусть в наименьшей кучке оказалось B конфет. Тогда он B конфет перекладывает из первой кучки во вторую, и также B конфет перекладывает из последней кучки в предпоследнюю. При этом, естественно, одна из кучек (или даже две, если в первой и последней кучках конфет было поровну) становится пустой, и Вася забывает про ее существование. Он повторяет эти операции до тех пор, пока на столе не останется одна или две кучки.
Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.
Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.
Начальное расположение кучек конфет будет описываться K парами чисел Ai, Ni, которые обозначают, что на столе выложено подряд Ni кучек конфет, по Ai конфет в каждой.
Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.
В выходной файл выведите сначала 1 или 2 — количество кучек конфет, которые останутся в конце игры. Затем выведите соответственно одно или два числа — количества конфет в оставшихся кучках.
Комментарии к примерам тестов
1. Исходно конфеты расположены в следующих кучках: 2 кучки по 2 конфеты, две кучки из 3-х конфет и одна из 2-х:
2 2 3 3 2
Далее по 2 конфеты перекладывается из 1 и 5кучек во 2 и 4, при этом и 1 и 5 кучки становятся пустыми, т.е. на столе остается только 3 кучки:
4 3 5
Теперь по 4 конфеты перекладываются из 1 и 3 кучек во 2-ю и на столе остается две кучки, игра заканчивается с результатом 11 1
2. Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.
3. Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5
3 2 2 3 2 2 1
2 11 1
1 1 7
1 7
5 1 1 2 1 3 1 4 1 5 2
2 15 5