Datortīkls

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

Doti N datori, kas savienoti tīklā: daži datoru pāri ir savā starpā savienoti ar vada palīdzību. Datori ir sanumurēti ar naturāliem skaitļiem pēc kārtas no 1 līdz N. Visi savienojumi ir divpusēji – ja dators A ir savienots ar datoru B, tad arī dators B ir savienots ar datoru A. Katri divi datori savā starpā ir savienoti ar ne vairāk kā viena vada palīdzību. No datora Ai ir iespējams nosūtīt ziņojumu uz datoru Aj, ja eksistē tāda datoru virkne a1,a2,...,ap, ka savā starpā ir savienoti datori Ai un a1, a1 un a2, ...., ap-1 un ap, ap un Aj.
Dažreiz datori mēdz sabojāties un tad caur tiem ziņojumus nosūtīt nav iespējams. Divi operatori, kas strādā pie datoriem K un M, vēlas uzzināt, cik droši ir sakari starp viņu datoriem. Lai to uzzinātu, viņi vēlas noskaidrot, kādam mazākajam datoru skaitam jāsabojājas, lai no datora K uz datoru M nebūtu iespējams nosūtīt ziņojumu. Uzskatām, ka datori K un M nevar sabojāties un ka šie datori nav tieši savienoti ar vada palīdzību. 

Piemēram, zīmējumā redzamajā datortīklā no datora 1 var nosūtīt ziņojumu uz datoru 4. Tomēr, ja sabojāsies gan dators 2, gan dators 3, tad vairs no datora 1 uz datoru 4 ziņojumu nosūtīt nevarēs. 

Ievaddati  
Ievaddatu faila pirmajā rindā dotas četru naturālu skaitļu N, C, K, M vērtības. N ir datoru skaits, C – savienojumu (vadu) skaits, bet К un М – datoru, pie kuriem strādā operatori, numuri. Starp katriem diviem blakus skaitļiem failā ir viens tukšumsimbols. Zināms, ka 2<=N<=50,  1<=K<=N,  1<=М<=N,  KM. 
Katrā no nākošajām С rindām dota informācija par vienu savienojumu: divi skaitļi, kas atdalīti ar tukšumsimbolu un kuru vērtības nepārsniedz N – datoru, kas savienoti ar vadu, numuri.
Atgādinām, ka visi savienojumi ir divpusēji un, ka K un M nav tieši savienoti ar vada palīdzību.

Izvaddati 
Pirmajā rindā jāizvada vesels skaitlis P – mazākais datoru skaits, kam jāsabojājas, lai no datora K uz datoru M nebūtu iespējams nosūtīt ziņojumu. Nākošajās P faila rindās jāizvada pa vienam skaitlim katrā – to datoru numuri, kuriem jāsabojājas, lai no datora K uz datoru M ziņojumu nevarētu nosūtīt. Datoru numurus drīkst izvadīt patvaļīgā secībā. Ja šos P datorus var izvēlēties dažādos veidos, jāizvada viens no tiem. 

Piemērs		NETWORK.IN 		NETWORK.OUT
4 4 1 4			2
1 3				3
2 1				2
4 3
2 4

Компьютерная сеть

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

Имеется N компьютеров, соединенных в сеть: некоторые пары компьютеров соединены между собой проводом. Компьютеры пронумерованы натуральными числами от 1 до N. Все соединения двусторонние - если компьютер А соединен с компьютером В, то и компьютер В соединен с компьютером А. Любые два компьютера соединены не более, чем одним проводом. Мы можем передать сообщение с компьютера Ai на компьютер Aj, если существует такая последовательность компьютеров a1,a2,...,ap, что компьютеры Ai и a1 соединены проводом, компьютеры a1 и a2 соединены проводом, ...., ap-1 и ap соединены проводом, ap и Aj соединены проводом.
 Время от времени некоторые компьютеры выходят из строя, и тогда через них сообщения не проходят. Два оператора, работающие за компьютерами К и М, хотят узнать, насколько надежна связь между ними. Для этого они хотят определить, какое наименьшее количество компьютеров должно выйти из строя, чтобы между компьютерами К и М нельзя было передать сообщение. Считаем, что компьютеры К и М никогда не выходят из строя, и что эти два компьютера не соединены между собой проводом.
Например, в сети, изображенной на рисунке, компьютер 1 может посылать сообщения на компьютер 4. Однако, если испортятся и копьютер 2 и компьютер 3, то тогда пересылать сообщения с компьютера 1 на компьютер 4 будет нельзя. 

Входные данные.  Первая строка содержит 4 натуральных числа N, C, K, M: N - количество компьютеров, C - количество соединений (проводов), К и М - номера компьютеров, за которыми работают операторы. Каждые два соседних числа разделены одним пробелом. 2<=N<=50,  1<=K<=N,  1<=М<=N,  KM. 
Каждая из следующих С строк содержит по два различных натуральных числа, не превосходящих N, - эти два компьютера соединены проводом.
Напомним, что все соединения двусторонние, что любые два компьютера соединены не более, чем одним проводом, и что компьютеры К и М не соединены проводом.

Выходные данные. В первой строке выходного файла должно стоять одно целое число Р - наименьшее количество компьютеров, которые должны выйти из строя, чтобы между компьютерами К и М нельзя было передать сообщение. Во следующих Р строках должны идти номера компьютеров, которые должны выйти из строя, чтобы прервать сообщение между К и М. Номера компьютеров можно выводить в произвольном порядке. Если эти Р компьютеров можно выбрать несколькими способами, то достаточно привести любой один из них.

Пример		NETWORK.IN 		NETWORK.OUT
4 4 1 4			2
1 3				3
2 1				2
4 3
2 4

Palindroms

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

Dota ciparu virkne. Par operāciju sauksim darbību, kad divi blakus esoši cipari tiek nodzēsti un to vietā tiek ierakstīta šo ciparu summas pēdējais cipars. Tā, piemēram, no virknes 234567 izdarot vienu operāciju var iegūt virkni 23967 (4 un 5 vietā ierakstīts 9), virkni 23453 (6 un 7 vietā ierakstīts 3), kā arī vairākas citas virknes.  
Virkni sauc par palindromu, ja tā lasāma vienādi gan no kreisās puses uz labo, gan no labās puses uz kreiso. Piemēram, virknes 0123210 un 25733752 ir palindromi, bet 123210 nav palindroms. Palindromi ir arī visas viencipara virknes.
Uzrakstiet programmu, kas nosaka kādu garāko palindromu iespējams iegūt no dotās ciparu virknes ar operāciju palīdzību un izvada šī palindroma garumu!

Ievaddati
	Vienīgajā ievaddatu faila rindā dota ciparu virkne, kas sastāv no ne vairāk kā 3000 cipariem. Virkne var saturēt tikai ciparus no 0 līdz 9.

Izvaddati
	Izvaddatu faila vienīgajā rindā jāizvada naturāls skaitlis - garākā palindroma, kuru iespējams iegūt no dotās ciparu virknes ar operāciju palīdzību, garums. 
 
Piemērs		PALINUM.IN		PALINUM.OUT 
23456789			5

Piezīme: palindromu garumā 5 iespējams iegūt sekojoši: pasvītroti katrā operācijā aizvietotie cipari:  23456789   2345659  275659  95659

Палиндром

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

Имеется строка цифр. Одна операция состоит в том, что любые две соседние цифры мы стираем и заменяем их на одну цифру - последнюю цифру суммы двух стертых цифр. Например, из строки 234567 можно одной операцией получить, например, строку 23967 (стерев цифры 4 и 5), строку 23453 (стерев цифры 6 и 7) и другие строки.  
Строка называется палиндромом, если она читается одинаково справа налево и слева направо. Например, строки 0123210 и 25733752 являются палиндромами, а строка 123210 палиндромом не является. Также палиндромами являются все односимвольные строки.
Требуется определить наибольшую возможную длину палиндрома, который можно получить из заданной строки с помощью описанных операций.

Входные данные. 
	В единственной строке входного файла содержится строка, содержащая не более 3000 цифр. Никаких других символов, кроме цифр от 0 до 9, строка не содержит.

Выходные данные.  
	В единственной строке выходного файла должно содержаться одно число - максимальная возможная длина палиндрома, который можно получить из исходной строки с помощью вышеописанных операций.
 
Пример		PALINUM.IN		PALINUM.OUT 
23456789			5
Примечание: палиндром длины 5 можно получить следующим образом (подчеркнуты зачеркиваемые цифры):  
23456789   2345659  275659  95659

Vārdi

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

Vārds ir latīņu alfabēta mazo burtu virkne. Par vārda v1 papildināšanu ar vārdu v2 sauc vārda v2 pierakstīšanu vārda v1 galā. Piemēram, vārdu “abra” papildinot ar vārdu “kadabra”, iegūst vārdu “abrakadabra”. 
Ir doti divi vārdi V1 un V2 un vārdnīca, kurā ir N vārdi. Par operāciju sauksim V1 vai V2 papildināšanu ar kādu vārdu no vārdnīcas. Vienu un to pašu vārdnīcas vārdu operācijās drīkst izmantot vairākkārt.
Uzrakstiet programmu, kas nosaka, vai ar operāciju palīdzību no abiem dotajiem vārdiem var iegūt vienu un to pašu vārdu un, ja var, kāds ir mazākais nepieciešamais operāciju skaits!

Ievaddati
Ievaddatu faila pirmajā rindā dots vārds V1, bet otrajā vārds V2. Faila trešajā rindā dota naturāla skaitļa N (0 < N <= 100) vērtība – vārdnīcas vārdu skaits. Katrā no nākošajām N faila rindām dots viens vārdnīcas vārds. Neviena vārda garums nepārsniedz 100 burtus.

Izvaddati
Izvaddatu faila vienīgajā rindā jāizvada viens vesels skaitlis – mazākais nepieciešamais operāciju skaits, lai no V1 un V2 iegūtu vienādus vārdus. Ja vienādus vārdus izveidot nav iespējams, failā izvadiet skaitli ‘–1’.

Piemēri 

WORDS.IN 		WORDS.OUT		Piezīme
g			5			Iegūtais vārds ir “gadadiena”
ga
4
ad
dadie
na
iena

WORDS.IN 		WORDS.OUT
ga			-1
g
2
ab
ga

Слова

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

Слово - это последовательность маленьких букв латинского алфавита. Дополнением слова v1 словом v2 называется слово, получаемое при дописывании слова v2 к концу слова v1. Например, слово “abra” при дополнении словом “kadabra”, переходит в “abrakadabra”. 
Даны два слова: V1 и V2, и словарь, состоящий из N слов. Операцией назовем дополнение слова V1 или V2 каким-либо словом из словаря. Одно и то же слово из словаря можно использовать неоднократно.
Напишите программу, которая определяет, можно ли с помощью описанной операции получить из обоих данных слов одно и то же слово, и, если да, то каково наименьшее необходимое для этого количество операций.

Входные данные
В первой строке входного файла дано слово V1, во второй строке - слово V2. В третьей строке файла находится натуральное число N               (0 < N <= 100) – количество слов в словаре. Каждая из следующих N строк файла содержит одно слово словаря. Длина каждого слова не превосходит 100 букв.

Выходные данные
В единственной строке выходного файла должно находится одно целое число - наименьшее количество операций, необходимое для того, чтобы получить из слов V1 и V2 одинаковые слова. Если одинаковые слова получить невозможно, то следует выводить число ‘–1’.

Примеры 

WORDS.IN 		WORDS.OUT		Примечание
g			5				Получается слово “gadadiena”
ga
4
ad
dadie
na
iena

WORDS.IN 		WORDS.OUT
ga			-1
g
2
ab
ga