Problemi 117

Kërkesa

Në një lojë kemi N monedha të numëruara nga 1N, dhe fillimisht të gjitha monedhat janë nga e njëjta anë (H ose T). Loja luhet me N raunde, dhe në çdo raund k, lojtari kthen k monedhat e para (nga 1 deri në k) në anën tjetër. Duam të gjejmë se sa monedha do jenë në një anë të caktuar (H ose T) në fund të lojës.

Referenca: https://www.codechef.com/problems/CONFLIP

Shembull

$ cat input.txt
2
1 5 1
1 5 2

$ python3 prog.py < input.txt
2
3

Kemi 2 raste testimi. Në rastin e parë kemi I=1, N=5, Q=1, që do të thotë se fillimisht monedhat janë të gjitha në anën H, kemi 5 monedha dhe 5 raunde, dhe në fund të raundit të 5-të duam të dimë se sa monedha janë në anën H.

Në rastin e dytë është e njëjta gjë, vetëm se duam të dimë se sa monedha janë në anën T (Q=2).

Gjendja e monedhave pas çdo raundi do jetë e tillë: 1. T H H H H 2. H T H H H 3. T H T H H 4. H T H T H 5. T H T H T

Kështu që përgjigja për rastin e parë është 2, kurse për rastin e dytë është 3.

Zgjidhja 2

Sqarime

Zgjidhja e parë është e rendit \(O(N^2)\), që do të thotë se duhen kryer përafërsisht \(N^2\) veprime. Kur \(N\) bëhet e madhe, \(N^2\) bëhet shumë shpejt jashtëzakonisht e madhe.

Kurse zgjidhja e e dytë është e rendit \(O(C)\), që do të thotë se nuk ka rëndësi se sa e madhe është N-ja, ne mund ta gjejmë gjithmonë përgjigjen me një numër konstant veprimesh.