코드포스 후기 #5
Codeforces Round #373 (Div. 2)
2016/09/23(금) 22:05
A. Vitya in the Countryside
0에서 15 사이를 증가/감소하는 수열에서 다음 숫자가 증가인지 감소인지 판별하는 문제
0이면 무조건 증가, 15면 무조건 감소, 나머지 경우는 그전 숫자와 비교해서 증가 상태인지, 감소 상태인지 판별한다. (길이 1의 수열인 경우 판별불가)
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ProblemA {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] temp = br.readLine().split(" ");
int last = Integer.parseInt(temp[n-1]);
if (last == 0) {
System.out.println("UP");
} else if (last == 15) {
System.out.println("DOWN");
} else {
if (n == 1) {
System.out.println(-1);
} else {
int prev = Integer.parseInt(temp[n-2]);
if (prev < last) {
System.out.println("UP");
} else {
System.out.println("DOWN");
}
}
}
}
}
B. Anatoly and Cockroaches
r과 b로만 이루어진 문자열을 r과 b가 서로 번갈아 나타나도록 만들 때, 최소 move 수를 구하는 문제
가능한 조작은 두 문자의 위치를 서로 swap하는 것과 하나를 다른 것으로 flip하는 것 두가지이다.
rbrb... 형태와 brbr... 형태로 만드는 것 두가지 케이스로 나눠서 풀었다.
입력된 처음 상태와 각 케이스에서 최종 상태를 각 자리마다 비교해서 다른(조작해야하는) b과 r을 count한다.
min(b, r)만큼 swap하면 되고, max(b, r)-min(b,r)만큼 flip하면 최종 상태를 만들 수 있으므로, move 수는 max(b, r)이다.
rbrb...와 brbr... 두가지 케이스 중에서 적은 move 수가 답이 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ProblemB {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String cocks = br.readLine();
int res = 100000;
// start with 'b'
int bCnt = 0;
int rCnt = 0;
for (int i=0; i<n; i+=2) {
if (cocks.charAt(i) != 'b') {
bCnt++;
}
}
for (int i=1; i<n; i+=2) {
if (cocks.charAt(i) != 'r') {
rCnt++;
}
}
int temp = Math.max(bCnt, rCnt);
if (temp < res) {
res = temp;
}
// start with 'r'
bCnt = 0;
rCnt = 0;
for (int i=1; i<n; i+=2) {
if (cocks.charAt(i) != 'b') {
bCnt++;
}
}
for (int i=0; i<n; i+=2) {
if (cocks.charAt(i) != 'r') {
rCnt++;
}
}
temp = Math.max(bCnt, rCnt);
if (temp < res) {
res = temp;
}
System.out.println(res);
}
}
C. Efim and Strange Grade
소수점 이하 자릿수들에 반올림을 t번 해서 최대로 만들 수 있는 수를 구하는 문제
앞에서부터 스캔하다가 5이상인 자릿수를 발견하면 거기서부터 반올림하면서 다시 앞자리로 돌아간다.
200000자리 숫자가 들어오는데 String.substring 함수를 쓰는 바람에 첫시도에 타임아웃 두번째에 Accepted
근데 시스템 채점에서 틀려서 보니 마지막에 정수자리로 올리는 부분에서 반올림 횟수가 남았는지 조건(t>0)을 빼먹었었다ㅠ
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ProblemC {
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 t = Integer.parseInt(temp[1]);
String numStr = br.readLine();
int[] num = new int[n];
int pointIdx = 0;
for (int i=0; i<n; i++) {
char ch = numStr.charAt(i);
if (ch == '.') {
pointIdx = i;
break;
}
num[i] = ch-'0';
}
int[] stack = new int[n-pointIdx];
int top = -1;
for (int i=pointIdx+1; i<n; i++) {
stack[++top] = numStr.charAt(i)-'0';
if (stack[top] >= 5 || i == n-1) {
break;
}
}
while (top > 0 && stack[top] >= 5 && t > 0) {
stack[--top]++;
t--;
}
if (t > 0 && stack[0] >= 5) {
num[pointIdx-1]++;
for (int i=pointIdx-1; i>0; i--) {
if (num[i] >= 10) {
num[i] -= 10;
num[i-1]++;
} else {
break;
}
}
for (int i=0; i<pointIdx; i++) {
System.out.print(num[i]);
}
} else {
for (int i=0; i<pointIdx; i++) {
System.out.print(num[i]);
}
System.out.print(".");
for (int i=0; i<=top; i++) {
System.out.print(stack[i]);
}
System.out.println();
}
}
}
D. Alyona and Copiers
제출했다가 타임아웃으로 틀렸는데, 대회끝나고 출제측에서 데이터 오류가 있었다고 문제를 삭제했다.
E. Sasha and Array
미제출
Final Standings
Rank | Points | Extras | A 500 | B 1000 | C 1500 | E 2250 |
945 | 1400 | - | 488 00:06 | 912 00:22 | -2 |
|
시스템 채점에서 자주 틀리는 친구 맨날 놀렸는데 내가 시스템 채점에서 틀리다니... (우울)
자꾸 빨리만 풀려고 하니깐 테스트 케이스 같은거 안만들어보고 검토 안하고 그러니 이렇게 된다. 정신 차리자!
Rating Changes
Rank | Points | Rating | |
945 | 1400 | 1696 → 1692 (-4) | |
D번 문제 삭제 때문에 레이팅 되느냐 마느냐 잠시 논란거리가 되었는데, Div.2는 레이팅, Div.1은 언레이팅으로 정해졌다.
C번 시스템 채점에서 틀리는바람에 은근히 언레되기를 바랐는데 흑흑...
처음으로 레이팅이 감소됐다!ㅠ 감소폭은 무지 적지만 그래도 가슴 아픈 것... 다음엔 다시 회복하장.
※ 링크 : 대회공지 / 출제자해설
