Educational Codeforces Round 124 (Rated for Div. 2) 1545 -> 1507
https://codeforces.com/contest/1651
Dashboard - Educational Codeforces Round 124 (Rated for Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. Playoff
https://codeforces.com/contest/1651/problem/A
Problem - A - Codeforces
codeforces.com
문제
n이 주어진다. 2^n명이 토너먼트에 참가하는데 처음에는 1vs2 , 3vs4 와 같은 바로 옆사람과 대결한다. 그리고 대결하는 각 사람의 인덱스를 더했을때 짝수면 숫자가 큰사람이 이기고 홀수면 숫자가 작은사람이 이긴다. n이 주어졌을 때 최종적으로 승리하는 사람을 출력하는 문제
풀이
첫경기는 무조건 홀수가 나오니 앞 인덱스가 이기고 이들은 모두 홀수 인덱스다. 그럼 이제 앞으로 더해질 경기들은 다 짝수이니 무조건 뒷사람이 이기고 결론은 2^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--) {
long long n;
cin >> n;
cout << (1LL << n) - 1 << '\n';
}
}
B. Prove Him Wrong
https://codeforces.com/contest/1651/problem/B
Problem - B - Codeforces
codeforces.com
문제
n이 주어진다. 인덱스가 서로다른 i,j를 선택하여 a[i] = a[j] = abs(a[i]-a[j])로 바꾸는 연산을 딱 한번 했을때 어떤 인덱스를 선택하더라도 주어진 배열의 총합이 적어지지 않는 배열(단 원소의 크기는 1<= a[i] <= 10^9)을 만들 수 있으면 YES와 그러한 배열을 출력하고 그렇지 않으면 NO를 출력한다
풀이
n이 주어졌을때 만들 수 있는 최소 숫자들로 구성된 숫자는 a[1]이 1이고 이후부터 3을 곱하는 배열이다. 원소중 하나라도 10^9를 넘어간다면 NO를 출력하고 이외에는 YES와 3을 곱해서 출력하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[1001];
const long long MAX = 1000000000;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
bool flag = true;
a[1] = 1;
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] * 3LL;
if (a[i] > MAX) {
flag = false;
break;
}
}
if (flag) {
cout << "YES\n";
for (int i = 1; i <= n; i++)cout << a[i] << ' ';
cout << '\n';
}
else {
cout << "NO\n";
}
}
}
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.