题目
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
代码语言：javascript复制4 2 1
出力例 1
代码语言：javascript复制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
代码语言：javascript复制27182818284 59045 23356
出力例 2
代码语言：javascript复制10752495144
题解
小码匠
代码
代码语言：javascript复制#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 输了。以后，我们称它为ngeq A 。
现在，您应该注意到以下重要事实：
- 爱丽丝最好的做法是尽可能多地拿走石头。
- 证明 如果A≤B，那么尽可能多的取子会使棋子的数量少于A，所以你赢的比Aleq B 多。我们应该尽可能多地从中获取。在 A>B 的情况下，如果取走后的棋子数量为 A 或更多，Alice 从上述论证中总是会比 A>B 输，所以在这种情况下，你也应该尽可能多地取走。
由上可知，Alice 获胜的充要条件为
- 和 nbmod A <b
[2] 推导
代码
代码语言：javascript复制#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）
代码语言：javascript复制#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）
代码语言：javascript复制#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("0n");
return 0;
}
if (a <= b) {
printf("%lldn", n - a 1);
return 0;
}
n -= a;
ll k = n / a;
n %= a;
n ;
printf("%lldn", k * b min(n, b));
return 0;
}
END
