Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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.

  1. Każdy jednoliterowy wyraz jest palindromem jednokrotnym.
  2. 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.
  3. 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 (≤ 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 (≤ 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:

Dodane przez:Witold Długosz
Data dodania:2013-04-02
Limit czasu wykonania programu:0.100s-0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.