Codeforces Round 753 (Div. 3) |
---|
Закончено |
Известный шеф-повар опять приготовил $$$n$$$ блюд: $$$i$$$-е блюдо состоит из $$$a_i$$$ грамм рыбы и $$$b_i$$$ грамм мяса.
Организаторы банкета считают два блюда $$$i$$$ и $$$j$$$ равными, если $$$a_i=a_j$$$ и одновременно $$$b_i=b_j$$$.
Организаторы банкета оценивают разнообразие $$$n$$$ блюд следующим образом. Разнообразие набора блюд равно количеству различных блюд в нём. Чем разнообразие меньше, тем лучше.
Для того, чтобы уменьшить разнообразие, был приглашен дегустатор. Он съест ровно $$$m_i$$$ грамм еды из каждого блюда. Для каждого блюда дегустатор определяет отдельно сколько он съест рыбы, а сколько мяса. Главное, чтобы суммарно в $$$i$$$-м блюде он съел ровно $$$m_i$$$ грамм.
Определите, сколько какого типа еды должен съесть дегустатор в каждом из блюд, чтобы величина разнообразия оказалась минимально возможной. Если ответов несколько, выведите любой из них.
В первой строке входных данных записано целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных в тесте.
Перед каждым набором в тесте записана пустая строка. Далее идёт строка, которая содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество блюд. Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит три целых числа $$$a_i$$$, $$$b_i$$$, $$$m_i$$$ ($$$0 \leq a_i, b_i \le 10^6$$$; $$$0 \le m_i \le a_i+b_i$$$) — количество грамм рыбы в $$$i$$$-м блюде, количество грамм мяса в $$$i$$$-м блюде и сколько суммарно грамм дегустатор должен съесть в $$$i$$$-м блюде.
Сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите в первой строке минимальное значение разнообразия, которое можно достичь, съев из блюда $$$i$$$ ровно $$$m_i$$$ грамм еды (для всех $$$i$$$ от $$$1$$$ до $$$n$$$).
Далее выведите $$$n$$$ строк, которые описывают способ это сделать: $$$i$$$-я строка должна содержать два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \leq x_i \leq a_i$$$; $$$0 \leq y_i \leq b_i$$$; $$$x_i+y_i=m_i$$$), где $$$x_i$$$ — сколько грамм рыбы надо съесть из $$$i$$$-го блюда, а $$$y_i$$$ — сколько грамм мяса.
Если есть несколько способов добиться минимального баланса, выведите любой из них.
5 3 10 10 2 9 9 0 10 9 1 2 3 4 1 5 1 2 3 7 2 5 6 5 4 5 5 6 1 13 42 50 5 5 7 12 3 1 4 7 3 7 0 0 0 4 1 5
1 1 1 0 0 1 0 2 0 1 1 1 2 3 2 0 4 1 5 1 8 42 2 5 7 3 1 4 3 0 0 4 1
Название |
---|