cpp optimum soultion for : Problem Solving time limit per test2 seconds memory limit per…
- User
cpp optimum soultion for : Problem Solving time limit per test2 seconds memory limit per test512 megabytes Jane has decided to solve a list of n problems on Codeforces. The i -th problem in her list has difficulty di , and the last problem in the list is the hardest one (for every problem j<n , dj<dn ).
Jane's problem-solving skill is some integer x (unknown to you). If a problem's difficulty is greater than x , then Jane cannot solve it, otherwise she can solve it.
Jane has solved all problems form the list, except for the last one — she found out that it was too difficult for her. Can you uniquely determine the value of x — Jane's problem solving skill?
Input The first line contains one integer t (1≤t≤1000 ) — the number of test cases.
Each test case consists of two lines:
the first line contains one integer n (2≤n≤50 ) — the number of problems; the second line contains n integers d1,d2,…,dn (1≤di≤50 ). Additional constraint on the input: in every test case, the last problem is more difficult than every other problem (i. e. dn>dj for every j<n ). This means that at least one possible value of x exists.
Output For each test case, print one line:
if you can determine the value of x uniquely, print x ; otherwise, print Ambiguous. The checking program is case-sensitive, so if you print ambiguous or AMBIGUOUS, your answer will be considered wrong. Example InputCopy 3 5 1 2 3 4 5 8 8 8 5 3 4 6 8 12 4 3 3 3 4 OutputCopy 4 Ambiguous 3 Note In the second test case of the example, the value of x could be 11 , but it also could be 10 (other possible values for x also exist).
- Assistant
To solve the problem of determining Jane's problem-solving skill ( x ), we can follow these steps:
-
Understand the Requirements:
- Jane has solved all the first ( n-1 ) problems, meaning her skill ( x ) must be at least as great as the hardest among these ( n-1 ) problems.
- She couldn't solve the last problem, which means ( x ) must be strictly less than the difficulty of the last problem.
-
Determine ( x ):
- Let ( m ) be the maximum difficulty among the first ( n-1 ) problems.
- Let ( l ) be the difficulty of the last problem.
- ( x ) must satisfy ( m \leq x < l ).
- If ( m = l - 1 ), there is only one possible value for ( x ), which is ( m ).
- If ( m < l - 1 ), multiple possible values for ( x ) exist, making it ambiguous.
-
Implementation:
- For each test case, compute ( m ) and ( l ).
- Check the condition ( m = l - 1 ). If true, print ( m ); otherwise, print "Ambiguous".
Here's the C++ implementation based on the above reasoning:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; vector<int> d(n); for(auto &x:d) cin>>x; int m = *max_element(d.begin(), d.begin()+n-1); int l = d[n-1]; if(m == l-1){ cout<<m<<"\n"; } else{ cout<<"Ambiguous\n"; } } } -