InterLOS 2012 && Haluzná letargia

... v zložení MišoF, Janka, Danka, Monika a YoYo

Nasledujúce riadky nesú nejaké útržky informácií o tom, ako sme čo riešili, ak to stálo za zmienku.

P1 Vyloženě triviální

Vyriešené v podstate autorsky, až na to, že inverznú funkciu k t(l,r) sa robí binárnym vyhľadávaním, ktoré je blbuvzdornejšie ako sa zamýšľať nad odmocninami. Môj kód prekladajúci číslo na program je o niečo stručnejší od autorského.

from sys import stdin
program = int(stdin.read())

def split(x): # prevedie x=t(l,r) na l,r: prvy krok je binarne vyhladanie l+r, druhy dopocitanie l,r
    lo, hi = 0, x+1
    while hi-lo > 1:
        med = (lo+hi)//2
        if med*(med+1)//2 <= x: lo = med
        else: hi = med
    l = x - lo*(lo+1)//2
    return l, lo-l

def getpow(x,p):
    ans = 0
    while x%p==0: ans, x = ans+1, x//p
    return ans

def parsuj(program):
    if program%2==0:
        l,r = split(program//2)
        if l==0:
            cmds = []
            while r:
                r,c = split(r)
                cmds.append(c)
            for c in cmds[::-1]: parsuj(c)
        else:
            print "while X[%d]!=X[%d] do begin" % (getpow(l,2),getpow(l,3))
            parsuj(r)
            print "end;"
    else:
        p3, p5, p7 = getpow(program,3), getpow(program,5), getpow(program,7)
        if p3>0 and p7>0: print "X[%d] := X[%d] * X[%d];" % (p3,p3,p7);
        if p5>0 and p7>0: print "if X[%d]=0 then X[%d]:=0 else X[%d]:=X[%d]-1;" % (p7,p5,p5,p7)
        if p3>0 and p5>0: print "X[%d] := X[%d] + %d;" % (p5,p5,p3)

parsuj(program)

P3 Sudoku netradične

Hrubá sila, teda obyčajná rekurzia, po každom vnorení surovo skontrolujeme celý hrací plán (just because we can) či náhodou nemáme nejaký viditeľný spor.

hodnoty = [ [0]*6 for r in range(6) ]
hodnoty[0][5] = 5 ; hodnoty[1][4] = 4 ; hodnoty[4][1] = 5 ; hodnoty[5][0] = 2

oblasti = []
oblasti.append([ (0,0), (0,1), (0,2), (1,2), (1,3), (1,4) ])
oblasti.append([ (0,3), (0,4), (0,5), (1,5), (2,5), (3,5) ])
oblasti.append([ (1,0), (1,1), (2,1), (3,1), (4,1), (4,2) ])
oblasti.append([ (2,0), (3,0), (4,0), (5,0), (5,1), (5,2) ])
oblasti.append([ (2,2), (2,3), (2,4), (3,2), (3,3), (4,3) ])
oblasti.append([ (3,4), (4,4), (4,5), (5,3), (5,4), (5,5) ])

def check_area(values):
    for i in range(1,7):
        if values.count(i) > 1: return False
    return True

def get_row(x): return [ hodnoty[x][i] for i in range(6) ]
def get_col(x): return [ hodnoty[i][x] for i in range(6) ]
def get_box(x): return [ hodnoty[ oblasti[x][i][0] ][ oblasti[x][i][1] ] for i in range(6) ]

def check_everything():
    for i in range(6):
        if not check_area( get_row(i) ): return False
        if not check_area( get_col(i) ): return False
        if not check_area( get_box(i) ): return False
    return True

def solve(r,c):
    if not check_everything(): return 0
    if r==6: return 1
    if c==5: nr,nc = r+1,0
    else: nr,nc = r,c+1
    if hodnoty[r][c]>0: return solve(nr,nc)
    answer = 0
    for v in range(1,7): hodnoty[r][c]=v ; answer += solve(nr,nc)
    hodnoty[r][c] = 0
    return answer

print solve(0,0)

L1 Interlosí domino

Dominá najskôr skúšala Janka ručne, no keď ju neposlúchali, napísal na ne YoYo logický program. (Ten momentálne nemám.)

S2 Čítanka

Tu sme skončili asi ako všetci: Mali sme správne zoradených všetkých 6 ukážok do poradia, vedeli sme že záleží na dĺžkach ukážok, aj že treba aj pozerať, aj že treba googliť. Neprišiel krok na YouTube. Časť problému bola asi v tom, že veta "tvé jméno je pojem" bola zjavne adresovaná postave (ktorej meno sme vedeli a bolo jasné, že googliť ho nemá zmysel).

P4 ReMorse

Na jedno kolo prekladu bohate stačil sed:

sed -e 's/.-.-.-\//A/g' -e 's/-....-\//B/g' -e 's/-..-.\//C/g' -e 's/A/./g' -e 's/B/-/g' -e 's/C/\//g'

P5 Losí komprese

Monika napísala rekurziu s memoizáciou, z tej je jasné, že ak nie sú všetky písmená rovnaké, odpoveď by mala byť najviac 2. Intuícia potom jasne hovorí, že ak sa to dá zraziť na 1, dá sa to mrte veľa spôsobmi, takže stačí pár náhodne odskúšať. Ak nejaký sadne, sme si istí, že je to 1, ak nie, tak je to asi 2. Skúsime odovzdať, a ak nebude dobre, doladíme, ktorá 2 má byť 1. Dolaďovať samozrejme nebolo treba.

program z prvého kroku riešenia:

#include <iostream>
#include <map>
using namespace std;

map<string, int> M;

char treti(char a, char b) {
    if (a > b) swap(a,b);
    if (a == 'L' && b == 'O') return 'S';
    if (a == 'L' && b == 'S') return 'O';
    if (a == 'O' && b == 'S') return 'L';
    return '*';
}

int komprimuj(string s) {
    if (M.find(s) != M.end()) return M[s];
    M[s] = s.size();
    for (unsigned i=0; i+1<s.size(); ++i) {
        char c = treti(s[i],s[i+1]);
        if (c == '*') continue;
        const string ns = s.substr(0,i) + string(1,c) + s.substr(i+2);
        M[s] = min(M[s], komprimuj(ns));
    }
    return M[s];
}

int main(void) { string s; cin >> s; cout << s << " " << komprimuj(s) << endl; }

a program z druhého kroku riešenia:

from sys import stdin
from random import choice

def nahodne_vyzer(S):
    n = len(S)
    if S=='L'*n or S=='O'*n or S=='S'*n: return n
    i = choice( [ i for i in range(n-1) if S[i] != S[i+1] ] )
    for c in ['L','O','S']:
        if c!=S[i] and c!=S[i+1]:
            return nahodne_vyzer( S[:i] + c + S[i+2:] )

for line in [ x.strip() for x in stdin.readlines()]:
    best = len(line)
    for i in range(1000): best = min(best,nahodne_vyzer(line))
    print best

P6 Prolomení hesla

Myšlienka nášho riešenia bola OK, len Mišof mal bug v dekódovaní a našiel si ho až po konci.

Komu by sa chcelo čítať tie strany textu o tom, ako funguje to divné hashovanie? Lepšie je ich preskočiť a vyriešiť to celé bez toho.

Ako sa dešifruje? Použije sa 8-znakový hash, teda 256⁸ možností. To je veľa. Lenže pŕŕ. Pri dešifrovaní sa ráta modulo 26, takže stačí uvažovať hashe s hodnotami od 0 do 25 na každej pozícii. To už je len 26⁸ možností, čo je omnoho krajšie číslo. Pokojne ich môžeme veľa vyskúšať. Napríklad tak, že vyskúšame prvých 6 znakov hashu (300 miliónov možností). Pomocou nich vieme dešifrovať prvých 6 znakov správy. Zahodíme mizerne znejúce. Dobre znejúce usporiadame a od najnádejnejších spracúvame – teda skúšame všetky možnosti pre siedmy a ôsmy znak hashu.

#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

string CT = "vlswkfzsilbwdrkkozqcceyffjxuiztmkigvcnzrhyfdrmlpeigkysocbhoswlbuodkuyqqkpxzyhhdrvgjtks";
int tetra[32][32][32][32];

void loadTetragrams() {
    ifstream fin("tetra.txt");
    string buf; int x;
    while (fin >> buf >> x) tetra[ buf[0]-'a' ][ buf[1]-'a' ][ buf[2]-'a' ][ buf[3]-'a' ] += x;
}

bool good(const string &S) { return S.find(string("hashovaci")) != string::npos; }

string decode(const vector<int> &hash, int letters) {
    string out;
    for (int i=0; i<min(letters,(int)CT.size()); ++i) out += 'a' + ( 2600 + (CT[i]-'a') - hash[i%8] - (i?CT[i-1]-'a':0) ) % 26;
    return out;
}

double score(const vector<int> &hash, int letters) {
    double res = 0;
    string dec = decode(hash,letters);
    for (int i=0; i<letters-3; ++i) res += log( tetra[ dec[i]-'a' ][ dec[i+1]-'a' ][ dec[i+2]-'a' ][ dec[i+3]-'a' ] + 1. );
    return res;
}

int main() {
    loadTetragrams();
    vector<int> hash(8,0);
    vector< pair<double, vector<int> > > Z;

    for (hash[0]=0; hash[0]<26; ++hash[0])
    for (hash[1]=0; hash[1]<26; ++hash[1])
    for (hash[2]=0; hash[2]<26; ++hash[2])
    for (hash[3]=0; hash[3]<26; ++hash[3]) {
        if (score(hash,4) < 1) continue; // zahodime uplne blbe prve stvorice znakov
        for (hash[4]=0; hash[4]<26; ++hash[4])
        for (hash[5]=0; hash[5]<26; ++hash[5]) {
            // zoberieme nadejne vyzerajuce prve sestice znakov
            double s = score(hash,6);
            if (s>20) Z.push_back( make_pair(s,hash) );
        }
    }
    sort(Z.begin(),Z.end());
    reverse(Z.begin(),Z.end());
    for (auto hu : Z) {
        hash = hu.second;
        for (hash[6]=0; hash[6]<26; ++hash[6])
        for (hash[7]=0; hash[7]<26; ++hash[7]) {
            string d = decode(hash,CT.size());
            if (good(d)) { cout << d << endl; return 0; }
        }
    }
}

L4 Záhada v královském paláci

Je jasné, že ide o šachové figúrky. Zadanie je však dosť nejednoznačné (kedy sa kto hýbe? čo presne je pohyb bližšie? atď.) tak to v princípe viedlo k tomu, že YoYo a Danka hľadali nové a nové jednoznačne riešiteľné interpretácie zadania až kým pre jednu z nich (myslím, že štvrtú v poradí) odpoveď nebola uznaná.

S5 Nie som, čo som

Po nejakej tej snahe nájsť steganografickú správu priamo v obrázku nakoniec YoYo objavil hlavičku ZIPu a odtiaľ ďalej to už bolo "smooth sailing". Načo rozmýšľať, čo to je, keď nám to file (až na úvodné html) sám povie? Priebežne počas rozbaľovania sme teda už rovno prečítali "?IFAR" a potom podľa obrázku html5 ešte doklepli to G.

$ file 01.html 02.zip 03.zip 04.zip 05.zip 
01.html: JPEG image data, JFIF standard 1.01
02.zip:  Audio file with ID3 version 2.3.0, contains: MPEG ADTS, layer III, v1, 128 kbps, 44.1 kHz, Monaural
03.zip:  Composite Document File V2 Document, Little Endian, Os: Windows, Version 6.1, Code page: 1250, Title:
  \300ifra, Author: InterLoS, Keywords: interlos, sifra, los, Template: Normal.dotm, Last Saved By: Spravca, 
  Revision Number: 8, Name of Creating Application: Microsoft Office Word, Total Editing Time: 21:00, Create 
  Time/Date: Fri Nov 16 10:25:00 2012, Last Saved Time/Date: Thu Nov 29 12:50:00 2012, Number of Pages: 1, 
  Number of Words: 5, Number of Characters: 34, Security: 0
04.zip:  MS Windows icon resource - 5 icons, 256-colors
05.zip:  EBML file, creator matroska

S6 Co chybí?

Aha-krok že ide o slovné druhy bol pekný. Chýba zrejme predložka. Aj aha-krok že z ostatných názvov zmizli predložky je pekný. Ale prečo preboha je odpoveď LA? U nás odovzdané až na štvrtý pokus, po "PREDLOZKA", "PREDLOZKY" (oboje sú skutočne odpoveďou na otázku zo zadania, singulár preto, že ostatné slovné druhy v zadaní sú v singulári) a tuším "LKA" z nepozornosti. Toto je podľa mňa šifra, ktorá si zaslúžila upresnítko riešenia (napr. "riešenie má menej ako 5 písmen").

P7 Závody pixelů

Základ úspechu je využiť už existujúcu hlavičku bitmapy a len prehádzať poradie pixelov za ňou, potom si rovno môžeme pozrieť, čo to spravilo.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

unsigned char buf[30000], out[30000];
int kde[160][160];
int CIEL = 42195, dobehlo = 0;
long long A = 42;

int hod() { int out=(A%100)+1; A=(A*A)%9876553; return out; }

int main() {
    int z = read(0,buf,30000);
    memcpy(out,buf,z);
    while (dobehlo < 160*160) {
        for (int r=0; r<160; ++r) for (int c=0; c<160; ++c) if (kde[r][c] < CIEL) {
            kde[r][c] += hod();
            if (kde[r][c] >= CIEL) {
                out[z-25600+160*r+c] = buf[z-25600+dobehlo];
                ++dobehlo;
            }
        }
    }
    write(1,out,z);
}

P8 Retiazka

Takmer autorsky, postupne zvyšujeme K a kontrolujeme, či sa dá vhodne rozdeliť zvyšok retiazky.

// napisala Monika, uloha retiazka, Interlos 2012
// vstup: 10 456 789657 4654789 35468794 7258
#include <iostream>
using namespace std;

int main(void) {
    long long N;
    while(cin >> N) {
        for(long long K=1; K<100; ++K) {
            long long best = K;
            bool konec = false;
            for (int i=0; i<=K; ++i) {
                best = 2*best+1;
                if (best >= N) { konec = true; break; }
            }
            if (konec) { cout << K; break; }
        }
    }
    cout << endl;
}

P9 Slovní mutace

Najlenivejší možný algoritmus na najkratšie cesty: Bellmanov-Fordov. Stačí.

slova = set( open('slovnicek.txt','r').read().split() )
dist, odkial = {}, {}
dist['TEXT'] = 0

def hrany(start):
    for i in range(len(start)):
        w = start[:i] + start[i+1:]
        if w in slova: yield 2,w
        for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            w = start[:i] + c + start[i+1:]
            if w in slova: yield 1,w
    for i in range(len(start)+1):
        for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
            w = start[:i] + c + start[i:]
            if w in slova: yield 2,w

while True:
    for w in slova:
        if not w in dist: continue
        for c, z in hrany(w):
            if (not z in dist) or (dist[w]+c<dist[z]): dist[z], odkial[z] = dist[w]+c, w
    if 'PISAR' in dist:
        kde = 'PISAR'
        while kde != 'TEXT': print kde, ; kde = odkial[kde]
        print 'TEXT'

L9 Krychle krychlí

Danka začína niečo skladať, po chvíli hlási, že na konci je "ODYL", odovzdávame krokodíla a kocku jej pod hrozbou násilia berieme (dohráš sa po skončení!). Pobavilo, keď sme z autorských riešení zistili, koľko textu sme preskočili :)

S7 Vlnění

Už niekedy zo začiatku lúštenia padali humorné návrhy typu či nespravíme Fourierovu transformáciu. A až keď došlo na frekvenčnú analýzu, tak sme pochopili, že sme ju vlastne v princípe spravili. Bolože to radosti na starom bielidle :)

S8 Rozměrná

Skutočná šifrovacia lahôdka na koniec, mňam! Postupne sme odkrývali, čo nám to neuveriteľne minimalistické zadanie hovorí, a každý krok bol krásny, vrátane takých detailov ako že v 2D sa čítajú dvojky a v 3D potom trojky.