问题 21753 --奇偶游戏

21753: 奇偶游戏

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 7
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][400kb]

题目描述

     不时地,你和你的朋友玩下列游戏:你的朋友写下一个由许多“1”和“0”组成的数字序列。你从中选一个连续的子序列(假如这个序列从第3个数字开始到第5个数字,包含3,5在内),并问他这个序列中所含的“1”的个数是奇数还是偶数。你的朋友回答了你的这个问题。你可能接着问他另一个子序列如此之类的问题。你的任务是猜测整个数字序列。
你怀疑你的朋友的某些答案不正确,并且你想证实他在撒谎。因此你决定编一个程序来帮你判断,该程序将接收到一系列你所提的问题以及从你的朋友处获得的回答,该程序的目的是为了找到第一个可能错误的回答:即存在某个序列,能满足以前的所有问题的回答,但不存在任何一个序列能满足当前的回答。

输入

       输入文件PARITY.IN的首行包括一个数,代表0和1序列的长度,该长度小于等于1000000000。在第二行,有一个正整数,代表问题以及它们的回答的个数,此数要小于等于5000。剩下的行具体阐述问题和回答。每行包括一个问题和对它的回答:2个整数(选中子序列中第一个和最后一个数字的位置)和一个单词,即“EVEN”或是“odd”(这个回答就是“1”在该选中序列中的数量的奇偶性,even’表示偶数,‘odd’表示奇数)。

输出

      在输出文件PARITY.OUT中仅有一行,包括一个整数X。数字X表示存在满足前X个奇偶条件的某一序列,但不存在序列能满足前X+1个条件。如果存在一个序列的个数能满足所有给出的条件,那么X就是所问的全部问题的个数。

样例输入

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 even

样例输出

3

提示

来源

[提交][状态]