Solution to a problem from a local programming contest.

sierpinski.cpp

#include <iostream>
#include <vector>
#include <cstdio>


using namespace std;

struct Block {
	vector<vector<bool> > grid;
	int size;
	
	Block(int size)
	: size(size) {
		for(int i = 0; i < size; i++) {
			vector<bool> row;
			for(int j = 0; j < size; j++) {
				row.push_back(false);
			}
			grid.push_back(row);
		}
	}
	
	void set(int r, int c) {
		grid[r][c] = true;
	}
	
	bool get(int r, int c) const {
		return grid[r][c];
	}
	
	void paste(int r, int c, const Block* block) {
		int i, j;
		for(i = 0; i < block->size; i++) {
			for(j = 0; j < block->size; j++) {
				if(block->get(i, j)) {
					set(i + r, j + c);
				}
			}
		}
	}
	
	void print(char t, char f) const {
		int i, j;
		for(i = 0; i < size; i++) {
			for(j = 0; j < size; j++) {
				putchar(grid[i][j] ? t : f);
			}
			putchar('\n');
		}
	}
};


int main(int argc, char* argv[]) {
	vector<Block*> triangles;
	
	Block* cur = new Block(2);
	cur->set(0, 0);
	cur->set(1, 0);
	cur->set(0, 1);
	cur->set(1, 1);
	
	triangles.push_back(cur);
	
	int size = 2;
	
	for(int i = 1; i < 10; i++) {
		size <<= 1;
		Block* next = new Block(size);
		
		next->paste(size/2, 0, cur);
		next->paste(size/2, size/2, cur);
		next->paste(0, size/4, cur);
		
		cur = next;
		triangles.push_back(cur);
	}
	
	int n;
	cin >> n;
	
	int trial;
	for(trial = 1; trial <= n; trial++) {
		int k;
		cin >> k;
		
		printf("Triangle #%d:\n", trial);
		triangles[k-1]->print('X', ' ');
		putchar('\n');
	}
	
	for(int i = 0; i < triangles.size(); i++) {
		delete triangles[i];
	}
	
	return 0;
}