아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

선형 회귀는 너무 쉬워 1

시간 제한1초메모리 제한1024 MB

요약
고정된 y절편 b에 대해 잔차 합을 0으로 만드는 기울기 a를 구하고, 답이 여러 개면 EZPZ를 출력한다.
난이도

보통10점 중 4점

유형
수학, 배열
정답자
아직 제출이 없습니다

문제

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

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

∑_i=1n(a_1x_i+b−y_i)1\displaystyle\sum\_{i=1}^n (a\_1x\_i+b-y\_i)^1의 값이 00에 가장 가깝도록 하는 실수 a_1a\_1을 구하시오.

입력

첫 줄에 데이터의 개수를 의미하는 정수 nn (1≤n≤1051 \le n \le 10^5)과 yy 절편을 의미하는 정수 bb (−109≤b≤109-10^9 \le b \le 10^9)가 주어진다.

두 번째 줄부터 nn개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 x_ix\_i와 y_iy\_i (−109≤x_i,y_i≤109-10^9 \le x\_i, y\_i \le 10^9)의 값이 주어진다.

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

출력

첫 번째 줄에 ∑_i=1n(a_1x_i+b−y_i)1\displaystyle\sum\_{i=1}^n (a\_1x\_i+b-y\_i)^1의 값이 00에 가장 가깝도록 하는 a_1a\_1을 출력한다.

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

∑_i=1n(a_1x_i+b−y_i)1\displaystyle\sum\_{i=1}^n (a\_1x\_i+b-y\_i)^1의 값이 00에 가장 가깝도록 하는 a_1a\_1 중 유리수가 존재함을 증명할 수 있다.

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

예제4

  1. 예제 1

    입력
    2 1
    -1 1
    2 1
    
    예상 출력
    0
    
  2. 예제 2

    입력
    3 -2
    -1 0
    1 -5
    -1 0
    
    예상 출력
    -1
    
  3. 예제 3

    입력
    6 3
    -1 1
    0 2
    1 4
    -1 1
    2 5
    2 6
    
    예상 출력
    1/3
    
  4. 예제 4

    입력
    1 0
    0 0
    
    예상 출력
    EZPZ