Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def check(x):
s = str(x)
cnt = 0
for c in s:
if c != '0':
cnt += 1
return cnt == 1
a = []
for i in range(1, 1000000):
if check(i):
a.append(i)
t = int(input())
for i in range(t):
n = int(input())
ans = 0
for x in a:
if x <= n:
ans += 1
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
cur = {}
for i in range(n - 1):
t = s[i:i+2]
if t in cur:
if cur[t] < i - 1:
print("YES")
break
else:
cur[t] = i
else:
print("NO")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = [input() for i in range(2)]
pos = -1
for i in range(n):
if s[0][i] != s[1][i]:
pos = i
if pos == -1:
print("YES")
continue
ok = True
cur = 0 if s[0][pos] == 'B' else 1
for i in range(pos + 1, n):
if s[cur][i] == 'W':
ok = False
if s[cur ^ 1][i] == 'B':
cur ^= 1
cur = 0 if s[0][pos] == 'B' else 1
for i in range(pos - 1, -1, -1):
if s[cur][i] == 'W':
ok = False
if s[cur ^ 1][i] == 'B':
cur ^= 1
print("YES" if ok else "NO")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
const int INF = int(1e9);
const int N = int(1e7) + 5;
int mind[N];
void precalc() {
fore (i, 0, N)
mind[i] = i;
for (int p = 2; p < N; p++) {
if (mind[p] != p)
continue;
for (int d = 2 * p; d < N; d += p)
mind[d] = min(mind[d], p);
}
}
int x, y;
inline bool read() {
if(!(cin >> x >> y))
return false;
return true;
}
vector<int> getPrimes(int v) {
vector<int> ps;
while (v > 1) {
if (ps.empty() || ps.back() != mind[v])
ps.push_back(mind[v]);
v /= mind[v];
}
return ps;
}
inline void solve() {
int d = y - x;
if (d == 1) {
cout << -1 << '\n';
return;
}
int r = INF;
for (int p : getPrimes(d))
r = min(r, ((x + p - 1) / p) * p);
cout << r - x << '\n';
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
precalc();
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
int n;
int v[N];
map<vector<int>, long long> dp[N];
pair<int, vector<int>> go(vector<int> a, int x)
{
if(x == 0)
return {1, a};
else
{
bool f = false;
for(int i = 0; i < a.size() && !f; i++)
if((a[i] & x) > 0)
{
f = true;
a[i] = x;
}
int c = 0;
if(!f)
{
c = 1;
a.push_back(x);
}
return {c, a};
}
}
long long calc(int i, vector<int> a)
{
if(i == n) return 0ll;
if(dp[i].count(a)) return dp[i][a];
auto p = go(a, v[i]);
return (dp[i][a] = p.first * 1ll * (n - i) + calc(i + 1, p.second));
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &v[i]);
long long ans = 0;
for(int i = 0; i < n; i++)
ans += calc(i, vector<int>(0));
printf("%lld\n", ans);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 243;
struct edge
{
int y, c, w, f;
edge() {};
edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
};
vector<edge> e;
vector<int> g[N];
int rem(int x)
{
return e[x].c - e[x].f;
}
void add_edge(int x, int y, int c, int w)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, w, 0));
g[y].push_back(e.size());
e.push_back(edge(x, 0, -w, 0));
}
int n, m, s, t, v;
pair<int, long long> MCMF()
{
int flow = 0;
long long cost = 0;
while(true)
{
vector<long long> d(v, (long long)(1e18));
vector<int> p(v, -1);
vector<int> pe(v, -1);
queue<int> q;
vector<bool> inq(v);
q.push(s);
inq[s] = true;
d[s] = 0;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = false;
for(auto ei : g[k])
{
if(rem(ei) == 0) continue;
int to = e[ei].y;
int w = e[ei].w;
if(d[to] > d[k] + w)
{
d[to] = d[k] + w;
p[to] = k;
pe[to] = ei;
if(!inq[to])
{
inq[to] = true;
q.push(to);
}
}
}
}
if(p[t] == -1 || d[t] >= 0) break;
flow++;
cost += d[t];
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
}
return make_pair(flow, cost);
}
void no_answer()
{
cout << "Impossible" << endl;
exit(0);
}
int main()
{
cin >> n >> m;
vector<int> excess_flow(n, 0);
vector<int> orc(m);
for(int i = 0; i < m; i++)
{
int x, y, c, w;
cin >> x >> y >> c >> w;
orc[i] = c;
--x;
--y;
add_edge(x, y, c / 2, w);
if(c % 2 == 1)
{
excess_flow[x]--;
excess_flow[y]++;
}
}
s = n;
t = n + 1;
v = n + 2;
int total_excess = 0;
if(excess_flow[0] % 2 == -1)
{
excess_flow[0]--;
excess_flow[n - 1]++;
}
for(int i = 0; i < n; i++)
{
if(excess_flow[i] % 2 != 0)
no_answer();
int val = abs(excess_flow[i]) / 2;
if(excess_flow[i] > 0)
{
total_excess += val;
add_edge(s, i, val, -int(1e9));
}
if(excess_flow[i] < 0)
{
add_edge(i, t, val, -int(1e9));
}
}
add_edge(s, 0, 100000, 0);
add_edge(n - 1, t, 100000, 0);
auto ans = MCMF();
bool good_answer = true;
for(int x = 0; x < e.size(); x++)
if(e[x].w == -int(1e9) && rem(x) != 0)
good_answer = false;
if(!good_answer)
no_answer();
cout << "Possible" << endl;
for(int i = 0; i < 2 * m; i += 2)
{
if(i) cout << " ";
cout << e[i].f * 2 + orc[i / 2] % 2;
}
cout << endl;
}