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

A. Tricky Sum

 

문제 

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

 

문제요약

N값이 주어지면 2의 0, 1, ... , inf 제곱들에 대해 음수로 더하고 그 이외 수에 대해 양수로 더한 합을 출력해야한다.

 

풀이

1+2+...+2^(n-1) = 2^n - 1임을 알고 있을 때 전체에서 2의 제곱수들에 대해 두번 빼주면 된다.

즉, 수식으로 나타내면 다음과 같다.

N(N+1)/2 - 2(2^[log_2{N}] -1)

 

소스코드

#include <stdio.h>
typedef long long ll;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n, p=1;
        scanf("%lld",&n);
        for(int t=n; t; t>>=1, p<<=1);
        printf("%lld\n",((n*(n+1))>>1)-((p-1)<<1));
    }
}

 

B. Queries on a String

문제

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

Problem - B - Codeforces

 

문제풀이

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n, t;
	string s;
	int m, l, r, k, i, j;
	cin >> s;
	scanf("%d",&m);
	while(m--){
		scanf("%d%d%d",&l,&r,&k); l--, r--;
		k%=(r-l)+1; k=r-l+1-k;
		vector<char> v;
		for(i=0; i<k; i++) v.push_back(s[i+l]);
		for(j=l; i<r-l+1; j++, i++) s[j]=s[i+l];
		for(i=0; i<k; j++, i++) s[j]=v[i];
		v.clear();
	}
	cout << s;
}

 

C. Nearest Vectors

문제

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

Problem - C - Codeforces

문제요약

벡터들이 주어질 때 임의의 두 벡터간 작은 각을 theta라 하자. 가장 작은 theta를 가지는 벡터 쌍을 구하여라.

 

풀이

atan을 사용해서 각도 순으로 정렬 후 두 벡터간 각도를 비교한다.

double사용했을 때 로컬에선 맞는데 채점서버에서 틀린답으로 처리된다.

long double을 사용 및 M_PI값 인식을 못하므로 PI값 직접 사용하여 accept

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
//#define PI M_PI
const ld PI = 3.14159265358979323846264338327950288419716939937510;

struct data{ld w;int i;};

vector<data> v;

inline bool cmp(const data a,const data b){return a.w>b.w;}

int main(){
	int n, px, py;
	scanf("%d",&n);
	for(int i=0, x, y; i<n; ++i){
		scanf("%d%d",&x,&y);
		if(x<0) v.push_back({atan((ld)y/x)+PI,i});
		if(x>0) v.push_back({atan((ld)y/x),i});
		if(x==0) {
			if(y>0) v.push_back({PI/2,i});
			if(y<0) v.push_back({PI/2*3,i});
		}
	}
	sort(v.begin(),v.end(),cmp); v.push_back(v[0]);
	ld mo = 7;
	for(int i=1; i<v.size(); ++i){
		ld o = v[i].w-v[i-1].w;
		if(o<0) o+=2*PI;
		if(mo>min(o,PI-o)){
			mo=min(o,PI-o);
			px=v[i].i, py=v[i-1].i;
		}
	}
	printf("%d %d\n",px+1,py+1);
}

 

D. Igor In the Museum

문제

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

Problem - D - Codeforces

 

문제요약

풀이

소스코드

#include <bits/stdc++.h>
using namespace std;
int n, m;
int mp[1100][1100];
int dfs1(int x,int y){
	if(x<1 || y<1 || x>n || y>m || mp[x][y]==1) return 1;
	int a=0;
	mp[x][y]=-1;
	if(mp[x+1][y]!=-1) a+=dfs1(x+1,y);
	if(mp[x-1][y]!=-1) a+=dfs1(x-1,y);
	if(mp[x][y+1]!=-1) a+=dfs1(x,y+1);
	if(mp[x][y-1]!=-1) a+=dfs1(x,y-1);
	return a;
}
void dfs2(int x, int y, int z){
	if(x<1 || y<1 || x>n || y>m || mp[x][y]==1) return;
	mp[x][y]=z;
	if(mp[x+1][y]==-1) dfs2(x+1,y,z);
	if(mp[x-1][y]==-1) dfs2(x-1,y,z);
	if(mp[x][y+1]==-1) dfs2(x,y+1,z);
	if(mp[x][y-1]==-1) dfs2(x,y-1,z);
}
int main(){
	int k, i, j;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1; i<=n; i++){
		string s;
		cin >> s;
		for(j=1; j<=m; j++) mp[i][j]=(s[j-1]!='.');
	}
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			if(mp[i][j]) continue;
			int x=dfs1(i,j);
			dfs2(i,j,x);
		}
	}
	for(i=0; i<k; i++){
		int a, b;
		scanf("%d%d",&a,&b);
		printf("%d\n",mp[a][b]);
	}
}