Neuzbrūkošie zirgi

Ievaddatu fails: KNIGHTS.IN    exe-fails: KNIGHTS.EXE
Izvaddatu fails: KNIGHTS.OUT   Laika limits: 1 sek.

Šaha zirgs apdraud lauciņus uz šaha galdiņa saskaņā ar zīmējumu:

	X		X		
X				X	
		K			
X				X	
	X		X		
Zirgs atrodas rūtiņā, kas apzīmēta ar К un apdraud lauciņus, kas apzīmēti ar X. 
Citus lauciņus zirgs neapdraud.

Dots rūtiņu laukums, kura izmēri ir Nx3 (N rindas, 3 kolonas). Dažas laukuma rūtiņas jau ir aizņemtas – tajās atrodas citas figūras. Baltos zirgus atļauts novietot laukuma brīvajās rūtiņās (ne vairāk kā vienu zirgu katrā rūtiņā) tā, lai nekādi divi baltie zirgi neapdraudētu viens otru.
Uzrakstiet programmu, kas noskaidro:
-	kādu lielāko balto zirgu skaitu iespējams novietot uz laukuma?
-	cik dažādos veidos to iespējams izdarīt?

 Ievaddati
Ievaddatu faila pirmajā rindā dots naturāls skaitlis N(1<=N<=100). Nākošajās N faila rindās katrā ir trīs simboli. Katrs no simboliem var būt “+” vai “-“. Ja faila i+1-ās rindas j-tais simbols ir “+”, tad tas nozīmē, ka laukuma i-tās rindas j-tās kolonas rūtiņa ir aizņemta. Ja faila i+1-ās rindas j-tais simbols ir “-”, tad tas nozīmē, ka laukuma i-tās rindas j-tās kolonas rūtiņa ir tukša.

Izvaddati 
Izvaddatu failam jāsatur divas rindas. Faila pirmajā rindā jāizvada lielākais iespējamais balto zirgu skaits, kādu iespējams izvietot uz laukuma. Faila otrajā rindā jāizvada dažādo variantu skaits, kādā šo zirgu skaitu var izvietot laukumā. 
Testi ir izvēlēti tā, ka abu šo skaitļu vērtības ir mazākas par 231. Daļējs punktu skaits tiks piešķirts arī par atbildi, kurā pareizi būs norādīts tikai maksimālais balto zirgu skaits. 

Piemērs
KNIGHTS.IN 		KNIGHTS.OUT
2			4
+--			2
---

Неатакующие кони

Input file:  KNIGHTS.IN     exe-file: KNIGHTS.EXE
Output file: KNIGHTS.OUT    Time limit: 1 sec.

Шахматный конь атакует поля на шахматной доске в соответствии с рисунком:

	X		X		
X				X	
		K			
X				X	
	X		X		
Конь стоит в клетке, обозначенной К, и атакует все поля, обозначенные X (и только эти поля).

Имеется шахматная доска размером Nx3 (N рядов, 3 столбца), 1<=N<=100. Некоторые клетки доски заняты - в них стоят другие фигуры. Мы можем ставить белых коней в свободные клетки (не более одного коня в клетку) так, чтобы никакие два белых коня не били друг друга.
Нипишите программу, которая определяет:
-	какое наибольшее количество белых коней мы можем поставить на доску?
-	сколько существует различных способов это сделать?

Входные данные.  
В первой строке входного файла содержится натуральное число N (1<=N<=100). Следом за ней идут N строк, каждая из которых содержит 3 символа; каждый их этих символов является плюсом или минусом. Если в (I+1)-й строке входного файла J-й символ "+", то это означает, что клетка в J-й колонке I-й строки занята. Если же в (I+1)-й строке входного файла J-й символ "-", то это означает, что клетка в J-й колонке I-й строки пуста. 

Выходные данные. 
Выходной файл должен состоять из двух строк: в первой строке должно стоять максимальное количество белых коней, которых мы можем поставить на доску; во второй - количество способов расставить такое количество белых коней на доске.
Тесты построены так, что обе выводимых величины не превосходят наибольшего целого 32-битового числа со знаком (231-1). 
Часть очков получит и такая программа, которая правильно найдет только наибольшее количество белых коней.

Пример	        KNIGHTS.IN 	     KNIGHTS.OUT
		2             4          
		+--           2         
		---

Kartiņas

Ievaddatu fails: CARDS.IN    exe-fails: CARDS.EXE
Izvaddatu fails: CARDS.OUT   Laika limits: 1 sek.

Dots kvadrātveida rūtiņu laukums, kuram ir n rindas un m kolonas. Katrā rūtiņā atrodas kartiņa, kuras viena puse ir melna, bet otra puse – balta. Tieši k (k>0) kartiņas ir ar melno pusi uz augšu. Ar vienu gājienu var apgriezt divās blakus rūtiņās (rūtiņās ar kopīgu malu) novietotās kartiņas otrādi (ja kartiņa bija vērsta ar melno pusi uz augšu, tad tagad tā ir vērsta ar balto pusi uz augšu, bet, ja bija ar balto pusi uz augšu, tad tagad ir vērsta ar melno pusi uz augšu).
Uzrakstiet programmu, kas dotam sākotnējo k ar melno pusi uz augšu novietoto kartiņu izvietojumam nosaka, ar kādu mazāko gājienu skaitu iespējams panākt, ka visas laukumā novietotās kartiņas ir ar balto pusi uz augšu!

Ievaddati
Ievaddatu faila pirmajā rindā dotas divas naturālu skaitļu n(n<10000) un m(m<10000) vērtības, kas atdalītas ar tukšumsimbolu. Nākošajā faila rindā dota naturāla skaitļa k (k<=100) vērtība. Katrā no nākošajām k faila rindām doti divi naturāli skaitļi, kas apzīmē attiecīgās, ar melno pusi uz augšu esošās, kartiņas rindas un kolonas numuru. Šie skaitļi ir atdalīti ar tukšumsimbolu. Informācija par katru, ar melno pusi uz augšu vērsto, kartiņu failā dota tieši vienreiz.

Izvaddati
Izvaddatu faila vienīgajā rindā jāizvada vesels skaitlis – mazākais gājienu skaits, kāds nepieciešams, lai visas kartiņas būtu pavērstas ar balto pusi uz augšu. Ja šādu situāciju dotajam kartiņu izvietojumam panākt nav iespējams, failā jāizvada skaitlis 0.

Piemērs
CARDS.IN		CARDS.OUT
3 4			4
4
1 1
1 4
3 4
1 3

Карточки

Input file: CARDS.IN      exe-file: CARDS.EXE
Output file: CARDS.OUT    Time limit: 1 sec.

Имеется прямоугольное поле, состоящее из квадратных клеток. Размеры поля - n строк, m столбцов. В каждой клетке находится карточка, у которой одна сторона черная, а другая - белая. Ровно k (k>0) карточек лежат черной стороной вверх, остальные - белой стороной вверх. Одним ходом можно перевернуть любые две рядом лежащие карточки (лежащие в клетках, имеющих общую сторону). Если карточка лежала черной стороной вверх, то после переворачивания она будет лежать белой стороной вверх, и наоборот. 
Напишите программу, которая по заданному расположению карточек, лежащих черной стороной вверх, определяет, какое наименьшее количество ходов надо сделать, чтобы все карточки на поле лежали белой стороной вверх.

Входные данные. 
	В первой строке входного файла содержатся два натуральных числа, разделенные пробелом - значения n (n<10000) и m (m<10000). В следующей строке содержится одно натуральное число - значение k (k<=100). Каждая из следующих k строк содержит два натуральных числа, разделенных пробелом, - соответственно, номер строки и номер столбца клетки, в которой лежит карточка черной стороной вверх. Клетки в этом списке не повторяются. 

Выходные данные.  
	В единственной строке выходного файла должно содержаться одно целое число - наименьшее количество ходов, которые надо сделать, чтобы все карточки были повернуты белой стороной вверх. Если этого при данной начальной конфигурации сделать нельзя, то следует выводить число 0.
 
Пример		CARDS.IN		CARDS.OUT 
3 4			4
4
1 1
1 4
3 4
1 3

Tālās permutācijas

Ievaddatu fails: FAR.IN    exe-fails: FAR.EXE
Izvaddatu fails: FAR.OUT   Laika limits: 1 sek.

Par permutāciju garumā N sauc sakārtotu naturālu skaitļu masīvu, kurā katrs no skaitļiem no 1 līdz N ir sastopams tieši vienreiz. Piemēram, masīvs (2, 5, 3, 1, 4) ir permutācija garumā 5, bet masīvi (1, 3, 5, 4), (3, 1, 2, 6, 4) un (2, 3, 5, 1, 2, 4) – nav.
Sauksim permutāciju par tālu, ja neviens skaitlis K(1<=K<=N) tajā neatrodas K-tajā vietā.
Sakārtosim visas dotā garuma N tālās permutācijas leksikogrāfiskā (vārdnīcas) kārtībā. Piemēram, ja N ir 4, iegūsim deviņas tālās permutācijas šādā secībā: 
(2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1).

Uzrakstiet programmu, kas dotam N nosaka, kāda permutācija atrodas tālo permutāciju virknes P-tajā vietā! 

Ievaddati 
Ievaddatu faila pirmajā rindā dots naturāls skaitlis N (1<=N<=20) – permutācijas garums. Faila otrajā rindā dots naturāls skaitlis P (1<=P<=2000000000). Zināms, ka P vērtība nepārsniedz tālo permutāciju garumā N skaitu.

Izvaddati  
Izvaddatu faila vienīgajā rindā jāizvada meklētā permutācija – N skaitļi (robežās no 1 līdz N, katrs vienreiz), kas atdalīti ar tukšumsimboliem.
 
Piemērs		
FAR.IN 			FAR.OUT
4				3 4 1 2
5

Далекие перестановки

Input file:  FAR.IN     exe-file: FAR.EXE
Output file: FAR.OUT    Time limit: 1 sec.

Перестановкой длины N называется упорядоченный массив чисел от 1 до N, в котором каждое число встречается ровно один раз. Например, массив (2, 5, 3, 1, 4) является перестановкой длины 5, а массивы (1, 3, 5, 4),  (3, 1, 2, 6, 4) и (2, 3, 5, 1, 2, 4) перестановками не являются.
Назовем перестановку далекой, если каждое число K (1<=K<=N) в ней стоит не на K-ом месте.
Расставим все далекие перестановки заданной длины N  в лексикографическом (словарном) порядке. Например, для N=4 получим 9 далеких перестановок, расположенных в следующем порядке: 
(2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3),  (4,3,1,2),  (4,3,2,1).

Напишите программу, которая определяет, какая перестановка стоит на P-ом месте в ряду далеких перестановок длины N.

Входные данные. Первая строка входного файла содержит натуральное число N (1<=N<=20); вторая строка входного файла содержит натуральное число P (1<=P<=2000000000). Гарантируется, что величина P не превосходит количества далеких перестановок длины N. 

Выходные данные.  Выходной файл должен содержать в своей единственной строке искомую перестановку - N чисел от 1 до N, каждое ровно один раз. Каждые два соседних числа в этой строке должны быть разделены одним пробелом.
 
Пример		FAR.IN 			FAR.OUT
4				3 4 1 2
5