USACO 2019 December Contest, Silver Problem 1. MooBuzz

USACO 2019 December Contest, Silver Problem 1. MooBuzz

Farmer John's cows have recently become fans of playing a simple number game called "FizzBuzz". The rules of the game are simple: standing in a circle, the cows sequentially count upward from one, each cow saying a single number when it is her turn. If a cow ever reaches a multiple of 3, however, she should say "Fizz" instead of that number. If a cow reaches a multiple of 5, she should say "Buzz" instead of that number. If a cow reaches a multiple of 15, she should say "FizzBuzz" instead of that number. A transcript of the first part of a game is therefore:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Having a slightly more limited vocabulary, the version of FizzBuzz played by the cows involves saying "Moo" instead of Fizz, Buzz, and FizzBuzz. The beginning of the cow version of the game is therefore

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

Given?NN?(1≤N≤1091≤N≤109), please determine the?NNth number spoken in this game.

 

 

 

 

SAMPLE INPUT:

4

SAMPLE OUTPUT:

7

The 4th number spoken is 7. The first 4 numbers spoken are 1, 2, 4, 7, since we skip over any time a cow says "Moo".

 

Problem credits: Brian Dean

<h3>USACO 2019 December Contest, Silver Problem 1. MooBuzz 題解(翰林國際教育提供，僅供參考)</h3>
<p style="text-align: center;">題解請<a href="/register" target="_blank" rel="noopener">注冊</a>或<a href="/login" target="_blank" rel="noopener">登錄</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

Let?f(n)f(n)?denote the?nn-th number spoken. Within the first 15 turns exactly eight numbers are spoken; in fact, this is true for any 15 consecutive turns. Therefore, we should be able to calculate?f(n)f(n)?recursively. For?n>8,n>8,

Defining?num=?n?18?,num=?n?18?,?we can rewrite this as equation as

where?1≤n?8?num≤8.1≤n?8?num≤8.?When?n≤8,n≤8,?we can easily calculate?f(n)f(n)?via brute force, so we're done. My code follows:

 

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
 
void setIO(string name) {
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
	ios_base::sync_with_stdio(0);
}

vi stor; // first 8 numbers
 
bool ok(int x) { return x%3 && x%5; } // not fizz or buzz
int dumb(int N) { // get f(n) slowly
	for (int i = 1;;++i) if (ok(i)) {
		N --;
		if (N == 0) return i;
	}
}
int smart(int N) { // get f(n) quickly
	int num = (N-1)/8;
	return stor[N-8*num-1]+15*num;
}
 
int main() {
	setIO("moobuzz");
	FOR(i,1,16) if (ok(i)) stor.pb(i);
	int N; cin >> N;
	cout << smart(N) << "\n";
}

[/hide]