Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Try writing the speed of each gear in terms of the previous one. Don’t worry about the whole arrangement yet; just expand the first few transitions.
For an arrangement , the second gear spins at , the third at , and so on.
Everything in the middle cancels. The final speed is always , no matter what gears you put between them.
So the contraption is satisfactory exactly when the first and last gears in the chosen order have the same number of teeth.
Since the first and last positions need equal values and must be two different gears, the answer is YES iff some tooth count appears at least twice.
Let the final arrangement be
The leftmost gear has speed .
The next gear has speed
The third gear has speed
The fourth gear has speed
At this point the pattern is screaming at us: after every step, the middle gears cancel. Classic telescoping, just with gears instead of sums.
So the rightmost gear spins at
We need this to equal , so:
which means
That is the whole problem. The middle gears do absolutely nothing to the final speed. They are just standing there looking mechanical.
So Steve can make a satisfactory arrangement iff he can choose two different gears with the same number of teeth: one for the left end, one for the right end.
Therefore, we just check whether any value appears at least twice.
Algorithm
For each test case:
YES.NO.Because , we can use a tiny frequency array. A set would also work, but a frequency array is cleaner here.
Correctness Proof
Consider any arrangement .
The speed of gear is obtained by multiplying all previous ratios:
All intermediate terms cancel, leaving
So the speed of the rightmost gear is
The arrangement is satisfactory exactly when this equals , which happens exactly when .
If some tooth count appears at least twice, put two gears with that tooth count at the two ends. Then , so the final speed is , and the answer is YES.
If no tooth count appears twice, then the first and last gears must always have different tooth counts, so , meaning the final speed is not . Then no arrangement works, and the answer is NO.
Thus the algorithm is correct.
Complexity
For each test case, we scan the array once.
Memory usage is
since tooth counts are bounded by .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> freq(101, 0);
bool ok = false;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
if (freq[x] >= 2) ok = true;
}
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> freq(101, 0);
bool ok = false;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
if (freq[x] >= 2) ok = true;
}
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}