#include <iostream>
#include <vector>

using namespace std;

namespace {

void
part1(const size_t n)
{
	vector<size_t> v{ 3, 7 };
	size_t         first  = 0;
	size_t         second = 1;

	while ( v.size() < n + 10 ) {
		auto value = v[first] + v[second];
		if ( value >= 10 ) {
			v.emplace_back(1);
			value -= 10;
		}
		v.emplace_back(value);

		first  = (first + v[first] + 1) % v.size();
		second = (second + v[second] + 1) % v.size();
	}

	cout << "Part 1: ";
	for ( size_t i = n; i != n + 10; ++i ) {
		cout << v[i];
	}
	cout << '\n';
}

void
part2(const size_t n)
{
	vector<size_t> v{ 3, 7 };
	size_t         first  = 0;
	size_t         second = 1;

	const size_t len = to_string(n).length();

	auto check = [&] {
		if ( v.size() < len ) {
			return false;
		}

		size_t value = 0;
		for ( size_t i = len; i > 0; --i ) {
			value *= 10;
			value += v[v.size() - i];
		}

		return value == n;
	};

	for ( ;; ) {
		auto value = v[first] + v[second];
		if ( value >= 10 ) {
			v.emplace_back(1);
			if ( check() ) {
				break;
			}

			value -= 10;
		}

		v.emplace_back(value);
		if ( check() ) {
			break;
		}

		first  = (first + v[first] + 1) % v.size();
		second = (second + v[second] + 1) % v.size();
	}

	cout << "Part 2: " << v.size() - len << '\n';
}

} // namespace

int
main()
{
	const size_t input = 607331;
	part1(input);
	part2(input);
}