Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
E. Төрсөн өдөр
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Өнөөдөр бяцхан Дашагийн төрсөн өдөр ба тэр 8 нас хүрч байна! Энэ үйл явдалд түүний $n$ ширхэг найз болон хамаатан бүр түүнд дээрээ мэндчилгээтэй тууз өгсөн ба бүх мэндчилгээ ялгаатай. Даша бүх туузыг цуглуулсан ба үлдсэн туузуудыг ганган байлгахаар заримыг нь хаяхаар шийдсэн. Даша ямар ч туузан дээр бичсэн мэндчилгээ өөр туузан дээр бичигдсэн өөр мэндчилгээний дэд тэмдэгт мөр болохгүй байх туузны бүрдлийг ганган гэж үзнэ. $s$-н дэд тэмдэгт мөр гэдэг нь $s$ тэмдэгт мөр дахь үргэлжилсэн хэсгийг хэлнэ.
Дашад бүх найзууддаа гайхуулж чадах боломжит хамгийн олон тууз үлдээхэд туслана уу. Даша туузуудыг эргүүлж, тонгоргож чадахгүй буюу мэндчилгээ бүр оролтонд өгөгдсөн ганц л замаар уншигдана.
Оролт
Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 750$) байх Дашагийн хамаатнууд болон найзуудын тоо.
Дараагийн $n$ мөр бүрт яг нэг мэндчилгээ байна. Мэндчилгээ бүр зөвхөн '$a$' болон '$b$' тэмдэгтээс л тогтоно.
Бүх мэндчилгээнүүдийн нийт урт $10 000 000$ тэмдэгтээс хэтрэхгүй.
Гаралт
Эхний мөрөнд ганган бүрдлийн хамгийн их хэмжээг хэвлэ. Хоёр дахь мөрөнд үүнд оролцсон туузнуудын дугааруудыг хэвлэх ба туузнууд оролтонд өгсөн дарааллаараа $1$-c $n$ хүртэл дугаарлагдсан гэж үз. Хэрвээ хамгийн их хэмжээтэй хэд хэдэн ганган бүрдэл байвал алийг нь ч хэвлэж болно.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
5 abab aba aabab ababb bab
Гаралт
2 2 5
Тэмдэглэл
Жишээн дээр 3 болон 4 туузуудыг хадгалах нь бас зөвд тооцогдоно.