#6381. 「是男人就过8题——Pony.ai」NumberGameWithOneLie

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

如下定义一个在 Alice 和 Bob 之间进行的数字游戏:选中一个正整数 n , 之后 Alice 会在 1 n 之间选取一个整数 x , 每次 Bob 会选择一些区间并询问 Alice x 是不是在其中的某个区间内,一个特殊的规则就是,Alice 可以撒谎至多一次。

在游戏中,给定一个 n , 所有的问题已经由 Bob 提出,并由 Alice 一一回答。请计算 Bob 为了确定整数 x ,最少需要额外问几次。

输入格式

每个测试点最多包含 10000 组测试数据,每组数据包含 n , m (Bob 已经问的问题数),用一个空格隔开

下面紧跟 m 行,每行第一个整数 c , 之后 c [s_i, t_i], (1\le s_i \le t_i \le n) , 表示本次询问中的第 i 个区间,最后一个字符串 yesno 表示 Alice 给出的答案,假设 Alice 十分遵守规则,且 Bob 如果继续进行游戏,一定能确定 x 的值

输出格式

对于每组测试数据,输出一行包含一个整数,表示最少需要额外问的次数

样例

样例输入

1 0
2 0
2 2
1 1 1 yes
1 1 1 no
2 2
1 1 1 yes
1 1 1 yes
2 3
1 1 1 yes
1 1 1 no
1 1 1 yes

样例输出

0
3
1
0
0

数据范围与提示

1 \leq n \leq 10^{16} , 0 \leq m \leq 10 , 且 1 \leq c \leq 100

特别鸣谢楼天城和吉如一提供试题,数据。