题目
B - AB Game
下面的游戏称为游戏 n。
Alice和Bob玩游戏。最初有 n 颗石头。 从 Alice 开始,交替执行以下操作,谁不能执行操作谁就输了。
找出在第 1、2、...、第 N 场比赛中Alice在双方都采取最佳行动时获胜的次数。
输入从标准输入以下列格式给出。
打印出你的答案。
4 2 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 场比赛。
27182818284 59045 23356
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] Alice可以获胜的棋盘
让我们分析一下,当 n、A 和 B 满足关系式时,Alice 是如何获胜的,其中 n 是初始石子的数量。
如果 n < A,显然 Alice 输了。以后,我们称它为n\geq A 。
现在,您应该注意到以下重要事实:
由上可知,Alice 获胜的充要条件为
[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;
}
}
}
#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;
}
#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