[BOJ 27295] 선형 회귀는 너무 쉬워 1

View as PDF

Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 1G

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중을 하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 더 어려운 문제를 내주었다. 일반적인 선형 회귀의 경우 데이터 $(x_1, y_1), (x_2, y_2), \cdots , (x_n, y_n)$이 주어졌을 때, 잔차 제곱의 합이 $0$에 가장 가깝도록, 즉 $\displaystyle\sum_{i=1}^n (a_2x_i+b_2-y_i)^2$이 최소가 되도록 하는 실수 $a_2$와 $b_2$를 찾는 문제이다. 동우는 여기에서 더 발전시켜 잔차 $k$제곱의 합 즉, $\displaystyle\sum_{i=1}^n (a_kx_i+b_k-y_i)^k$이 $0$에 가장 가깝도록 하는 실수 $a_k$와 $b_k$을 구하는 문제를 냈다. 이 문제를 풀던 유림이는 너무 어려워서 동우에게 조금만 쉽게 바꿔 달라고 하자 동우는 조금 고민을 하다 다음과 같은 조건을 추가한다. "$k = 1$일 때만 구해. 그리고 $y$절편이 정해져 있을 때 기울기만 정해."</p>

유림이를 도와 $y$절편이 주어졌을 때 문제를 풀어보자. 즉, 주어진 $b$에 대해 다음 문제의 답을 구해보자.

$\displaystyle\sum_{i=1}^n (a_1x_i+b-y_i)^1$의 값이 $0$에 가장 가깝도록 하는 실수 $a_1$을 구하시오.

입력 형식

첫 줄에 데이터의 개수를 의미하는 정수 $n$ ($1 \le n \le 10^5$)과 $y$ 절편을 의미하는 정수 $b$ ($-10^9 \le b \le 10^9$)가 주어진다.</p>

두 번째 줄부터 $n$개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)의 값이 주어진다.

이때, 서로 같은 점이 여러 번 주어질 수 있음에 유의한다.

출력 형식

첫 번째 줄에 $\displaystyle\sum_{i=1}^n (a_1x_i+b-y_i)^1$의 값이 $0$에 가장 가깝도록 하는 $a_1$을 출력한다.</p>

만약 답이 정수라면 그대로 출력하고, 정수가 아닌 유리수라면 기약분수 ${p\over q}$ ($1 \le \lvert p\rvert, \ 2\le q$이며 $gcd(\lvert p\rvert,q)=1$)로 약분해 $p$/$q$의 형태로 출력한다.

$\displaystyle\sum_{i=1}^n (a_1x_i+b-y_i)^1$의 값이 $0$에 가장 가깝도록 하는 $a_1$ 중 유리수가 존재함을 증명할 수 있다.

만약 답으로 가능한 $a_1$이 여러 개 존재한다면, "EZPZ"를 출력한다.

예제 입력 1

2 1
-1 1
2 1

예제 출력 1

0

예제 입력 2

3 -2
-1 0
1 -5
-1 0

예제 출력 2

-1

예제 입력 3

6 3
-1 1
0 2
1 4
-1 1
2 5
2 6

예제 출력 3

1/3

예제 입력 4

1 0
0 0

예제 출력 4

EZPZ

Comments

There are no comments at the moment.