Олимпиадный тренинг

Задача . A2. Чередующаяся колода (сложная версия)


Задача

Темы: реализация *800

Это сложная версия задачи. В этой версии карты бывают двух цветов.

У Алисы есть \(n\) карт, каждая карта либо черная, либо белая. Карты уложены в колоду, причем цвета карт чередуются, начиная с белой. Алиса раздает карты себе и Бобу, забирая по несколько карт сразу сверху стопки в таком порядке: одну карту себе, две карты Бобу, три карты Бобу, четыре карты себе, пять карт себе, шесть карт Бобу, семь карт Бобу, восемь карт себе и т. д.. Иными словами, на \(i\)-м шаге Алиса отдает верхние \(i\) карт из колоды одному из игроков, при этом на первом шаге она отдает карты себе, а затем чередует игроков через каждые два шага. Если на очередном шаге в колоде недостаточно карт, Алиса выдает все оставшиеся карты текущему игроку и процесс заканчивается.

Первые шаги Алисы для колоды из большого числа карт.

Сколько карт каждого цвета окажется у Алисы и Боба в конце?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 200\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 10^6\)) — количество карт.

Выходные данные

Для каждого набора входных данных выведите четыре числа — количество карт в конце у игроков — в таком порядке: белые карты у Алисы, черные карты у Алисы, белые у Боба, черные у Боба.


Примеры
Входные данныеВыходные данные
1 5
10
6
17
8
1000000
3 2 2 3
1 0 2 3
6 4 3 4
2 1 2 3
250278 249924 249722 250076

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя