Lista de probleme 2

Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).

Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.

Definim două tipuri de operații:

• 1 x y – ce reprezintă faptul că x se împrietenește cu y.
• 2 p – Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.

Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j, cu proprietatea 1<j<i şi i%j=0. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.

Cătălin alege T greșeli G[1] G[2] … G[T] și dorește să știe, pentru fiecare G[i], numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.