We hope you enjoyed the contest! The tutorial to problem G will be added shortly.
1950A - Stair, Peak, or Neither?
Idea: SlavicG
Tutorial
Tutorial is loading...
Solution
#include <iostream>
void solve() {
int a, b, c;
std::cin >> a >> b >> c;
if(a < b && b < c) std::cout << "STAIR"<< "\n";
else if(a < b && b > c) std::cout << "PEAK"<< "\n";
else std::cout << "NONE" << "\n";
}
int main() {
int tt; std::cin >> tt;
while(tt--)
solve();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) {
cout << (i / 2 + j / 2 & 1 ? '.' : '#');
}
cout << '\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 <bits/stdc++.h>
using namespace std;
void solve() {
int h, m; char c;
cin >> h >> c >> m;
string am = (h < 12 ? " AM" : " PM");
h = (h % 12 ? h % 12 : 12);
cout << (h < 10 ? "0" : "") << h << c << (m < 10 ? "0" : "") << m << am << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1950D - Product of Binary Decimals
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100'007;
const int MOD = 1'000'000'007;
vector<int> binary_decimals;
bool ok(int n) {
if (n == 1) {return true;}
bool ans = false;
for (int i : binary_decimals) {
if (n % i == 0) {
ans |= ok(n / i);
}
}
return ans;
}
void solve() {
int n;
cin >> n;
cout << (ok(n) ? "YES\n" : "NO\n");
}
int main() {
for (int i = 2; i < MAX; i++) {
int curr = i;
bool bad = false;
while (curr) {
if (curr % 10 > 1) {bad = true; break;}
curr /= 10;
}
if (!bad) {binary_decimals.push_back(i);}
}
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1950E - Nearly Shortest Repeating Substring
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for(int i = 1; i <= n; i++)
{
if(n%i == 0)
{
int satisfy = 2;
for(int j = 0; j < i; j++)
{
for(int k = j+i; k < n; k+=i)
{
if(s[k] != s[j])
{
satisfy--;
}
}
}
if(satisfy > 0)
{
cout << i << endl;
return;
}
satisfy = 2;
for(int j = n-i; j < n; j++)
{
for(int k = j-i; k >= 0; k-=i)
{
if(s[k] != s[j])
{
satisfy--;
}
}
}
if(satisfy > 0)
{
cout << i << endl;
return;
}
}
}
}
int32_t main(){
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b, c;
cin >> a >> b >> c;
if (a + 1 != c) {cout << -1 << '\n'; return;}
if (a + b + c == 1) {cout << 0 << '\n'; return;}
int curr = 1, next = 0, res = 1;
for (int i = 0; i < a + b; i++) {
if (!curr) {
swap(next, curr);
res++;
}
curr--;
next++;
if (i < a) {next++;}
}
cout << res << '\n';
}
int main() {
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Idea: SlavicG
Tutorial
Tutorial is not ready yet. We will add it shortly.
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
#define all(x) x.begin(),x.end()
void solve() {
int n; cin >> n;
vector<int> s(n), g(n);
vector<string> aa(n), bb(n);
vector<string> vals;
for(int i = 0; i < n; ++i) {
string a, b; cin >> a >> b;
vals.push_back(a);
vals.push_back(b);
aa[i] = a, bb[i] = b;
}
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for(int i = 0; i < n; ++i) {
s[i] = lower_bound(all(vals), aa[i]) - vals.begin();
g[i] = lower_bound(all(vals), bb[i]) - vals.begin();
}
vector<vector<int>> dp(1 << n, vector<int>(n, 0));
for(int i = 0; i < n; ++i) dp[1 << i][i] = 1;
for(int mask = 0; mask < (1 << n); ++mask) {
for(int lst = 0; lst < n; ++lst) {
if(!dp[mask][lst]) continue;
for(int i = 0; i < n; ++i) {
if(mask >> i & 1) continue;
if(s[lst] == s[i] || g[lst] == g[i]) {
dp[mask | (1 << i)][i] |= dp[mask][lst];
}
}
}
}
int ans = 0;
for(int mask = 0; mask < (1 << n); ++mask) {
for(int i = 0; i < n; ++i) {
if(dp[mask][i]) {
ans = max(ans, __builtin_popcount(mask));
}
}
}
cout << n - ans << "\n";
}
main() {
int t = 1; cin >> t;
while(t--) {
solve();
}
}