Codeforces/1829/d.cpp
Matej Focko 0bfc6f808e
1829(cpp): solve contest
* “A. Love Story”
* “B. Blank Space”
* “C. Mr. Perfectly Fine”
* “D. Gold Rush”
* “E. The Lakes”
* “F. Forewer Winter”
* “G. Hits Different”
* “H. Don't Blame Me”

Signed-off-by: Matej Focko <me@mfocko.xyz>
2023-07-23 11:33:22 +02:00

118 lines
1.8 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <functional>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>
namespace helpers {
using namespace std;
long pow(long base, long exp) {
if (exp == 0) return 1;
long half = pow(base, exp / 2);
if (exp % 2 == 0) return half * half;
return half * half * base;
}
template <typename T>
inline void answer(const T &ans) {
cout << ans << "\n";
}
inline void yes() { cout << "YES\n"; }
inline void no() { cout << "NO\n"; }
inline void yesno(bool ans) {
if (ans) {
yes();
} else {
no();
}
}
} // namespace helpers
namespace {
using namespace std;
using namespace helpers;
bool can_split(int n, int m) {
if (n == m) {
// we already have a pile
return true;
}
if (n < m) {
// cannot make bigger pile
return false;
}
if (n % 3 != 0) {
// cannot split the pile
return false;
}
int third = n / 3;
return can_split(third, m) || can_split(2 * third, m);
}
void solve() {
int n, m;
cin >> n >> m;
yesno(can_split(n, m));
}
} // namespace
// for single test case, comment out for N test cases
// #define SINGLE
#ifdef TEST
#include "../.common/cpp/catch_amalgamated.hpp"
TEST_CASE("examples") {
CHECK(can_split(6, 4));
CHECK(can_split(9, 4));
CHECK(!can_split(4, 2));
CHECK(!can_split(18, 27));
CHECK(can_split(27, 4));
CHECK(can_split(27, 2));
CHECK(!can_split(27, 10));
CHECK(can_split(1, 1));
CHECK(can_split(3, 1));
CHECK(!can_split(5, 1));
CHECK(!can_split(746001, 2984004));
}
#else
int main(void) {
#ifdef SINGLE
solve();
#else
// for multiple test cases
int N;
std::cin >> N >> std::ws;
for (auto i = 0; i < N; ++i) {
solve();
}
#endif
return 0;
}
#endif