Facebook
From emanlaicepsa, 1 Month ago, written in C++.
Embed
Download Paste or View Raw
Hits: 29
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. array<int,4> ans;
  5. int rem[10][150005];
  6. int lmp[10][100005], rmp[10][100005];
  7. bool operator<(array<int,4> a, array<int,4> b){
  8.         if(b[0] == 0) return true;
  9.         assert(a[0] + a[2] == b[0] + b[2]);
  10.         if(a[1] != b[1]) return a[1] < b[1];
  11.         if(b[0] > a[0]) return a[3] < b[1];
  12.         else if(a[0] > b[0])return a[1] < b[3];
  13.         else return a[3] < b[3];
  14. }
  15.  
  16. int toint(array<int,4> ar){
  17.         if(ar[0]+ar[2] > 6) return -1;
  18.         int ans = 0;
  19.         for(int i=0;i<ar[0];i++) ans = ans*10+ar[1];
  20.         for(int i=0;i<ar[2];i++) ans = ans*10+ar[3];
  21.         return ans;
  22. }
  23.  
  24. void solve(){
  25.         ans = {0, 0, 0, 0};
  26.         memset(lmp, 0, sizeof(lmp));
  27.         memset(rmp, 0x3f, sizeof(rmp));
  28.         for(int i=1;i<=9;i++){
  29.                 for(int j=1;j<=150000;j++){
  30.                         rem[i][j] = (rem[i][j-1] * 10 + i) % n;
  31.                 }
  32.         }
  33.         for(int i=1;i<=9;i++) lmp[i][rem[i][1]] = rmp[i][rem[i][1]] = 1;
  34.         for(int dig=2;dig<=100005;dig++){
  35.                 for(int i=1;i<=9;i++){
  36.                         int re = rem[i][dig];
  37.                         for(int j=1;j<=i;j++){
  38.                                 if(lmp[j][re] > 0){
  39.                                         array<int, 4> ar = {dig - lmp[j][re], i, lmp[j][re],i-j};
  40.                                         if(toint(ar) != n && (ans[0] == 0 || ar < ans)) ans = ar;
  41.                                 }
  42.                         }
  43.                         re = (n - re) % n;
  44.                         for(int j=1;i+j<10;j++){
  45.                                 if(rmp[j][re] < dig){
  46.                                         array<int, 4> ar = {dig - rmp[j][re], i, rmp[j][re],i+j};
  47.                                         if(toint(ar) != n && (ans[0] == 0 || ar < ans)) ans = ar;
  48.                                 }
  49.                         }
  50.                 }
  51.                 if(ans[0] != 0){
  52.                         cout<<n<<": "<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<'\n';
  53.                         return;
  54.                 }
  55.                 for(int i=1;i<=9;i++){
  56.                         lmp[i][rem[i][dig]] = max(lmp[i][rem[i][dig]], dig);
  57.                         rmp[i][rem[i][dig]] = min(rmp[i][rem[i][dig]], dig);
  58.                 }
  59.         }
  60. }
  61.  
  62. int main(){
  63.         ios::sync_with_stdio(0), cin.tie(0);
  64.         while(cin>>n){
  65.                 if(n==0) break;
  66.                 solve();
  67.         }
  68. }
  69.