Hello 2022 1599 -> 1645

https://codeforces.com/contest/1621

Dashboard - Hello 2022 - Codeforces

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. Stable Arrangement of Rooks

https://codeforces.com/contest/1621/problem/A

Problem - A - Codeforces

문제

 

n*n 체스보드에 k개의 룩을 배치하고자 한다. 이때 임의의 배치된 룩을 골라서 인접한 칸으로 한 칸 옮겨도 서로 공격받지 않게 배치할 수 있으면 배치된 룩과 체스보드를 출력하고 아니라면 -1을 출력하는 문제

 

풀이

 

각 대각선마다 2칸씩 띄워서 배치하면 된다. 만약 개수가 round(n/2)를 초과한다면 배치할 수 없다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    char ans[60][60];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n, k;
    		cin >> n >> k;
    		int cnt = n / 2;
    		if (n % 2)cnt++;
    		if (k > cnt) {
    			cout << -1<<'\n';
    			continue;
    		}
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n; j++) {
    				ans[i][j] = '.';
    			}
    		}
    		int start = 0;
    		for (int i = 0; i < n; i += 2) {
    			ans[i][i] = 'R';
    			start++;
    			if (start == k)break;
    		}
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n; j++) {
    				cout << ans[i][j];
    			}
    			cout << '\n';
    		}
    	}
    }

 

 

B. Integers Shop

https://codeforces.com/contest/1621/problem/B

Problem - B - Codeforces

문제

 

정수 가게에 n개의 구간을 판다. i 번째에는 li ~ ri 를 ci 비용에 판다 만약 정수 1~2와 , 7~8을 구매하였으면 이 사이에있는 3~6 정수는 공짜로 준다. 목표는 첫번째로 i번째 구간의 정수를 샀을 때 최대한 많은 정수를 가지는 것과, 두번째로 가장 싼 값에 최대 정수 갯수를 구하는 것이다. 각 i번째 구간마다 조건에 맞는 최소 비용을 출력하는 문제

 

풀이

 

여태 나온 구간중 최소 l과 최대r을 저장하여 새로 갱신될때 마다 사고, 여태 저장한 최소l = 현재l, 여태 저장한 최소r = 현재r 이라면 , min(여태 저장된 최소 비용,현재 비용)을 저장한다. 이 외에는 최소 l의 최소비용과 최대r의 최소 비용을 매번 저장해서 더한 값을 출력해준다.

 

코드

 

    #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;
    		long long minV = INT32_MAX, maxV = 0,minC=INT32_MAX,maxC=INT32_MAX,ans=INT32_MAX,tans=0;
    		for (int i = 0; i < n; i++) {
    			long long l, r, c,cnt=0;
    			cin >> l >> r >> c;
    			bool lflag = false, rflag = false;
    			tans = 0;
    			if (minV == l) {
    				cnt++;
    				minC = min(minC, c);
    			}
    			if (minV > l) {
    				minV = l;
    				minC = c;
    				cnt++;
    				lflag = true;
    			}
    			if (maxV == r) {
    				cnt++;
    				maxC = min(maxC, c);
    			}
    			if (maxV < r) {
    				maxV = r;
    				maxC = c;
    				cnt++;
    				rflag = true;
    			}
    			if (lflag && rflag) {
    				ans = c;
    				cout << ans << '\n';
    				continue;
    			}
    			if (lflag) {
    				ans = c + maxC;
    				if (cnt == 2)ans = c;
    				cout << ans << '\n';
    				continue;
    			}
    			if (rflag) {
    				ans = c + minC;
    				if (cnt == 2)ans = c;
    				cout << ans << '\n';
    				continue;
    			}
    			if (cnt == 2) {
    				ans = min(ans, c);
    				cout << ans << '\n';
    				continue;
    			}
    			if (cnt == 0) {
    				cout << ans << '\n';
    				continue;
    			}
    			ans = min(ans, minC + maxC);
    			cout << ans << '\n';
    		}
    	}
    }

 

C. Hidden Permutations

https://codeforces.com/contest/1621/problem/C

Problem - C - Codeforces

문제

 

원래의 permutation p를 찾는 인터랙티브 문제다. 새로운 permutation q를 만들어서 질문을 하는데, 쿼리는 i번째 인덱스를 질문하면 q[i] 출력해주고, 한번의 쿼리마다 q[i] = q[p[i]] 로 바뀐다. 최대 2n번 이하의 쿼리로 p를 찾아내서 출력하는 문제

 

풀이

 

매 인덱스 i마다 한번 출력을 했던 숫자를 다시 출력할 때 까지 계속 쿼리를 주면서, ans[이전에 받은 답]=새로받은답 으로 갱신하면서 답을 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int ans[10001];
    bool c[10001];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n;
    		for (int i = 1; i <= n; i++)c[i] = false;
    		int x, lastx;
    		for (int i = 1; i <= n; i++) {
    			if (c[i])continue;
    			cout << "? "<< i << endl;
    			cin >> x;
    			lastx = x;
    			c[x] = true;
    			while (true) {
    				cout << "? "<< i << endl;
    				cin >> x;
    				ans[lastx] = x;
    				lastx = x;
    				if (c[x])break;
    				c[x] = true;
    			}
    		}
    		cout << "! ";
    		for (int i = 1; i <= n; i++)cout<<ans[i] << ' ';
    		cout << endl;
    	}
    }

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.