Codeforces Round #777 (Div. 2) 1507 -> 1648
https://codeforces.com/contest/1647
Dashboard - Codeforces Round #777 (Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. Madoka and Math Dad
https://codeforces.com/contest/1647/problem/A
Problem - A - Codeforces
codeforces.com
문제
n이 주어진다. 각 자릿수의 합이 n이되는 가장 큰 수를 출력하는 문제 단 수의 인접한 자리수가 같은 숫자면 안된다.
풀이
1212 혹은 21212로 시작하는게 가장 큰 수를 만들 수 있다. 처음에 sum=0으로 만들어 sum < n일때 계속 2121을 순서대로 더하다가 최종적으로 만들어진 수가 n보다 작으면 맨앞에 1을 붙여서 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string ans = "";
int sum = 0;
int idx = 0;
while (sum < n) {
if (idx % 2) {
sum += 1;
ans += '1';
}
else {
if (sum + 2 > n)break;
sum += 2;
ans += '2';
}
if (sum == n)break;
idx++;
}
if (sum != n)cout << "1";
cout << ans << '\n';
}
}
B. Madoka and the Elegant Gift
https://codeforces.com/contest/1647/problem/B
Problem - B - Codeforces
codeforces.com
문제
N*M 그리드가 주어진다. 각 셀에는 1또는 0으로 이루어져 있으며 1로만 구성된 가장 큰 직사각형을 nice한 직사각형이라고 부른다. 이 때 nice한 직사각형끼리 하나라도 교차하지 않으면 YES 아니라면 NO를 출력하는 문제
풀이
서로 다른 nice한 직사각형들끼리 교차한다면 반드시 어떠한 2*2 그리드에는 3개의 1로 구성된 구간이 있기때문에 모든 2*2 그리드를 방문해서 이러한 구간이 있는지 검사하고 있으면 NO 없다면 YES를 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
string s[101];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)cin >> s[i];
bool flag = true;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m - 1; j++) {
int cnt = 0;
for (int o = i; o <= i + 1; o++) {
for (int p = j; p <= j + 1; p++) {
if (s[o][p] == '1')cnt++;
}
}
if (cnt == 3) {
flag = false;
break;
}
}
if (flag == false)break;
}
if (flag)cout << "YES\n";
else cout << "NO\n";
}
}
C. Madoka and Childish Pranks
https://codeforces.com/contest/1647/problem/C
Problem - C - Codeforces
codeforces.com
문제
0 과 1로 구성된 n*m 그리드가 있다. 0은 흰색 칸이며 1은 검은색 칸이다. 한번의 연산에 원하는 직사각형을 골라 체스판처럼 색칠할 수 있다. 이때 최대 n*m번의 연산동안 입력받은 그리드를 만들 수 있으면 YES 아니라면 NO를 출력하는 문제
풀이
가장 왼쪽 위의 색이 검은색이라면 어떠한 방법을써도 안되고 나머지는 오른쪽이나 아래부터 2*1 , 1*2 셀들로 1을 색칠해가면서 구성할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
string s[101];
struct A {
int x1, y1, x2, y2;
};
vector<A> v;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
v.clear();
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)cin >> s[i];
if (s[0][0] == '1') {
cout << -1 << '\n';
continue;
}
for (int i = 0; i < n; i++) {
for (int j = m - 1; j > 0; j--) {
if (i == 0 && j == 0)continue;
if (s[i][j] == '1') {
v.push_back({ i+1,j,i+1,j+1 });
}
}
}
for (int i = n - 1; i > 0; i--) {
if (s[i][0] == '1') {
v.push_back({ i,1,i+1,1 });
}
}
cout << v.size() << '\n';
for (int i = 0; i < v.size(); i++) {
cout << v[i].x1 << ' ' << v[i].y1 << ' ' << v[i].x2 << ' ' << v[i].y2 << '\n';
}
}
}
D. Madoka and the Best School in Russia
https://codeforces.com/contest/1647/problem/D
Problem - D - Codeforces
codeforces.com
문제
어떠한 수가 d의 배수이면 good이라고 불린다.
어떠한 수가 good 이면서 두개의 good 수의 곱으로 나타낼 수 없으면 beautiful이라고 불린다.
n과 d가 주어졌을 때 최소 2개의 beautiful 수로 구성된 셋으로 만들 수 있으면 YES 아니라면 NO를 출력하는 문제
단 n은 good 수로 주어진다.
풀이
2개의 beautiful수로 구성된 셋으로 만드려면 (d*x) * (d*y)로 구성되어야 하기 때문에 n은 반드시 d*d의 배수여야한다. 하지만 n = d*d라면 2개의 셋을 만들 수 없다.
그리고 n을 d로 나눌 수 있는 만큼 나누고 수를 d*d* (d*(x))로 바꿔서 최소1개의 셋을 만든 후 x가 만약 소수가 아니라면 약수 2개로 분할하여 2개를 무조건 만들 수있다. 만약 x가 소수라면 n 약수중에서 d를 제외한 수의 제곱이 d가 된다면 d가 최소 4개이상이여야하고 아니라면 d가 소수가 아니기만 하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
long long x, d;
cin >> x >> d;
if (x % (d * d)) {
cout << "NO\n";
continue;
}
long long x2 = x,cnt=0;
while (x2 % d == 0) {
x2 /= d;
cnt++;
}
bool flag = false;
for (long long i = 2; i * i <= x2; i++) {
if (x2 % i == 0) {
flag = true;
break;
}
}
if (flag) {
cout << "YES\n";
continue;
}
if (cnt == 2) {
cout << "NO\n";
continue;
}
if (d == (x2 * x2)) {
if (cnt > 3)cout << "YES\n";
else cout << "NO\n";
}
else {
flag = false;
for (long long i = 2; i * i <= d; i++) {
if (d % i == 0) {
flag = true;
break;
}
}
if (flag)cout << "YES\n";
else cout << "NO\n";
}
}
}
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.