USACO 2019 December Contest Silver Division - MooBuzz

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can binary search the result. For each number, we apply inclusion-exclusion principle to find out if there are at least as many numbers as \(n\) if we subtract from the current value the numbers divisible by \(3\) or \(5\). Alternatively, you can also solve it using a closed form formula determined by the same aforementioned principle.

Source code

The source code in C++ can be seen below.

#include <fstream>
using namespace std;
ifstream cin("moobuzz.in");
ofstream cout("moobuzz.out");
int check(int x) {
    return x - (x / 3 + x / 5 - x / 15);
}
int main() {
    long long n;
    cin >> n;
    long long l = 0, r = 4e9;
    while(l <= r) {
        long long mid = (l + r) / 2;
        if(mid % 3 != 0 && mid % 5 != 0 && check(mid) == n) {
            cout << mid << endl;
            return 0;
        }
        if(check(mid) > n) {
            r = mid - 1;
        } 
        else {
            l = mid + 1;
        }
    }
    for(int i = r - 10; i <= r + 10; i ++) {
        if(check(i) == n && i % 3 != 0 && i % 5 != 0) {
            cout << i;
            break;
        }
    }
    return 0;
}