Home » 國際競賽 » Details

USACO 2019 December Contest, Silver Problem 1. MooBuzz

Category: 國際競賽, 計算機國際競賽 Date: 2022年7月1日下午2:39

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? $N$ ?( $1 \leq N \leq 10^{9}$ ), please determine the? $N$ th number spoken in this game.

SCORING

Test cases 2-5 satisfy? $N \leq 10^{6} .$

INPUT FORMAT (file moobuzz.in):

The input consists of a single integer,? $N$ .

OUTPUT FORMAT (file moobuzz.out):

Please print out the? $N$ th number spoken during the game.

SAMPLE INPUT:

SAMPLE OUTPUT:

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)$ ?denote the? $n$ -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)$ ?recursively. For? $n > 8,$

f (n) = f (n ? 8) + 15.

Defining? $n u m = ⌊ \frac{n - 1}{8} ⌋,$ ?we can rewrite this as equation as

f (n) = f (n ? 8 ? n u m) + 15 ? n u m,

where? $1 \leq n - 8 \cdot n u m \leq 8.$ ?When? $n \leq 8,$ ?we can easily calculate? $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]

以上就是關于【USACO 2019 December Contest, Silver Problem 1. MooBuzz】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！