Некако сте се нашли упослени на пројекту производње најновије РНК вакцине, где радите на прототипу који се може описати као низ од \(N\) кодона, односно карактера који могу бити A, C, G, и U. Произведена вакцина ће бити стабилна само ако не садржи превише истих кодона. Конкретно, сматрамо је стабилном ако се ни један кодон не појављује строго више од \(\frac{N}{2}\) пута.

На располагању вам је РНКпоправљач, уређај који треба искористити тачно једном и који ће обрнути све кодоне у датом интервалу тако што A претвори у U и обрнуто, а C у G и обрнуто. Ваш задатак је да одредите да ли је овим путем могуће од прототипа добити стабилну вакцину (и како).

Нажалост, изгубили сте белешке, тако да не знате како прототип изгледа. На располагању вам је скенер, којим можете да испитате колико пута се неки кодон појављује у неком интервалу прототипа. Пошто сте у журби, скенер можете користити ограничен број пута.

Описи функција

Потребно је да имплементирате функцију

• \(\text{Resi}(N, L, R)\)

где је:

• \(N\) број кодона у прототипу.
• \(L\) и \(R\) променљиве у које треба да упишете индексе првог и последњег кодона које ћете обрнути РНКпоправљачем. Уколико није могуће добити стабилну вакцину овим путем, упишите \(L = R = -1\).

Ваш програм може да користи функцију

\(\text{Skener}(L, R, C)\)

која ће вратити број појављивања кодона \(C\) у интервалу \([L, R]\) прототипа (укључујући и \(L\)-ти и \(R\)-ти).

Низови су индексирани од 1.

Ограничења

Тест примери су подељени у неколико подзадатака. У сваком подзадатку је дато ограничење \(Q\), које представља дозвољен број позива функције \(\text{Skener}\).

• [? поена]: \(N \leq 1000\), \(Q = 4000\)
• [? поена]: \(N \leq 10^5\), \(Q = 3 \times 10^5 + 10\)
• [? поена]: \(N \leq 10^5\), \(Q = 2 \times 10^5 + 10\)
• [? поена]: \(N \leq 10^5\), \(Q = 1.5 \times 10^5 + 50\)
• [? поена]: \(N \leq 10^5\), \(Q = 36\)

Детаљи имплементације

Потребно је да пошаљете тачно један фајл rnk.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Resi(int N, int *L, int *R)

Ваш програм мора укључивати header code.h, у ком је дефинисана функција \(\text{Skener}\) следећег потписа:

int Skener(int L, int R, char C)

Уз задатак, обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N\) и \(Q\).
• У наредном реду стринг дужине \(N\) који представља прототип (сачињен искључиво од великих слова A, C, T и U).

Затим овај програм позива вашу функцију и штампа вредности \(L\) и \(R\) које је функција попунила у једном реду, и број позива функције \(\text{Skener}\) у другом. Уколико ваше решење користи скенер више од \(Q\) пута, биће прекинуто са статусом RTE (runtime error).