TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3986
  • 题目
  • P3986 [Usaco2004 Mar]说谎的奶牛
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    兽群中总是有一些麻烦制造者.约翰知道他的N(1≤N≤100)头奶牛中可能有一头总是说谎,其他的总是说真话.他想快速的找出这个麻烦制造者.为了实现这个目标,他一个一个的问这些奶牛Q(1≤Q≤1000)个关于它们吃草的简单问题(虽然大多数奶牛是诚实的但它们依旧很笨只能懂得一些关于食物的话题).

    他将这些问题用以下的格式写了下来:

    牛4说:牛5比牛10吃得多

    牛6说:牛10比牛7吃得多

    牛3说:牛2比牛6吃得多

    牛1说:牛7比牛5吃得多

    从这个例子中不难看出说谎的奶牛只有可能是4,6,1.你的任务是确定可能说谎的奶牛的个

    数.可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾.

    输入格式

    兽群中总是有一些麻烦制造者.约翰知道他的N(1≤N≤100)头奶牛中有一头总是说谎,其他的总是说真话.他想快速的找出这个麻烦制造者.为了实现这个目标,他一个一个的问这些奶牛Q(1≤Q≤1000)个关于它们吃草的简单问题(虽然大多数奶牛是诚实的但它们依旧很笨只能懂得一些关于食物的话题).

    他将这些问题用以下的格式写了下来:

    牛4说:牛5比牛10吃得多

    牛6说:牛10比牛7吃得多

    牛3说:牛2比牛6吃得多

    牛1说:牛7比牛5吃得多

    从这个例子中不难看出说谎的奶牛只有可能是4,6,1.你的任务是确定可能说谎的奶牛的个

    数.可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾.

    输出格式

    仅一行一个整数即可能说谎的奶牛的头数.

    样例输入

    3 4
    3 1 2
    1 3 1
    1 3 2
    2 2 1

    样例输出

    2

    提示

    样例说明
    3头奶牛给出了4个回答.奶牛1说3>1,3>2,奶牛2说2>1,奶牛3说1>2.当然“>”的意思是“吃得多”. 显然,2号和3号的话是矛盾的.它们都有可