만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

전차 경주

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

요약
n개의 동전을 승리에 거는 부분과 패배에 거는 나머지로 나눠, 두 결과 모두 이익이 나는 분할 중 최대 수익이 가장 큰 분할을 모두 구합니다.
난이도

보통10점 중 4점

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

문제

어느 날 운명의 장난으로 크라토스가 전차 경주장에 가게 되었다. 그는 운을 시험해 보기로 하고 경주 결과에 동전을 몇 개 걸기로 했다. 다만 그냥 돈을 잃을 생각은 없어서, 어떤 결과가 나오든 이득을 볼 수 있을 때에만 베팅하기로 굳게 마음먹었다.

크라토스는 동전 nn개를 베팅한다. 그중 일부 aa개는 고른 전차 기수의 승리에, 나머지는 패배에 건다. 처음에 알려진 것은 xx와 yy뿐이다. xx는 기수가 이기면 베팅 금액에 곱해지는 계수이고, yy는 기수가 지면 베팅 금액에 곱해지는 계수이다. 여기에 더해, 일어난 결과에 걸었던 부분의 금액은 전액 돌려받는다.

예를 들어 승리에 aa개를 걸었고 기수가 실제로 이겼다면 크라토스는 a+x⋅aa + x \cdot a개를 받는다. 패배했다면 (n−a)+y⋅(n−a)(n - a) + y \cdot (n - a)개를 받는다.

계산에 약한 전사를 도와, 동전을 나눠서 어떤 결과가 나와도 받는 금액이 베팅한 금액보다 엄격히 큰 것이 가능한지 판단해 달라. 또한 가장 좋은 결과가 나왔을 때 얻을 수 있는 최대 금액이 얼마인지도 알고 싶어 한다. 가능한 경우라면 이런 식으로 동전을 나누는 방법을 모두 알고 싶어 한다.

입력

첫 번째 줄에 동전 개수를 나타내는 정수 nn이 주어진다 (1≤n≤1091 \le n \le 10^9).

두 번째 줄에 전차 기수의 승리 계수와 패배 계수를 나타내는 실수 xx와 yy가 주어진다 (10−5≤x,y≤10410^{-5} \le x, y \le 10^4, 소수점 아래 자릿수는 다섯 자리를 넘지 않는다).

출력

조건을 만족하는 분배가 불가능하면 -1을 한 줄에 출력한다.

가능하면 첫 줄에 가장 좋은 결과가 나왔을 때 얻을 수 있는 최대 금액을 실수로 출력한다. 절대 오차 또는 상대 오차는 10−610^{-6}을 넘지 않아야 한다. 이때 다른 결과가 나와도 크라토스는 여전히 이익을 봐야 한다.

둘째 줄에 최대 금액이 나오는 분배의 개수 kk를 출력한다. 이어서 kk개의 줄에 각각 승리에 건 동전 수 aa와 패배에 건 동전 수 bb를 출력한다. 같은 분배를 두 번 출력하면 안 된다. 승리에 건 금액이 작은 순서대로 출력한다. 이런 분배의 개수가 유한하다는 것은 보장된다.

예제2

  1. 예제 1

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

    입력
    8
    3 1
    
    예상 출력
    12.0000000
    1
    3 5