SWERC 2018

문제

https://www.acmicpc.net/category/detail/2067

SWERC 2018

22/06/01 연습

Postech의 slah007님과 leo020630님 두 분과 연락이 닿아 팀연습을 같이 하게 되었다.

두 달간 조금 바쁘다는 핑계로 후기작성이 늦어져 죄송합니다..

같이 하는 다른 팀이 있다는게 생각보다 동기부여도 되고 경쟁심리도 생겨서 재밌었습니다.

아이디어만 말하고 직접 푼게 몇문제 없어서 아쉬웠습니다.

 

A - City of Lights

문제

처음에 모두 켜진 불들이 n개 있고 k개의 수를 입력받는다.

i번째 수에 대해 i, 2i, 3i, ...의 불을 모두 toggle하면서 동시에 켜지는 수의 최대값을 구한다.

 

풀이

그냥 그대로 구하면 된다..

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int b[1000001];

int main() {
	int n, k, p = 0;
	scanf("%d%d", &n, &k);
	for (int m; k--;) {
		int c = 0;
		scanf("%d", &m);
		for (int i = 1; i <= n; ++i) {
			if (i % m == 0) b[i] = !b[i];
			c += b[i];
		}
		if (p < c) p = c;
	}
	printf("%d", p);
}

 

B - Blurred Pictures

문제

각 레이어의 구간이 주어지고 만들 수 있는 가장 큰 정사각형의 한 변 길이를 출력하라

 

풀이

파라메트릭 서치로 길이를 정하고 되는 정사각형인지 체크한다

 

C - Crosswords

문제

N길이의 문자열이 A개, M길이의 문자열이 B개 주어진다.

이 문자열들을 잘 조합해서 NxM의 문자열을 만들 수 있는 경우의 수를 구하여라

단, 수직을 이어 만든 문자열은 N-letter words에 속하고 수평을 이어 만든 문자열은 M-letter words에 속해야 한다.

 

풀이

모르겠다 ㅠ

 

D - Monument Tour

문제

가로로 긴 도로 하나를 정하고 중간중간 수평을 왔다갔다 하면서 필요한 격자점을 방문할 때, 최소 이동거리를 구하여라

 

풀이

풀이가 잘 기억은 안나는데, 아무튼 bnb2011형님이 푸셨다.

 

E - Rounding

문제

rounding한 결과가 주어졌을 때, 원래 가능한 수의 범위를 소수점 두자리까지 표현하라

 

풀이

최대 -0.5~0.5사이로 변화하고 0이나 100일 때 처리를 잘 해주면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<string, int>> e;
vector<pair<int, int>> f;

int main() {
	int n, c = 0, ms = 0, me = 0;
	cin >> n; e.resize(n);
	for (auto& [s, m] : e) cin >> s >> m, c += m * 100, ms += m * 100 - max(0, m * 100 - 50), me += min(10000, m * 100 + 49) - m * 100;
	for (auto& [s, m] : e) {
		int ns = ms - (m * 100 - max(0, m * 100 - 50)), ne = me - (min(10000, m * 100 + 49) - m * 100), ks = max(0, m * 100 - 50), ke = min(10000, m * 100 + 49);
		int S = 10000 - (c - m * 100 + ne), E = 10000 - (c - m * 100 - ns);
		//cout << S << " " << E << " " << ks << " " << ke << endl;
		if (ke < S || E < ks) puts("IMPOSSIBLE"), exit(0);
		f.push_back({ max(S,ks),min(E,ke) });
	}
	for (int i = 0; i < n; ++i) {
		cout << e[i].first << " ";
		printf("%.2lf %.2lf\n", (double)f[i].first / 100, (double)f[i].second / 100);
	}
}

 

F - Paris by Night

문제

임의의 두 정점을 선택하여 직선을 만들고 양쪽 면의 정점들의 등급 합의 abs값을 최소화 할 때 그 값을 출력하라.

 

풀이

각도순 정렬과 스위핑을 잘 하면 처리가 된다.

 

G - Strings

문제

초기 string f(0)이 주어지고 다음을 반복한다.

SUB x lo hi : f(x)의 index [lo,hi)를 의미한다

APP x y : f(i) = f(x)+f(y)

마지막 문자열에 대해서 askii로 바꾼 값의 합을 1e9+7로 나눈 나머지를 구하라

 

풀이

모르겠다 ㅎㅎ

 

H - Travel Guide

문제

안읽어서 잘 모르는 문제

 

I - Mason’s Mark

문제

'.'과 '#'으로 이뤄진 2차원 맵이 주어질 때 아래의 그림과 같은 A, B, C가 몇 번 나오는지 구하여라

풀이

g3gogogo가 256줄의 엄청난 구현을 통해 AC!

 

J - Mona Lisa

문제

읽어도 잘 모르는 문제

 

K - Dishonest Driver

문제

문자열을 최소 수로 압축할 때, 그 수를 출력하라

 

풀이

n^3 dp를 사용하여 풀 수 있다 생각되었지만 3WA