Thank you for participating!
1926A - Vlad and the Best of Five
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
string s;
cin >> s;
int a = 0, b = 0;
for (char c : s) {
if (c == 'A') {a++;}
else {b++;}
}
cout << (a > b ? 'A' : 'B') << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<string> g;
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
g.push_back(s);
}
bool triangle = false;
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
{
if(g[i][j] == '1')
{
cnt++;
}
}
if(cnt == 1)
{
triangle = true;
}
else if(cnt > 1)
{
break;
}
}
reverse(g.begin(), g.end());
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
{
if(g[i][j] == '1')
{
cnt++;
}
}
if(cnt == 1)
{
triangle = true;
}
else if(cnt > 1)
{
break;
}
}
if(triangle)
{
cout << "TRIANGLE" << endl;
}
else
{
cout << "SQUARE" << endl;
}
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
1926C - Vlad and a Sum of Sum of Digits
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
int res[MAX];
int S(int x) {
int res = 0;
while (x) {
res += (x % 10);
x /= 10;
}
return res;
}
void solve() {
int x;
cin >> x;
cout << res[x] << '\n';
}
int main() {
res[0] = 0;
for (int i = 1; i < MAX; i++) {
res[i] = res[i - 1] + S(i);
}
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n; cin >> n;
map<int, int> cnt;
int ans = 0;
for(int i = 0, x; i < n; ++i) {
cin >> x;
if(!cnt[x]) ++ans, ++cnt[((1 << 31) - 1) ^ x];
else --cnt[x];
}
cout << ans << "\n";
}
main() {
int t = 1; cin >> t;
while(t--) {
solve();
}
}
1926E - Vlad and an Odd Ordering
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
void solve() {
int n, k;
cin >> n >> k;
vector<int> v;
while (n) {
v.push_back((n + 1) / 2);
n /= 2;
}
int tot = 0, pow2 = 1;
for (int x : v) {
if (tot < k && k <= tot + x) {
cout << pow2 * (2 * (k - tot) - 1) << '\n';
return;
}
tot += x;
pow2 *= 2;
}
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200'007;
const int MOD = 1'000'000'007;
vector<pair<int, int>> odd, even;
bool valid(int gc[7][7], bool odd) {
for (int r = 1; r < 6; r++) {
for (int c = 1; c < 6; c++) {
if (gc[r][c] && ((r + c) % 2 == odd)) {
if (gc[r - 1][c - 1] && gc[r - 1][c + 1] && gc[r + 1][c - 1] && gc[r + 1][c + 1]) {
return false;
}
}
}
}
return true;
}
bool check(int g[7][7], int flips_left, int idx, vector<pair<int, int>>& vec, int valid_val) {
if (flips_left == 0) {
return valid(g, valid_val);
}
if (idx == vec.size()) {
return false;
}
bool ok = false;
ok |= check(g, flips_left, idx + 1, vec, valid_val);
g[vec[idx].first][vec[idx].second] ^= 1;
ok |= check(g, flips_left - 1, idx + 1, vec, valid_val);
g[vec[idx].first][vec[idx].second] ^= 1;
return ok;
}
void solve() {
int g[7][7];
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
char c;
cin >> c;
g[i][j] = (c == 'B');
}
}
int res = 0;
for (int i = 0; i <= 4; i++) {
if (check(g, i, 0, odd, 1)) {res += i; break;}
}
for (int i = 0; i <= 4; i++) {
if (check(g, i, 0, even, 0)) {res += i; break;}
}
cout << res << '\n';
}
int main() {
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if ((i + j) % 2) {
odd.emplace_back(i, j);
}
else {
even.emplace_back(i, j);
}
}
}
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}
1926G - Vlad and Trouble at MIT
Idea: mesanu
Tutorial
Tutorial is loading...
Solution coded by Dominater069, thanks!
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
int n;
const int N = 1e5 + 69;
int dp[N][3];
string s;
vector <int> adj[N];
void dfs(int u){
// dp[u][0] = nothing open
// dp[u][1] = P open
// dp[u][2] = S open
dp[u][0] = INF;
if (s[u] != 'S') dp[u][1] = 0;
else dp[u][1] = INF;
if (s[u] != 'P') dp[u][2] = 0;
else dp[u][2] = INF;
int tot = 0;
for (int v : adj[u]){
dfs(v);
dp[u][1] = dp[u][1] + min({dp[v][1], dp[v][2] + 1, dp[v][0]});
dp[u][2] = dp[u][2] + min({dp[v][2], dp[v][1] + 1, dp[v][0]});
tot += dp[v][0];
}
if (s[u] != 'C') tot = INF;
dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1});
//cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << "\n";
}
void Solve()
{
cin >> n;
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 2; i <= n; i++){
int x; cin >> x;
adj[x].push_back(i);
}
cin >> s; s = "0" + s;
dfs(1);
cout << min({dp[1][0], dp[1][1], dp[1][2]}) << "\n";
}
int32_t main()
{
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
return 0;
}