Runda 10 - Anagramy

07.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

 

 

Zawody stałe, runda 10.

Limit czasowy: 2s; Limit pamięciowy: 32MB

 


Anagramy

 

Pan Władek uwielbia spędzać swój czas w Bibliotece. Jego ulubionym zajęciem ostatnio jest wyszukiwanie w książkach par anagramów. Dwa słowa są anagramami jeśli jedno słowo można utworzyć z drugiego poprzez zmianę kolejności liter. I tak na przykład słowo rekwizyt jest anagramem do wietrzyk, latryna do ratalny, algorytm do logarytm a sufiks do fiskus. Pan Władek ostatnio zajął się szukaniem największego zbioru anagramów. Do tej pory udało mu się znaleźć zbiór 5-elementowy złożony ze słów:
- korab
- robak
- barok
- korba
- kobra
Pan Władek na pewno będzie Ci dozgonnie wdzięczny jeśli pomożesz mu w znalezieniu jeszcze większego zbioru anagramów.

Wejście

Na standardowym wejściu znajdują się zbiór słów, po jednym słowie w linijce. Słowo składa się z małych, angielskich liter alfabetu. Słowa nie będą dłuższe niż 30 znakowe. Możesz założyć, że na wejściu nie znajdą się dwa takie same słowa. Słów na wejściu będzie będzie przynajmniej jedno i będzie ich mniej niż 100 tysięcy. Wejście kończyć się będzie linią ze znakiem '0'.

Wyjście

W pierwszej linijce należy wypisać liczbę zbiorów anagramów, które zawierają co najmniej dwa różne słowa. W następnej linii wypisz ilość elementów największego zbioru. Wypisz zero jeśli nie ma zbiorów większych niż jednoelementowe. W kolejnych wierszach wypisz zbiory najliczniejszych anagramów. Jeden zbiór w każdej linijce. Elementy oddziel pojedynczą spacją. Elementy zbioru powinny być posortowane tak jak w słowniku (w sposób leksykograficzny). Zbiory w kolejnych wierszach powinny być posortowane po pierwszym elemencie zbioru. Nie wypisuj tych zbiorów jeśli nie ma zbioru większego niż jednoelementowy.

Przykład

Dla danych wejściowych:

atol
lato
rata
rola
tara
tola
0


Poprawną odpowiedzią jest:

2
3
atol lato tola

Dla danych wejściowych:

faul
sofa
rufa
forsa
lufa
fosa
fart
traf
sfora
fura
0


Poprawną odpowiedzią jest:

5
2
fart traf
faul lufa
forsa sfora
fosa sofa
fura rufa

Wytłumaczenie

W pierwszym teście mamy następujące zbiory anagramów {atol, lato, tola}, {tara, rata}, {rola}. Zatem mamy dwa zbiory, które mają co najmniej dwa elementy. Największy z tych zbiorów ma 3 elementy. Wypisujemy go w kolejności rosnącej (takiej jak w słowniku).

W drugim teście mamy zbiory: {fart, traf}, {faul, lufa}, {forsa, sfora}, {fosa, sofa} oraz {fura, rufa}. Zatem mamy 5 zbiorów które mają co najmniej dwa elementy. Największy z tych zbiorów ma 2 elementy. Wypisujemy je w ten sposób, że każdy zbiór sortujemy rosnąco, a następnie rosnąco sortujemy po najmniejszym elemencie każdego zbioru.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska1010:45:28
2Maciej Szeptuch1061:35:33
3Bartek Dudek10132:05:34
4Michal Zgliczynski101039:45:51
5Michał Karpiński107013:21:27
6Łukasz Hanuszczak109197:12:03
7Kuba Skudlarski9152:06:27
8Marek Rusinowski94452:26:21
9Mateusz Wasilewski82239:08:56
10Jakub Stanecki86874:08:19
11Janusz Wróbel711:46:44
12Darek Bukowski7154:51:57
13Łukasz Hryniuk55438:14:14
14Mateusz Piecuch3133:24:02
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com