1495. One-two, One-two 2

Myth丶恋晨 2022-01-05 15:37 205阅读 0赞

## 1495. One-two, One-two 2 ##

Time limit: 2.0 second Memory limit: 64 MB

A year ago the famous gangster Vito Maretti woke up in the morning and realized that he was bored of robbing banks of round sums. And for the last year he has been taking from banks sums that have only digits 1 and 2 in their decimal notation. After each robbery, Vito divides the money between   *N*  members of his gang. Your task is to determine the minimal stolen sum which is a multiple of   *N*.

### Input ###

The input contains the number   *N*  (1 ≤  *N* ≤ 10 6).

### Output ###

Output the minimal number which is a multiple of   *N*  and whose decimal notation contains only digits 1 and 2. If it contains more than 30 digits or if there are no such numbers, then output "Impossible".

### Samples ###

<table style="border:1px solid #000000;border-collapse:collapse;"> 
 <tbody> 
  <tr> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">input</th> 
   <th style="border:1px solid #000000;color:#000000;vertical-align:top;">output</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>5
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>Impossible
</pre> </td> 
  </tr> 
  <tr> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>8
</pre> </td> 
   <td style="border:1px solid #000000;vertical-align:top;"> <pre>112
</pre> </td> 
  </tr> 
 </tbody> 
</table>

**Problem Author: **Igor Chevdar **Problem Source: **XIII-th USU Junior Contest, October 2006

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

广搜优化（需要对  数   的感应能力）

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<string>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<cstdio>
     6 #include<vector>
     7 #include<queue>
     8 #include<algorithm>
     9 #define  LL  long long
    10 using namespace std;
    11 struct  que
    12  {
    13      int L,k;//k记录数，L记录长度
    14      int mod,f;//mod记录余数，f记录前驱
    15  }q[1000001];
    16  int had[1000001];//记录余数防止余数重
    17  int mod1,mod2;//记录取1和2时的余数
    18  int I,J;//如果余数出现循环时说明无解（两个指针）
    19  int n,m,k,t;
    20  int gs;
    21  void  bfs()
    22   {
    23       while(I<J)
    24        {
    25            int L=q[I].L;
    26            if(L==30){
           return;I++;}
    27            int mod=q[I].mod;
    28            mod1=(mod*10+1)%n;
    29            mod2=(mod*10+2)%n;
    30 
    31            if(had[mod1]==false)
    32             {
    33                 had[mod1]=true;
    34                 q[J].f=I;q[J].k=1;q[J].mod=mod1;
    35                  q[J].L=L+1;
    36                  if(mod1==0)
    37                   {
    38                       gs=J;
    39                       return;
    40                   }
    41                   ++J;
    42             }
    43             if(had[mod2]==false)
    44              {
    45                  had[mod2]=true;
    46                  q[J].f=I;q[J].k=2;q[J].mod=mod2;
    47                  q[J].L=L+1;
    48                  if(mod2==0)
    49                   {
    50                       gs=J;
    51                       return;
    52                   }
    53                   ++J;
    54              }
    55              I++;
    56        }
    57   }
    58   void  print(int k)
    59    {
    60        if(q[k].L>1)
    61         print(q[k].f);
    62        cout<<q[k].k;
    63    }
    64 int main()
    65 {
    66     cin>>n;
    67     if(n==1||n==2)
    68     {
    69         cout<<n<<endl;
    70         return 0;
    71     }
    72     memset(had,false,sizeof(had));//初始化
    73     I=J=0;
    74     q[J].L=1;q[J].k=1;q[J].mod=1;++J;
    75     q[J].L=1;q[J].k=2;q[J].mod=2;++J;
    76     had[1]=had[2]=true;
    77     gs=-1;
    78     bfs();
    79     if(gs==-1)
    80      cout<<"Impossible"<<endl;
    81     else
    82     {
    83        print(gs);
    84         cout<<endl;
    85     }
    86     return 0;
    87 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3260669.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/23b274aea7d542779774b666725d38a5.png