Envy-freeness

题号：NC253181
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Fair division of goods among competing agents is a fundamental problem in Economics and Computer Science. There is a set $M$ of $m$ goods and the goal is to allocate goods among $n$ 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 $M$ into disjoint subsets $X_1, \dots , X_n$ where $X_i$ is the set of goods given to agent $i$ . Every agent $i$ has a value associated with each good $j$ ,which represented as $w_{i,j}$ . And every agent values a set of goods $S$ as the sum of the values of the goods in $S$ , which represented as $W_i(S) = \sum_{j\in S} w_{i,j}$ .

Then we define that agent $i$ envies agent $j$ if $i$ values $X_j$ more than $X_i$ , i.e. $W_i(X_j)>W_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 $i$ may envy agent $j$ , however this envy would vanish as soon as any good is removed from $X_j$ . i.e. if $W_i(X_j)>W_i(X_i)$ , then $\forall g \in X_j,W_i(X_j\setminus g)\le W_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 $i$ may envy agent $j$ , however this envy would vanish as soon as a good is removed from $X_j$ . i.e. if $W_i(X_j)>W_i(X_i)$ , then $\exists g \in X_j,W_i(X_j\setminus g)\le W_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 $1$ ) and Eva (agent $2$ ). At first neither of them had any goods. Then there comes $m$ operations (allocate $m$ goods) , each operation will provide three values $c_i,e_i, b_i=0/1$ to represent one good , which means the value of this good in Colin's perspective ( i.e. $W_{1,i}=c_i$ ), the value of this good in Eva's perspective ( i.e. $W_{2,i}=e_i$ ) , and who it was allocated to (i.e. if $b_i=0$ , 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".

输入描述:

The first line contains one integer 

Each of the following  lines 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

输入

复制

输出

复制

EFX
EF
EFX
EF1
E