Codeforces Round #641 (Div. 2)

Codeforces Round #641 (Div. 2) 를 봤다. 열심히 하지는 않은거 같다...

 

A - Orac and Factors

 

맨 처음에는 $n$의 약수중 1을 제외한 가장 작은 수를 더한다. 그 다음 부터는 무조건 2씩 더해진다.

증명) $n$이 홀수라면 무조건 가장 작은 1을 제외한 약수는 홀수가 될 것이다.

그러면 $odd+odd = even$ 이므로 그 다음부터는 2가 1을 제외한 가장 작은 약수가 된다.

$n$이 짝수라면 무조건 2씩 더해진다. 이게 왜 그런지는 알 것이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
vector <ll> p;
int n,c[200005];
ll a[100005];
ll mn[200005],mn2[200005],d[200005],mx,mx2;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		int n,k,is;
		cin >> n >> k;
		is = n;
		for(int i = 2;i*i <= n;i++) {
			if(n % i == 0) {
				is = i;
				break;
			}
		}
		cout << n+is+(k-1)*2 << '\n';
	}
	return 0;
}

 

B - Orac and Models

 

우리는 이런 정의를 내릴 수 있다.

$dp[i] : $ i번째 수를 사용했을때 1~i까지의 최대 길이

그러면 $dp[i] = \max_{j| i} dp[j]+1$ 라는 점화식이 나오는데, i의 약수는 $\sqrt{n}$ 개 밖에 없으므로

$O(n\sqrt{n})$ 정도의 시간복잡도로 풀 수 있다.

 

아쉽게도 문제를 잘못읽어 대회 중에는 못풀었다. 그래서 코드는 없다...

 

C - Orac and LCM

 

우리는 각각의 소수에 대해 몇제곱 만큼 나오는지 체크 해준다음, 모두 곱해주면 된다.

이걸 잘 하면 되는데 내 코드는 터졌다...

 

만약 어떤 소수 $x$가 모든 수에 대해 나왔다고 가정해보면 두번째로 작은 $x$의 제곱수가 소수 $x$에 대한 값이다.

하나의 숫자가 안나왔다고 해보자. ($n-1$개의 숫자가 나옴) 이럴때는 가장 작은 $x$의 제곱수가 소수 $x$에 대한 값이다.

만약 두개 이상 안나왔다면, 그중 두개를 lcm한 값에는 소수 $x$가 포함되지 않는다. 그래서 $gcd$값에도 소수 $x$가 없다.

 

이걸 잘 처리해주면 된다.

 

아쉽게도 나는 코드가 터져서 올리진 못한다.

 

D - Orac and Medians

 

일단 배열에서 찾고자 하는 수 $k$가 없다면 $no$다.

어느 인접한 두 수가 모두 k보다 크거나 같으면 $yes$ 다.

한칸 띄어져 인접해 있는 두수 모두 k보다 크거나 같으면 $yes$다.

$n = 1$인 경우는 무조건 $yes$다.

좀만 생각해보면 왜 그런지 나온다. 이건 읽는 여러분들이 직접 생각해 보기 바란다. 

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
int n,k,a[100005],b[100005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> k;
		int is = 0;
		a[n+1] = a[n+2] = -1;
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			if(a[i] == k) is = 1;
		}
		if(!is) {
			cout << "no\n";
			continue;
		}
		int ans = 0;
		if(n == 1) ans = 1;
		for(int i = 1;i <= n;i++) {
			if(a[i] < k) continue;
			if(a[i+1] >= k) ans = 1;
			else if(a[i+2] >= k) ans = 1;
		}
		cout << (ans?"yes":"no") << '\n';
	}
	return 0;
}