Codeforces Round 734 (Div. 3) |
---|
Закончено |
Поликарпу необходимо заплатить на кассе ровно $$$n$$$ бурлей. При этом у Поликарпа есть монеты двух номиналов: $$$1$$$ бурль и $$$2$$$ бурля. Поликарп одинаково любит монеты обоих номиналов. Поэтому он не может отдать намного больше монет одного номинала, чем другого.
Таким образом, Поликарп хочет минимизировать разницу между количеством отданных монет номиналом $$$1$$$ бурль и номиналом $$$2$$$ бурля. Помогите ему, определив два целых неотрицательных числа $$$c_1$$$ и $$$c_2$$$ — количество монет номиналом $$$1$$$ бурль и количество монет номиналом $$$2$$$ бурля соответственно — таких, что такое количество монет в сумме составляет ровно $$$n$$$ бурлей (то есть $$$c_1 + 2 \cdot c_2 = n$$$), а абсолютная величина разности $$$c_1$$$ и $$$c_2$$$ минимальна (то есть минимизируйте $$$|c_1-c_2|$$$).
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки. Строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — сумма в бурлях, которую должен заплатить Поликарп.
Для каждого набора входных данных в отдельной строке выведите искомые два числа — $$$c_1$$$ и $$$c_2$$$ ($$$c_1, c_2 \ge 0$$$) — разделённые пробелом, где $$$c_1$$$ — количество монет номиналом $$$1$$$ и $$$c_2$$$ — количество монет номиналом $$$2$$$. Если оптимальных решений несколько, выведите любое из них.
6 1000 30 1 32 1000000000 5
334 333 10 10 1 0 10 11 333333334 333333333 1 2
В первом наборе данных примера ответ имеет вид «334 333». Сумма номиналов монет равна $$$334 \cdot 1 + 333 \cdot 2 = 1000$$$, при этом $$$|334 - 333| = 1$$$. При этом невозможно добиться того, чтобы $$$|c_1 - c_2| = 0$$$, поскольку тогда $$$c_1 = c_2$$$, значит $$$c_1 \cdot 1 + c_1 \cdot 2 = 1000$$$, но тогда $$$c_1$$$ не будет являться целым числом.
Во втором наборе данных примера ответ имеет вид «10 10». Действительно, с одной стороны, $$$10 \cdot 1 + 10 \cdot 2 = 30$$$, с другой стороны, $$$|10 - 10| = 0$$$, меньше $$$0$$$ абсолютная величина любого числа быть не может.
Название |
---|