A - Shuffled Equation Editorial by en_translator
For beginners
- If you are new to learning programming and do not know where to start, please try Problem A "Welcome to AtCoder" from practice contest. There you can find a sample code for each language.
- Also, if you are not familiar with problems in programming contests, we recommend you to try some problems in "AtCoder Beginners Selection".
- 「C++入門 AtCoder Programming Guide for beginners (APG4b)」 is a C++ tutorial for competitive programmers. Sadly, this is only in Japanese too.
- 「Python入門 AtCoder Programming Guide for beginners (APG4bPython)」 is a Python tutorial for competitive programmers. Again, this is only in Japanese.
Solution 1: Try all permutations
The problem can be solved by trying all permutations of \(A\).
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
if(a[0]*a[1]==a[2]){cout << "Yes\n"; return 0;}
if(a[0]*a[2]==a[1]){cout << "Yes\n"; return 0;}
if(a[1]*a[0]==a[2]){cout << "Yes\n"; return 0;}
if(a[1]*a[2]==a[0]){cout << "Yes\n"; return 0;}
if(a[2]*a[0]==a[1]){cout << "Yes\n"; return 0;}
if(a[2]*a[1]==a[0]){cout << "Yes\n"; return 0;}
cout << "No\n";
return 0;
}
In case of C++, one can use a feature called next_permutation
to try all permutations.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
sort(a.begin(),a.end());
do{
if(a[0]*a[1]==a[2]){cout << "Yes\n"; return 0;}
}while(next_permutation(a.begin(),a.end()));
cout << "No\n";
return 0;
}
Solution 2: Utilize commutative law
For two integers \(A\) and \(B\) we have \(A \times B = B \times A\), so whether a[0]*a[1]==a[2]
and whether a[1]*a[0]==a[2]
are equivalent.
This helps us reduce the conditional branches to three.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
if(a[0]*a[1]==a[2]){cout << "Yes\n"; return 0;}
if(a[1]*a[2]==a[0]){cout << "Yes\n"; return 0;}
if(a[2]*a[0]==a[1]){cout << "Yes\n"; return 0;}
cout << "No\n";
return 0;
}
Solution 3: Utilize the ordering
For integers \(A,B,C \ge 1\), if \(A \times B = C\), then we have \(A \le C\) and \(B \le C\).
Thus, one can show that if the answer is Yes
, then \(A_1 \times A_2 = A_3\) holds after sorting \(A\) in ascending order.
Thus, one can sort \(A\) and check only once.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
sort(a.begin(),a.end());
if(a[0]*a[1]==a[2]){cout << "Yes\n"; return 0;}
cout << "No\n";
return 0;
}
posted:
last update: