UVa 1237 – Expert Enough
Given N pieces of data, each telling you the factory name, and the minimum and maximum prices of cars produced.
There are Q inquiries in total. Each group gives you an integer P.
Output the names of factories whose price range for produced cars includes P.
If multiple factories simultaneously meet the criteria or if none do, output "UNDETERMINED."
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains an integer T, representing the number of test cases. (T≤10) The first line of each test case contains a positive integer D, representing the number of factories. (D<10000) Following are D lines, each containing the factory name (without spaces), and the price range L and R (0 < L < R < 1000000). After that, there is a positive integer Q representing the number of inquiries. Next, there are Q lines, each containing a positive integer P representing the price of the queried car (0 < P < 1000000). | If it's known which factory produces the car, output the name of that factory. Otherwise, output "UNDETERMINED." |
| 1 4 HONDA 10000 45000 PEUGEOT 12000 44000 BMW 30000 75900 CHEVROLET 7000 37000 4 60000 7500 5000 10000 | BMW CHEVROLET UNDETERMINED UNDETERMINED |
Thought Process
Use a Pair to store the price range (L, R) for each factory, and store each pair in an array/vector.
Declare a Map where the key is the Pair received earlier, and the value is the name of the factory.
Upon receiving P, iterate through the array/vector containing L and R pairs using a for loop. If P falls within any interval defined by L and R, set the answer to the name of the factory associated with the current L and R (the value in the map). Also, initialize an integer variable called Count to count how many factories match, and increment it by 1 for each match.
If, during the for loop, it's determined that Count is already greater than 1, output "UNDETERMINED" and then break the loop. After the for loop ends, if Count = 1, output the answer that was set earlier. If Count = 0, indicating there's no factory at that price, output "UNDETERMINED."
Sample Code－ZeroJudge F446: Expert Enough
#include <iostream>
#include <map>
#include <vector>
using namespace std;
pair<int, int> rtn(int a, int b)
{
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
int T;
cin >> T;
for (int i = 0; i<T; i++)
{
int N;
cin >> N;
map<pair<int, int>, string>MAP;
vector<pair<int, int>>v;
for (int j = 0; j<N; j++)
{
string name;
int low, high;
cin >> name >> low >> high;
pair<int, int>tmp = rtn(low, high);
v.push_back(tmp);
MAP[tmp] = name;
}
int Q;
cin >> Q;
for (int j = 0; j<Q; j++)
{
int money, count = 0;
cin >> money;
string ans;
for (auto it:v)
{
if (money >= it.first && money <= it.second)
{
count++;
ans = MAP[it];
}
if (count > 1)
{
cout << "UNDETERMINED\n";
break;
}
}
if (count == 1) cout << ans << "\n";
else if (count == 0) cout << "UNDETERMINED\n";
}
}
}
//ZeroJudge F446
//Dr. SeanXD