UVa 11936 – The Lazy Lumberjacks
Once upon a time, in a distant forest, there was a group of lazy lumberjacks. Because they were too lazy to cut down trees, they always tried to find ways to slack off. Their foreman, always trying to get them to work seriously, attempted various methods. After many discussions, the foreman and the lumberjacks reached an agreement. The lumberjacks said they would work, but only if the forest assigned to each person was in the shape of a triangle. If it was any other shape, they would go on strike. Since the lumberjacks were very lazy and cunning, they convinced the foreman to let them determine the lengths and positions of the sides of the forest they were supposed to work in. As a result, the lumberjacks kept passing on lengths of sides that could not form triangular forests to slack off and rest. After a while, the foreman noticed something was wrong and decided to write a program to verify the input from each lumberjack. Now, when the lumberjacks pass incorrect numbers, they will be fined $1000 (more than a day's wages). Your job is to write a program to help the foreman.
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The first line of input contains an integer N (2 <= N <= 20), indicating the number of test cases. Following are N lines, each containing three integers representing the lengths of the sides of the forest given by the lumberjacks. | For each test case: If a triangle can be made, output "OK." Otherwise, output "Wrong!!". |
6 1 2 3 3 2 5 3 4 5 6 6 1 3 3 3 7 3 10 | Wrong!! Wrong!! OK OK OK Wrong!! |
Thought Process
To determine if the lengths of any two sides sum up to be greater than the third side, you can sort the three numbers and check if the sum of the two smaller numbers is greater than the largest side. This way, you won't need to check every possible combination.
Sample Code-ZeroJudge E614: The Lazy Lumberjacks
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
vector<int>num;
for (int j = 0; j<3; j++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
sort(num.begin(), num.end());
if (num[0] + num[1] > num[2]) cout << "OK\n";
else cout << "Wrong!!\n";
}
}
//ZeroJudge E614
//Dr. SeanXD