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]