Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 KB | None | 0 0
  1. /* #################### */
  2. /* # I_LOVE_THUY_LINH # */
  3. /* #################### */
  4. #include <bits/stdc++.h>
  5. #define ll long long
  6. #define db double
  7. #define ld long double
  8. #define ii pair<int,int>
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define vi vector<int>
  12. #define vii vector<ii>
  13. #define matrix vector<vector<ll>>
  14. #define fir first
  15. #define sec second
  16. #define all(s) s.begin(),s.end()
  17. #define rall(s) s.rbegin(),s.rend()
  18. #define uni(a) (a).erase(unique(all(a)),(a).end())
  19. #define sz(a) int((a).size())
  20. #define ms(s,val) memset(s,val,sizeof(s))
  21. #define bitcount(n) __builtin_popcountll(n)
  22. #define getbit(s,k) ((s >> k)&1)
  23. #define turnbit(s,k) (s | (1<<k))
  24. #define offbit(s,k) (s & ~(1<<k))
  25. #define flipbit(s,k) (s ^ (1<<k))
  26. #define prec(n) fixed<<setprecision(n)
  27. #define sqr(x) (ll)(x)*(ll)(x)
  28. #define lcm(a,b) ((ll)a/__gcd((ll)a,(ll)b)*(ll)(b))
  29. #define gcd(a,b) __gcd(a,b)
  30. using namespace std;
  31. const int INF = int(1e9);
  32.  
  33. void solve(){
  34. int a, b , c;
  35. cin >> a >> b >> c;
  36.  
  37. vector<vector<int>> dp(20001,vector<int> (3,INF));
  38. for (int i = 1; i <= 20000; i++){
  39. dp[i][0] = abs(i - a);
  40. for (int j = i ; j <= 20000; j+= i){
  41. dp[j][1] = min(dp[j][1],dp[i][0] + abs(j - b));
  42. dp[j][2] = min(dp[j][2],dp[i][1] + abs(j - c));
  43. }
  44. }
  45. int C = 20000;
  46. for (int i = 1; i <= 20000; i++)
  47. if (dp[i][2] < dp[C][2]) C = i;
  48.  
  49. int B;
  50. for (int i = 1; i <= 20000; i++)
  51. if ((C % i == 0) && dp[i][1] + abs(C - c)== dp[C][2]){
  52. B = i;
  53. break;
  54. }
  55. int A;
  56. for (int i = 1; i <= 20000; i++)
  57. if ((B % i == 0) && dp[i][0] + abs(B - b)== dp[B][1]){
  58. A = i;
  59. break;
  60. }
  61. cout << dp[C][2] << '\n';
  62. cout << A << ' ' << B << ' ' << C << '\n';
  63.  
  64.  
  65. }
  66.  
  67. int main(){
  68. ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  69. int t;
  70. cin >> t;
  71. while (t--) solve();
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement