Rephrasing the condition, feasibility check

Let \(S_x \subseteq \{1, \dots, N\}\) denote the set of cards on which the integer \(x\) (\(1 \leq x \leq K\)) is written.

For a pair of positive integers \((x, y)\) to not satisfy the condition means that every card satisfies either “both \(x\) and \(y\) are written on it” or “neither \(x\) nor \(y\) is written on it”. This is equivalent to \(S_x = S_y\).

Therefore, the condition is equivalent to \(S_1, \dots, S_K\) being pairwise distinct.

Since there are \(2^N\) possible choices for each \(S_i\), the task is possible if \(K \leq 2^N\), and impossible if \(K > 2^N\).

Minimization

Let \(c_i := |S_i|\). Then the total cost is \(\displaystyle \sum_{i=1}^{K} c_i \cdot \mathrm{digitnum}(i)\) (here, \(\mathrm{digitnum}(i)\) is the number of digits of \(i\)). Let us consider how to choose \(c_1, \dots, c_K\) to minimize this.

The value \(k\) (\(0 \leq k \leq N\)) can be used as \(c_i\) at most \(\mathrm{binom}(N, k)\) times (\(\mathrm{binom}\) denotes the binomial coefficient). Conversely, any \((c_1, \dots, c_K)\) respecting this upper bound is achievable.

In this case, it is optimal to greedily assign, in decreasing order of \(i\) (\(1 \leq i \leq K\)), the smallest not-yet-exhausted value \(k\) (\(0 \leq k \leq N\)) as \(c_i\) (a simple proof is given below).

Simple Proof

Suppose \(c_{i+1}, \dots, c_K\) have already been assigned. When assigning \(c_i\), consider adopting a larger value \(k_{sub}\) (\(k_{sub} > k_{opt}\)) instead of the smallest not-yet-exhausted value \(k_{opt}\).

• If \(k_{opt}\) is assigned to some \(c_j\) (\(j < i\)): We can swap \(c_i\) and \(c_j\). Since \(\mathrm{digitnum}(j) \leq \mathrm{digitnum}(i)\), we have \(k_{opt} \cdot \mathrm{digitnum}(j) + k_{sub} \cdot \mathrm{digitnum}(i) > k_{sub} \cdot \mathrm{digitnum}(j) + k_{opt} \cdot \mathrm{digitnum}(i)\), so the solution strictly improves.
• If \(k_{opt}\) is not assigned to any \(c_j\) (\(j < i\)): We can update \(c_i\) to \(k_{opt}\). We have \(k_{sub} \cdot \mathrm{digitnum}(i) > k_{opt} \cdot \mathrm{digitnum}(i)\), so the solution strictly improves.

Therefore, in an optimal solution, \(c_i\) adopts the smallest not-yet-exhausted value \(k\) (\(0 \leq k \leq N\)).

Sample Implementation (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
#include <string>
using std::string;
using std::to_string;
using std::min;
using std::max;

#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

typedef long long int ll;

void output (const ll x) {
	cout << x << "\n";
}

ll n, k;


void solve() {
	const auto disect = [](vector<ll> &d) -> void {
		d.clear();
		d.push_back(0);

		ll l = 1, r = 9;
		while (l <= k) {
			ll cnt = min(r, k) - l + 1;
			d.push_back(cnt);

			l = l * 10;
			r = l * 10 - 1;
		}
	};
	vector<ll> dc;
	disect(dc);

	const auto listncr = [](vector<ll> &ncr) -> ll {
		ncr.clear();

		ll curr = 1;
		ll sum = 0;
		ll r = 0;
		while (true) {
			ncr.push_back(curr);
			sum += curr;
			if (sum >= k) break;

			if (r == n) break;
			++r;
			curr *= (n+1-r);
			curr /= r;
		}
		return sum;
	};
	vector<ll> ncr;
	ll allsum = listncr(ncr);

	if (allsum < k) {
		// no
		output(-1);
		return;
	}

	// yes
	ll ans = 0;
	ll di = dc.size() - 1;
	ll dused = 0;
	ll ri = 0;
	ll rused = 0;
	while (di >= 0) {
		if (dc[di] == dused) {
			di--;
			dused = 0;
			continue;
		}
		if (ncr[ri] == rused) {
			ri++;
			rused = 0;
			continue;
		}

		ll uadd = min(dc[di] - dused, ncr[ri] - rused);
		ans += di * ri * uadd;
		dused += uadd;
		rused += uadd;
	}

	output(ans);
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int ti = 0; ti < T; ti++) {
		cin >> n >> k;

		solve();
	}
	
	return 0;
}