// Uncompression algorithm: sample solution // for the "Cold Compress" contest problem. #include #include #include #include #include using namespace std; int gcd (int k, int m) { while (k != 0 && m != 0) { if (k < m) m = m % k; else k = k % m; } return k+m; } int leastCommonMultiple (int k, int m) { return k / gcd(k,m) * m; } struct Coordinate { int x; int y; Coordinate (int xx, int yy): x(xx), y(yy) {} }; //////////////////////////////////////////////////////////////// // Picture stores a B&W picture, providing (x,y) access to each pixel. // The upper-left corner of the picture is addresswed as (0,0). // class Picture { public: Picture (): width(0), height(0) {} Picture (bool color): width(1), height(1), pixels(1,color) {} // Creates a 1x1 pixel of the indicated color bool colorAt (int x, int y) const {return pixels[x + width*y];} void setColorAt (int x, int y, bool b); int getHeight() const {return height;} int getWidth() const {return width;} void get (istream&); void put (ostream&) const; Picture horizontalJoin (const Picture& p) const; Picture verticalJoin (const Picture& p) const; Picture scale (int multiplier) const; private: vector pixels; int width; int height; void extend (int x, int y); }; void Picture::setColorAt (int x, int y, bool b) { extend(x,y); pixels[x + width*y] = b; } istream& operator>> (istream& in, Picture& p) { p.get(in); return in; } ostream& operator<< (ostream& out, const Picture& p) { p.put(out); return out; } bool charToBool (char c) { return (c == ' '); } void Picture::get(istream& in) { string line; while (line == "" && !(!in)) getline(in, line); // First line is --------- envelope. From this we determine the width. width = line.length() - 2; // Fill in rest of lines until we get one with more '-' characters height = 0; pixels.clear(); getline(in, line); while (line[1] != '-' && !(!in)) { transform (line.begin()+1, line.end()-1, back_inserter(pixels), charToBool); ++height; getline(in, line); } } char boolToChar (bool b) { return (b)? ' ' : 'X'; } void Picture::put(ostream& out) const { fill_n (ostream_iterator(out), width+2, '-'); out << endl; for (int h = 0; h < height; ++h) { out << '|'; transform (pixels.begin()+h*width, pixels.begin()+(h+1)*width, ostream_iterator(out), boolToChar); out << '|' << endl; } fill_n (ostream_iterator(out), width+2, '-'); out << endl; } void Picture::extend (int x, int y) { int i = x + y*width; if (i >= pixels.size()) pixels.resize(i+1); } Picture Picture::horizontalJoin (const Picture& p) const { int newHeight = leastCommonMultiple(height, p.height); Picture left = scale(newHeight / height); Picture right = p.scale(newHeight / p.height); Picture join; join.width = left.width + right.width; join.height = newHeight; for (int y = 0; y < newHeight; ++y) { for (int x = 0; x < left.width; ++x) join.setColorAt(x, y, left.colorAt(x,y)); for (int x = 0; x < right.width; ++x) join.setColorAt(x+left.width, y, right.colorAt(x,y)); } return join; } Picture Picture::verticalJoin (const Picture& p) const { int newWidth = leastCommonMultiple(width, p.width); Picture top = scale(newWidth / width); Picture bottom = p.scale(newWidth / p.width); Picture join; join.width = newWidth; join.height = top.height + bottom.height; for (int x = 0; x < newWidth; ++x) { for (int y = 0; y < top.height; ++y) join.setColorAt(x, y, top.colorAt(x,y)); for (int y = 0; y < bottom.height; ++y) join.setColorAt(x, y+top.height, bottom.colorAt(x,y)); } return join; } Picture Picture::scale (int multiplier) const { Picture scaled; scaled.width = multiplier*width; scaled.height = multiplier*height; for (int y = 0; y < scaled.height; ++y) for (int x = 0; x < scaled.width; ++x) scaled.setColorAt(x, y, colorAt(x/multiplier, y/multiplier)); return scaled; } //////////////////////////////////////////////////////////////// // Recursive descent parser Picture parse () { char c1, c2; cin >> c1 >> c2; int code = 2 * (c1 - '0') + (c2 - '0'); switch (code) { case 0: // black pixel // cout << "B" << flush; return Picture(false); case 1: // Vertical split { // cout << "V" << flush; Picture top = parse(); Picture vj = top.verticalJoin(parse()); // cout << "\n\nV\n" << vj; return vj; } case 2: // Horizontal split { // cout << "H" << flush; Picture left = parse(); Picture hj = left.horizontalJoin(parse()); // cout << "\n\nH\n" << hj; return hj; } case 3: // White pixel // cout << "W" << flush; return Picture(true); } } ////////////////////////////////////////////////////////////////// int main() { char c; while (cin >> c) { cin.putback(c); Picture p = parse(); cout << p << flush; } return 0; }