Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution 1 (awoo)
for _ in range(int(input())):
n = int(input())
a = set(map(int, input().split()))
ans = 0
for i in range(10000):
num = str(i)
num = (4 - len(num)) * '0' + num
used = set(num)
if len(used) != 2:
continue
d1 = int(used.pop())
d2 = int(used.pop())
if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2:
ans += 1
print(ans)
Solution 2 (fcspartakm)
#include <bits/stdc++.h>
using namespace std;
int n;
inline void read() {
cin >> n;
int x;
for (int i = 0; i < n; ++i)
cin >> x;
}
inline int fac(int n) {
int res = 1;
for (int i = 2; i <= n; i++) {
res *= i;
}
return res;
}
inline int c(int n, int k) {
return fac(n) / fac(k) / fac(n - k);
}
inline void solve() {
cout << c(10 - n, 2) * c(4, 2) << endl;
}
int main () {
int t;
cin >> t;
while (t--){
read();
solve();
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
cout << 1;
for(int i = n; i >= 2; i--)
cout << " " << i;
cout << endl;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = '0' + input()
a = [0] + list(map(int, input().split()))
ans = 0
i = 0
while i <= n:
mn = a[i]
sm = a[i]
j = i + 1
while j <= n and s[j] == '1':
mn = min(mn, a[j])
sm += a[j]
j += 1
ans += sm - mn
i = j
print(ans)
1743D - Problem with Random Tests
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
char buf[1000043];
string normalize(const string& v)
{
int cnt = 0;
while(cnt < v.size() && v[cnt] == '0') cnt++;
if(cnt == v.size()) return "0";
return v.substr(cnt, int(v.size()) - cnt);
}
string operator |(const string& a, const string& b)
{
int sz = max(a.size(), b.size());
string ans(sz, '0');
for(int i = 0; i < a.size(); i++)
if(a[i] == '1') ans[i + sz - int(a.size())] = '1';
for(int i = 0; i < b.size(); i++)
if(b[i] == '1') ans[i + sz - int(b.size())] = '1';
return normalize(ans);
}
bool better(const string& a, const string& b)
{
if(a.size() != b.size()) return a.size() > b.size();
return a > b;
}
int main()
{
int n;
scanf("%d", &n);
string s;
scanf("%s", buf);
s = buf;
string ans = s | s;
int pos1 = s.find("1");
if(pos1 != string::npos)
{
int pos2 = s.find("0", pos1);
if(pos2 != string::npos)
{
int cur = pos1;
int not_needed = 0;
while(true)
{
if(cur == n || (s[cur] == '1' && cur > pos2)) break;
string nw = s | s.substr(pos1, n - pos1 - not_needed);
if(better(nw, ans)) ans = nw;
cur++;
not_needed++;
}
}
}
puts(ans.c_str());
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const long long INF64 = 1e18;
int main() {
vector<int> ps(2);
vector<long long> ts(2);
int h, s;
forn(i, 2) scanf("%d%lld", &ps[i], &ts[i]);
scanf("%d%d", &h, &s);
long long ans = INF64;
vector<long long> dp(h + 1, INF64);
dp[0] = 0;
forn(i, h) for (int j = 1; j <= h - i; ++j) forn(k, 2){
int ni = min((long long)h, i + j * (ps[k] - s) + j * ts[k] / ts[k ^ 1] * (ps[k ^ 1] - s));
if (ni == h)
ans = min(ans, dp[i] + j * ts[k]);
if (j * ts[k] >= ts[k ^ 1]){
ni = min((long long)h, i + (j - 1) * (ps[k] - s) + (j * ts[k] / ts[k ^ 1] - 1) * (ps[k ^ 1] - s) + (ps[0] + ps[1] - s));
dp[ni] = min(dp[ni], dp[i] + j * ts[k]);
}
}
ans = min(ans, dp[h]);
printf("%lld\n", ans);
}
1743F - Intersection and Union
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
typedef array<int, 2> vec;
typedef array<vec, 2> mat;
const int MOD = 998244353;
mat operator*(const mat& a, const mat& b)
{
mat c;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
c[i][j] = 0;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
c[i][k] = (a[i][j] * 1ll * b[j][k] + c[i][k]) % MOD;
return c;
}
mat ZERO = {vec({3, 0}), vec({1, 2})};
mat ONE = {vec({1, 2}), vec({1, 2})};
mat t[4 * N];
void recalc(int v)
{
t[v] = t[v * 2 + 1] * t[v * 2 + 2];
}
void build(int v, int l, int r)
{
if(l == r - 1)
{
t[v] = ZERO;
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
recalc(v);
}
}
void upd(int v, int l, int r, int pos, int val)
{
if(l == r - 1)
{
if(val == 0) t[v] = ZERO;
else t[v] = ONE;
}
else
{
int m = (l + r) / 2;
if(pos < m) upd(v * 2 + 1, l, m, pos, val);
else upd(v * 2 + 2, m, r, pos, val);
recalc(v);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<vector<pair<int, int>>> v(N);
for(int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
v[l].push_back(make_pair(1, i));
v[r + 1].push_back(make_pair(0, i));
}
build(0, 0, n - 1);
int cur = 0;
int ans = 0;
for(int i = 0; i <= 300000; i++)
{
for(auto x : v[i])
{
if(x.second == 0) cur = x.first;
else upd(0, 0, n - 1, x.second - 1, x.first);
}
ans = (ans + t[0][cur][1]) % MOD;
}
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, MOD - y);
}
int expected(int mask)
{
if(mask & 2) return 0;
return 1;
}
int last_bit(int x)
{
if(x == 0) return -1;
return x - (x & (x - 1));
}
bool go(int& a, int x)
{
if(expected(a) != x)
{
a = 1 << x;
return false;
}
a ^= (1 << x);
while(true)
{
int b = last_bit(a);
int c = last_bit(a - b);
if(c == 2 * b) a += b;
else break;
}
return true;
}
bool is_fib(int a)
{
return a == last_bit(a);
}
vector<pair<int, int>> go(const vector<pair<int, int>>& a, int x)
{
vector<pair<int, int>> nw;
for(auto b : a)
{
int cost = b.first;
int seqn = b.second;
if(go(seqn, x)) nw.push_back(make_pair(cost, seqn));
}
return nw;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int last = 1, sum = 1;
vector<pair<int, int>> w;
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
for(auto x : s)
{
int c = x - '0';
int ndp = sub(sum, last);
w = go(w, c);
for(int j = 0; j < w.size(); j++)
{
if(is_fib(w[j].second))
ndp = sub(ndp, w[j].first);
}
if(c == 1) w.push_back(make_pair(last, 2));
sum = add(sum, ndp);
last = ndp;
assert(w.size() <= 60);
}
cout << last << endl;
}
}