Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define loop(i,b,e) for(int i=b;i<=e;i++)
  4. #define loop2(i,e,b) for(int i=e;i>=b;i--)
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7.  
  8. int n;
  9. int ans = 1e6;
  10. int m[5][5];
  11.  
  12. void solve(int x,int y,int curr) {
  13.     if (ans == n)
  14.         return;
  15.     if (abs(curr - n) < abs(ans - n) || curr==n)
  16.         ans = curr;
  17.     if (x>=4 || y>=3 || (x==3 && y==0) || (x == 3 && y == 2))
  18.         return;
  19.     solve(x + 1, y, curr);
  20.     solve(x, y + 1, curr);
  21.     int prev = 1e9;
  22.     int prev2 = abs(curr - n);
  23.     while(curr<n && prev!=prev2){
  24.         prev = prev2;
  25.         curr = (curr * 10) + m[x][y];
  26.         solve(x + 1, y, curr);
  27.         solve(x, y + 1, curr);
  28.         prev2 = abs(curr - n);
  29.     }
  30. }
  31.  
  32. int main() {
  33.     scanf("%d",&n);
  34.     int c = 1;
  35.     loop(i, 0, 3)
  36.         loop(j, 0, 2) {
  37.         m[i][j] = c;
  38.         c++;
  39.     }
  40.     m[3][0] = 1e6;
  41.     m[3][1] = 0;
  42.     m[3][2] = 1e6;
  43.     solve(0,0,0);
  44.     printf("%d",ans);
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement