BAPC 2016

이번엔 엡실론, 플랫과 셋이서 BAPC 2016 을 쳤다.

[플랫 블로그]

L - Sticky Situation (gunwookim, 3분)

 

두번 뇌절을  했다. (흙흙)

정렬 후 인접한 3개에 대해 삼각형이 만들어지는지 판별한다.

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

int n;
ll a[20005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	sort(a+1,a+n+1);
	for(int i = 1;i <= n-2;i++) {
		if(a[i]+a[i+1] > a[i+2]) {
			cout << "possible";
			return 0;
		}
	}
	cout << "impossible";
	return 0;
}

I - Older Brother (urd05, 5분)

 

플랫이 슥삭해서 나는 풀이는 모른다.

 

B - Battle Simulation (gunwookim, 10분)

 

연속한 3개가 모두 다른 거라면 'C',

나머진 'R' -> 'S', 'B' -> 'K', 'L' -> 'H' 로 치환하면 된다.

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
char a[1000005];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a+1;
	int i,n = strlen(a+1);
	for(i = 1;i <= n-2;) {
		if(a[i] != a[i+1]&&a[i] != a[i+2]&&a[i+1] != a[i+2]) {
			cout << "C";
			i += 3;
			continue;
		}
		if(a[i] == 'R') cout << "S";
		if(a[i] == 'B') cout << "K";
		if(a[i] == 'L') cout << "H";
		i++;
	}
	for(;i <= n;i++) {
		if(a[i] == 'R') cout << "S";
		if(a[i] == 'B') cout << "K";
		if(a[i] == 'L') cout << "H";
	}
	return 0;
}

 

C - Brexit (urd05, 18분)

 

플랫이 슥삭해서 나는 풀이는 모른다.

 

E - Charles in Charge (urd05, 43분)

 

C풀고 필 받아서 플랫이 슥삭 하고 풀었다.

 

K - Safe Racing (mckingtori, 46분)

 

dp식을 잘 세워보면 O(SL) 정도 시간이 나오는데, 적당한 변형을 통해 O(L+S)로 변환 가능하다.

 

D - Bridge Automation (gunwookim, 80분)

 

이것도 dp인데,

dp[i] : i번째까지 보트를 보냈을때 최소 시간

이런 dp식을 세워보면, dp[i] = min(dp[j]+max(a[i]-a[j+1]-1780,20*(i-j))+120) (0 <= j < i) 가 된다.

이러면 O(N^2) 이 된다.

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,g,INF = 1e9;
int a[4005],d[4005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		d[i] = INF;
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 0;j < i;j++) {
			d[i] = min(d[i],d[j]+max(a[i]-a[j+1]-1780,20*(i-j))+120);
		}
	}
	cout << d[n];
	return 0;
}

 

J - Programming Tutors (urd05, 144분)

 

원래 엡실론이 J번을 잡고 풀고 있었는데 TLE가 나자

플랫이 갑자기 슥하고 나타나서 풀었다. 갓플랫;;

 

G - Manhattan Positioning System (gunwookim, 147분)

 

첫번째 입력으로 주어진 것을 잡고 그 조건에 해당하는 모든 점을 판별해준다. 

시간상, O(4*D_1*N) 가 나와야 하는데 적당한 최적화(?) 를 해서 풀었다.

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,b;
int x,y,ans,nx,ny;

struct diamond {
	int x,y,d;
}a[1005];

bool isok(int xx,int yy) {
	for(int i = 1;i <= n;i++) {
		if(abs(a[b].x-xx)+abs(a[b].y-yy) != a[b].d) return false;
		b = b%n+1;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	b = 1;
	for(int i = 1;i <= n;i++) {
		cin >> a[i].x >> a[i].y >> a[i].d;
	}
	for(int i = 1;i <= a[1].d;i++) {
		x = a[1].x+a[1].d-i+1, y = a[1].y+i-1;
		if(isok(x,y)) {
			ans++;
			nx = x, ny = y;
			if(ans >= 2) {
				cout << "uncertain";
				return 0;
			}
		}
	}

	for(int i = 1;i <= a[1].d;i++) {
		x = a[1].x-a[1].d+i-1, y = a[1].y-i+1;
		if(isok(x,y)) {
			ans++;
			nx = x, ny = y;
			if(ans >= 2) {
				cout << "uncertain";
				return 0;
			}
		}
	}

	for(int i = 1;i <= a[1].d;i++) {
		x = a[1].x-i+1, y = a[1].y+a[1].d-i+1;
		if(isok(x,y)) {
			ans++;
			nx = x, ny = y;
			if(ans >= 2) {
				cout << "uncertain";
				return 0;
			}
		}
	}

	for(int i = 1;i <= a[1].d;i++) {
		x = a[1].x+i-1, y = a[1].y-a[1].d+i-1;
		if(isok(x,y)) {
			ans++;
			nx = x, ny = y;
			if(ans >= 2) {
				cout << "uncertain";
				return 0;
			}
		}
	}
	if(a[1].d == 0&&isok(a[1].x,a[1].y)) {
		ans++;
		nx = a[1].x, ny = a[1].y;
	}
	if(ans >= 2) cout << "uncertain";
	else if(!ans) cout << "impossible";
	else cout << nx << ' ' << ny;
	return 0;
}

 

H - Multiplying Digits (gunwookim, 241분)

 

일단 뚫는 풀이를 생각하고 여어어어어어러가지 최적화를 했다.

1. memorization

2. 지금까지 나온 최대 자리수를 저장하는 변수를 만들고, 그 자리수를 넘으면 return

3. 최대 자리수까지 남은 자리수에 넣을 수 있는 최대값을 넣었을때 만들어야 할 값보다 작게 나오면 return

4. 지금까지 온 수중에 가장 큰 수를 저장하고, 그 수보다 작은 수들만 돈다.

5. 숫자를 매길때, 맨 마지막 자리를 제외하고 모두 루트 b보다 커야한다.

6. i로 나누려고 할때 i보다 큰 i의 배수중 x의 약수가 있으면 return (즉, 이미 넣을 수 있는건 더 많이 넣어봤으니 할 필요가 없다)

이정도로 최적화를 했다. 힘들었다

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
ll n;
ull b;
int mxdep;
map <ll,__int128> d;
map <ll,int> ansdig;
vector <ll> p;
__int128 INF = ULLONG_MAX-1;
__int128 A;

__int128 go(ull x,ull la,int dep) {
	__int128 ret = INF;
	int mndig = 1;
	if(d.find(x) != d.end()) {
		if(ansdig[x] >= la) return d[x];
		else ret = d[x],mndig = ansdig[x]+1;
	}
	if(x < b) {
		mxdep = dep;
		return d[x] = x;
	}
	A = 1;
	for(int i = dep;i <= mxdep;i++) {
		A *= la;
		if(A > INF) {
			A = INF;
			break;
		}
	}
	if(A < x||mxdep < dep) return d[x] = (__int128)INF/b-b;
	bool f;
	for(ull i = la;i >= mndig&&i*i >= b;i--) {
		if(x % i == 0) {
			f = false;
			for(ull j = 2;j*i < b;j++) {
				if(x % (i*j) == 0) {
					f = true; break;
				}
			}
			if(f) continue;
			ret = min(ret,go(x/i,i,dep+1)*b+i);
		}
	}
	ansdig[x] = la;
	return d[x] = ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> b >> n;
	for(ll i = 2;i < b;i++) {
		if(n % i == 0) {
			p.push_back(i);
		}
	}
	ll tn = n;
	mxdep = -1;
	for(ll i = 2;i < b;i++) {
		while(tn % i == 0) mxdep++,tn /= i;
	}
	if(tn != 1) {
		cout << "impossible";
		return 0;
	}
	ull x = go(n,b-1,0);
	if(x == INF) return 1;
	cout << x;
	return 0;
}

 

내일(5/6)은 코포 때문에 셋을 안돌것 같다.