[USACO 2011 Ope S]Cow Checkers

NC24606. [USACO 2011 Ope S]Cow Checkers

描述

One day, Bessie decides to challenge Farmer John to a game of 'Cow Checkers'. The game is played on an M*N (1 <= M <= 1,000,000; 1 <= N <= 1,000,000) checkerboard that initially contains a single checker piece on the checkboard square coordinates (X, Y) (0 <= X < M; 0 <= Y < N). The bottom leftmost square of the checkerboard has
coordinates (0, 0), and the top rightmost square has coordinates (M-1, N-1). Bessie always moves first, and then the two players alternate turns. Each turn comprises one of three types of moves:
1) Move the checker piece to any square on the same row to the left of its current position.
2) Move the checker piece to any square on the same column below its current position.
3) Move the checker piece to any spot k squares below and k squares to the left of the current square (where k is any positive integer such that this new spot is still on the checkerboard).
The first player unable to make a move (i.e., because the checker is at (0, 0)) loses. Given that Bessie always goes first, determine who will win the game if both play optimally.
Play and report the winner for T games (1 <= T <= 1,000) reading in a new X,Y starting value for each new game.

输入描述

* Line 1: Two space-separated integers: M and N
* Line 2: A single integer: T
* Lines 3..T+2: Two space-separated integers: X and Y

输出描述

* Lines 1..T: Should contain either 'Farmer John' or 'Bessie' depending on who wins each game.

示例1

输入:

3 3 
1 
1 1

输出:

Bessie

说明:

Farmer John and Bessie are playing one game on a 3*3 checkerboard with the checker piece initially at (1, 1) (i.e. at the center of the board).
Bessie initially can only move the checker piece to either (1, 0) or (0, 1), or (0, 0). Bessie can immediately win by moving the piece to (0, 0).

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 488K, 提交时间: 2020-03-07 18:25:59

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int t; cin >> t;
    int a,b;
    while(t--)
    {
        cin >> a >> b;
        if(a > b) swap(a,b);
        int k = floor((b-a)*((1.0+sqrt(5.0))/2.0));
        if(k != a) cout<<"Bessie"<<endl;
        else cout<<"Farmer John"<<endl;
    }
    return 0;
}

Python3 解法, 执行用时: 56ms, 内存消耗: 4636K, 提交时间: 2023-04-11 17:10:47

import math
N, M = map(int, input().split())
T = int(input())
while T:
    x, y = map(int, input().split())
    z = 0
    if x > y:
        x, y = y, x
    tmp = int((y-x) * (math.sqrt(5) + 1) / 2)

    if tmp == x:
        print("Farmer John")
    else:
        print("Bessie")
    T -= 1

C++(clang++ 11.0.1) 解法, 执行用时: 6ms, 内存消耗: 468K, 提交时间: 2022-09-03 20:45:38

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,e,t,n,m;
	cin>>n>>m>>t;
	while(t--)
	{
		cin>>a>>b;
		if(a>b) swap(a,b);
		if(a==int((b-a)*((sqrt(5.0) + 1) / 2))) cout<<"Farmer John"<<endl;
		else cout<<"Bessie"<<endl;
	}
 }