nikkei2019_2_qual_e Non-triangular Triplets

nikkei2019_2_qual_e Non-triangular Triplets

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_e

给出 (N) 和 (K) .

判断对于这 (3N) 个数 (K,K+1,cdots,K+3N-1) .是否存在一种将它们分为 (N) 个三元组 ((a_i,b_i,c_i)) 的方案,且满足每个数恰好出现一次,且

[a_i + b_i le c_i ]

判断是否存在方案,若不存在,输出 (-1) .否则输出一组方案

(1 le N le 10^5)

(1 le K le 10^9)

Tutorial

假设存在方案,那么满足

[sum (a_i+b_i) le sum c_i \ sum(a_i+b_i+c_i) le 2sum c_i \ sum_{i=K}^{K+3N-1} i le 2sum c_i le 2sum_{i=K+2N}^{K+3N-1} i \ (K+K+3N-1)(3N) le (K+2N+K+3N-1)(2N) \ N ge 2K-1 ]

那么当 (N<2K-1) 时则无解,否则考虑构造方案.

当 (N) 为奇数时,设 (N=2L-1) 则有 (K le L) ,那么

[(a_1,a_2,cdots,a_N)=(K,K+2,K+4,cdots,K+2L-2,K+1,K+3,cdots,K+2L-3) \ (b_1,b_2,cdots,b_N)=(K+3L-2,K+3L-3,cdots,K+2L-1,K+4L-3,K+4L-4,cdots,K+3L-1) \ (c_1,c_2,cdots,c_N)=(K+4L-2,cdots,K+6L-4) ]

主要思想为将 ((a,b)) 以 ((x+y),(x+2,y-1),cdots) 的顺序安排以达到每次和增加 (1) 的效果.

(N) 为偶数时类似的构造即可.

Code

#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr, __VA_ARGS)
using namespace std;
const int maxn = 1e5 + 50;
int N, K;
int a[maxn], b[maxn], c[maxn];
bool sol()
{
	if (N < (K << 1) - 1) return 0;
	if (N & 1)
	{
		int L = (N + 1) >> 1;
		int cnt = 0;
		for (int i = K; i <= K + 2 * L - 2; i += 2) 
			a[++cnt] = i;
		for (int i = K + 1; i <= K + 2 * L - 3; i += 2)
			a[++cnt] = i;
		cnt = 0;
		for (int i = K + 3 * L - 2; i >= K + 2 * L - 1; --i)
			b[++cnt] = i;
		for (int i = K + 4 * L - 3; i >= K + 3 * L - 1; --i)
			b[++cnt] = i;
		cnt = 0;
		for (int i = K + 4 * L - 2; i <= K + 6 * L - 4; ++i)
			c[++cnt] = i;
	}
	else
	{
		int L = N >> 1;
		int cnt = 0;
		for (int i = K; i <= K + 2 * L - 2; i += 2)
			a[++cnt] = i;
		for (int i = K + 1; i <= K + 2 * L - 1; i += 2)
			a[++cnt] = i;
		cnt = 0;
		for (int i = K + 3 * L - 1; i >= K + 2 * L; --i)
			b[++cnt] = i;
		for (int i = K + 4 * L - 1; i >= K + 3 * L; --i)
			b[++cnt] = i;
		cnt = 0;
		for (int i = K + 4 * L; i <= K + 6 * L; ++i)
			c[++cnt] = i;
	}
	for (int i = 1; i <= N; ++i)
		printf("%d %d %d
", a[i], b[i], c[i]);
	return 1;
}
int main()
{
	scanf("%d%d", &N, &K);
	if (!sol())
		puts("-1");
	return 0;
}