|
Titlul: Codeforces: Good Bye 2013 - Problem D Scris de: Emanuel Truta din Februarie 19, 2014, 23:22:00 Salut !
Imi spuneti va rog cum se face problema aceasta: http://codeforces.com/contest/379/problem/D ? Tutorialul la runda respectiva e foarte vag si nu am reusit sa inteleg nimic din el, iar in comentrui e explicat ceva acolo, dar iar nu am reusit sa inteleg. Help is very much appreciated ! Multumesc anticipat. Manu Titlul: Răspuns: Codeforces: Good Bye 2013 - Problem D Scris de: Mihai Calancea din Februarie 20, 2014, 00:08:52 Din recurența pentru string poți găsi o recurență pentru numărul de apariții ale șirului AC in șirul final: nr[j] = nr[j - 1] + nr[j - 2] + overlap, unde overlap e 0 sau 1. Chestia e că dacă ai două stringuri X și Y, numărul de apariții "AC" în X + Y e suma aparițiilor din X și din Y + eventual încă o apariție pe mijloc, la concatenare, dacă X se termină în A și Y începe cu C.
Deci în primul rând ar trebui să-ți fixezi de câte ori apare AC în primele două șiruri. Apoi trebuie să te hotărăști dacă vrei să apară AC-uri noi pe mijloc. Dacă examinezi puțin cum se formează șirurile ai să vezi că chestia asta depinde exclusiv de primele și ultimele litere ale celor două șiruri inițiale. |