subject

Nearest Beautiful Number (easy version)

Problem Description

Given Data n ( 1 ≤ n ≤ 1 0 9 ) n(1\leq n\leq10^9) n(1 < n < 109) and k ( k ≤ 2 ) k(k\leq2) k(k≤2)
x x x By k k k digits, output satisfies x ≥ n x\geq n Closest in x < n n n n's x x x.

Example: n = 177890 , k = 2 n=177890,k=2 n=177890,k=2
output x = 181111 x=181111 x=181111

Analysis

Idea one (enumeration then dichotomy)

Due to the extent of the data, there is a clever way to store the K1 data in set1, which is nine. set2 contains data of k2, which can be enumerated in turn through a loop.
After entering n and k at the end, you only need to find the first number greater than or equal to n in the corresponding set with the function dichotomy, which is the x that satisfies the condition.

Idea 2 (cyclic simulation)

When k equals 1, you only need to enumerate the strings from large to small, and output the first string greater than or equal to n. The rules for string comparison after converting to string are consistent with the rules for size comparison of numbers.
And there is a rule: the first t bit in n is taken out, and the first t bit in x still satisfies the condition.

When k equals 2, the first qualified x can be found by simulation because the data is small:

given a a a heel b b b, satisfy a < b a<b A <b, assume first that you can a , b a,b a,b constructs the x that meets the criteria, and in order to find the first, a , b a,b The enumeration of a and B is from small to large, so the next goal is to find the first satisfaction x > = n x>=n X>=n and only needs two numbers x x x.

for(char a = '0'; a <= '8'; a++)
		for (char b = a + 1; b <= '9'; b++)
		{
		//......
		}

Determined a , b a,b a,b, to see if it can be a , b a,b a,b constructs the x that meets the criteria, and the next loop begins with the first position of n and ends with it.

Processing i i For i-bit data, we guarantee that a a a， b b b Built by x x Before x i − 1 i-1 i_1-bit data greater than or equal to n n Before n i − 1 i-1 i_1-bit data,

If i i Bit i greater than a a a heel b b b, explain that this combination is unreasonable, quit and test the next group a , b a,b a,b；

If i i Bit i is less than or equal to b b b, indicating that this bit can be used a , b a,b a,b instead, because a a a Smaller, in order to meet the nearest minimum required by the title, we give priority to the test a a a, if greater than a a a, select again b b b, at this time by a a a， b b b Built by x x Before x i i i-bit data greater than or equal to n n Before n i i i-bit data, test again i + 1 i+1 i+1 bit

When we found a group a , b a,b a,b can completely indicate that each meets a condition x x x, this x x x is our answer and we can return the result.

Code

#include <bits/stdc++.h>

using namespace std;

string solve1(string n)
{
	string res(n.length(), '9');
	for (char c = '8'; c >= '0'; c--)
	{
		string t(n.length(), c);
		if (t >= n)
			res = t;
	}

	return res;
}

string solve2(string n)
{
	string res(n.length(), '9');

	for(char a = '0'; a <= '8'; a++)
		for (char b = a + 1; b <= '9'; b++)
		{
			bool n_ok = true;
			for (int i = 0; i < n.length(); i++)
			{
				if (n[i] < b)
				{
					string t = n;
					if (t[i] < a) t[i] = a;
					else t[i] = b;
					for (int j = i + 1; j < n.length(); j++)
						t[j] = a;
					if (res > t)
						res = t;
				}

				if(n[i] != a && n[i] != b)
				{
					n_ok = false;
					break;
				}
			}

			if (n_ok) return n;
		}

	return res;
}

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	if (k == 1) return solve1(n);
	else return solve2(n);
}

int main()
{
	int t;
	cin >> t;

	while (t--)
		cout << solve() << '\n';

	return 0;
}