import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC253181. Envy-freeness
描述
Fair division of goods among competing agents is a fundamental problem in Economics and Computer Science. There is a set 
of 
goods and the goal is to allocate goods among 
agents in a fair way. When can an allocation be considered "fair" ? One of the most well-studied notions of fairness is Envy-freeness.
An allocation is a partition of into disjoint subsets 
where 
is the set of goods given to agent 
. Every agent has a value associated with each good 
,which represented as 
. And every agent values a set of goods 
as the sum of the values of the goods in , which represented as %20%3D%20%5Csum_%7Bj%5Cin%20S%7D%20w_%7Bi%2Cj%7D)
.
Then we define that agent envies agent if values 
more than , i.e. %3EW_i(X_i))
.
An allocation is "envy-free"(represented as EF) if no agent envies another, however, it's not always exists.
Then we define "envy-free up to any good" (represented as EFX) : In an EFX allocation, agent may envy agent , however this envy would vanish as soon as any good is removed from . i.e. if , then %5Cle%20W_i(X_i))
. However, an EFX allocation may not exist too.
Then we define "envy-free up to one good" (represented as EF1) : In an EF1 allocation, agent may envy agent , however this envy would vanish as soon as a good is removed from . i.e. if , then %5Cle%20W_i(X_i))
.
Note that in EFX and EF1, no good is really removed.
Today Colin and Eva wants to study this problem. To simplify the problem, we considered there only exists two agents: Colin (agent
) and Eva (agent 
). At first neither of them had any goods. Then there comes operations (allocate goods) , each operation will provide three values 
to represent one good , which means the value of this good in Colin's perspective ( i.e. 
), the value of this good in Eva's perspective ( i.e. 
) , and who it was allocated to (i.e. if 
, then it was allocated to Colin, otherwise it was allocated to Eva)
They want you to tell them, after each operation, what is the highest situation for the current allocation?
We define the priority as: "envy-free" is the highest, "envy-free up to any good" is the second, "envy-free up to one good" is the third, and if none of the three conditions are satisfied, the worst is "envy".
An allocation is a partition of
Then we define that agent
An allocation is "envy-free"(represented as EF) if no agent envies another, however, it's not always exists.
Then we define "envy-free up to any good" (represented as EFX) : In an EFX allocation, agent
Then we define "envy-free up to one good" (represented as EF1) : In an EF1 allocation, agent
Note that in EFX and EF1, no good is really removed.
Today Colin and Eva wants to study this problem. To simplify the problem, we considered there only exists two agents: Colin (agent
They want you to tell them, after each operation, what is the highest situation for the current allocation?
We define the priority as: "envy-free" is the highest, "envy-free up to any good" is the second, "envy-free up to one good" is the third, and if none of the three conditions are satisfied, the worst is "envy".
输入描述
The first line contains one integerEach of the followinglines contains three integers
and
输出描述
After each operation, output a single line with:If the current allocation is "envy-free", then output "EF";Otherwise if the current allocation is "envy-free up to any good", then output "EFX";Otherwise if the current allocation is "envy-free up to one good", then output "EF1";Otherwise output "E".
示例1
输入:
5 5 2 0 5 2 1 2 2 0 9 2 1 9 2 1
输出:
EFX EF EFX EF1 E