1). I've solved it using LZP based algorithm, but I think it is easy to solve it using simple order-0(1) entropy coder, like Huffman.

2). It is possible to solve it on C++.

P.S. I think this problem is one of the best on acm.tinus.ru