#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <memory>

struct Node {
	Node(const std::string& name, int prob) : name(name), prob(prob) { }
	Node(std::unique_ptr<Node>&& left, std::unique_ptr<Node>&& right) {
		prob = left->prob + right->prob;
		this->left = std::move(left);
		this->right = std::move(right);
	}
	std::string name;
	std::unique_ptr<Node> left;
	std::unique_ptr<Node> right;
	int prob;
};

void view_tree(const Node* node, int indent) {
	if (!node) return;
	for (int i = 0; i < indent; i++)
		std::cout << "  ";
	if (!node->name.empty())
		std::cout << node->name << " ";
	std::cout << "(" << node->prob << ")" << std::endl;
	view_tree(node->left.get(), indent + 1);
	view_tree(node->right.get(), indent + 1);
}

void view_code(const Node* node, std::string code) {
	if (!node) return;
	if (!node->name.empty())
		std::cout << node->name << "\t" << code << std::endl;
	view_code(node->left.get(), code + "0");
	view_code(node->right.get(), code + "1");
}

void encode(std::vector<std::unique_ptr<Node>>& nodes) {
	auto priority = [](const std::unique_ptr<Node>& x, const std::unique_ptr<Node>& y) { return x->prob < y->prob; };
	while (nodes.size() > 1) {
		auto most_min_it = std::min_element(nodes.begin(), nodes.end(), priority);
		auto most_min = std::move(*most_min_it);
		nodes.erase(most_min_it);
		auto most_min2_it = std::min_element(nodes.begin(), nodes.end(), priority);
		auto most_min2 = std::move(*most_min2_it);
		nodes.erase(most_min2_it);
		nodes.emplace_back(std::make_unique<Node>(std::move(most_min), std::move(most_min2)));
	}
}

int main(void) {
	std::vector<std::unique_ptr<Node>> nodes;
	do {
		std::string name;
		std::cout << "name: ";
		std::cin >> name;
		if (name.empty()) {
			std::cout << std::endl;
			break;
		}
		int prob;
		std::cout << "prob: ";
		std::cin >> prob;
		nodes.emplace_back(std::make_unique<Node>(name, prob));
	} while (1);
	if (nodes.empty()) {
		std::cerr << "Number of nodes must be greater than 0." << std::endl;
		return EXIT_FAILURE;
	}

	encode(nodes);

	std::cout << std::endl;
	std::cout << "tree" << std::endl;
	view_tree(nodes.front().get(), 0);

	std::cout << std::endl;
	std::cout << "code" << std::endl;
	view_code(nodes.front().get(), std::string());
	return EXIT_SUCCESS;
}