준연구소

문제 링크

10718번: We love kriii (acmicpc.net)

문제

ACM-ICPC 인터넷 예선, Regional, 그리고 World Finals까지 이미 2회씩 진출해버린 kriii는 미련을 버리지 못하고 왠지 모르게 올해에도 파주 World Finals 준비 캠프에 참여했다.

대회를 뜰 줄 모르는 지박령 kriii를 위해서 격려의 문구를 출력해주자.

입력

본 문제는 입력이 없다.

출력

두 줄에 걸쳐 "강한친구 대한육군"을 한 줄에 한 번씩 출력한다.

예제 입력 1                                                        예제 출력 1

                                                                                                        강한친구 대한육군

                                                                                                        강한친구 대한육군

소스 코드

#include <stdio.h>

int main()
{
	printf("강한친구 대한육군\n");
	printf("강한친구 대한육군");
	return 0;	
}

문제 링크

2557번: Hello World (acmicpc.net)

문제

Hello World!를 출력하시오.

입력

없음

출력

Hello World!를 출력하시오.

예제 입력                                                                                             예제 출력

                                                                                                        Hello World!

소스 코드

#include <stdio.h>

int main()
{
	printf("Hello World!");
	return 0;
}

문제 링크

1001번: A-B (acmicpc.net)

문제

두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

첫째 줄에 A-B를 출력한다.

예제 입력 1                                                                              예제 출력 1

     3 2                                                                                          1

소스 코드

#include <stdio.h>

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", a - b);
	return 0;
}

문제 링크

1000번: A+B (acmicpc.net)

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

첫째 줄에 A+B를 출력한다.

예제 입력 1                                                                              예제 출력 1

     1 2                                                                                         3

소스 코드

#include <stdio.h>

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", a + b);
	return 0;
}

간단 설명

a와 b라는 변수를 선언해 scnaf로 입력을 받고 printf괄호 안에 a + b를 쓰면 a + b 값이 출력된다.

문제 링크

3028번: 창영마을 (acmicpc.net)

문제

상근이와 정인이는 창영마을에 살고 있다. 창영마을은 전세계에서 가장 평화로운 마을로 알려져 있다. 이 마을의 이장은 상근이다.

정인이는 항상 상근이의 자리를 질투하고 있다. 정인이는 상근이가 이장의 자격이 없다는 것을 속임수를 이용해서 사람들에게 알려주려고 한다. 

먼저 정인이는 불투명한 컵 세 개를 일렬로 탁자 위에 올려놓고, 가장 왼쪽 컵에 작은 공 하나를 넣어놓았다. 이제 정인이는 컵 2개를 위치를 바꿔가면서 여러 번 섞을것이고, 모두 섞은 뒤에 상근이에게 어떤 컵에 공이 들어있는지 말하라고 할 것이다. 컵이 3개가 있을 때, 위치를 바꿀 수 있는 가능한 방법은 아래와 같이 3가지가 있다.

정인이는 이날만을 위해 컵 섞기를 30년간 연습해왔다. 따라서 상근이는 아무리 쳐다보아도 정인이의 팔 속도를 따라갈수 없다.

하지만, 정인이는 상근이가 뛰어난 프로그래머라는 것을 잊고 있었다. 또한, 상근이는 정인이가 언젠간 이런 반란을 일으킬 것을 알았기 때문에, 항상 정인이와 만날 때는 모든 상황을 비디오로 녹화하고 있었다.

정인이가 컵을 섞은 방법이 순서대로 주어질 때, 어떤 컵에 공이 있는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 정인이가 컵을 섞은 순서가 주어진다. 이 순서는 A, B, C중 하나이고, 문제에 있는 그림을 참고하면 된다. 정인이는 컵을 최대 50번 섞는다.

출력

공이 가장 왼쪽 컵에 있으면 1, 중앙에 있는 컵에 있으면 2, 오른쪽에 있는 컵에 있으면 3을 출력한다.

예제 입력 1                                                                                      예제 출력 1

AB                                                                                                         3

예제 입력 2                                                                                      예제 출력 2  

CBABCACCC                                                                                            1

소스 코드

#include <stdio.h>

int main()
{
	char a[51];
	int b[3] = { 1, 2, 3 };
	int c, i = 0;

	scanf("%s", a);

	while (1)
	{
		if (a[i] == 'A')
		{
			c = b[0];
			b[0] = b[1];
			b[1] = c;
		}

		if (a[i] == 'B')
		{
			c = b[1];
			b[1] = b[2];
			b[2] = c;
		}

		if (a[i] == 'C')
		{
			c = b[0];
			b[0] = b[2];
			b[2] = c;
		}

		if (a[i] == '\0') break;
		i++;
	}

	for (int i = 0; i < 3; i++)
	{
		if (b[i] == 1)
		{
			printf("%d", i + 1);
		}
	}
	return 0;
}

설명

만약 입력(a[i])에 A를 입력받았다면 1번째 컵과 2번째 컵을 바꾼다.

if (a[i] == 'A')
	{
		c = b[0];
		b[0] = b[1];
		b[1] = c;
	}

만약 입력(a[i])에 B를 입력받았다면 2번째 컵과 3번째 컵을 바꾼다.

if (a[i] == 'B')
	{
		c = b[1];
		b[1] = b[2];
		b[2] = c;
	}

만약 입력(a[i])에 C를 입력받았다면 1번째 컵과 3번째 컵을 바꾼다.

if (a[i] == 'C') 
	{
		c = b[0];
		b[0] = b[2];
		b[2] = c;
	}

만약 a배열에 맨 마지막(\0 널문자)까지 왔다면 while를 나간다.

if (a[i] == '\0') break;

맨 처음에 첫번쨰 컵에 공을 넣었으므로 1이 있는 컵을 찾아 그 컵에 위치에 따라 i + 1을 출력한다.(배열의 인덱스와
실제 순서는 1씩 차이가 있기 때문에 i를 출력하면 안되고 i + 1을 해야 됨)

for (int i = 0; i < 3; i++)
	{
		if (b[i] == 1)
		{
			printf("%d", i + 1);
		}
	}

ABC 190 간단 후기 올립니다~ (atcoder.jp/contests/abc190)

A - Very Very Primitive Game

간단한 구현 문제입니다. 먼저 시작하는 사람의 캔디가 더 많으면 먼저 시작하는 사람이 이기고, 그렇지 않으면 다른 사람이 이깁니다.

int main() {
	int a, b, c; cin >> a >> b >> c;
	if (c == 0) {
		if (a > b) cout << "Takahashi";
		else cout << "Aoki";
	}
	else {
		if (b > a) cout << "Aoki"; 
		else cout << "Takahashi";
	}
}

B - Magic 3

간단한 구현 문제입니다.  X < S and Y > D인 (X, Y)가 존재하면 Yes, 아니면 No를 출력하면 됩니다.

int main() {
	int n, s, d; cin >> n >> s >> d;
	int x, y;
	while (n--) {
		cin >> x >> y;
		if (x<s && y>d) {
			cout << "Yes"; return 0;
		}
	}
	cout << "No";
}

C - Bowls and Dishes

완전탐색 문제입니다. K명의 사람이 C or D를 선택하는 모든 경우(2^K)에 대하여 가장 많은 조건을 만족하는 경우를 출력하면 됩니다

typedef pair<int, int> p;
 
int N, M, K, ans, S[100];
p ab[100], cd[100];
 
void f(int idx) {
	if (idx == K) {
		int dish[104], i;
		for (i = 1; i <= N; i++) dish[i] = 0;
		for (i = 0; i < K; i++) {
			if (S[i] == 1) dish[cd[i].x] = 1;
			else dish[cd[i].y] = 1;
		}
		int sum = 0;
		for (i = 0; i < M; i++) {
			if (dish[ab[i].x] && dish[ab[i].y]) sum++;
		}
		ans = max(ans, sum);
		return;
	}
	S[idx] = 1; f(idx + 1);
	S[idx] = 2; f(idx + 1);
}
 
int main() {
	int i;
	cin >> N >> M;
	for (i = 0; i < M; i++) cin >> ab[i].x >> ab[i].y;
	cin >> K;
	for (i = 0; i < K; i++) cin >> cd[i].x >> cd[i].y;
	f(0);
	cout << ans;
}

D - Staircase Sequences

수학 문제입니다. 등차수열의 시작과 끝을 각각 a, b라고 할 경우 a + (a+1) + ... + b = N 인 (a, b) 쌍의 개수를 구하면 됩니다. 좌변은 (1+2+...+b) - (1+2+...+a-1) 이므로, b(b+1) - a(a-1)= 2N --> (b+a)(b-a+1)=2N이 됩니다.

2N을 xy꼴로 나타내서 x=b+a, y=b-a+1 or x=b-a+1, y=b+a가 성립하는지 확인하면 됩니다.

ll N;

inline int f(ll x, ll y) {
	if ((x + y - 1) % 2 == 0) return 1;
	return 0;
}
 
int main() {
	cin >> N;
	N *= 2;
	ll ans = 0;
	for (ll i = 1; i*i <= N; i++) {
		if (N%i) continue;
		ll j = N / i;
		if (f(i, j)) ans++;
		if (f(-i, -j)) ans++;
	}
	cout << ans;
}

E - Magical Ornament

Graph + bit DP 문제입니다. M개의 이웃한 쌍 (A,B)를 edge, N개의 gem이 node인 graph를 생각하자. K개의 C에 대하여 Ci에서 Cj의 shortest path를 구하자.(BFS 이용) 모든 (Ci, Cj) 쌍의 shortest path를 D[K][K]라고 하자. K개의 C를 node, D를 edge로 갖는 Graph에서 임의의 정점에서 다른 모든 노드를 방문하는 최소 비용 (salesman problem)을 구하면 된다.

int N, M, K, C[20], CC[100004], CI[100004], S[20];
vector<int> adj[100004];
int adj2[20][20];
const int INF = (int)1e9;
int dp[1 << 17][17];
 
int dfs(int state, int u) {
	int &ret = dp[state][u]; if (ret != -1) return ret;
	if (state == ((1 << K) - 1)) return ret = 0;
 
	ret = INF;
	for (int v = 0; v < K; v++) {
		if (state&(1 << v)) continue;
		if (adj2[u][v] == -1) continue;
		int a = dfs(state | (1 << v), v) + adj2[u][v];
		if (a < INF) ret = min(ret, a);
	}
	return ret;
}
 
int main() {
	int i, j;
	cin >> N >> M;
	for (i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	cin >> K;
	for (i = 0; i < K; i++) {
		cin >> C[i]; CC[C[i]] = 1; CI[C[i]] = i;
	}
 
	for (i = 1; i <= N; i++) {
		if (CC[i] == 0) continue;
		queue<int> q; q.push(i);
		vector<int> dist(N + 1, -1); dist[i] = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : adj[u]) {
				if (dist[v] != -1) continue;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
		for (j = 1; j <= N; j++) {
			if (CC[j] == 0 || i == j) continue;
			adj2[CI[i]][CI[j]] = adj2[CI[j]][CI[i]] = dist[j];
		}
	}
 
	int ans = INF;
	for (i = 0; i < (1 << K); i++) for (j = 0; j < K; j++) dp[i][j] = -1;
	for (i = 0; i < K; i++) {
		int ret = dfs(1 << i, i);
		if (ret < INF) ans = min(ans, ret + 1);
	}
	if (ans == INF) ans = -1;
	cout << ans;
}

F - Shift and Inversions

Segment Tree 문제입니다. i ~ i + N -1 구간의 inversion count를 구하면 됩니다. (0<= i <N) i=0일 경우는 segment tree를 이용하면 됩니다. (소스코드 rev_cnt) i=1 ~ N-1일 경우는 A[i]보다 작은 숫자와 큰 숫자는 O(1)에 찾을 수 있습니다. (소스크도 up, dn) 이유는 0 ~ N-1 숫자가 한 번씩 나오기 때문입니다.

struct sg {
	int st[1200004];
	void upd(int a, int b, int node, int node_st, int node_en) {
		if (a < node_st || node_en < a) return;
		if (node_st == node_en) {
			st[node] = b; return;
		}
		upd(a, b, node * 2, node_st, (node_st + node_en) / 2);
		upd(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
		st[node] = st[node * 2] + st[node * 2 + 1];
	}
	int qry(int a, int b, int node, int node_st, int node_en) {
		if (a > node_en || node_st > b) return 0;
		if (a <= node_st && node_en <= b) return st[node];
		return qry(a, b, node * 2, node_st, (node_st + node_en) / 2) +
			qry(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
	}
}S;
 
int main() {
	int i, n; cin >> n;
	vector<int> A(n + 1);
	ll rev_cnt = 0;
	for (i = 1; i <= n; i++) {
		cin >> A[i]; A[i]++;
		S.upd(A[i], 1, 1, 1, n);
		rev_cnt += (i - S.qry(1, A[i], 1, 1, n));
	}
	cout << rev_cnt << '\n';
	for (i = 1; i < n; i++) {
		int dn, up;
		dn = A[i] - 1; up = n - A[i];
		rev_cnt = rev_cnt - dn + up;
		cout << rev_cnt << '\n';
	}
}