Codeforces Round 697 (Div.3)
Updated:
A. Odd Divisor
정수 $n$이 주어질 때 홀수인 수 $x$로 나누어 떨어지는지 확인하는 문제이다.
먼저, $n$이 홀수일 때 홀수인 수 $x$로 반드시 나누어 떨어진다.
다음, $n$이 짝수일 때 $n$을 만드는 방법은 세 가지가 있다.
- 짝수 * 짝수 = 짝수
- 짝수 * 홀수 = 짝수
- 홀수 * 짝수 = 짝수
$n$을 짝수로 이루어진 수를 제외하면 모두 홀수 $x$를 가지고 있다는 이야기이다. 그리고 소수인 짝수는 2가 유일하기 때문에 $n$을 2로 계속 나누다 마지막에 1이 남았을 때 $n$이 2의 제곱수의 형태를 갖는다는 것을 알 수 있다.
- 만약, $n$ & $(n-1)$이 0이 아니라면 n은 홀수인 $x$를 가지고 있다.
- $n$ & $(n-1)$이 0이라면 2로 이루어진 제곱수의 형태를 가지고 있어서 $x$가 없다.
예를들면, $n$이 6이라면 이진수로 110과 101을 AND연산했을 때 100 = 4가 출력되면서 홀수가 존재하는 것을 알 수 있다.
반면에, $n$이 4라면 이진수로 100과 011을 AND연산했을 때 0이 출력되면서 홀수가 존재하지 않음을 알 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll n;
cin >> n;
if (n & (n - 1)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. New Year’s Number
정수 $n$이 주어질 때 2020과 2021의 합으로 이루어졌는지 확인하는 문제이다.
$x$를 2020의 개수, $y$를 2021의 개수라 가정하면 $n=2020\times x + 2021\times y$가 성립되어야 한다.
위의 식을 다시 정리하면 $n=2020(x+y)+y$이며, $n-y$는 $2020$으로 나누어 떨어져야 한다. 즉, 다음의 식이 성립되어야 한다.
$x=\frac{n-y}{2020}-y$
만약, $x$가 0보다 크거나 같다면 $n$은 2020과 2021로 표현될 수 있다.
#include <bits/stdc++.h>
#include <utility>
using namespace std;
using pii = pair<int, int>;
void solve() {
int n;
cin>>n;
int cnt2021 = n%2020;
int cnt2020 = (n-cnt2021)/2020 - cnt2021;
if(cnt2020>=0 && 2020*cnt2020 + 2021 * cnt2021 == n) {
cout<<"YES\n";
}
else {
cout<<"NO\n";
}
}
int main() {
int t;
cin >> t;
while(t--) {
solve();
}
return 0;
}
C. Ball in Berland
주어지는 준비된 페어 ($a,b$)에 대해 가능한 순서쌍을 구하는 문제이다.
먼저, boys와 girls를 그래프의 정점이라 생각하면 우리는 ($a,b$)에 대해 이분그래프라 생각할 수 있다. 그리고 ($a,b$)는 $a$와 $b$에 edge(간선)가 생긴 것이라 하자.
그러면 우리는 이 그래프에서 두 간선를 찾는데 서로 교차하지 않는 간선들을 찾아야 한다.
이제 $deg(x)$를 정점 $x$가 포함된 간선의 개수라 하자.
어떠한 간선을 연결하는 두 정점을 $a,b$가 있을 때 $a,b$를 연결하는 간선과 교차하지 않은 간선의 개수는 $k-deg(a)-deg(b)+1$이다. (집합의 개념)
- +1을 하는 이유는 $deg(a)$와 $deg(b)$에 ($a,$$b$)를 연결하는 간선이 두 번 중복되기 때문이다.
따라서 모든 간선에 대해 전부 더해주고 두 번더해지므로 마지막에 2를 나누면 된다.
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
void solve() {
int A, B, k;
cin >> A >> B >> k;
vector<int> a(A+1), b(B+1);
vector<pair<int, int> > edges(k);
for(int i=0;i<k;i++) cin>>edges[i].first;
for(int i=0;i<k;i++) cin>>edges[i].second;
for (int i=0;i<k;i++) {
int x=edges[i].first;
int y=edges[i].second;
a[x]++;
b[y]++;
}
ll ans = 0;
for (int i=0;i<k;i++) {
int x=edges[i].first;
int y=edges[i].second;
ans += k - a[x] - b[y] + 1;
}
cout << ans / 2 << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Cleaning the Phone
필요한 메모리를 확보하면서 가장 적은 convience points를 잃어야 하는 문제이다.
convience points는 2가지이며 $b_i=1$ 또는 $b_i=2$이다. 우리는 1과 2에 해당하는 app을 따로 저장해야 한다.
- $b_i=1$인 app의 메모리는
vector<int> a에, $b_i=2$인 app의 메모리는vector<int> b에 저장하도록 한다. - 다음
a,b모두 내림차순으로 정렬한다.
a에서 먼저 필요한 app을 합친 후 나머지를 b에서 가져오면서 필요한 메모리 m을 확보할 수 있는지 확인한다.
- 먼저, $b$의 메모리 총합을 시작으로 $a_i$를 하나씩 추가하면서 필요한 메모리 한해서 필요없는 $b_i$를 빼준다.
```cpp
#include
#include #include #include // accumulate함수 헤더 #define ll long long #define INF 987654321 using namespace std;
void solve() {
int n, m;
cin»n»m;
vector
// a, b 내림차순 정렬 sort(a.rbegin(),a.rend()); sort(b.rbegin(),b.rend());
ll curSumA=0; int r=b.size(); ll curSumB=accumulate(b.begin(),b.end(),0ll); // b의 메모리 총합 int ans=INF; for(int l=0;l<=a.size();l++) { // a를 하나 늘려주면 while(r>0 && (curSumA+curSumB-b[r-1] >= m)) { // m을 지키는 한에서 b에서 하나 뺄 수있다. r–; curSumB-=b[r]; }
if(curSumB+curSumA >= m) {
ans=min(ans,2*r+l);
}
if(l!=a.size()) {
curSumA+=a[l];
} }
cout«(ans==INF ? -1 : ans)«endl; }
int main() { freopen(“input.txt”,”r”,stdin); int t; cin » t; while (t–) { solve(); } return 0; } ```
Comments