058.md

058 - Original Calculator (★4)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::find()
#include <iterator> // std::distance()

constexpr int MOD = 100000;

// 各桁の和を計算
int SumDigits(int x)
{
	int result = 0;

	while (x)
	{
		result += (x % 10);
		
		x /= 10;
	}

	return result;
}

// 整数 x が表示されているときにボタン A を 1 回押したときの次の値を計算
int Next(int x)
{
	return ((x + SumDigits(x)) % MOD);
}

int main()
{
	// 最初に N が表示されていて, ボタンを K 回押す
	int N;
	long long K;
	std::cin >> N >> K;

	// 事前に変換テーブルを作成
	std::vector<int> table(MOD);
	for (int i = 0; i < MOD; ++i)
	{
		table[i] = Next(i);
	}

	// [i] を、何回ボタンを押したときに訪れるかを記録（未訪問は -1）
	std::vector<int> timestamps(MOD, -1);
	{
		// 表示している数
		int current = N;

		// ボタンを押した回数
		int buttonCount = 0;

		// 循環を見つけたら抜ける
		while (timestamps[current] == -1)
		{
			timestamps[current] = buttonCount;

			current = table[current];

			++buttonCount;
		}

		// 何回ボタンを押したときから循環に入るか
		const int cycleStartsAt = timestamps[current];

		// 見つかった循環のサイクル数
		const int cycle = (buttonCount - cycleStartsAt);

		if (cycleStartsAt <= K)
		{
			// 循環を考慮して K の値を小さくする
			K = ((K - cycleStartsAt) % cycle + cycleStartsAt);
		}
	}

	// K 回ボタンを押したときに表示されている値を調べる
	const auto answer = std::distance(timestamps.begin(), std::find(timestamps.begin(), timestamps.end(), K));

	// 解答を出力
	std::cout << answer << '\n';
}