Codeforces Round #624 (Div. 3) D.Three Integers

本文介绍了一种算法，用于在给定三个整数a、b、c（a≤b≤c）的情况下，通过增加或减少1的操作，使这三个数满足特定条件：中间的数B能被最小的数A整除，最大的数C能被B整除。文章提供了一个暴力求解的AC代码示例，并详细展示了如何在限定的时间和内存内，找到满足条件的最小操作次数及对应的A、B、C值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Three Integers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given three integers a≤b≤ca≤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 A≤B≤CA≤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 (1≤t≤1001≤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 (1≤a≤b≤c≤1041≤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 A≤B≤CA≤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

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

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

woc,想了半天没想出来，md竟然是暴力，ac代码的复杂度我他妈怎么觉得铁超时啊....

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
ll t;
int main()
{
	cin>>t;
    for(rg i=1;i<=t;i++)
    {
        ll a,b,c,ans=inf,ansa,ansb,ansc;
        cin>>a>>b>>c;
        for(rg j=1;j<=20000;j++)
        {
            for(rg k=1;j*k<=20000;k++)
            {
                for(rg h=1;j*k*h<=20000;h++)
                {
                    if(ans>abs(j-a)+abs(j*k-b)+abs(j*k*h-c))
                    {
                        ans=abs(j-a)+abs(j*k-b)+abs(j*k*h-c);
                        ansa=j,ansb=j*k,ansc=j*k*h;
                    }
                }
            }
        }
        cout<<ans<<endl<<ansa<<" "<<ansb<<" "<<ansc<<endl;
    }
    //while(1)getchar();
    return 0;
    
}