Educational Codeforces Round 100(Div. 2) A~D
A. Dungeon
3마리의 몬스터가 나타났다. 우리는 3마리 중 1마리의 몬스터에게 한 번 공격하여 1의 데미지를 가할 수 있고 이 공격을 이용해 모든 몬스터를 물리쳐야 한다. 다만 7의 배수 번째 공격을 할 때는 3마리 모두에게 공격이 들어간다. (이를 enhanced shot이라 한다)
우리는 모든 몬스터를 물리칠 때 enhanced shot으로 한번에 3마리의 몬스터를 동시에 죽이게 하고 싶다. 이게 가능한지를 판별하면 된다. 쉽지만 은근히 헷갈리는 문제다. 문제의 조건이 충족될 조건을 찾아보자. enhanced shot까지 포함된 7번의 공격으로 나오는 데미지가 9이므로 모든 몬스터의 피통의 합이 9의 배수여야 한다. 그리고 필요한 공격/9의 횟수가 어떤 몬스터의 피통보다 크면 안 된다. 만약 그렇게 되면 마지막 공격 전에 한 마리 이상의 몬스터가 피가 0이 되기 때문이다. 그걸 고려해서 코드를 짜 주면된다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
ll a, b, c;
cin >> a >> b >> c;
int ans = 1;
if ((a + b + c) % 9 != 0) { ans = 0; }
int d = (a + b + c) / 9;
if (a < d || b < d || c < d) { ans = 0; }
cout << (ans ? "YES\n" : "NO\n");
}
return 0;
}
B. Find the Array
문제의 조건을 만족하는 수열을 만들면 되는데, 생각해 보면 수열의 홀수혹은 짝수 번째를 모두 1로 바꿔 놓으면 조건을 만족하는 수열이 만들어짐을 알 수 있다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
ll n, arr[55], b1[55], b2[55];
ll s = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 0; i < n; i++) {
s += arr[i];
}
for (int i = 0; i < n; i++) {
if (i % 2 == 0) { b1[i] = 1; }
else { b1[i] = arr[i]; }
}
for (int i = 0; i < n; i++) {
if (i % 2 == 1) { b2[i] = 1; }
else { b2[i] = arr[i]; }
}
ll sub1=0, sub2=0;
for (int i = 0; i < n; i++) {
sub1 += abs(arr[i] - b1[i]);
sub2 += abs(arr[i] - b2[i]);
}
if (2 * sub1 <= s) {
for (int i = 0; i < n; i++) {
cout << b1[i] << " ";
}cout << "\n";
}
else {
for (int i = 0; i < n; i++) {
cout << b2[i] << " ";
}cout << "\n";
}
}
return 0;
}
C. Busy Robot
https://codeforces.com/contest/1463/problem/C
며칠 내로 추가 예정
D. Pairs
1, 2, ...2n의 정수 2n개가 있다. 이 정수들을 2개씩 묶어서 n개의 쌍들으 만든다. 그리고 거기서 x개의 쌍을 골라서 둘 중 작은 원소를, 나머지 n-x개의 쌍에서는 둘 중 큰 원소를 고른다. 우리의 목표는 그 원소들을 이용해서 특정한 수열 {b1, b2, —, bn}을 만드는 것이다. 이때 그 수열을 만들기 위해 x개의 쌍을 고를 때, 우리가 목표로 하는 수열을 만들 수 있다는 조건을 충족시키는 x는 여러 가지가 있을 수 있다. (숫자쌍은 마음대로 짝지을 수 있다고 한다) 이때 그 가능한 x가 몇 가지인지 구하는 문제다.
2n개의 숫자 중에 n개가 주어져 있고, 나머지 n개를 잘 분배해서 쌍 내에서 max나 min이 되도록 하면 된다. 그러면 최대한, min값을 고르는 쌍이 많아지도록 해보자. 먼저 수열에 쓰인 숫자들을 B 라고 하고 안 쓰인 걸 A라고 하자. 그러면 A를 B와 잘 짝지어서 min이 가장 많이 쓰이도록 A를 재배열해야 한다. 그럼 B가 큰 것부터 보면서, A에서 가장 큰 숫자와 매칭했을 때 B<A이면 그 쌍에서는 min을 쓸 수 있으므로 그대로 매칭한다. 그런데 그게 불가능하면 A에서 가장 작은 숫자 하나를 소모해 준다. 즉 A쪽의 숫자가 더 큰 쌍을 최대한 많이 만드는 방향으로 가는 것이다. 그때의 x를 구할 수 있다. 마찬가지로, max를 가장 많이 쓰는 경우의 x도 구할 수 있다. 그 사이 숫자들의 수가 가능한 모든 x의 종류이다. 그대로 코드로 옮기면 다음과 같다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
int n, check[400005] = { 0 };
cin >> n;
vector<int> A(n), B;
for (int &a : A) {
cin >> a;
a--;
check[a] = 1; //수열 만드는데 쓰인건 체크해준다
}
for (int i = 0; i < 2 * n; i++) {
if (!check[i]) { B.push_back(i); }
//수열만드는 데 안 쓰인 것들을 저장
}
int minx = 0, maxx = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (A[i] < B[maxx]) { maxx--; }
}
maxx = n - 1 - maxx;
for (int i = 0; i < n; i++) {
if (A[i] > B[minx]) { minx++; }
}
minx = n - minx;
cout << maxx - minx + 1 << "\n";
}
return 0;
}