1245A - Good ol' Numbers Coloring
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
while (b)
{
a %= b;
swap(a, b);
}
return a;
}
int main()
{
int t;
for (cin >> t; t--;)
{
int a, b;
cin >> a >> b;
if (gcd(a, b) == 1)
cout << "Finite" << '\n';
else
cout << "Infinite" << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
for (cin >> q; q--;)
{
int n;
cin >> n;
int a, b, c;
cin >> a >> b >> c;
string s;
cin >> s;
vector<int> count(26);
for (char x : s)
count[x - 'A']++;
int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);
if (2 * wins < n)
{
cout << "NO" << '\n';continue;
}
cout << "YES" << '\n';
string t;
for (int i = 0; i != n; ++i)
{
if (s[i] == 'S' && a)
{
t += 'R';
a--;
}
else if (s[i] == 'R' && b)
{
t += 'P';
b--;
}
else if (s[i] == 'P' && c)
{
t += 'S';
c--;
}
else
t += '_';
}
for (int i = 0; i != n; ++i)
{
if (t[i] != '_')
continue;
if (a)
{
t[i] = 'R';
a--;
}
else if (b)
{
t[i] = 'P';
b--;
}
else
{
t[i] = 'S';
c--;
}
}
cout << t << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
for (cin >> q; q--;)
{
int n;
cin >> n;
int a, b, c;
cin >> a >> b >> c;
string s;
cin >> s;
vector<int> count(26);
for (char x : s)
count[x - 'A']++;
int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);
if (2 * wins < n)
{
cout << "NO" << '\n';continue;
}
cout << "YES" << '\n';
string t;
for (int i = 0; i != n; ++i)
{
if (s[i] == 'S' && a)
{
t += 'R';
a--;
}
else if (s[i] == 'R' && b)
{
t += 'P';
b--;
}
else if (s[i] == 'P' && c)
{
t += 'S';
c--;
}
else
t += '_';
}
for (int i = 0; i != n; ++i)
{
if (t[i] != '_')
continue;
if (a)
{
t[i] = 'R';
a--;
}
else if (b)
{
t[i] = 'P';
b--;
}
else
{
t[i] = 'S';
c--;
}
}
cout << t << '\n';
}
return 0;
}
1245D - Shichikuji and Power Grid
Tutorial
Tutorial is loading...
Solution
#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
pair<int, int> pos[n];
for (int i = 0; i != n; ++i)
cin >> pos[i].first >> pos[i].second;
int c[n];
for (int i = 0; i != n; ++i)
cin >> c[i];
int k[n];
for (int i = 0; i != n; ++i)
cin >> k[i];
long long ans = 0;
vector<int> power_plants;
vector<pair<int, int>> connections;
vector<bool> done(n);
vector<int> parent(n, -1);
for (int _n = n; _n--;)
{
int mi = 2000000000;
int u = -1;
for (int i = 0; i != n; ++i)
{
if (done[i])
continue;
if (c[i] < mi)
{
mi = c[i];
u = i;
}
}
ans += mi;
done[u] = 1;
if (parent[u] == -1)
power_plants.push_back(u);
else
connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));
for (int i = 0; i != n; ++i)
if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])
{
c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));
parent[i] = u;
}
}
cout << ans << '\n';
cout << power_plants.size() << '\n';
sort(power_plants.begin(), power_plants.end());
for (int x : power_plants)
cout << x + 1 << ' ';
cout << '\n';
cout << connections.size() << '\n';
for (pair<int, int> x : connections)
cout << x.first + 1 << ' ' << x.second + 1 << '\n';
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int grid[10][10];
for (int i = 0; i != 10; ++i)
for (int j = 0; j != 10; ++j)
cin >> grid[i][j];
int flat[10][10];
for (int i = 0; i != 10; ++i)
for (int j = 0; j != 10; ++j)
flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
int d = 1;
int x = 9;
int y = 0;
int arr[100];
for (int i = 0; i != 100; ++i)
{
arr[i] = flat[x - grid[x][y]][y];
if (y + d == -1 || y + d == 10)
{
d *= -1;
x--;
}
else
y += d;
}
double dp[100];
dp[99] = 0;
for (int i = 98; i >= 0; --i)
{
dp[i] = 1;
int c = 6;
for (int r = 1; r <= 6; ++r)
{
if (i + r >= 100)
continue;
dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;
c--;
}
dp[i] = 6 * dp[i] / (6 - c);
}
cout << setprecision(10) << fixed << dp[0] << '\n';
return 0;
}
1245F - Daniel and Spring Cleaning
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int f(int a, int b)
{
int ret = 0;
int zeroes = 0;
for (int i = 1; i <= b; i <<= 1)
{
if (b & i)
{
b ^= i;
if (!(a & b))
ret += 1 << zeroes;
}
if (!(a & i))
zeroes++;
}
return ret;
}
long long rec(int a, int b)
{
if (a == b)
return 0;
if (a == 0)
return 2 * b - 1 + rec(1, b);
long long ret = 0;
if (a & 1)
{
ret += 2 * (f(a, b) - f(a, a));
a++;
}
if (b & 1)
{
ret += 2 * (f(b - 1, b) - f(b - 1, a));
b--;
}
return ret + 3 * rec(a / 2, b / 2);
}
int main()
{
int t;
for (cin >> t; t--;)
{
int a, b;
cin >> a >> b;
cout << rec(a, b + 1) << '\n';
}
return 0;
}