Guess Your Way Out! II

题意翻译

问题描述 Amr 买来了一个新的游戏，名叫 Guess Your Way Out! II。这个游戏需要你找到迷宫的出口。迷宫是一个高度为h的完全二叉树，一开始你在根节点，迷宫的唯一出口在某一个叶子节点处。 这棵树的节点编号是这样规定的，根节点编号为 $1$，编号为 $i$ 的节点的左儿子编号为 $2\times i$，右儿子编号为 $2 \times i + 1$。每个节点的层次是这样定义的，根节点在第一层，儿子节点的层数在它的父亲节点的基础上增加 $1$。 一开始玩家并不知道迷宫的出口在哪里，于是就只能向游戏提问，每次的提问都是这样的：“出口节点的层数为 $i$ 的祖先节点的编号是否在区间 $[L,R]$ 内？”这时游戏会给出回答“是”或“不是”，不过这个游戏又是会出错，就会给出错误的回答。 Amr 已经进行了若干次提问，并记录下了每次的提问和回答，他想知道，游戏是否一定给出过错误的回答，通过这些答案能不能唯一确定出口的位置。于是 Amr 就来求助于你了。 输入格式 第一行两个整数 $h$, $q$，表示完全二叉树迷宫的总层数和 Amr 的提问次数。 接下来 $q$ 行，每行四个整数 $i$, $L$, $R$, $ans$，表示 Amr 的一次提问和游戏给出的回答（$ans=1$表示“是”，$ans=0$表示“不是”）。 输出格式 如果游戏一定给出过错误的回答，输出“Game cheated!”，不含引号； 如果有了这些问答可能的出口仍然有多个，输出“Data not sufficient!”，不含引号； 否则输出出口节点唯一可能的编号。

题目描述

Amr bought a new video game "Guess Your Way Out! II". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height $ h $ . The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node. Let's index all the nodes of the tree such that - The root is number $ 1 $ - Each internal node $ i $ ( $ i<=2^{h-1}-1 $ ) will have a left child with index = $ 2i $ and a right child with index = $ 2i+1 $ The level of a node is defined as $ 1 $ for a root, or $ 1 $ + level of parent of the node otherwise. The vertices of the level $ h $ are called leaves. The exit to the maze is located at some leaf node $ n $ , the player doesn't know where the exit is so he has to guess his way out! In the new version of the game the player is allowed to ask questions on the format "Does the $ ancestor(exit,i) $ node number belong to the range $ [L,R] $ ?". Here $ ancestor(v,i) $ is the ancestor of a node $ v $ that located in the level $ i $ . The game will answer with "Yes" or "No" only. The game is designed such that it doesn't always answer correctly, and sometimes it cheats to confuse the player!. Amr asked a lot of questions and got confused by all these answers, so he asked you to help him. Given the questions and its answers, can you identify whether the game is telling contradictory information or not? If the information is not contradictory and the exit node can be determined uniquely, output its number. If the information is not contradictory, but the exit node isn't defined uniquely, output that the number of questions is not sufficient. Otherwise output that the information is contradictory.

输入输出格式

输入格式

The first line contains two integers $ h,q $ ( $ 1<=h<=50 $ , $ 0<=q<=10^{5} $ ), the height of the tree and the number of questions respectively. The next $ q $ lines will contain four integers each $ i,L,R,ans $ ( $ 1<=i<=h $ , $ 2^{i-1}<=L<=R<=2^{i}-1 $ , ), representing a question as described in the statement with its answer ( $ ans=1 $ if the answer is "Yes" and $ ans=0 $ if the answer is "No").

输出格式

If the information provided by the game is contradictory output "Game cheated!" without the quotes. Else if you can uniquely identify the exit to the maze output its index. Otherwise output "Data not sufficient!" without the quotes.

输入输出样例

输入样例 #1

3 1
3 4 6 0

输出样例 #1

7

输入样例 #2

4 3
4 10 14 1
3 6 6 0
2 3 3 1

输出样例 #2

14

输入样例 #3

4 2
3 4 6 1
4 12 15 1

输出样例 #3

Data not sufficient!

输入样例 #4

4 2
3 4 5 1
2 3 3 1

输出样例 #4

Game cheated!

说明

Node $ u $ is an ancestor of node $ v $ if and only if - $ u $ is the same node as $ v $ , - $ u $ is the parent of node $ v $ , - or $ u $ is an ancestor of the parent of node $ v $ . In the first sample test there are $ 4 $ leaf nodes $ 4,5,6,7 $ . The first question says that the node isn't in the range $ [4,6] $ so the exit is node number $ 7 $ . In the second sample test there are $ 8 $ leaf nodes. After the first question the exit is in the range $ [10,14] $ . After the second and the third questions only node number $ 14 $ is correct. Check the picture below to fully understand.