2. Vladkova hra vzorové riešenie

3
0 0 1

3

Simulácia

Priamočiarým riešením by mohlo byť si Vladkove hranie odsimulovať. Prechádzať po políčkach zľava doprava, vždy zmeniť stav plošinky a po postavení sa na políčko bez plošinky, vrátiť sa na začiatok. Počas tohto si budeme počítať, koľko krokov sme spravili. Toto budeme opakovať dovtedy, kým sa Vladko nedostane na koniec.

Toto riešenie funguje, avšak je pomerne pomalé.

Potrebujeme to simulovať?

Skúsme sa pozrieť na niektoré hry. Ak Vladkov level začína v stave 0 0 0, po prvom prejdení skončí v stave 1 0 0, potom 0 1 0, 1 1 0, 0 0 1, 1 0 1, 0 1 1 a skončí v 1 1 1. Vladko tento level dokončí po \(7\)-ich pokusoch.

Môžeme si všimnúť, že ak by sme level mali nakreslený opačne, tak postupnosť 0 0 0, 0 0 1, 0 1 0… vyzerá presne ako postupnosť binárnych čísiel od \(0\) do \(7\). Teraz si potrebujeme uvedomiť, že každý level, ktorý sa skladá iba z políčok bez plošiniek sa správa rovnako, a teda ho vieme reprezentovať ako postupnosť binárnych čísiel od \(0\) po \(x\). Následne potrebujeme zistiť, aké je to \(x\) pre daný počet políčok. Ak máme v leveli \(n\) políčok, aké najväčšie binárne číslo v ňom vieme zobraziť? To bude \(n\) jednotiek. Ak \(n\) binárnych jednotiek chceme premeniť na číslo v desiatkovej sústave, dostaneme \(2^0 + 2^1 + \dots + 2^{n-1}\). Alternatívne, vieme, že ak máme \(n\) binárnych jednotiek, tak číslo o jedna väčšie bude jednotka a \(n\) núl, čiže \(2^n\) v desiatkovej sústave. Potom naše pôvodné číslo bude \(2^n-1\).

Čo ale, ak nezačíname so samými nulami? Vtedy môžeme počiatočný stav vyjadrený ako binárne číslo odpočítať od celkového počtu pokusov, keby všetky políčka boli nulové.

Alternatívne môžeme počiatočný stav ako binárne číslo znegovať (0 1 0 -> 1 0 1) a premeniť do desiatkovej sústavy, čím dostaneme počet pokusov.

Časová aj pamäťová zložitosť takéhoto riešenia je \(O(n)\). Technicky si nemusíme pamätať celý vstup, ale spracovávať ho postupne, vtedy by sme vedeli dostať pamäťovú zložitosť aj \(O(1)\).

n = int(input())
states = list(map(bool, map(int, input().split())))

flips = 0

for i, s in enumerate(states):
	if not s:
		flips += 2**i

print(flips)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    ll helper = 0;
    ll power = 1;

    char c;
    for (int i = 0; i < n; i++){
        cin >> c;
        helper += power*(c - '0');
        power *= 2;
    }
    
    cout << (power - helper - 1) << "\n";
}