A: Merkkijono

Tässä tehtävässä riittää simuloida tehtävänannossa kuvattua prosessia jollakin toimivalla tavalla. Tässä on yksi mahdollinen C++-ratkaisu:

#include <iostream>

using namespace std;

int main() {
    string s;
    cin >> s;
    while (true) {
        int n = s.size();
        bool ok = false;
        for (int i = 0; i < n-1; i++) {
            if (s[i] == s[i+1]) {
                ok = true;
                int a = i;
                int b = i+1;
                while (b+1 < n && s[a] == s[b+1]) b++;
                s.erase(a,b-a+1);
                break;
            }
        }
        if (!ok) break;
    }
    cout << s << "\n";
}

B: Fraktaali

Yksi tapa ratkaista tehtävä on muodostaa fraktaalia taso kerrallaan. Lähtökohtana on 1 \times 1 -ruudukko, jossa on vain yksi musta ruutu, ja jokainen askel laajentaa ruudukkoa. Koodin voi toteuttaa näin:

#include <iostream>

using namespace std;

int k[1000][1000];

int main() {
    k[0][0] = 1;
    int n;
    cin >> n;
    int z = 1;
    for (int i = 1; i < n; i++) {
        for (int y = 0; y < z; y++) {
            for (int x = 0; x < z; x++) {
                k[y+z][x] = k[y][x];
                k[y][x+z] = k[y][x];
                k[y+z][x+z] = 1-k[y][x];
            }
        }
        z *= 2;
    }
    for (int y = 0; y < z; y++) {
        for (int x = 0; x < z; x++) {
            cout << ".#"[k[y][x]];
        }
        cout << "\n";
    }
}

C: Kyselyt

Kaksi ensimmäistä osatehtävää ratkeavat muodostamalla riittävän pitkä alkuosa merkkijonosta muistiin ja vastaamalla kyselyihin suoraan sen perusteella. Seuraava koodi muodostaa merkkijonon, johon on liitetty yhteen luvut 1,2,\ldots,10^6.

#include <iostream>

using namespace std;

int main() {
    string s;
    for (int i = 1; i <= 1000000; i++) s += to_string(i);
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        k--;
        cout << s[k] << "\n";
    }
}

Viimeinen osatehtävä on vaikeampi, koska kyselyt voivat kohdistua pitkälle merkkijonoon eikä ole mahdollista muodostaa koko merkkijonoa muistiin. Seuraavassa koodissa on ideana käsitellä tehokkaasti merkkijonon osia, joissa on peräkkäin samanpituisia lukuja. Esimerkiksi luvut 10,11,\ldots,99 muodostavat osan, jonka pituus on 2 \cdot 90 = 180.

#include <iostream>

using namespace std;

typedef long long ll;

char query(ll n) {
    n -= 1;
    ll cur = 1;
    ll len = 1;
    ll cnt = 9;
    while (len*cnt < n) {
        n -= len*cnt;
        cur *= 10;
        len++;
        cnt *= 10;
    }
    cur += n/len;
    n -= (n/len)*len;
    return to_string(cur)[n];
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        ll n;
        cin >> n;
        cout << query(n) << "\n";
    }
}

D: Bittijono

Hyvä ensimmäinen tavoite on tehdä koodi, joka ratkaisee kolme ensimmäistä osatehtävää. Tämä onnistuu käymällä läpi bittijonoja pituusjärjestyksessä ja tulostamalla ensimmäisen bittijonon, jolla on n alijonoa. Seuraavassa koodissa funktio count laskee tehokkaasti bittijonon alijonojen määrän. Ideana on laskea muuttujaan a, montako nollaan päättyvää alijonoa on, ja muuttujaan b, montako ykköseen päättyvää alijonoa on.

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<string> v;

int count(string x) {
    int a = 0, b = 0;
    for (int i = 0; i < x.size(); i++) {
        if (x[i] == '0') a = a+b+1;
        else b = a+b+1;
    }
    return a+b;
}

int main() {
    cin >> n;
    v.push_back("0");
    v.push_back("1");
    for (int i = 0; ; i++) {
        if (count(v[i]) == n) {
            cout << v[i] << "\n";
            return 0;
        }
        v.push_back(v[i]+"0");
        v.push_back(v[i]+"1");
    }
}

Viimeinen osatehtävä ratkeaa simuloimalla käänteisesti äskeisen funktion count toimintaa. Tämän voi tehdä käymällä läpi kaikki vaihtoehdot, mitkä muuttujien a ja b arvot ovat lopussa, ja valitsemalla lyhimmän bittijonon tuottavan ratkaisun. Seuraavassa koodissa funktio rev toteuttaa simuloinnin. Hyödyllinen lisätieto on, että lyhimmän bittijonon pituus on aina alle 50 merkkiä tehtävän rajoilla.

#include <iostream>

using namespace std;

int n;
int p = 50;

string ss, ps;

int rev(int a, int b) {
    if (ss.size() >= p) return p;
    if (a == 0 && b == 0) return 0;
    if (a == b) return p;
    if (a > b) {
        ss += "0";
        return rev(a-b-1,b)+1;
    } else {
        ss += "1";
        return rev(a,b-a-1)+1;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i <= n && i <= n-i; i++) {
        ss = "";
        int u = rev(i,n-i);
        if (u < p) {
            p = u;
            ps = ss;
        }
    }
    cout << ps << "\n";
}

E: Eppapeli

Eppapeliä voi ratkoa sekä käsin että tietokoneen avulla. 90 pisteen ratkaisun muodostaminen on melko helppoa, mutta 100 pisteen ratkaisu on selvästi hankalampi. Löydät esimerkkejä ratkaisuista kilpailun tulostaulun kautta.

Eppapelin 100 pisteen ratkaisu tunnetaan paremmin nimellä kreikkalais-latinalainen neliö kokoa 10 \times 10. Vuonna 1780 Euler arveli, että tällaisen neliön muodostaminen ei ole mahdollista, ja oletus pysyi voimassa aina vuoteen 1959 asti, jolloin E. T. Parker löysi 10 \times 10 -neliön tietokoneen avulla.