infoarena

infoarena - concursuri, probleme, evaluator, articole => Probleme externe => Subiect creat de: Emanuel Truta din Februarie 19, 2014, 23:22:00



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.