条件の言い換え，可能性判定

整数 \(x\) (\(1 \leq x \leq K\)) を書くカードの集合を \(S_x \subseteq \{1, \dots, N\}\) とおきます．

ある正整数組 \((x, y)\) が条件を満たさないことは，すべてのカードが「\(x\) も \(y\) も書かれている」「\(x\) も \(y\) も書かれていない」のいずれかを満たすことと言い換えられます．これは \(S_x = S_y\) と同値です．

したがって条件は，\(S_1, \dots, S_K\) が相異なることと同値です．

\(S_i\) の取り方は \(2^N\) 通りあるため，\(K \leq 2^N\) であれば可能，\(K > 2^N\) であれば不可能です．

最小化

\(c_i := |S_i|\) とおくと，総コストは \(\displaystyle \sum_{i=1}^{K} c_i \cdot \mathrm{digitnum}(i)\) です(ここで，\(\mathrm{digitnum}(i)\) は \(i\) の桁数)．これを最小化するような \(c_1, \dots, c_K\) の選び方を考えます．

\(c_i\) の値として \(k\) (\(0 \leq k \leq N\)) を使える回数は \(\mathrm{binom}(N, k)\) 回です(\(\mathrm{binom}\) は二項係数)． 逆に，この上限を守った任意の \((c_1, \dots, c_K)\) は達成可能です．

このとき，\(i\) (\(1 \leq i \leq K\)) の大きいほうから順に，使い切っていない最小の \(k\) (\(0 \leq k \leq N\)) を貪欲に \(c_i\) として割り当てるのが最適です(以下に簡易的な証明を載せます)．

簡易的な証明

\(c_{i+1}, \dots, c_K\) は既に割り当て済みとする．\(c_i\) を割り当てるとき，使い切っていない最小の値 \(k_{opt}\) の代わりにより大きい値 \(k_{sub}\) (\(k_{sub} > k_{opt}\)) を採用したときを考える．

• \(k_{opt}\) をある \(c_j\) (\(j < i\)) に割り当てる場合：　\(c_i, c_j\) を交換することができる．\(\mathrm{digitnum}(j) \leq \mathrm{digitnum}(i)\) より \(k_{opt} \cdot \mathrm{digitnum}(j) + k_{sub} \cdot \mathrm{digitnum}(i) > k_{sub} \cdot \mathrm{digitnum}(j) + k_{opt} \cdot \mathrm{digitnum}(i)\) なので，解は真に改善される．
• \(k_{opt}\) をどの \(c_j\) (\(j < i\)) にも割り当てない場合：　\(c_i\) を \(k_{opt}\) に更新することができる．\(k_{sub} \cdot \mathrm{digitnum}(i) > k_{opt} \cdot \mathrm{digitnum}(i)\) なので，解は真に改善される．

したがって最適解において，\(c_i\) には使い切っていない最小の \(k\) (\(0 \leq k \leq N\)) を採用している．

実装例 (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;
}