D. Three Integers

You are given three integers abca≤b≤c .

In one move, you can add +1+1 or 1−1 to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.

You have to perform the minimum number of such operations in order to obtain three integers ABCA≤B≤C such that BB is divisible by AA and CC is divisible by BB .

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1t1001≤t≤100 ) — the number of test cases.

The next tt lines describe test cases. Each test case is given on a separate line as three space-separated integers a,ba,b and cc (1abc1041≤a≤b≤c≤104 ).

Output

For each test case, print the answer. In the first line print resres — the minimum number of operations you have to perform to obtain three integers ABCA≤B≤C such that BB is divisible by AA and CC is divisible by BB . On the second line print any suitable triple A,BA,B and CC .

Example
Input

Copy
8
1 2 3
123 321 456
5 10 15
15 18 21
100 100 101
1 22 29
3 19 38
6 30 46
Output

Copy
1
1 1 3
102
114 228 456
4
4 8 16
6
18 18 18
1
100 100 100
7
1 22 22
2
1 19 38
8
6 24 48

题解:
Tutorial

Let's iterate over all possible values of AA from 11 to 2a2a. It is obvious that AA cannot be bigger than 2a2a, else we can just move aa to 11. Then let's iterate over all possible multiples of AA from 11 to 2b2b. Let this number be BB. Then we can find CC as the nearest number to cc that is divisible by BB (we can check two nearest numbers to be sure). These numbers are C=cBBC=⌊cB⌋⋅B and C=cBB+BC=⌊cB⌋⋅B+B. Then we can update the answer with the found triple. Note that the only condition you need to check is that BCB≤C.

Time complexity: O(nlogn)O(nlog⁡n) because of the sum of the harmonic series.

 

  Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        int ans = 1e9;
        int A = -1, B = -1, C = -1;

        //重点
for (int cA = 1; cA <= 2 * a; ++cA) { for (int cB = cA; cB <= 2 * b; cB += cA) { for (int i = 0; i < 2; ++i) { int cC = cB * (c / cB) + i * cB; int res = abs(cA - a) + abs(cB - b) + abs(cC - c); if (ans > res) { ans = res; A = cA; B = cB; C = cC; } } } } cout << ans << endl << A << " " << B << " " << C << endl; } return 0; }

//转载于http://codeforces.com/blog/entry/74224

原文链接: https://www.cnblogs.com/lijiahui-123/p/12447029.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    D. Three Integers

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/372096

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月3日 上午11:04
下一篇 2023年3月3日 上午11:06

相关推荐