Educational Codeforces Round 002. A, B, C, D

A. Extract Numbers

문제

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

Problem - A - Codeforces

 

문제 요약

,와 ;로 문자열들을 구분한 후 Integer일 경우 첫줄에 그 이외 문자열일 경우 둘째 줄에 각 문자열에 대해 , 로 구분하여 출력한다.

(이때, NULL space도 ,와 ;로 구분되어있으면 공백인 문자열로 생각한다)

만약 출력할 문자열이 없다면 "-"를 출력한다.

 

풀이

strtok 대신 NULL space도 구분해주는 strsep을 사용한다.

한번에 여러개의 파라미터로 parsing하는 방법을 잘 몰라 중첩 for문을 사용하였다.

isN이라는 함수에서 문자열이 정수인지 아닌지 판별하고 정수라면 첫번째 문자열(a)에 strcat

그렇지 않다면 두번째 문자열(b)에 strcat

 

소스코드

#include <stdio.h>
#include <string.h>

char *strsep(char **stringp, const char *delim) { char *ptr = *stringp; if(ptr == NULL) { return NULL; } while(**stringp) { if(strchr(delim, **stringp) != NULL) { **stringp = 0x00; (*stringp)++; return ptr; } (*stringp)++; } *stringp = NULL; return ptr; }

inline bool isN(char* s){
    int n = strlen(s);
    if(!n) return false;
    if(n==1 && s[0]=='0') return true;
    if(s[0]<='0' || '9'<s[0]) return false;
    for(int i=1; i<n; ++i)
        if(s[i]<'0' || '9'<s[i]) return false;
    return true;
}

char s[110000];
char a[110000], b[110000];
int ca, cb;

int main(){
    scanf("%s",s);
    char* S = s;
    for(char *p1; (p1=strsep(&S,";"))!=NULL; ){
        for(char *p2; (p2=strsep(&p1,","))!=NULL; ){
            if(isN(p2)) strcat(a,","), strcat(a,p2), ca=1;
            else strcat(b,","), strcat(b,p2), cb=1;
        }
    }
    if(ca) a[0]=a[strlen(a)]='"';
    else a[0]='-';
    if(cb) b[0]=b[strlen(b)]='"';
    else b[0]='-';
    printf("%s\n%s",a,b);
}

이때 4번째 줄의 strsep은 string.h에 존재하지 않는 경우 사용하지만 그렇지 않다면 주석처리를 해두자 (로컬에선 잘 돌아갔는데 코포에선 string.h에 포함되어 있지 않았다)

 

B. Queries about less or equal elements

문제

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

Problem - B - Codeforces

문제요약

두 배열 a, b가 주어진다. b 배열 원소들에 대해서 a 배열 원소 중 자신보다 작은 것의 개수를 하나씩 출력하라.

 

풀이

두 배열을 입력받고 b의 각 원소에 대해 a 배열의 upper_bound를 구하면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, m, k;
	scanf("%d%d",&n,&k);
	vector<int> v(n);
	for(auto&t:v) scanf("%d",&t);
	sort(v.begin(),v.end());
	for(int i=0; i<k; ++i){
		scanf("%d",&m);
		int t=upper_bound(v.begin(),v.end(),m)-v.begin();
		printf("%d ",t);
	}
}

C. Make Palindrome

문제

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

Problem - C - Codeforces

문제요약

문자열이 주어졌을 때 이 문자열을 원하는 순서대로 배열할 수 있다. 최소한의 문자를 바꾸어 만들 수 있는 팰린드롬들 중 사전식 가장 빠른 팰린드롬을 출력하라.

 

풀이

문자열 순서는 중요하지 않으니 각 문자 개수를 카운팅 해준다. (알파벳 소문자 26개)

홀수개의 문자가 있는 것들 개수를 카운팅한다.

이 문자들이 사전식으로 1,2,...,N번 문자라 할 때

1번 문자 개수를 1 증가하고 N번 문자 개수를 1 감소시키는 과정을 N/2이전까지 반복한다.

 

출력 :

1. 가장 작은 문자부터 그 문자 개수 절반만큼 출력해준다.

2. N이 홀수인 경우, N/2+1번째 문자는 정중앙에 오게 한다.

3. 1번의 정반대 순서로 출력한다.

 

소스코드

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

char s[210000];
int ch[26], j;
vector<int> v;

int main(){
	scanf("%s",s);
	for(int i=-1; s[++i];) ++ch[s[i]-'a'];
	for(j=0; j<26; ++j) if(ch[j]%2) v.push_back(j);
	for(int i=0; i<v.size()/2; ++i) ++ch[v[i]], --ch[v[v.size()-i-1]];
	for(int i=0; i<26; ++i) for(int j=0; j<ch[i]/2; ++j) printf("%c",i+'a');
	if(v.size()%2) printf("%c",v[v.size()/2]+'a');
	for(int i=25; i>=0; --i) for(int j=0; j<ch[i]/2; ++j) printf("%c",i+'a');
}

 

D. Area of Two Circles' Intersection

문제

https://codeforces.com/contest/600/problem/D

Problem - D - Codeforces

문제요약

두 원이 주어질 때, 겹치는 부분의 넓이를 구하여라 (boj 7869번과 같다.)

 

풀이

cos 법칙을 이용하여 넓이를 잘 계산해주면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	long double x1, y1, r1, x2, y2, r2, d, p=0;
	scanf("%Lf%Lf%Lf%Lf%Lf%Lf",&x1,&y1,&r1,&x2,&y2,&r2);
	d = sqrt(pow(x1-x2,2)+pow(y1-y2,2));
	if(r1+r2<d) p=0;
	else if(abs(r1-r2)>=d) p=acos(-1)*pow(min(r1,r2),2);
	else {
		long double t1 = acos((pow(r1,2)+pow(d,2)-pow(r2,2))/(2*r1*d)), t2 = acos((pow(r2,2)+pow(d,2)-pow(r1,2))/(2*r2*d));
		p = (pow(r1,2)*t1) - (pow(r1,2)*sin(2*t1)/2) + (pow(r2,2)*t2) - (pow(r2,2)*sin(2*t2)/2);
	}
	printf("%.7Lf",p);
}