bzoj#P3373. [USACO 2004 Mar]Lying Livestock 说谎的牲畜
[USACO 2004 Mar]Lying Livestock 说谎的牲畜
题目描述
兽群中总是有一些麻烦制造者。约翰知道他的 头奶牛中有一头总是说谎,其他的总是说真话。他想快速的找出这个麻烦制造者。为了实现这个目标,他一个一个的问这些奶牛 个关于它们吃草的简单问题(虽然大多数奶牛是诚实的但它们依旧很笨只能懂得一些关于食物的话题)。
他将这些问题用以下的格式写了下来:
- 牛 说:牛 比牛 吃得多;
- 牛 说:牛 比牛 吃得多;
- 牛 说:牛 比牛 吃得多;
- 牛 说:牛 比牛 吃得多。
从这个例子中不难看出说谎的奶牛只有可能是 。你的任务是确定可能说谎的奶牛的个数。可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾。
输入格式
第 行:两个用空格分开的整数 和 。
第 到 行:每一行描述一个问题,由 个用空格隔开的整数 表示,意思是 说 牛吃的比 牛多。一头奶牛可能回答多次。
输出格式
仅一行一个整数即可能说谎的奶牛的头数。
3 4
3 1 2
1 3 1
1 3 2
2 2 1
2
头奶牛给出了 个回答。奶牛 说 、,奶牛 说 ,奶牛 说 。当然“>”的意思是“吃得多”。显然, 号和 号的话是矛盾的。它们都有可能说谎。如果 号说谎则 都没说谎,那是不可能的。所以, 号说的一定是实话。
数据范围与约定
对于 的数据,,。
题目来源
Orange