Codeforces Global Round 25 |
---|
Закончено |
У Алисы есть $$$n$$$ монет, и она хочет сделать покупки в ювелирном магазине Боба. Хотя Боб еще не открыл магазин, он хочет быть уверен, что Алиса сегодня купит ровно $$$k$$$ драгоценностей. Для этого Боб может построить не более $$$60$$$ прилавков (каждый из которых содержит неограниченное количество драгоценностей) и установить цену за драгоценность для каждого прилавка как целое число монет от $$$1$$$ до $$$10^{18}$$$.
К счастью, Боб знает, что Алиса покупает жадно: она подойдет к прилавку $$$1$$$, купит наибольшее возможное количество драгоценностей, затем перейдет к прилавку $$$2$$$, купит наибольшее возможное количество драгоценностей, и так до последнего прилавка. Зная это, Боб может выбрать количество прилавков, а также установить цену для каждого прилавка так, чтобы Алиса купила ровно $$$k$$$ драгоценностей. Помогите Бобу решить эту задачу или определите, что это невозможно.
Обратите внимание, не обязательно, чтобы Алиса потратила все монеты.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных содержит два целых положительных числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 10^{18}$$$) — количество монет у Алисы и количество драгоценностей, которое Боб хочет, чтобы Алиса купила.
Для каждого набора входных данных выведите в отдельной строке «YES», если Боб может построить не более $$$60$$$ прилавков и установить цены в них так, чтобы Алиса купила ровно $$$k$$$ драгоценностей, или «NO», если это невозможно.
Если ответ «YES», во второй строке выведите целое число $$$s$$$ ($$$1 \le s \le 60$$$) — количество прилавков, которое должен построить Боб. В третьей строке выведите $$$s$$$ целых положительных чисел $$$p_1, p_2, \ldots, p_s$$$ ($$$1 \le p_i \le 10^{18})$$$, которые представляют собой подходящий набор цен $$$p$$$, где $$$p_i$$$ — цена за драгоценный камень на прилавке $$$i$$$. Если таких $$$p$$$ несколько, выведите любое из них.
37 36 4255 8
YES 10 2 3 4 5 6 7 8 9 10 11 NO YES 8 128 64 32 16 8 4 2 1
В первом наборе входных данных, на первом прилавке Алиса покупает $$$3$$$ драгоценности и остается с $$$1$$$ монетой. Этого недостаточно, чтобы купить драгоценности на любом из оставшихся прилавков, поэтому в итоге Алиса купит ровно $$$3$$$ драгоценности.
В третьем наборе входных данных,
Название |
---|