| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_05_04 - Palindrom wielokrotny |
Powszechnie wiadomo, że wyraz jest palindromem, jeżeli czytany wspak brzmi tak samo jak czytany normalnie. Można też powiedzieć, że taki wyraz składa się z dwóch części składowych (lewej i prawej), które są względem siebie "symetryczne". W przypadku, gdy wyraz ma parzystą liczbę znaków, te dwie składowe to po prostu lewa i prawa połowa wyrazu, np. abba=ab+ba. Jeżeli palindrom ma nieparzystą liczbę liter, to przyjmijmy, że te "symetryczne" części uzyskamy usuwając środkową literę. Np. w wyrazie kajak, lewa składowa to ka, a prawa to ak. Oczywiście jest też możliwe, że składowe palindromu, również są palindromami. Np. w wyrazie oko, obie części to jednoliterowy wyraz o, który przecież sam jest też palindromem.
Zdefiniujmy więc teraz palindrom wielokrotny.
- Każdy jednoliterowy wyraz jest palindromem jednokrotnym.
- Jeżeli wyraz W jest palindromem n-krotnym, to wyraz P=W+W (tu + oznacza oczywiście konkatenację) oraz wyraz Q=W+c+W (gdzie c to dowolny pojedynczy znak) są palindromami (n+1)-krotnymi.
- Każdy wyraz, którego normalnie nie nazwalibyśmy palindromem, będzie teraz palindromem 0-krotnym.
Kilka przykładów palindromów i ich krotności:
abc 0
kajak 1
oko 2
oooo 3
aabaacaabaa 4
Napisz program, który wyznaczy krotność każdego z danych n palindromów, a następnie wśród otrzymanych wyników (oznaczmy je ki, dla i=1..n) znajdzie pewną charakterystyczną wartość x, spełniającą jednocześnie dwa warunki:
1. Co najmniej połowa liczb ki jest większa lub równa x.
2. Co najmniej połowa liczb ki jest mniejsza lub równa x.
Jeśli jest wiele liczb spełniających te warunki, należy wybrać najmniejszą.
Wejście
W pierwszej linii liczba n (0 < n ≤ 500000) oznaczająca liczbę palindromów.
W każdej z kolejnych n linii jeden palindrom (ciąg małych liter angielskiego alfabetu) o długości d (0 < d ≤ 5000000).
Suma długości wszystkich palindromów nie przekracza 5000000.
Wyjście
Jedna liczba całkowita będąca szukaną wartością x.
Przykład
Wejście: 6
kajak
bbcbbabbcbb
oko
otomoto
abaoboubuaba
zzzz
Wyjście: 2
| Dodane przez: | Witold Długosz |
| Data dodania: | 2013-04-02 |
| Limit czasu wykonania programu: | 0.100s-2s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
2013-04-07 12:44:52 narbej
Podpowiedź => forum - FAQ Ostatnio edytowany: 2013-04-07 16:15:07 |
|
|
2013-04-06 18:56:26 narbej
UWAGA! UWAGA! Proszę ;-) Nie róbcie edycji swoich wcześniejszych wiadomości - mogę ich nie zauważyć. Zawsze, jeżeli chcecie żebym je łatwiej zauważył, piszcie nowe. Ostatnio edytowany: 2013-04-06 19:24:25 |
|
|
2013-04-06 18:52:56 narbej
UWAGA Nie róbcie edycji swoich wiadomości - mogę ich nie zauważyć. Zawsze, jeżeli chcecie żebym ewentualnie je zauważył, piszcie nowe. |
|
|
2013-04-06 18:42:59 narbej
Masz, źle policzone palindromy. Ostatnio edytowany: 2013-04-06 18:46:21 |
|
|
2013-04-06 17:53:54 narbej
Zgodnie z treścią zadania: Jeśli jest wiele liczb spełniających te warunki, należy wybrać najmniejszą. Chyba, że pytasz czy dobrze policzyłaś palindromy? Jeżeli tak, to musiałbym je policzyć. Czy ta odpowiedź cię zadawala? Ostatnio edytowany: 2013-04-06 18:08:46 |
|
|
2013-04-06 17:46:22 Julia Ostrowska
Czy dobrze policzyłam że w przykładzie mamy liczby : 1 4 2 4 0 3 i mamy do wyboru 2 lub 3 i wybieramy 2 jako mniejsza? Poprawka, pytam czy dobrze obliczyłam, zrozumiałam zasady :) Ostatnio edytowany: 2013-04-06 17:58:59 |
RSS