1218. Episode N-th: The Jedi Tournament

Time limit: 1.0 second
Memory limit: 64 MB
Decided several Jedi Knights to organize a tournament once. To know, accumulates who the largest amount of Force. Brought each Jedi his lightsaber with him to the tournament. Are different the lightsaber, and Jedi different are. Three parameters there are: length of the saber, Force of the Jedi and how good the Light side of the Force the Jedi can use. If in at least two parameters one Jedi than the other one stronger is, wins he. Is not possible a draw, because no Jedi any equal parameter may have. If looses a Jedi, must leave the tournament he.
To determine, which Jedi the tournament can win, your program is. Can win the tournament a Jedi, if at least one schedule for the tournament possible is, when the last one remains he on the tournament, not looses any match. For example, if Anakin stronger than Luke by some two parameters is, and Luke stronger than Yoda by some two parameters is, and Yoda stronger than Anakin, exists in this case a schedule for every Jedi to win the tournament.

Input

In the first line there is a positive integer N ≤ 200, the total number of Jedi. After that followN lines, each line containing the name of the Jedi and three parameters (length of the lightsaber, Force, Light side in this order) separated with a space. The parameters are different integers, not greater than 100000 by the absolute value. All names are sequences of not more than 30 small and capital letters.

Output

Your program is to output the names of those Jedi, which have a possibility to win the tournament. Each name of the possible winner should be written in a separate line. The order of the names in the output should correspond to the order of their appearance in the input data.

Sample

input output
5
Solo 0 0 0
Anakin 20 18 30
Luke 40 12 25
Kenobi 15 3 2
Yoda 35 9 125
Anakin
Luke
Yoda
Problem Author: Leonid Volkov
Problem Source: The Seventh Ural State University collegiate programming contest
Difficulty: 338
 
题意:给出n个人,每个人有三个属性,一个人A比另一个人B优当且仅当A有至少两种属性不小于B的这两种属性,不存在两个人平局。问谁可能笑到最后?
注意,A优于B,B优于C,但C也可能优于A,此时A、B、C都可能笑到最后。
分析:就是说给出n个点,让你建出很多有向边I,j代表i优于j,最后问有多少点能访问全部点
floyd就好
 #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define Rep(i, t) for(int i = (0); i < (t); i++)
#define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
#define rep(i, x, t) for(int i = (x); i < (t); i++)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name) {
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} inline int Getint() {
int Ret = ;
char Ch = ' ';
while(!(Ch >= '' && Ch <= '')) Ch = getchar();
while(Ch >= '' && Ch <= '') {
Ret = Ret*+Ch-'';
Ch = getchar();
}
return Ret;
} const int N = ;
struct JediType {
string Name;
int a, b, c; inline void Read() {
cin>>Name;
scanf("%d%d%d", &a, &b, &c);
} inline bool operator >(const JediType &T) const {
return ((a >= T.a)+(b >= T.b)+(c >= T.c)) >= ;
}
} Jedi[N];
int n;
bool F[N][N]; inline void Input() {
scanf("%d", &n);
For(i, , n) Jedi[i].Read();
} inline void Solve() {
For(i, , n)
For(j, , n)
if(Jedi[i] > Jedi[j])
F[i][j] = ; For(k, , n)
For(i, , n)
For(j, , n)
F[i][j] |= F[i][k]&F[k][j]; For(i, , n) {
bool Flag = ;
For(j, , n)
if(!F[i][j]) {
Flag = ;
break;
}
if(Flag) cout<<Jedi[i].Name<<endl;
}
} int main() {
#ifndef ONLINE_JUDGE
SetIO("C");
#endif
Input();
Solve();
return ;
}

最新文章

  1. C#设计模式系列:建造者模式(Builder)
  2. 时间戳转化为日期TimeStamp转NSDate转NSString
  3. Something about Wake-sleep
  4. JAVA抽象方法,接口
  5. object实现小老鼠交互
  6. Array基本操作
  7. Spring源码追踪4——SpringMVC View解析
  8. js控制TR的显示隐藏
  9. C#中Delegate
  10. Google Accounts,OpenID,OAuth
  11. QTREE 树链剖分---模板 spoj QTREE
  12. map 树木品种
  13. [Codeforces Round #247 (Div. 2)] A. Black Square
  14. InstallShield 工程类型MSI 使用过程中碰到的问题及解决方法。
  15. lo dash api
  16. 说说API的防重放机制
  17. JAVA和Android的回调机制
  18. java异步编程降低延迟
  19. 开发中清除css加载的缓存使用
  20. C++ 退出双层for循环,解决 break、return、continue无法实现问题

热门文章

  1. openCV的基本操作
  2. ubuntu 修改保存报错E37:No write since last change(add ! to override)的解决方法
  3. XmlWriter/XmlReader示例代码
  4. 《ASP.NET MVC4 WEB编程》学习笔记------Web API 续
  5. object-c 继承多态 动态数据类型
  6. Java for LeetCode 140 Word Break II
  7. bootstrap学习总结1
  8. Find them, Catch them(poj 1703)
  9. (五)转载:通用定时器PWM输出
  10. Android实现支持缩放平移图片