Codeforces Round #368 (Div. 2)

코드포스 후기 #2

Codeforces Round #368 (Div. 2)
2016/08/20(토) 22:05

지난번의 쓰라린 패배를 딛고 두번째 도전

A. Brain's Photos

사진의 색깔이 문자열로 주어지고 컬러인지 흑백인지 판별하는 문제

흑백일때 출력이 "Blank&White"라서 그런지 Grey를 고려안한 사람들이 Hack을 많이 당했다.

사람들이 많이 실수할거라 생각은 했는데 아직 뉴비라 Hack은 엄두도 못냄 ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BrainsPhoto {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] temp = br.readLine().split(" ");
		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]);
		
		String[] line = new String[n];
		for (int i=0; i<n; i++) {
			line[i] = br.readLine();
		}
		
		for (int i=0; i<n; i++) {
			String[] s = line[i].split(" ");
			for (int j=0; j<m; j++) {
				if ("W".equals(s[j]) || "G".equals(s[j]) || "B".equals(s[j])) {
					continue;
				} else {
					System.out.println("#Color");
					return;
				}
			}
		}
		
		System.out.println("#Black&White");
	}
}

B. Bakery

간단한 그래프 문제

Storage에 연결된 edge중에 가장 짧은 것을 찾으면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Bakery {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] temp = br.readLine().split(" ");
		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]);
		int k = Integer.parseInt(temp[2]);
		
		int[] u = new int[m];
		int[] v = new int[m];
		int[] l = new int[m];
		boolean[] isStorage = new boolean[n+1];
		for (int i=0; i<m; i++) {
			temp = br.readLine().split(" ");
			u[i] = Integer.parseInt(temp[0]);
			v[i] = Integer.parseInt(temp[1]);
			l[i] = Integer.parseInt(temp[2]);
		}
		if (k > 0) {
			temp = br.readLine().split(" ");
			for (int i=0; i<k; i++) {
				isStorage[Integer.parseInt(temp[i])] = true;
			}
		}
		int res = 1000000001;
		for (int i=0; i<m; i++) {
			if (isStorage[u[i]] && !isStorage[v[i]]
			|| !isStorage[u[i]] && isStorage[v[i]]) {
				if (l[i] < res) {
					res = l[i];
				}
			}
		}
		
		if (res == 1000000001) {
			res = -1;
		}
		System.out.println(res);
	}
}

C. Pythagorean Triples
약간 수학 관련된 문제라서 신나서 풀었다.

숫자를 하나 주면 그 수로 피타고라스 수를 만드는 문제

다시말하면, $a^2+b^2=c^2$를 만족하는 세 수를 찾아야 된다.

0. $n=1, 2$일 때는 불가능

1. $n$이 $4$의 배수일 때 ($n=4k$)

나머지 두 수를 $3k$, $5k$로 잡으면

$(3k)^2+(4k)^2=(5k)^2$

2. $n$이 홀수일 때 ($n=2k+1$)

$(2k+1)^2=4k^2+4k+1\\ \qquad=((2k^2+2k+1)-(2k^2+2k))((2k^2+2k+1)+(2k^2+2k))\\ \qquad=(2k^2+2k+1)^2-(2k^2+2k)^2$

3. 남는 경우는 $n$이 $2$의 배수이면서 $4$의 배수는 아닌 것들이다. ($n=2k$, $k$는 홀수)

$k$에 대해서 피타고라스 수를 찾고(2.의 경우를 활용해서) 각각의 수에 $2$를 곱해주면 그 수도 피타고라스 수가 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class PythagoreanTriples {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		if (n == 1 || n == 2) {
			System.out.println(-1);
		} else {
			// n=4k
			if (n % 4 == 0) {
				int k = n / 4;
				System.out.printf("%d %d\n", 3*k, 5*k);
			} else {
				// n=2k
				int tmp = 1;
				if (n % 2 == 0) {
					n /= 2;
					tmp = 2;
				}
				long nn = n;
				nn *= n;
				long m = nn / 2;
				long k = m + 1;
				
				if (tmp == 2) {
					m *= 2;
					k *= 2;
				}
				System.out.printf("%d %d\n", m, k);
			}
		}
	}
}

D. Persistent Bookcase

미제출

E. Garlands

미제출

Final Standings

Rank	Points	Extras	A 500	B 1000	C 1500	D 2000	E 2500
328	2650	-	488 00:06	920 00:20	1242 00:43

C번까지 제출한게 43분째인데 그뒤로 한시간 넘게 D랑 E는 못풀어서 제출도 못했다ㅠ

Rating Changes

Rank	Points	Rating
328	2650	1528 → 1643 (+115)	Became Expert

Specialist에서 바로 Expert로 레벨업!

더 위를 향해 ~_~

※ 링크 : 대회공지 / 출제자해설