USACO 2020 February Contest (Bronze)

1. Triangles (Bronze)

점들을 이용해서 만들 수 있는 모든 직각삼각형 중 넓이가 가장 큰 값을 구하면 된다.

 

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;

vector<pii> vc;

int cross(int i, int j){
	return vc[i].second * vc[j].first - vc[i].first * vc[j].second;
}

bool check(int i, int j, int k){
	pii v1 = mp(vc[i].first - vc[j].first, vc[i].second - vc[j].second);
	pii v2 = mp(vc[k].first - vc[j].first, vc[k].second - vc[j].second);
	pii v3 = mp(vc[i].first - vc[k].first, vc[i].second - vc[k].second);
	bool cy = false, cx = false;
	cy = !v1.first || !v2.first || !v3.first;
	cx = !v1.second || !v2.second || !v3.second;
	return cy && cx;
}

int calc(int i, int j, int k){
	if(!check(i,j,k))return -1;
	int ret = cross(i, j) + cross(j, k) + cross(k, i);
	return abs(ret);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin >> n;
	for(int i=0;i<n;i++){
		int x, y; cin >> y >> x;
		vc.emplace_back(y, x);
	}
	int maxi = 0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				maxi = max(maxi, calc(i,j,k));
			}
		}
	}
	cout << maxi;
}

 

 

2. Mad Scientist

 

두 문자열 A와 B가 있고 이 두 문자열은 G와 H로 이루어져 있다. 이 두 문자열을 갖게 변경하고자 한다. 문자열에서 같은 문자열로 구성되는 부분 문자열을 잡고 G는 H로 H는 G로 변경을 할 때, 최소 횟수를 구하는 문제이다.

 

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	string A, B;cin >> A >> B;
	int ans = 0;
	bool c = false;
	for(int i=0;i<n;i++){
		if(A[i] != B[i]){
			if(c)continue;
			c = true;
			++ans;
		}
		else c = false;
	}
	cout << ans;
}

 

3. Swapity Swap

 

구간 두개를 잡고 돌리는 문제이다. N이 100이고 K가 10^9이다. 즉 그냥 아무생각없이 다 돌리면 시간 초과 난다.

A1 ~ A2와 B1 ~ B2 구간을 뒤집었을때 i번째 원소가 다시 i번째 오는 횟수를 구해 주기 (T)를 구하고 K % T만큼 더 돌려 그 원소가 어디로 가는지 구하면 된다.

 

#include<bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;

int ans[101], N, K, A1, A2, B1, B2;

int reverse(int idx){
	if(A1 <= idx && idx <= A2)idx = A1 + A2 - idx;
	if(B1 <= idx && idx <= B2)idx = B1 + B2 - idx;
	return idx;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K >> A1 >> A2 >> B1 >> B2;
	
	for(int i=1;i<=N;i++){
		int p = 1, cur = reverse(i);
		while(cur != i){
			p++;
			cur = reverse(cur);
		}
		for(int j=0;j<K%p;j++)
			cur = reverse(cur);
		ans[cur] = i;
	}
	for(int i=1;i<=N;i++){
		cout << ans[i] << '\n';
	}
}