Codeforces Round 858 (Div. 2)
A. Walking Master (800)
일단 $d<b$ 라면 $y$가 작아지는 방향으로 갈 수 없어서 불가능하다.
그렇지 않다면 $d-b$ 만큼 이동시킨다음, 왼쪽으로 가야 할 만큼 간다.
$d-b$ 만큼 $(x+1, y+1)$ 연산을 한다음에 $a<c$ 라면 $a$는 오른쪽으로 더 이동할 수 없으므로 불가능하고 아니라면 그만큼 정답에 더 더해준다.
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (d < b) {
cout << -1 << endl;
return;
}
int ans = d - b;
a += d - b;
b = d;
if (a < c) {
cout << -1 << endl;
return;
}
ans += a - c;
cout << ans << endl;
}
B. Mex Master (900)
0이 너무 많아서 0을 인접하게 두는 경우만 제외하면 항상 답은 0이다.
인접하게 두는 경우는 0 x 0 x 0 … x 0 0 같이 사이사이에 다른 수들을 끼워넣어도 0이 남는 경우이다.
즉, 0의 개수를 $Z$라고 하면, $Z>N-Z+1$ 인 경우이다.
주의할 점은 위 경우에 해당하고 0과 1밖에 없다면, 어느 곳에서는 0과 1이 인접하고 0과 0이 인접하는 곳이 항상 등장하므로 $MEX=2$ 가 되어야 한다는 점이다.
세 가지 경우만 따져주면 된다.
void solve() {
int n;
cin >> n;
vi a(n);
fv(a);
int zero = cntt(a, 0);
int other = n - zero;
if (zero == n) {
cout << 1 << endl;
return;
}
int one = cntt(a, 1);
if (zero >= other + 2) {
if (zero + one == n) cout << 2 << endl;
else cout << 1 << endl;
} else cout << 0 << endl;
}
C. Sequence Master (1600)
모든 숫자가 같은 경우에는 $nk=n^k$ 여야 하고, 이는 $n=0$ or $k=1$ or $n=2,\,k=2$ 인 경우밖에 없다.
이 경우는 따로 처리해준다.
모든 숫자가 같지 않다고 하면, $k, m$ 이 $q$ 안에 존재하고,
$\begin{aligned} k \cdot q_3q_4 \cdots q_{n+1}=m+q_{n+2}+\cdots+q_{2n}&~~~~(1)\\ \underline{m \cdot q_3q_4 \cdots q_{n+1}=k+q_{n+2}+\cdots+q_{2n}}\\ (k-m)(q_3q_4 \cdots q_{n+1}+1)=0 \end{aligned}$ $k \ne m$ 이므로 $q_3q_4 \cdots q_{n+1}=-1$ 이여야 하고, 어떠한 $k, m$ 에 대해서도 만족시켜야 하므로 두 수를 제외하고는 모두 $-1$이 되어야 한다.
$q_3=q_4=\cdots=q_{n+1}$ 이고 $q_3^{n-1}=-1$ 이므로 $n$ 은 짝수여야 한다.
$(1)$에서 $k \cdot -1=m-(n-1)$ 이고 $m+k=n-1$ 이다.
또한, $mkq_3 \cdots q_n=q_{n+1} + \cdots + q_{2n}=-n$ 이므로
이를 만족하는 $m, k$의 해는 $n$과 $-1$이다.
void solve() {
int n;
cin >> n;
vi p(n * 2);
fv(p);
sort(all(p));
if (n == 1) {
cout << abs(p[0] - p[1]) << endl;
} else if (n % 2 == 1) {
int ans = 0;
for (int i: p) ans += abs(i);
cout << ans << endl;
} else {
int ans = 2e17;
int ans1 = 0;
for (int i: p) ans1 += abs(i);
ans = ans1;
if (n == 2) {
ans1 = 0;
for (int i: p) ans1 += abs(i - 2);
ans = min(ans, ans1);
}
ans1 = 0;
for (int i = 0; i < n * 2 - 1; i++) ans1 += abs(p[i] + 1);
ans1 += abs(n - p.back());
ans = min(ans, ans1);
cout << ans << endl;
}
}
Comments