Submission #2649978

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#define int long long
#define double long double
#define oku7 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
using namespace std;
std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位


vector<int> stable, ntable,table;
bool visited[1000000];

signed main() {
	int s=6, n=9;
	for (int i = 1; i < 10; i++) {
		if(s <= 100000)stable.push_back(s);
		if(n <= 100000)ntable.push_back(n);
		s *= 6;
		n *= 9;
	}
	for (int i : stable) {
		table.push_back(i);
	}
	for (int i : ntable) {
		table.push_back(i);
	}

	//BFSをする
	int N, one, ans=100000;
	cin >> N;
	queue<pair<int, int>> q;
	visited[N] = true;
	q.push(make_pair(0, N));
	while (!q.empty()) {
		pair<int, int> p = q.front();
		q.pop();
		if (p.second < 6) {
			int nowans = p.first + p.second;
			if (nowans < ans) ans = nowans;

		}
		for (int i : table) {
			if (p.second < i) continue;
			if (visited[p.second - i]) continue;
			visited[p.second - i] = true;
			q.push(make_pair(p.first + 1, p.second - i));
		}
	}

	cout << ans << "\n";


	return 0;
}

Submission Info

Judge Result