提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【小码匠自习室】数学题是我的最爱：AtCoder ARC145 B - AB Game

AB Game 小码 自习室 Atcoder 数学题
2023-06-13 09:15:39 时间

题目

B - AB Game

  • https://atcoder.jp/contests/arc145/tasks/arc145_b

标签

  • AtCoder、数学

問題描述

下面的游戏称为游戏 n。

Alice和Bob玩游戏。最初有 n 颗石头。 从 Alice 开始，交替执行以下操作，谁不能执行操作谁就输了。

  • 如果 Alice 执行该操作，则移除 A 的正倍数的石头。
  • 如果 Bob 执行该操作，则移除B 的正倍数的石头。

找出在第 1、2、...、第 N 场比赛中Alice在双方都采取最佳行动时获胜的次数。

制約

  • 1 \leq N ,A,B \leq 10^{18}
  • 所有输入都是整数

入力

输入从标准输入以下列格式给出。

  • N A B

出力

打印出你的答案。

入力例 1

4 2 1

出力例 1

2

在第 1 场比赛中，Alice输了，因为她无法操作。

在第 2 场比赛中，Alice拿下 2 颗棋子获胜，而Bob失去控制。

在第 3 局比赛中，如果 Alice 拿了 2 块石头，Bob 拿了 1 块石头，Alice 输了，因为她不能移动。

在第 4 场比赛中，Alice赢得了 2 \times 2 = 4 块石头，而Bob失去了控制。

所以在第 1、2、3、4 场比赛中，Alice赢了 2 场比赛。

入力例 2

27182818284 59045 23356

出力例 2

10752495144

题解

小码匠

代码

#include <bits/stdc++.h>
 
using namespace std;
#define endl '\n';
int main() {
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<pair<int, int>> x_y(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = i;
        cin >> x_y[i].first >> x_y[i].second;
    }
    double ans = 0;
    double cnt = 0;
    do {
        for(int i = 0; i < n - 1; ++i) {
            ans += sqrt(pow(abs(x_y[a[i]].first - x_y[a[i + 1]].first), 2) + pow(abs(x_y[a[i]].second - x_y[a[i + 1]].second), 2));
        }
        ++cnt;
    } while (next_permutation(a.begin(), a.end()));
    cout << ans / cnt;
    return 0;
}

参考

题解1

思路

[1] Alice可以获胜的棋盘

让我们分析一下，当 n、A 和 B 满足关系式时，Alice 是如何获胜的，其中 n 是初始石子的数量。

如果 n < A，显然 Alice 输了。以后，我们称它为n\geq A 。

现在，您应该注意到以下重要事实：

  • 爱丽丝最好的做法是尽可能多地拿走石头。
  • 证明 如果A≤B，那么尽可能多的取子会使棋子的数量少于A，所以你赢的比A\leq B 多。我们应该尽可能多地从中获取。在 A>B 的情况下，如果取走后的棋子数量为 A 或更多，Alice 从上述论证中总是会比 A>B 输，所以在这种情况下，你也应该尽可能多地取走。

由上可知，Alice 获胜的充要条件为

  • 和 n\bmod A <b

[2] 推导

代码
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long N, A, B;
    cin >> N >> A >> B;
    if (A <= B){
        cout << max(N - (A - 1), (long long) 0) << endl;
    } else {
        N -= B;
        if (N < 0){
            cout << 0 << endl;
        } else {
            N++;
            long long ans = N / A * B + max(N % A - (A - B), (long long) 0);
            cout << ans << endl;
        }
    }
}
代码（jiangly）
#include <bits/stdc++.h>
 
using i64 = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 n, a, b;
    std::cin >> n >> a >> b;
    
    if (a <= b) {
        std::cout << n - std::min(a - 1, n) << "\n";
    } else {
        std::cout << n / a * b + std::min(b - 1, n % a) - std::min(b - 1, n) << "\n";
    }
    
    return 0;
}
代码（Um_nik）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
 
	ll n, a, b;
	scanf("%lld%lld%lld", &n, &a, &b);
	if (n < a) {
		printf("0\n");
		return 0;
	}
	if (a <= b) {
		printf("%lld\n", n - a + 1);
		return 0;
	}
	n -= a;
	ll k = n / a;
	n %= a;
	n++;
	printf("%lld\n", k * b + min(n, b));
 
	return 0;
}

END

相关文章