ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2010 > задача:


F. Liars and Knights

Задачи сборника

• A. Providers
• B. Primes
• C. Bishops
• D. Unusual Lottery
• E. Polygons
• F. Liars and Knights
• G. Sequence
• H. Coins
• I. Galls village
• J. String manipulations

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/4000/4000/4000 мс. Лимит памяти 65000/80000/80000/80000 Кб.
Автор: Павел Кузнецов, ПГУ.

NxM people have arrived to the congress of the largest party in Byteland, and they were all seated in N rows, M people in one row. The party consists of two fractions - liars and knights. The representatives of the fraction of knights always speak the truth, and the liars always lie. After the congress, each of the participants said that he had been sitting with the representatives of both fractions at his sides. Two participants are considered to be neighbors, if they are sitting next to each other in one row, or if they occupy the same places in two adjacent rows. The chairman of the party does not know how many there were liars and knights. So he wants to understand with what minimal number of liars such a situation could take place. Your task is to write a program, that will find out the minimal number of liars and the corresponding plan of seating the congress participants.

Input
The first line of the input gives two integers N and M - the number of rows and seats in each row, correspondingly (1 ≤ N ≤ 7, 1 ≤ M ≤ 100).

Output
Write in the first line of the output one number - the minimal quantity of liars in the required seating. The following N lines should show the seating itself, one row in each line. A knight must be shown by the symbol "." (point), and a liar by "x" (small Latin letter x). There should be no other symbols in the lines, not even the spaces. In case you find several ways of seating, show one of them.

Input 1 Output 1
2 3
2
..x
x..
Input 2 Output 2
6 6
10
x...x.
..x...
x....x
...x..
.x...x
x..x..

Для отправки решений необходимо выполнить вход.

www.contester.ru