[PS] 1002~1005, 1007 ~ 1013

problem1002

https://www.acmicpc.net/problem/1002
제곱근 계산이 들어가면 정밀도 때문에 정답을 맞추지 못한다

#!/usr/bin/perl
my $t=<>;
while($t--){
        my $s=<>;
        my ($x1,$y1,$r1,$x2,$y2,$r2)=split / /,$s;
        my ($dx,$dy)=($x2-$x1,$y2-$y1);
        my $a;
        if($dx==0 and $dy==0){
                if($r1==$r2){
                        $a=-1;
                }else{
                        $a=0;
                }
        }else{
                my $d=sqrt $dx**2 + $dy**2;
                if($d>$r1+$r2){
                        $a=0;
                }elsif($r1>$d+$r2 || $r2>$d+$r1){
                        $a=0;
                }elsif($d==$r1+$r2){
                        $a=1;
                }elsif($r1==$d+$r2 || $r2==$d+$r1){
                        $a=1;
                }else{
                        $a=2;
                }
        }
        print $a,"\n";
}

problem1003

https://www.acmicpc.net/problem/1003
0과 1의 개수도 피보나치 수열이다.

$s=<>;
while($s--){
    $n=<>;
    my @a;
    my @b;
    push @a,1;
    push @b,0;
    push @a,0;
    push @b,1;
    foreach my $i(2..$n){
        push @a,$a[i-1]+$a[i-2];
        push @b,$b[i-1]+$b[i-2];
    }
    print $a[$n]," ",$b[$n],"\n";
}

problem1004

https://www.acmicpc.net/problem/1004

for($T=<>;$T--;){
    my ($x1,$y1,$x2,$y2)=<>=~/([\d-]+)/g;
    my $ans=0;
    for($n=<>;$n--;){
        my ($cx,$cy,$r)=<>=~/([\d-]+)/g;
        my $d1=($x1-$cx)**2 + ($y1-$cy)**2;
        my $d2=($x2-$cx)**2 + ($y2-$cy)**2;
        if($d1<$r**2 xor $d2<$r**2){
            $ans++;
        }
    }
    if($x1==$x2 and $y1==$y2){
        $ans=0;
    }
    print $ans,"\n";
}

problem1005

https://www.acmicpc.net/problem/1005
거꾸로 계산하면 편하다.

my $w;
my @v;
my @time;
my @dp;
sub DFS($){
       my $a=shift;
       if(!$dp[$a]){
            $dp[$a]=$time[$a-1];
            foreach my $i(0..$#v){
                if($v[$i][$a]){
                    my $d=DFS($i)+$time[$a-1];
                    if( $dp[$a]<$d){
                        $dp[$a]=$d;
                    }
                }
            }
       }
       return $dp[$a];
}
for($T=<>;$T--;){
    my ($n,$k)=<>=~/(\d+)/g;
    @time=<>=~/(\d+)/g;
    @dp=undef;
    @v=undef;
    foreach my $i(0..$k-1){
        my ($s,$e)=<>=~/(\d+)/g;
        $v[$s][$e]=1;
    }
    $w=<>;
    print DFS($w),"\n";
}

#include<iostream>
#include<vector>
using namespace std;
int T;
int N, K;
vector<int> D;
int W;
vector<vector<int>> V;
vector<int> dp;
int dfs(int a) {
	if (dp[a] == -1) {
		dp[a] = D[a - 1];
		for(int i = 0; i < V.size(); i++) {
			if (V[i][a]) {
				int d = dfs(i) + D[a - 1];
				if (dp[a] < d) {
					dp[a] = d;
				}
			}
		}
	}
	return dp[a];
}
int main() {
	cin >> T;
	while (T--) {
		cin >> N >> K;
		D.assign(N, 0);
		for (int i = 0; i < N; i++) {
			cin >> D[i];
		}
		V.assign(N+1, vector<int>(N+1, 0));
		dp.assign(N+1, -1);
		for (int i = 0; i < K; i++) {
			int s, e;
			cin >> s >> e;
			V[s][e] = 1;
		}
		cin >> W;
		cout << dfs(W) << endl;
	}
}

problem 1007 vector 매칭

https://www.acmicpc.net/problem/1007

본 문제는 N(짝수)개의 점이 주어지고, 이를 수학적 벡터의 크기의 최소값을 찾는 문제이다.

이는 DFS를 통해 모든 경우를 찾아야 한다.

두 점을 더하는경우와 더하지 않는 경우를 모두 계산해야 해서 실로 $2^n$ 복잡도가 나올꺼 같지만,

절반은 반드시 음의 벡터가 되기 때문에 양의 벡터만 찾으면 나머진 알아서 구해지므로

nC(n/2) 의 복잡도로 계산을 할 수 있다.

perl로 풀고 싶었으나, perl이 재귀함수가 너무느려 TL 이 뜨므로 c++로 구현하였다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ALL(N)  (N).begin(),(N).end()
#define MINUS(A,B)  (A).first-=(B).first;(A).second-=(B).second;
#define PLUS(A,B)   (A).first+=(B).first;(A).second+=(B).second;
using namespace std;
typedef long long lld;
const lld INF = 9999999999999999;
int T, N;
lld A;
vector<pair<int, int> > V;
void DFS(int idx, pair<int, int> p, int c) {
    if (!c){
        for (int i = idx; i <N; i++){
            MINUS(p, V[i]);
        }
        A = min(A, (lld)p.first*p.first + (lld)p.second*p.second);
        return;
    }
    if (idx == N)return;
    for (int i = idx; i <N; i++){
        PLUS(p, V[i]);
        DFS(i+1, p, c - 1);
        MINUS(p, V[i]);
        MINUS(p, V[i]);
    }
}
int main() {
    cin >> T;
    while (T--){
        cin >> N;
        V.assign(N, pair<int, int>());
        generate(ALL(V), []()->pair<int, int>{pair<int, int> i; cin >> i.first >> i.second; return i; });
        A = INF;
        DFS(0, pair<int, int>(0, 0), N / 2);
        printf("%.6f\n", (double)sqrt(A));
    }
}

problem 1008 A/B

https://www.acmicpc.net/problem/1008
설명 써야 하니?

@_=split / /,<>;
print $_[0]/$_[1];

problem 1009 분산처리

https://www.acmicpc.net/problem/1009

1의 자릿수만 보면된다. perl이 연산작업에 너무 느려 TL이 뜨므로 c++로 풀었다….

#include<iostream>
#include<utility>
using namespace std;
int T;
pair<int, int> p;
int main() {
    cin >> T;
    while (T--){
        cin >> p.first >> p.second;
        int n = 1;
        while (p.second--){
            n *= p.first;
            n %= 10;
        }
        if (n == 0){
            n = 10;
        }
        cout << n << endl;
    }
}

problem 1010 다리 놓기

https://www.acmicpc.net/problem/1010
걍 nCr 구현하면 된다.

sub fac($){
    my $n=shift;
    my $r=1;
    foreach my $i(1..$n){
        $r*=$i;
    }
    return $r;
}
for($T=<>;$T--;){
     my ($a,$b)=<>=~/(\d+)/g;
     if($a==$b){
         print "1\n";
     }else{
        my $A=fac($b);
        my $B=(fac($a)*fac($b-$a));
        print $A/$B,"\n";
     }
}

problem 1011 Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011
거리의 차를 d라고 할때 d의 범위에 따라 답이 달라진다.

소스를 보면 바로 알 수 있다.

$n=<>;
while($n--){
    my ($x,$y)=split / /,<>;
    my $d=$y-$x;
    my $i=1;
    my $a=1;
    while($d!=1){
        if($i**2<$d and $d<=$i**2+$i){
            $a=2*$i;
            last;
        }elsif($i**2+$i<$d and $d<=$i**2+2*$i+1){
            $a=2*$i+1;
            last;
        }
        $i++;
    }
    print $a,"\n";
}

problem 1012 유기농 배추

https://www.acmicpc.net/problem/1012
설명이 필요한가..?

$t=<>;
@arr;
$n,$m,$cnt;
sub DFS($$){
    my ($i,$j)=@_;
    if($i<0 or $i>=$n or $j<0 or $j>=$m){return;}
    if($arr[$i][$j]==0){return;}
    $arr[$i][$j]=0;
    DFS($i-1,$j);
    DFS($i+1,$j);
    DFS($i,$j-1);
    DFS($i,$j+1);
}
while($t--){
    @arr=undef;
    ($n,$m,$cnt)=split / /,<>;
    while($cnt--){
        my ($x,$y)=split / /,<>;
        $arr[$x][$y]=1;
    }
    my $a=0;
    foreach my $i(0..$n-1){
        foreach my $j(0..$m-1){
            if($arr[$i][$j]==1){
                $a++;
                DFS($i,$j);
            }
        }
    }
    print $a,"\n";
}

problem 1013 Contact

https://www.acmicpc.net/problem/1013
아~~~!!!!!!!!!!!!!! 드디어 perl 같은 perl 문제가 나왔다.
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

$t=<>;
while($t--){
    print <>=~/^(100+1+|01)+$/?"YES\n":"NO\n";
}