CF1861F.Four Suits
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The game of Berland poker is played as follows. There are n+1 people: n players, numbered from 1 to n , and the dealer. The dealer has a deck which contains cards of four different suits (the number of cards of each suit is not necessarily the same); the number of cards in the deck is divisible by n . The dealer gives all cards to the players, so that every player receives the same number of cards, and the whole deck is used.
After the cards are dealt, every player chooses one of four suits (independently) and discards all cards from their hand which do not belong to their chosen suit. The winner of the game is the player with the maximum number of cards left in their hand. The number of points the winner receives is x−y , where x is the number of cards in the winner's hand, and y is the maximum number of cards among all other players; everyone else receives 0 points. Note that it means that if there are multiple players with the maximum number of cards, everyone receives 0 points.
Since every player wants to maximize their odds to win, they will choose a suit with the maximum number of cards in their hand.
Monocarp is the dealer. He has already given some cards to the players; the i -th player received ai,j cards of suit j . Note that the number of cards in players' hands don't have to be the same at this moment. Monocarp has b1,b2,b3,b4 cards of suit 1,2,3,4 respectively left in his deck. He has to give them to the players so that, after all cards are dealt, every player has the same number of cards.
For each player, calculate the maximum number of points they can receive among all ways to deal the remaining cards according to the rules of the game.
输入格式
The first line of the input contains one integer n ( 2≤n≤5⋅104 ) — the number of players.
Then n lines follow. The i -th of them contains four integers ai,1,ai,2,ai,3,ai,4 ( 0≤ai,j≤106 ), where ai,j is the number of cards of the j -th suit that the i -th player currently has.
The last line contains 4 integers b1,b2,b3,b4 ( 0≤bj≤106 ), where bj is the number of cards of the j -th suit Monocarp has to deal yet.
Additional constraint on the input: it is possible to deal all of the remaining cards so that every player has the same number of cards.
输出格式
Print n integers. The i -th of them should be the maximum number of points the i -th player can get among all possible ways to deal the remaining cards.
输入输出样例
输入#1
2 3 1 1 1 1 1 1 1 2 2 0 0
输出#1
1 0
输入#2
4 0 0 0 0 0 0 0 1 2 2 0 0 0 1 0 0 3 2 3 2
输出#2
1 1 1 1
输入#3
7 2 1 0 1 0 0 2 1 4 4 1 2 0 0 1 0 1 1 0 1 0 2 1 1 0 2 0 0 15 10 10 14
输出#3
5 6 1 7 5 5 7