310125: CF1786A2. Alternating Deck (hard version)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Alternating Deck (hard version)

题意翻译

Alice 有 $n$ 张牌,其中奇数牌为白色,偶数牌为黑色。 Alice 准备把牌分给 Bob 和她自己。Alice 以这样的方式发牌:一张牌给 Alice,两张牌给 Bob,三张牌给 Bob,四张牌给 Alice,五张牌给 Alice,六张牌给 Bob,以此类推。当某一步没有足够的牌时,Alice 会将所有剩余的牌发给当前玩家,且停止发牌。 给出牌的张数 $n$,求每个玩家每种牌各有多少张。 有多组数据。

题目描述

This is a hard version of the problem. In this version, there are two colors of the cards. Alice has $ n $ cards, each card is either black or white. The cards are stacked in a deck in such a way that the card colors alternate, starting from a white card. Alice deals the cards to herself and to Bob, dealing at once several cards from the top of the deck in the following order: one card to herself, two cards to Bob, three cards to Bob, four cards to herself, five cards to herself, six cards to Bob, seven cards to Bob, eight cards to herself, and so on. In other words, on the $ i $ -th step, Alice deals $ i $ top cards from the deck to one of the players; on the first step, she deals the cards to herself and then alternates the players every two steps. When there aren't enough cards at some step, Alice deals all the remaining cards to the current player, and the process stops. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1786A2/0207dd60d582562fa5c47d04eb7edab3058bc16d.png) First Alice's steps in a deck of many cards.How many cards of each color will Alice and Bob have at the end?

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 200 $ ). The description of the test cases follows The only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of cards.

输出格式


For each test case print four integers — the number of cards in the end for each player — in this order: white cards Alice has, black cards Alice has, white cards Bob has, black cards Bob has.

输入输出样例

输入样例 #1

5
10
6
17
8
1000000

输出样例 #1

3 2 2 3
1 0 2 3
6 4 3 4
2 1 2 3
250278 249924 249722 250076

Input

题意翻译

Alice 有 $n$ 张牌,其中奇数牌为白色,偶数牌为黑色。 Alice 准备把牌分给 Bob 和她自己。Alice 以这样的方式发牌:一张牌给 Alice,两张牌给 Bob,三张牌给 Bob,四张牌给 Alice,五张牌给 Alice,六张牌给 Bob,以此类推。当某一步没有足够的牌时,Alice 会将所有剩余的牌发给当前玩家,且停止发牌。 给出牌的张数 $n$,求每个玩家每种牌各有多少张。 有多组数据。

Output

题目大意:
Alice 有 $n$ 张牌,牌面数字交替出现,从一张白色的奇数牌开始,然后是黑色的偶数牌,依此类推。Alice 按照一定的规则将牌分给自己和 Bob:先给自己一张,然后给 Bob 两张,接着给 Bob 三张,再给自己四张,然后给自己五张,给 Bob 六张,如此循环。在每一步,Alice 从牌堆顶部取 $i$ 张牌分给一个玩家;第一步时,她给自己发牌,然后每两步交替一次玩家。当某一步没有足够的牌时,Alice 将所有剩余的牌发给当前玩家,并停止发牌。

输入输出数据格式:
输入包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 200$)。每个测试用例只有一行,包含一个整数 $n$($1 \le n \le 10^6$)——牌的数量。

对于每个测试用例,按顺序输出四个整数——每个玩家最后拥有的各种牌的数量:Alice 的白色牌数量,Alice 的黑色牌数量,Bob 的白色牌数量,Bob 的黑色牌数量。题目大意: Alice 有 $n$ 张牌,牌面数字交替出现,从一张白色的奇数牌开始,然后是黑色的偶数牌,依此类推。Alice 按照一定的规则将牌分给自己和 Bob:先给自己一张,然后给 Bob 两张,接着给 Bob 三张,再给自己四张,然后给自己五张,给 Bob 六张,如此循环。在每一步,Alice 从牌堆顶部取 $i$ 张牌分给一个玩家;第一步时,她给自己发牌,然后每两步交替一次玩家。当某一步没有足够的牌时,Alice 将所有剩余的牌发给当前玩家,并停止发牌。 输入输出数据格式: 输入包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 200$)。每个测试用例只有一行,包含一个整数 $n$($1 \le n \le 10^6$)——牌的数量。 对于每个测试用例,按顺序输出四个整数——每个玩家最后拥有的各种牌的数量:Alice 的白色牌数量,Alice 的黑色牌数量,Bob 的白色牌数量,Bob 的黑色牌数量。

加入题单

上一题 下一题 算法标签: