首页 > 其他 > 详细

JZOJ 3058. 火炬手

时间:2019-07-12 21:57:28      阅读:96      评论:0      收藏:0      [点我收藏+]

题目

 

 

Description

 


 

【问题描述】


    全运会就要开始了,笨笨想成为湖南地区的火炬手,经过层层选拔,最终到了最后一关,这一关给出了一个正整数n(N<=100000),求一个最小的正整数m,使得n*m的十进制表示形式中只含1和0. 


 

 

Input

 


 

【输入格式】


    一行一个数n


 

Output

 


 

【输出格式】


    输出一行,如果有解,输出最小的m,否则输出‘no solution’.


 

 

Sample Input

12

Sample Output

925
 

Data Constraint

 
 

Hint

 


N<=100000

 

分析

 

  • 正解=暴力 OVO
  • 首先DFS,好像会炸的哦(但是他们都过了)
  • 还是广搜吧
  • 队列
  • 但如果无解会超时还是负数??
  • 那就特判,或者用个time?(比赛不能用)
  • 好吧特判

 

代码

 

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 using namespace std;
 7 queue <long long> q;
 8 long long n;
 9 long long tot;
10 char s[50];
11 int main ()
12 {
13     cin>>n;
14     q.push(1);
15     while (1)
16     {
17         long long x=q.front(); q.pop();
18         if(x<0)
19         {
20             cout<<"no solution";
21             return 0;
22          } 
23         if (x%n==0)
24         {
25             cout<<x<<" "<<x/n;
26             return 0;
27         }
28         q.push(x*10); q.push(x*10+1);
29     }
30 }

 

 

JZOJ 3058. 火炬手

原文:https://www.cnblogs.com/zjzjzj/p/11178155.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!