공평한 분배 timer 1s memory 1024MB

An entrepreneur has N blueprints, each describing a type of building. Each blueprint specifies the building’s height through two integers G and R.

 G: Height of the ground floor. It can be zero, indicating that the building has no ground floor.

 R: Height of each residential floor. Each building has at least one residential floor.

The entrepreneur wants to distribute all of these blueprints among their two children Alice and Bob. Each child will build exactly one building from each blueprint allocated to them, choosing the number of residential floors for each building.

The entrepreneur wants to avoid showing favoritism towards either child, so they are looking for a fair distribution of the blueprints. They decided that a fair distribution is one in which it is possible to construct the buildings in such a way that the sum of the heights of the buildings constructed by each child is the same. Can you tell whether a fair distribution exists?

Consider the following example for N = 3 blueprints: 

1. G = 1 and R = 1 (possible heights are 2, 3, 4, \dots);

2.  G = 0 and R = 3 (no ground floor, possible heights are 3, 6, 9, \dots);

3.  G = 2 and R = 1 (possible heights are 3, 4, 5, \dots).

In this case a possible fair distribution is assigning the second blueprint to Alice and the rest to Bob. Even though Alice receives a single blueprint while Bob receives two, they may construct two residential floors on the first building type (height 3), two residential floors on the second (height 6), and one residential floor on the third (height 3). In this way, the sum of the heights of the buildings constructed by each child would be 6.