(2020년 9월 12일에 작성한 글입니다.)
Dashboard - Codeforces Round #655 (Div. 2) - Codeforces
codeforces.com
학회 스터디에서 버추얼 참가로 진행
A.
거의 역대급으로 빨리 풀었는데
그냥 개수만큼 1을 출력하면 됨.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i;
cin >> T;
while (T--) {
cin >> N;
for (i = 0; i < N; i++) {
cout << 1 << ' ';
}
cout << '\n';
}
return 0;
}
B.
진짜진짜진짜 헤맸고 결국 못 풀었는데
어떻게 풀어야 되냐면
일단 N이 소수면 N/2, N/2가 답이다.
N이 홀수면
N의 소인수 중 가장 작은 걸 찾는다.
그걸 prime이라고 칭하면
N * (1 / prime), N * ((prime - 1) / prime)
이렇게 두 수가 답이 된다.
답이 되는 두 수를 a, b라고 부르면(a < b)
a + b = N이고
b % a == 0이어야 한다.
왜냐하면, lcm(a, b)가 N보다 작은 경우가 존재하고
그 중에서도 lcm(a, b)가 가장 작은 걸 골라야 하니까.
그래서 N의 소인수들을 prime이라고 하면
a = N * (1 / prime)
b = N * ((prime - 1) / prime) 일때 b % a == 0를 만족한다.
근데 prime이 소인수 중에서 가장 작은 수일때가 b, 즉 lcm(a, b)가 최소다.
왜냐하면 prime이 커질수록, (prime - 1) / prime은 1에 가까워지고 b는 커지니까
근데 여기서 내가 헷갈렸던 건
N / prime을 (1, N / prime - 1), (2, N / prime - 2), ... 이런식으로
다 확인해보고 나누어 떨어지는 관계인지 확인하고 그 중에서 최소를 구해야 되는거 아닌지였다.
이렇게 생각했는데
그런 경우는, prime이 더 작을 때 이미 걸러지기 때문에 상관 없다...
내가 뭘 잘못했는 지 정리해보자면
1. 일단 내가 처음에 생각한 풀이는 위에 적은 풀이랑 다른건데,
어떻게 보면 위의 저 풀이를 처음부터 떠올리지 못했다는 것도 잘못한 거긴 하다.
2. 근데 진짜 잘못한 건
내가 짠 코드에서는 prime들을 모두 구해놓고,
그걸 이용해서 N의 소인수 중 가장 큰 것을 골랐는데,
prime을 구할 때 end = (int)sqrt(MAX) + 1로 해놓고 end까지만 가도록 해놨기 때문에
N의 소인수 중 가장 큰 게 end보다 크면 primeNums 벡터에 저장이 안 됐다.
그때는 N / prime[i]을 체크하면서 더 큰 것도 넣어줬어야 한다.
근데 이건 너무 복잡하네...
여튼 포인트는, i <= (int)sqrt(MAX) + 1일때까지만 체크하면
소인수 중 일부는 저장이 안 될 수 있다는거다.
헷갈린다.
잘 정리해놓고 다음엔 이런 실수 안 해야지.
근데 애초에, 이런 문제가 안 생기도록
위에 적어놓은 풀이대로 했으면 맞았긴 하다.
#define MAX 1000000000
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int prime, a, b;
int lcm;
int i, j;
//freopen("input.txt", "r", stdin);
vector<int> primeNums;
const int end = (int)sqrt(MAX) + 1;
vector<bool> isPrime(end + 1, true);
isPrime[0] = isPrime[1] = false;
for (i = 2; i <= end; i++) {
if (isPrime[i]) {
primeNums.push_back(i);
for (j = i * i; j <= end; j += i) {
isPrime[j] = false;
}
}
}
cin >> T;
while (T--) {
cin >> N;
if (N % 2 == 0) {
cout << N / 2 << ' ' << N / 2 << '\n';
continue;
}
vector<int> primes;
for (i = 0; i < primeNums.size() && primeNums[i] < N; i++) {
if (N % primeNums[i] == 0) {
primes.push_back(primeNums[i]);
}
}
if (primes.size() == 0) {
cout << 1 << ' ' << N - 1 << '\n';
continue;
}
lcm = N;
for (i = 0; i < primes.size(); i++) {
prime = N / primes[i];
for (a = (N - prime) / 2; a >= prime; a -= prime) {
b = N - a; //a < b
if (b > lcm) {
break;
}
if (b % a == 0) {
lcm = b;
break;
}
}
}
cout << N - lcm << ' ' << lcm << '\n';
}
return 0;
}
C.
간단했다.
자기 자리에 있지 않은 수들의 연속이 몇 개 있는지를 체크하고
그게 0개이면 답은 0, 1개이면 1, 2개 이상이면 답은 2이다.
2개 이상이면, 그냥 전체 수열을 뒤죽박죽 섞은 다음에, 오름차순으로 정렬하면 되니까. 2번.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int cnt;
bool flag;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N + 1);
for (i = 1; i <= N; i++) {
cin >> arr[i];
}
cnt = 0;
flag = false;
for (i = 1; i <= N && cnt < 2; i++) {
if (arr[i] == i) {
flag = false;
}
else {
if (flag == false) {
flag = true;
cnt++;
}
}
}
if (cnt == 0) {
cout << 0 << '\n';
}
else if (cnt == 1) {
cout << 1 << '\n';
}
else {
cout << 2 << '\n';
}
}
return 0;
}