Ideas: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int k;
cin >> k;
for (int i = 1; ; i++)
{
if (i % 3 == 0 || i % 10 == 3)
continue;
if (--k == 0)
{
cout << i << '\n';
break;
}
}
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin >> t;
while (t--)
{
ll a, b, c;
cin >> a >> b >> c;
ll n = 2 * abs(a - b);
if (a > n || b > n || c > n)
cout << -1 << '\n';
else
{
ll d = n / 2 + c;
while (d > n) d -= n;
cout << d << '\n';
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int k;
cin >> k;
int a = 1;
int x = 1;
int i = 1;
while (k >= x + a)
{
x += a;
a += 2;
i += 1;
}
int m = k - x + 1;
if (m <= i)
cout << m << ' ' << i << '\n';
else
cout << i << ' ' << (i - (m - i)) << '\n';
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P2LIM = (ll)2e18;
int solve(string s, string t)
{
int tp = 0;
int sp = 0;
int taken = 0;
while (sp < s.length() && tp < t.length())
{
if(s[sp] == t[tp])
{
taken++;
tp++;
}
sp++;
}
return (int)s.length() - taken + (int)t.length() - taken;
}
vector<string> ts;
int main()
{
for (ll p2 = 1; p2 <= P2LIM; p2 *= 2)
ts.push_back(to_string(p2));
int t;
cin >> t;
while (t--)
{
string n;
cin >> n;
int ans = n.length() + 1;
for (auto p2 : ts)
ans = min(ans, solve(n, p2));
cout << ans << '\n';
}
return 0;
}
1560E - Polycarp and String Transformation
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int cntsrc[26]; // don't forget to memset it but not cnt
int* cnt = cntsrc - 'a'; // so cnt['a'] = cntsrc[0] and so on
pair<string, string> decrypt(string s)
{
string order;
reverse(s.begin(), s.end());
for (auto c : s)
{
if (!cnt[c])
order.push_back(c);
cnt[c]++;
}
int m = order.length();
int originalLength = 0;
for (int i = 0; i < m; i++)
originalLength += cnt[order[i]] / (m - i);
reverse(order.begin(), order.end());
return { string(s.rbegin(), s.rbegin() + originalLength), order };
}
string encrypt(pair<string, string> p)
{
string result = p.first;
for (auto c : p.second)
{
string temp;
for (auto d : p.first)
if (d != c)
{
temp.push_back(d);
result.push_back(d);
}
p.first = temp;
}
return result;
}
int main()
{
int t;
cin >> t;
while (t--)
{
memset(cntsrc, 0, sizeof(cntsrc));
string s;
cin >> s;
auto ans = decrypt(s);
auto check = encrypt(ans);
if (check == s)
cout << ans.first << ' ' << ans.second << '\n';
else
cout << "-1\n";
}
return 0;
}
1560F1 - Nearest Beautiful Number (easy version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
string solve1(string n)
{
string res(n.length(), '9');
for (char c = '8'; c >= '0'; c--)
{
string t(n.length(), c);
if (t >= n)
res = t;
}
return res;
}
string solve2(string n)
{
string res = solve1(n);
for(char a = '0'; a <= '9'; a++)
for (char b = a + 1; b <= '9'; b++)
{
bool n_ok = true;
for (int i = 0; i < n.length(); i++)
{
if (n[i] < b)
{
string t = n;
if (t[i] < a) t[i] = a;
else t[i] = b;
for (int j = i + 1; j < n.length(); j++)
t[j] = a;
if (res > t)
res = t;
}
if(n[i] != a && n[i] != b)
{
n_ok = false;
break;
}
}
if (n_ok) return n;
}
return res;
}
string solve()
{
string n;
int k;
cin >> n >> k;
if (k == 1) return solve1(n);
else return solve2(n);
}
int main()
{
int t;
cin >> t;
while (t--)
cout << solve() << '\n';
return 0;
}
1560F2 - Nearest Beautiful Number (hard version)
Tutorial
Tutorial is loading...
Short solution
#include <bits/stdc++.h>
using namespace std;
string solve()
{
string n;
int k;
cin >> n >> k;
while (true)
{
set<char> s;
for (auto c : n) s.insert(c);
if (s.size() <= k) return n;
s.clear();
int ptr = 0;
for (; ; ptr++)
{
s.insert(n[ptr]);
if (s.size() > k)
{
while (n[ptr] == '9')
ptr--;
n[ptr]++;
for (int i = ptr + 1; i < n.size(); i++)
n[i] = '0';
break;
}
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
cout << solve() << '\n';
return 0;
}
Long solution
#include <bits/stdc++.h>
using namespace std;
string solveFillingSuffix(string& n, char d, int from)
{
for (int i = from; i < n.length(); i++)
n[i] = d;
return n;
}
void decAt(map<char, int>& d, char c)
{
if (d.count(c))
{
d[c]--;
if (d[c] == 0) d.erase(c);
}
}
string solve()
{
string n;
int k;
cin >> n >> k;
map<char, int> d;
int pref = 0;
while (pref < n.length())
{
if (d.count(n[pref]))
{
d[n[pref++]]++;
continue;
}
if (d.size() == k) break;
d[n[pref++]]++;
}
if (pref == n.length())
return n;
while (true)
{
if (n[pref] == '9')
{
decAt(d, n[--pref]);
continue;
}
if (d.size() < k)
{
d[++n[pref]]++;
return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1);
}
auto it = d.upper_bound(n[pref]);
if (it == d.end())
{
decAt(d, n[--pref]);
continue;
}
n[pref] = it->first;
return solveFillingSuffix(n, d.begin()->first, pref + 1);
}
}
int main()
{
int t;
cin >> t;
while (t--)
cout << solve() << '\n';
return 0;
}//