Preface

I haven't written a blog for a long time , Maybe a little rusty , If there is any mistake, please point it out in the comment area ~
Come to Jizhong , Play games every day , A little tired ,~~~~(>_<)~~~~.

Original title website

For some reason , This website will be inaccessible …

Title Description

The National Games is about to begin , Benben wants to be a torch bearer in Hunan , After layers of selection , Finally, we reached the last level , This level gives a positive integer $n$, Find the smallest positive integer $m$, bring $n\ast m$ The decimal representation of contains only $1$ and $0$.

Format

Input format

Count one line at a time $n$.

Output format

Output one line , If there is any solution , The smallest output $m$, Otherwise output ‘no solution’.

Examples

sample input

12

sample output

925

Tips

$n\le 100000$

Their thinking

As the only one who depends on himself in two days A Missing topic , This problem is actually very challenging , It took me a long time to come up with a non positive solution , And there are many ways , I'm using metaphysics DFS（ Breadth first search ） Algorithm .
It's actually enumeration $01$ Every bit of the string , The number of digits is a little big , For some particular $n$, Their corresponding $m$ It could be as much as $\infty$ position （ To make fun of ）.

Code

too · On · detailed · fine

#include<bits/stdc++.h> //  The header file 
#define integer unsigned long long //  habit 
using namespace std; //  Namespace 
integer n; //  Definition n
queue<integer> q; //  Define the queue 
void bfs(integer first) {
     //  Definition bfs
	while(!q.empty()) {
     //  Empty first 
		q.pop(); //  eject 
	} //  Emptying end 
	q.push(first); //  Put the initial value in 
	while(!q.empty()) {
     //  It doesn't need to be !q.empry(), Because it's on the bottom return Exit function 
		integer m=q.front(); //  Get first element 
		q.pop(); //  eject 
		if(m%n==0) {
     //  eureka 
			cout<<m/n; //  Output 
			return; //  return 
		} //  The judgment is over 
		q.push(m*10); //  End the next one with 0 Put the string of into the queue 
		q.push(m*10+1); //  End the next one with 1 Put the string of into the queue 
	} // while The loop ends 
}  // bfs end 
int main() {
     //  The main function starts 
	cin>>n; //  Input 
	bfs(1); //  Start bfs, The initial value is 1
	return 0; //  end 
} //  End of main function 

Such a detailed program is certainly not a positive solution , The positive solution also needs high accuracy , Otherwise, you can't face things like 99999 So tricky $n$ The data of .