QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #862309 | #9981. Collatz Conjecture | ucup-team3584# | TL | 1ms | 3712kb | C++23 | 1.3kb | 2025-01-18 23:47:34 | 2025-01-18 23:47:51 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
inline unsigned long long nextState(unsigned long long x, unsigned long long A, unsigned long long B) {
if (x % A == 0ULL) {
return x / A;
} else {
return x + B;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll A, B, n;
cin >> A >> B >> n;
auto tortoise = (unsigned long long)n;
auto hare = (unsigned long long)n;
bool foundCycle = false;
const int MAX_STEPS = 9000;
for (int step = 1; step <= MAX_STEPS; step++) {
tortoise = nextState(tortoise, A, B);
hare = nextState(hare, A, B);
hare = nextState(hare, A, B);
if (tortoise == hare) {
if (tortoise == (unsigned long long)n) {
foundCycle = true;
}
break;
}
}
cout << (foundCycle ? "Yes\n" : "No\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
7 2 1 1 2 1 2 2 1 3 2 1 100 314 159 265 314 159 2653 314 159 26535
output:
Yes Yes No No Yes Yes No
result:
ok 7 tokens
Test #2:
score: -100
Time Limit Exceeded
input:
100000 123 457 1 123 457 2 123 457 3 123 457 4 123 457 5 123 457 6 123 457 7 123 457 8 123 457 9 123 457 10 123 457 11 123 457 12 123 457 13 123 457 14 123 457 15 123 457 16 123 457 17 123 457 18 123 457 19 123 457 20 123 457 21 123 457 22 123 457 23 123 457 24 123 457 25 123 457 26 123 457 27 123 4...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...