1790A - Polycarp and the Day of Pi
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
t = int(input())
pi = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
for _ in range(t):
n = input() + '#'
for i in range(len(n)):
if pi[i] != n[i]:
print(i)
break
Idea: Gornak40
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int n, s1, s2;
vector<int> res;
void solve() {
res.clear();
int d = s1 - s2;
for (; s2 >= d; s2 -= d)
res.push_back(d);
if (s2) res.push_back(s2);
for (int i = 0; i < res.size() && res.size() + 1 < n;) {
if (res[i] == 1) {
++i;
continue;
}
--res[i];
res.push_back(1);
}
res.push_back(d);
}
int main() {
int t; cin >> t;
while (t--) {
cin >> n >> s1 >> s2;
solve();
sort(res.begin(), res.end());
for (int x: res)
cout << x << ' ';
cout << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
int n;
void solve(){
cin >> n;
vector<vector<int>>perm(n, vector<int>(n - 1));
vector<int>p(n, 0);
vector<int>cnt(n + 1, 0);
for(int i = 0; i < n; i++){
p[i] = i + 1;
for(int j = 0; j < n - 1; j++){
cin >> perm[i][j];
if(j == 0) cnt[perm[i][j]]++;
}
}
for(int i = 1; i <= n; i++){
if(cnt[i] == n - 1){
p[0] = i;
break;
}
}
for(int i = 0; i < n; i++){
if(perm[i][0] != p[0]){
for(int j = 0; j < n - 1; j++){
p[j + 1] = perm[i][j];
}
}
}
for(int i = 0; i < n; i++) cout << p[i] << ' ';
cout << endl;
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
map<int, int> cnt;
set<int> b;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
b.insert(a[i]);
b.insert(a[i] + 1);
}
int last = 0;
int res = 0;
for (auto x: b) {
int c = cnt[x];
res += max(0, c - last);
last = c;
}
cout << res << '\n';
}
int main(int argc, char* argv[]) {
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
}
1790E - Vlad and a Pair of Numbers
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
x = int(input())
a = x
b = 0
for i in range(32, -1, -1):
if x & (1 << i) > 0:
continue
if 2 * x - a - b >= (2 << i):
a += 1 << i
b += 1 << i
if a + b == 2 * x and a ^ b == x:
print(a, b)
else:
print(-1)
1790F - Timofey and Black-White Tree
Idea: molney
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200200;
const int INF = 1e9;
int n, ANS = INF;
int crr[MAXN], dist[MAXN], res[MAXN];
bool clr[MAXN];
vector<int> gr[MAXN];
void init() {
ANS = INF;
for (int v = 0; v < n; ++v)
gr[v].clear();
fill(dist, dist + n, INF);
memset(clr, 0, n);
}
void dfs(int v, int p) {
if (dist[v] >= ANS) return;
if (clr[v]) ANS = min(ANS, dist[v]);
for (int u: gr[v]) {
if (u == p) continue;
if (dist[v] + 1 < dist[u]) {
dist[u] = dist[v] + 1;
dfs(u, v);
} else ANS = min(ANS, dist[v] + 1 + dist[u]);
}
}
void solve() {
dist[*crr] = 0;
dfs(*crr, -1);
clr[*crr] = true;
for (int i = 1; i < n; ++i) {
dist[crr[i]] = 0;
dfs(crr[i], -1);
clr[crr[i]] = true;
res[i] = ANS;
}
}
int main() {
int gorilla; cin >> gorilla;
while (gorilla--) {
cin >> n >> *crr, --(*crr);
init();
for (int i = 1; i < n; ++i)
cin >> crr[i], --crr[i];
for (int i = 1; i < n; ++i) {
int v, u; cin >> v >> u, --v, --u;
gr[v].push_back(u);
gr[u].push_back(v);
}
solve();
for (int i = 1; i < n; ++i)
cout << res[i] << ' ';
cout << '\n';
}
}
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> token(n), boni(n);
vector<vector<int>> g(n);
vector<int> good(n);
int m;
cin >> m;
int p, b;
cin >> p >> b;
for(int i = 0; i < p; i++)
{
int x;
cin >> x;
--x;
token[x] = 1;
}
for(int i = 0; i < b; i++)
{
int x;
cin >> x;
--x;
boni[x] = 1;
}
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < n; i++)
for(auto x : g[i])
if(boni[i] && boni[x]) good[i] = 1;
set<int> good_tokens;
set<int> not_so_good_tokens;
for(int i = 0; i < n; i++)
for(auto x : g[i])
{
if(token[i] && good[x]) good_tokens.insert(i);
else if(token[i] && boni[x]) not_so_good_tokens.insert(i);
}
vector<int> d(n, int(1e9));
queue<int> q;
d[0] = 0;
q.push(0);
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto x : g[k])
{
if(d[x] > d[k] + 1)
{
d[x] = d[k] + 1;
if(boni[x]) q.push(x);
}
}
}
bool has_ans = false;
for(int i = 0; i < n; i++)
{
if(!token[i] || d[i] > n) continue;
has_ans |= (!good_tokens.empty() && (*good_tokens.begin() != i || *good_tokens.rbegin() != i));
int cnt = not_so_good_tokens.size();
if(not_so_good_tokens.count(i)) cnt--;
has_ans |= d[i] <= 1 + cnt;
}
cout << (has_ans ? "YES" : "NO") << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int tc = 1;
cin >> tc;
for(int i = 0; i < tc; i++)
{
solve();
}
}