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

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

Гонки на колесницах

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

요약
n개의 동전을 승리 측에 a개, 패배 측에 n-a개로 나눠 배당 x와 y로 두 결과 모두에서 이익이 나는 분배를 찾고, 최선의 결과에서 얻는 최대 이익과 그 이익을 내는 모든 분배를 구한다.
난이도

보통10점 중 4점

유형
수학, 완전 탐색, 그리디
정답자
아직 제출이 없습니다

문제

Как-то раз судьба привела Кратоса на колесничные бега, и он решил испытать удачу, поставив несколько монет на исход заезда. Разумеется, просто так тратить деньги воин не собирается, и поэтому он твердо решил, что сделает ставку только в том случае, если сможет остаться в выигрыше при любом исходе состязаний.

Кратос решил потратить на ставку nn монет: какую-то часть из них он поставит на победу выбранного им колесничего, остальное --- на его поражение. Изначально известны только 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, число знаков после запятой не превышает 55).

출력

Если невозможно распределить монеты так, чтобы гарантированно остаться в выигрыше, в единственной строке выведите число −1-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