Задача C1. Хипервръзка

Чухте ли за новия browser? Pencho Browser е най-новото творение на Пенчо, с което той много се гордее. Той притежава всички качества, за да се превърне в абсолютен хит и, освен това, вече е почти време да се издаде първата му официална стабилна версия. Ръководството на проекта е далo срок до следващата седмица да има готова работеща версия, но за съжаление има още много бъгове за поправяне!
Вече почти няма време, а намирането на бъга, който изяжда хипервръзките в html документите, все още не е локализирано (това е едно от най-лошите наследства на бившия разработчик на проекта Унуфри). Тази част от кода е доста объркана и на всичкото отгоре е написана на асемблер и намирането на причината за това бъгче доста се усложнява. Поради тази причина, екипът на проекта реши да поправи сбърканите документи, като сложи отново хипервръзките в тях. Тъй като в момента всички от екипа са заети с това да усъвършенстват уменията си по Quake, вие сте тези, който трябва да се заемете с тази така важна задача.
Трябва да напишете програма HLINKS, която чете текст от стандартния вход (текстът може да е на няколко реда) и отпечатва този текст на стандартния изход, като търси всички хипервръзки в текста и за всяка намерена връзка LINK, замества LINK с (всичко се изписва с малки букви):

<a href="LINK">LINK</a>  

Дефиницията на хипервръзка в тази първа версия на browser-а е доста проста. Тя отговаря на следните условия:
1.	Съдържа само латински букви, цифри, точки (.) и наклонени черти (/);
2.	Ако пред връзката има залепен (без никакви разделящи интервали или знаци) http://, този низ трябва да се прибави към тази връзка;
3.	Във връзката трябва да има поне една точка;
4.	Ако след най-дясната точка няма наклонени черти, буквите след тази точка трябва да са повече от 1 и по-малко от 5;
5.	Преди и след всяка връзка, или няма нищо, или има знак различен от буква, цифра, точка и наклонена черта;
6.	Никога връзка не може да започва с наклонена черта или точка;
7.	Връзката не може да има 2 или повече последователни точки.

Знае се, че текстът не е по-дълъг 10000 знака и тези знаци са взети измежду знаците на ASCII таблицата. Текстът във входа завършва с края на файла.

Примерен вход:

Tova e link kym nai-noviq Pencho Browser:
http://www.pencho.browser.com, a
tova ne e: http://document.com/pencho.comma
I malko reklama - infoman.musala.com

Примерен изход:

Tova e link kym nai-noviq Pencho Browser:
<a href="http://www.pencho.browser.com">http://www.pencho.browser.com</a>, a
tova ne e: http://document.com/pencho.comma
I malko reklama - <a href="infoman.musala.com">infoman.musala.com</a>

Задача C2. Школа

Започна новата учебна година и в Школата по информатика в град Ш. отново се събраха много нови състезатели. За да подсигури редовното уведомяване на учениците за сбирките на групата, ръководителката на Школата направила малко проучване и установила, че новите ученици са N (5  N  500), номерирани с числата от 1 до N, по реда, в който са записани в дневника на Школата. M двойки от тях се познават и когато единият от двойката научи за поредната сбирка, може да уведоми другия за сбирката. За да си улесни работата, ръководителката би искала да избере колкото може по-малко ученици, които да уведоми лично, а те от своя страна да разпространят информацията до всички, като използват познанствата помежду си. Разбира се, че всеки уведомен за сбирката може да се свърже с всички свои познати и да ги уведоми, ако някой друг не го е направил до момента.
Напишете програма SCHOOL, която по зададени познанствата на учениците намира и извежда на стандартния изход минималния брой ученици, които трябва да бъдат уведомени от ръководителката така, че информацията да може да стигне до всички останали. 
На първия ред на стандартния вход ще бъдат зададени числата N и M, разделени с един интервал. На всеки един от следващите M  редa, разделени с интервал, са зададени два номера на ученици, които се познават.

Пример. 
Вход:
6 4
1 3 
1 4 
2 5
4 6

Изход:
2

Решение:

За решението на тази задача ще използваме техника от теорията на графите. Неориентираният граф G(V,E) е съставен от множество от върхове V={1,2,…,N} и множество от ребра Е такова, че всяко ребро от E свързва два върха u и w от E – означаваме го с (u,w). Редицата от върхове u1,u2,…,uk  наричеме път от върха u1 до върха uk, ако всеки два съседни в редицата върха ui и ui+1 са свързани с ребро. Когато u1= uk тогава пътя наричаме цикъл. Графът е свързан, ако в него има път от всеки връх до всички останали. Графът е дърво, ако е свързан и няма цикли. Дървото D(V,E’) такова, че E’  E наричаме покриващо дърво на G. В сила е следното важно свойство: графът G е свързан тогава и само тогава, когато има покриващо дърво. 
Ако графът не е свързан, тогава той се разпада на отделни свързани подграфи, всеки от които наричаме  свързана компонента. На Фиг. 1 е показан граф с 6 върха и 4 ребра, който не е свързан и има 2 свързани компоненти (върховете 1, 3, 4 е 6 са в едната, а върховете 2 и 5 в другата). 

		0	1	2	3	…			
	1	2	3	4					
	2	1	5						
	3	1	1						
	4	2	1	6					
	5	1	2						
	6	1	4						

	                           Фиг 1.						Фиг. 2.           

Да представим даденото в задачата като неориентиран граф. На всеки от учениците да съпоставим връх на графа и да свържем с ребро два върха, ако съответните им ученици се познават и, ако единият от тях бъде уведомен за сбирка на Школата, може да уведоми другия. Нека ученикът, съответен на върха с номер 1 е уведомен за сбирката, той може да уведоми всички ученици с които се познава. Всеки от тях може да уведоми всеки от познатите си, които още не са уведомени. В резултат ще бъдат уведомени всички ученици, за върховете на които в графа има път до (от) върха с номер 1, т.е. тези които са в една и съща свързана компонента на графа. Очевидно, за всяка свързана компонента ще е необходимо и достатъчно да бъде уведомен точно един от учениците, т.е търсеният в задача минимален брой ученици, които трябва да бъдат уведомени е равен на броя на свързаните компоненти на графа. 
За намиране на броя на свързаните компоненти ще приложим сравнително универсалната техника “обхождане в ширина”. С малка модификация, обаче, алгоритъмът може да се приложи и за решаване на задачата за определяне на самите компоненти (опитайте се да го направите сами). 
Много важно за успешната реализация е начинът по който ще представим графа. Ще използваме представяне, което наричаме “списъци на съседите”. Нека g е двумерен масив с толкова реда, колкото са върховете на графа и стълбове с 1 повече от върховете на графа (в реализацията използваме редовете с номера 1,2,..., N и стълбовете с номера 0,1,2,..., N). Списъкът на съседите на върха u съхраняваме в реда с номер u. Първият, вторият и т.н до k-тия съсед на u записваме в първия, втория и т.н. до k-тия елемент на реда, а в нулевия елемент поставяме броя k на съседите на u. На Фиг.2 е показано представянето на графа от Фиг.1 със списъци на съседите. 
При “обхождане в ширина” използваме опашка q, като в променливите qs и qe се намират началото и краят на опашката. Започваме с произволен начален връх (например 1). Поставяме го в опашката, обявяваме го за обходен (като поставим 1 в съответния елемент на масива used), преброявяме първата свързана компонента (променливата cnt) и обхождаме тази компонента в ширина. За целта, докато в опашката има елементи, изваждаме елемент от началото на опашката и добавяме в края на опашката всички негови необходени съседи, обявявайки всеки един такъв съсед за обходен. Ако в края на тази стъпка няма необходени върхове – алгоритъмът завършва. Ако имаме необходен върх – избираме този връх за начален, преброяваме още една компонента и повтаряме описаните вече стъпки. На Фиг. 3 е показан програмен фрагмент с основните стъпки на алгоритъма.

cnt=0;
for(i=1;i<=N;i++)  {used[i]=0;g[i][0]=0;}
for(k=1;k<=N;k++) 
{
   if(used[k]==1) continue;
   qs=qe=0;q[qs]=k;used[k]=1;cnt++;
   while(qs<=qe) 
   {
      x=q[qs++];
      for(i=1;i<=g[x][0];i++) 
      {
         y=g[x][i];
	    if(used[y]==0)
	    {used[y]=1;q[++qe]=y;}
	 }
   }
 }
                       cout<<cnt<<endl;

Фиг. 3

Задача C3. Числа
Дадени са 3 двуцифрени числа d1, d2,  d3.   
Напишете програма NUMBER, която намира броя M на n-цифрените числа a1 a2…an, за които всеки две съседни цифри ai ai+1 образуват двуцифрено число (без водеща нула), което се дели на някое от числата d1, d2, d3. 
Данните се въвеждат от стандартния вход, където на един ред са записани последователно числата n, d1, d2, d3, разделени с по един интервал.
Търсеният брой M  да се изведе на стандартния изход.
Ограничения: 
а) 1 < n  < 20 (за 50% от тестовите примери: 1 < n < 10) 
б) за всички тестови примери  M < 10000.
Пример
Вход					
3 13 28 34	
Изход		
15			
Обяснение на примера:
134, 139, 265, 268, 284, 391, 526, 528, 565, 568, 652, 656, 684, 784, 913

Решение:
Следва пълният текст на програма, която решава задачата:
// Идея: Рекурсивно генериране на всички числа
#include <iostream>
using namespace std;
int n, d1, d2, d3;
int a[22];
int M=0;
bool OK(int a, int b)    
// проверява дали две цифри a и b могат  
// да бъдат една след друга в числото
// без водеща нула
{ if(a==0) return false; 
  int x = 10*a + b;
  if(x%d1==0) return true;
  if(x%d2==0) return true;
  if(x%d3==0) return true;
  return false;
}
void Gen(int k) // избира k-тата цифра
{ for(int i=0; i<10; i++) 
    if(OK(a[k-1],i))
    { a[k]=i;
      if(k<n) Gen(k+1); // рекурсивно търси (k+1)-вата цифра 
      else M++;         // намерено е още едно от търсените числа
    }
}
int main()
{ cin >> n >> d1 >> d2 >> d3;
  for(int i=1; i<10; i++)
  { a[1]=i;  // първа цифра: 1,2,...,9
    Gen(2);  // генерира останалите цифри
  }
  cout << M << endl;
  return 0;
}