1796A - Typical Interview Problem
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
string fb;
int cur = 1;
while(fb.size() < 100)
{
if(cur % 3 == 0) fb += "F";
if(cur % 5 == 0) fb += "B";
cur++;
}
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int k;
cin >> k;
string s;
cin >> s;
cout << (fb.find(s) != string::npos ? "YES" : "NO") << endl;
}
}
1796B - Asterisk-Minor Template
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
a = input()
b = input()
if a[0] == b[0]:
print("YES")
print(a[0] + "*")
continue
if a[-1] == b[-1]:
print("YES")
print("*" + a[-1])
continue
for i in range(len(b) - 1):
if (b[i] + b[i + 1]) in a:
print("YES")
print("*" + b[i] + b[i + 1] + "*")
break
else:
print("NO")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int l, r;
cin >> l >> r;
int max_size = 1;
while((l << max_size) <= r)
max_size++;
int ans2 = (r / (1 << (max_size - 1)) - l + 1);
if(max_size > 1)
ans2 += (max_size - 1) * max(0, (r / (1 << (max_size - 2)) / 3 - l + 1));
cout << max_size << " " << ans2 << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const int N = 222222;
const int K = 22;
const li INF = 1e18;
int n, k, x;
int a[N];
li dp[N][K][3];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
cin >> n >> k >> x;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int t = 0; t < 3; ++t) {
dp[i][j][t] = -INF;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int t = 0; t < 3; ++t) {
if (dp[i][j][t] == -INF) continue;
for (int jj = j; jj <= min(k, j + 1); ++jj) {
li add = a[i] + (j == jj ? -x : x);
for (int tt = t; tt < 3; ++tt) {
dp[i + 1][jj][tt] = max(dp[i + 1][jj][tt], dp[i][j][t] + (tt == 1 ? add : 0));
}
}
}
}
}
cout << max(dp[n][k][1], dp[n][k][2]) << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
vector<vector<int>> g;
vector<multiset<int>> len;
multiset<int> all;
int getlen(int v){
return len[v].empty() ? 1 : *len[v].begin() + 1;
}
void init(int v, int p = -1){
for (int u : g[v]) if (u != p){
init(u, v);
len[v].insert(getlen(u));
}
if (int(len[v].size()) > 1){
all.insert(*(++len[v].begin()));
}
}
int ans;
void dfs(int v, int p = -1){
ans = max(ans, min(*len[v].begin() + 1, *all.begin()));
for (int u : g[v]) if (u != p){
if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
len[v].erase(len[v].find(getlen(u)));
if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
len[u].insert(getlen(v));
if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
dfs(u, v);
if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
len[u].erase(len[u].find(getlen(v)));
if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
len[v].insert(getlen(u));
if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
}
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n;
scanf("%d", &n);
g.assign(n, {});
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
len.assign(n, {});
all.clear();
all.insert(n);
init(0);
ans = 0;
dfs(0);
printf("%d\n", ans);
}
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
using li = long long;
const int MAXLEN = 5;
vector<int> divs(int x) {
vector<int> res;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
res.push_back(i);
if (i * i != x)
res.push_back(x / i);
}
}
return res;
}
int main() {
int A, B, N;
cin >> A >> B >> N;
vector<int> pw(10);
pw[0] = 1;
for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10;
int PW = pw[MAXLEN];
set<array<int, 3>> used;
vector<int> len(PW);
for (int i = 0; i < PW; ++i)
len[i] = sz(to_string(i));
for (int lenn = 1; lenn <= 9; ++lenn) {
int x = pw[lenn] - 1;
for (int k2 : divs(x)) {
int r = x / k2;
for (int d = 1; d < PW; ++d) {
for (int lenb = len[d]; lenb <= MAXLEN; ++lenb) {
int bg = pw[lenb] - d * li(r) % pw[lenb];
int dd = d / __gcd(d, bg);
int lb = (pw[lenb - 1] + bg - 1) / bg;
int rb = (pw[lenb] - 1) / bg;
for (int g = (lb + dd - 1) / dd * dd; g <= rb; g += dd) {
int b = bg * g;
assert(b % d == 0);
if (b >= B || __gcd(b / d, r) != 1) continue;
int ag = (d * li(r) + bg) / pw[lenb];
li n = b / d * li(k2) * ag;
if (n < N && ag * g < A && __gcd(ag, bg) == 1 && sz(to_string(n)) == lenn)
used.insert({ag * g, b, n});
}
}
}
}
}
int res = 0;
for (auto it : used) {
li a = it[0], b = it[1], n = it[2];
int lenn = sz(to_string(n));
int lenb = sz(to_string(b));
res += a * b * pw[lenn] + n * b == a * n * pw[lenb] + a * b;
}
cout << res << endl;
}