In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Biolodzy molekularni od dawna badają genomy (czyli sekwencje genów) różnych organizmów, usiłując na ich podstawie wysnuć wnioski dotyczące ewolucji gatunków, a także działania komórek i tkanek. Podczas tych badań m.in. porównują poszczególne geny pod względem budowy i funkcji i utożsamiają ze sobą geny bardzo podobne do siebie (tzw. geny homologiczne).
Ostatnio, badając wirusy atakujące bakterie (zwane bakteriofagami lub po prostu fagami), zaobserwowali bardzo intrygujące zjawisko. Jeśli mianowicie ustawić sekwencje genów niektórych fagów jedne pod drugimi i pokolorować homologiczne geny tą samą barwą, to uzyskuje się swoistą mozaikę:
Do opisu zjawiska, które odkryli, naukowcy wymyślili miarę, którą nazwali współczynnikiem mozaikowatości. Współczynnik ten można wyznaczyć dla danego faga tylko w zestawieniu z innymi fagami - jest nim wtedy łączna liczba punktów obliczona następująco. Za każde dwa geny z faga -tego oraz za każde dwa różne fagi , takie że:
W sytuacji przedstawionej na rysunku fag numer ma współczynnik mozaikowatości równy Jest tak, ponieważ gen niebieski ma gen homologiczny w fagu i nie ma genu homologicznego w fagu ; z kolei gen pomarańczowy ma gen homologiczny w fagu i nie ma genu homologicznego w fagu . Analogiczna sytuacja ma miejsce dla genów brązowego i pomarańczowego. Natomiast fag numer ma współczynnik mozaikowatości równy - dostaje punkty za pary genów: czerwony-niebieski, czerwony-brązowy, 2 razy żółty-niebieski i 2 razy żółty-brązowy.
Ręczne wyznaczanie współczynników nie jest proste, więc biolodzy postanowili poprosić Cię o napisanie programu, który policzy współczynniki mozaikowatości wszystkich podanych fagów.
Napisz program, który:
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę fagów, które należy rozważyć.
W -tym z następnych wierszy znajduje się opis sekwencji genów -tego faga. Każdy taki opis składa się z jednej liczby całkowitej () oznaczającej liczbę genów w sekwencji -tego faga, po której następuje liczb całkowitych () opisujących kolejne jego geny. Wszystkie te liczby są pooddzielane pojedynczymi odstępami.
Dwa geny uważamy za homologiczne wtedy i tylko wtedy, gdy w opisie na wejściu są im przypisane te same numery. Naukowcy dowiedli, że żadne dwa geny jednego faga nie mogą być homologiczne (W praktyce wystąpienie dwóch homologicznych genów u jednego faga jest mało prawdopodobne.), a zatem w opisie żadnego faga nie może się pojawić dwukrotnie ta sama liczba.
Wyjście powinno składać się z wierszy. W -tym z nich powinna znajdować się jedna liczba, równa współczynnikowi mozaikowatości -tego faga.
Dla danych wejściowych:
4 4 1 5 2 4 3 3 6 4 3 5 2 6 3 4 3 1
poprawną odpowiedzią jest:
6 3 2 1
Rysunek z treści zadania jest ilustracją dla testu przykładowego.
Autor zadania: Aleksander Mielczarek.