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;
const int MOD = 1000000007;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
for (char x : s)
{
if (x == 'w' || x == 'm')
{
cout << 0 << '\n';
return 0;
}
}
int n = s.size();
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
{
dp[i] = dp[i - 1];
if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))
dp[i] = (dp[i] + dp[i - 2]) % MOD;
}
cout << dp[n] << '\n';
return 0;
}
Solution (Arpa)
// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14, mod = 1e9 + 7;
int n, fib[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
fib[0] = fib[1] = 1;
for(int i = 2; i < maxn; i++)
fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
string s;
cin >> s;
n = s.size();
if(s.find('m') != -1 || s.find('w') != -1)
return cout << "0\n", 0;
int ans = 1;
for(int i = 0, j = 0; i < n; i = j){
while(j < n && s[j] == s[i])
j++;
if(s[i] == 'n' || s[i] == 'u')
ans = (ll) ans * fib[j - i] % mod;
}
cout << ans << '\n';
}
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;
}
Solution (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
int main(){
int n;
scanf("%d", &n);
vector<int> x(n), y(n);
forn(i, n)
scanf("%d%d", &x[i], &y[i]);
vector<int> c(n), k(n);
forn(i, n)
scanf("%d", &c[i]);
forn(i, n)
scanf("%d", &k[i]);
++n;
vector<int> p(n, -1);
vector<int> d(n, int(1e9));
vector<bool> used(n);
forn(i, n - 1){
d[i] = c[i];
p[i] = n - 1;
}
used[n - 1] = true;
long long ans = 0;
vector<int> vv;
vector<pair<int, int>> ee;
forn(_, n - 1){
int v = -1;
forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))
v = i;
if (p[v] == n - 1)
vv.push_back(v + 1);
else
ee.push_back(make_pair(v + 1, p[v] + 1));
ans += d[v];
used[v] = true;
forn(i, n) if (!used[i]){
long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));
if (dist < d[i]){
d[i] = dist;
p[i] = v;
}
}
}
printf("%lld\n", ans);
printf("%d\n", int(vv.size()));
for (auto it : vv)
printf("%d ", it);
puts("");
printf("%d\n", int(ee.size()));
for (auto it : ee)
printf("%d %d\n", it.first, it.second);
}
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;
}