A. Stone Game
https://codeforces.com/contest/1538/problem/A
Problem - A - Codeforces
codeforces.com
관심있게 봐야하는건 1과 n의 위치이다.
부수는 방법은 세가지
1) 왼쪽부터 가장 먼 1 또는 n까지
2) 오른쪽부터 가장 먼 1 또는 n까지
3) 왼쪽부터 제일 가까운 1 또는 n까지 + 오른쪽부터 제일 가까운 1 또는 n까지
위 세 가지 중 하나가 답이 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int a[101] = { 0, };
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int MAX = -1, MIN = 101;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 1) MIN = i;
else if (a[i] == n) MAX = i;
}
if (MIN > MAX) swap(MIN, MAX);
cout << min({MAX, (n - MIN + 1), MIN + (n - MAX + 1)}) << '\n';
}
return 0;
}
B. Friends and Candies
https://codeforces.com/contest/1538/problem/B
Problem - B - Codeforces
codeforces.com
캔디를 정확하게 나눠야 하므로 캔디의 합이 n으로 나누어 떨어지는지 확인해준다.
나누어 떨어진다면 평균보다 높은 것의 개수만 세주면 된다.
시간 복잡도는 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int a[200001] = { 0, };
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int ans = n;
ll sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
if (sum % n != 0) {
cout << -1 << '\n';
continue;
}
for(int i = 0 ; i < n; i++) if(a[i] <= sum / n) ans--; // n에서 평균보다 작거나 같은 것을 빼준다
cout << ans << '\n';
}
return 0;
}
C. Number of Pairs
https://codeforces.com/contest/1538/problem/C
Problem - C - Codeforces
codeforces.com
시간 복잡도가 \(O(n^2)\)이면 TLE에 걸리게 된다.
시간 복잡도를 줄이기 위해 이분 탐색을 사용한다. 이분 탐색을 위해 배열을 sort해준 후, lower_bound와 upper_bound를 이용해 답을 구해주었다.
찾아야하는 조건을 \(a[i]\)를 기준으로 바꿔보면 \(a[j]\)는 \(l - a[i] <= a[j] <= r - a[i]\)를 만족시키는 \(a[j]\)를 찾아주면된다.
따라서 \(i < j\)임을 고려했을 때, \(a[i + 1], a[i+2], ... , a[n]\) 중 에서 \(l - a[i] <= a[j] <= r - a[i]\)를 만족시키는 가장 작은 인덱스를 lower_bound를 통해 구해주고(= low), upper_bound를 통해 \(r - a[i]\)를 초과하는 수 중 가장 작은 인덱스(=high)를 구해주자.
결국 답은 \(i, low <= j < high)\)를 만족시켜야 하기 때문에 모든 \(i\)에 대해서 (high - low)구해서 합해주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll num[200001] = { 0, };
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll n, l, r;
ll ans = 0;
cin >> n >> l >> r;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n);
for (int i = 0; num[i] < r && i < n; i++) {
int low = lower_bound(num + i + 1, num + n, max(0LL, l - num[i])) - num;
int high = upper_bound(num + i + 1, num + n, r - num[i]) - num;
ans += (high * 1LL - low);
}
cout << ans << '\n';
}
return 0;
}
D. Another Problem About Dividing Numbers
https://codeforces.com/contest/1538/problem/D
Problem - D - Codeforces
codeforces.com
두 수 \(a, b\)를 소인수분해하여 몇 개의 소수로 이루어져 있는지 확인하는게 키워드다.
\(k\)가 소수의 개수 합보다 작거나 같으면 항상 k번 만에 두 수를 같게 만들 수 있다.
단, \(k\)가 1일 때는 예외적으로 \(a, b\)가 서로 다른 수이면서 배수 관계인지 확인해주어야한다.
\(k\)가 1일 땐 서로 다르면서 배수 관계일 때만 같게 만들 수 있기 때문.
참고로 소인수 분해할 때
int num, div = 2;
while(num != 1){
if(num % div == 0) num /= div;
else{
if(div % 2 == 0) div++;
else div += 2;
}
}
이렇게 구하면 TLE에 걸린다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
int a, b, k;
cin >> a >> b >> k;
ll cnt = 0;
int cp = a;
for (int i = 2; i * i <= cp; ++i) {
while (cp % i == 0) {
cp /= i;
cnt++;
}
}
if (cp > 1) cnt++;
cp = b;
for (int i = 2; i * i <= cp; ++i) {
while (cp % i == 0) {
cp /= i;
cnt++;
}
}
if (cp > 1) cnt++;
if (k == 1) {
if (a != b && ((a % b == 0) || (b % a == 0))) cout << "YES\n";
else cout << "NO\n";
}
else if (k <= cnt) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
'codeforce' 카테고리의 다른 글
Round #731 (Div. 3) (0) | 2021.07.11 |
---|---|
Round #728 (0) | 2021.06.26 |
Round #727 (0) | 2021.06.25 |
Round #707 (Div. 2) (0) | 2021.05.25 |
Round #706 (Div. 2) (0) | 2021.05.24 |