Malíř kvadrantista

Bonifác o poněkud nudné hodině výtvarné výchovy vymýšlel nové umělecké směry. Třeba kvadrantismus. Kvandantisté své obrazy malují na čtvercová plátna. Vždy plátno rozdělí na čtyři čtvrtiny (křížem), jednu čtvrtinu namalují celou černě, jinou celou bíle, a do zbylých dvou čtvrtin namalují menší kvadrantistické obrazy. Když byl Bonifác přistižen, že nedává pozor, dostal za domácí úkol nějaký kvadrantistický obraz namalovat.

Jenže ono to není tak snadné, pokud chcete vytvořit dílo srozumitelnější než běžné moderní umění. Tak si Bonifác pomohl předlohou: vzal fotku své kočky, což je černobílý obrázek o rozměrech \(2^k\times 2^k\) pixelů. A chce vymyslet algoritmus, který najde co nejpřesnější kvadrantistickou aproximaci fotky. Tedy kvadrantistický obraz, který se od fotky liší v co nejméně pixelech.

Tuto úlohu také potkáte pod názvem Kvadrantová komprese v ReCodExu.