当前位置：网站首页>[training Day2] torch bearer [violence] [DFS]

[training Day2] torch bearer [violence] [DFS]

2022-07-18 15:50:00 【VL——MOESR】

Insert picture description here

Ideas ：

We consider constructing 01 strand , Then let it remove the smallest m
Construct with search
although bfs Better , but dfs You can pass this question
（ The valley of Los Angeles cannot pass ）

$c o d e$

#include<iostream>
#include<cstdio>

using namespace std;

long long n;
long long ans=1e18;

void dfs(long long x, long long m)
{
    
	if(m%n==0)
	{
    
		ans=min(ans, m/n);
		return;
	}
	if(x>18)
		return;
	dfs(x+1, m*10+1);
	dfs(x+1, m*10);
}

int main()
{
    
	scanf("%lld", &n);
	dfs(1, 1);
	if(ans==1e18)
		printf("no solution");
	else printf("%lld %lld", ans);
	return 0;
}