0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。
2641. Great World of Goo
单点时限: 4.0 sec
内存限制: 256 MB
The game is built around the idea of creating large structures using balls of goo. It is based on the prototype game Tower of Goo developed for Kyle Gabler’s rapid game prototyping Experimental Gameplay Project. The game is divided into five chapters, each containing several levels. Each level has its own graphic and musical theme, giving it unique atmosphere, similar in style to Tim Burton’s film designs. There is also a bonus meta-game called World of Goo Corporation, where the objective is to build the highest tower using goo balls which the player collected through the course of the game. Players from all over the world can compete, as the height of the tower and number of goo balls used are being constantly uploaded to the 2D Boy server.
–Wikipedia
As mentioned above, World of Goo is an excellent independent game. Personally I like playing it rather than Plants vs. Zombies though both of them are great.
Let’s consider a simplified version of “Fisty Bog” in Chapter One (Figure 1).
Ignore the part before the red line, as it’s given by the system initially. The following goo balls make the bridge using regular triangles, numbered from 1, beginning from left to right. To ensure the bridge formed strictly horizontal, we place a light goo ball every three triangles, and in this problem we don’t need to care about those balls.
From the figure we know that, some triangles are more dangerous during the construction process. For that case, goo balls want to be placed in different triangles. Risky goo balls want to be placed on the triangle more dangerous while others want safer ones. Now, my question comes, how many number of solutions exist when all goo balls are used and all wills are satisfied.
输入格式
The first line: and integer k (k<=15) indicates the number of test case;
For each test case:
First line: n and m, 0<m,n<=500 , n represents the number of goo balls, m represents the number of wills;
Line 2…m+1:
Each line is consist of integers K A1 B1 A2 B2 … AK BK P C1 D1 C2 D2 … CP DP, represents a restriction. That means the goo ball(s) numbered between A1 and B1 (inclusive), or between A2 and B2 (inclusive) or … or between Ak and Bk (inclusive) wants to be placed at triangle(s) number between C1 and D1 (inclusive), or between C2 and D2 (inclusive) or … or between Ck and Dk (inclusive). Two restrictions may be the same or partly same. Every restriction is legal.
输出格式
For each test case, output one line with following rules.
Because in the world of goo, they only used 16bit system, which means the max number can be stored in one unit is 2^16-1. So when the number of solutions exceeds 2^16-1, we must output “OVERFLOW!”, otherwise, output the accurate number of solutions.
样例
Input
3 6 1 1 1 6 1 1 4 6 1 1 1 6 1 1 3 10 1 1 1 10 1 1 8
Output
720 0 OVERFLOW!
题目标签