1207A - There Are Two Types Of Burgers
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
int t;
int b, p, f;
int h, c;
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> b >> p >> f;
cin >> h >> c;
b /= 2;
if(h < c){
swap(h, c);
swap(p, f);
}
int res = 0;
int cnt = min(b, p);
b -= cnt, p -= cnt;
res += h * cnt;
cnt = min(b, f);
b -= cnt, f -= cnt;
res += c * cnt;
cout << res << endl;
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(n):
a[i] = list(map(int, input().split()))
ans = []
for i in range(n - 1):
for j in range(m - 1):
if(a[i][j] * a[i][j + 1] * a[i + 1][j] * a[i + 1][j + 1] > 0):
a[i][j] = 2
a[i + 1][j] = 2
a[i][j + 1] = 2
a[i + 1][j + 1] = 2
ans.append([i, j])
cnt1 = 0
for i in range(n):
for j in range(m):
if(a[i][j] == 1):
cnt1 += 1
if(cnt1 != 0):
print(-1)
else:
print(len(ans))
for x in ans:
print(x[0] + 1, x[1] + 1)
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
const val INF64 = 1e18.toLong()
fun main(args: Array<String>) {
val tc = readLine()!!.toInt()
for (t in 1..tc) {
val (n, a, b) = readLine()!!.split(' ').map { it.toInt() }
val s = readLine()!!
val d = Array(n + 1) { arrayOf(INF64, INF64) }
d[0][0] = b.toLong()
for (pos in 0 until n) {
if (s[pos] == '0') {
d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][0] + a + b)
d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][0] + 2 * (a + b))
d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][1] + 2 * a + b)
} else {
d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
}
}
println(d[n][0])
}
}
1207D - Number Of Permutations
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const int MOD = 998244353;
int mul(int a, int b){
return (a * 1LL * b) % MOD;
}
int sum(int a, int b){
return (a + b) % MOD;
}
int n;
pair<int, int> a[N];
int f[N];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d%d", &a[i].first, &a[i].second);
f[0] = 1;
for(int i = 1; i < N; ++i)
f[i] = mul(i, f[i - 1]);
int res = f[n];
for(int c = 0; c < 2; ++c){
int d = 1;
sort(a, a + n);
int l = 0;
while(l < n){
int r = l + 1;
while(r < n && a[l].first == a[r].first) ++r;
d = mul(d, f[r - l]);
l = r;
}
res = sum(res, MOD - d);
for(int i = 0; i < n; ++i)
swap(a[i].first, a[i].second);
}
sort(a, a + n);
int l = 0;
int d = 1;
while(l < n){
int r = l + 1;
while(r < n && a[l].first == a[r].first) ++r;
map<int, int> m;
for(int i = l; i < r; ++i) ++m[a[i].second];
for(auto p : m) d = mul(d, f[p.second]);
l = r;
}
for(int i = 1; i < n; ++i)
if(a[i - 1].second > a[i].second) d = 0;
res = sum(res, d);
printf("%d\n", res);
return 0;
}
Идея: adedalic, Neon, BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout << "?";
for(int i = 1; i <= 100; i++)
cout << " " << i;
cout << endl;
cout.flush();
int res1;
cin >> res1;
cout << "?";
for(int i = 1; i <= 100; i++)
cout << " " << (i << 7);
cout << endl;
cout.flush();
int res2;
cin >> res2;
int x = 0;
x |= (res1 & (((1 << 7) - 1) << 7));
x |= (res2 & ((1 << 7) - 1));
cout << "! " << x << endl;
cout.flush();
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 500043;
const int K = 750;
int a[N];
int sum[K][K];
int main()
{
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int t, x, y;
scanf("%d %d %d", &t, &x, &y);
if(t == 1)
{
a[x] += y;
for(int i = 1; i < K; i++)
sum[i][x % i] += y;
}
else
{
if(x >= K)
{
int ans = 0;
for(int i = y; i <= 500000; i += x)
ans += a[i];
printf("%d\n", ans);
}
else
printf("%d\n", sum[x][y]);
}
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 26;
const int N = 400 * 1000 + 13;
struct node{
int nxt[AL];
node(){
memset(nxt, -1, sizeof(nxt));
}
int& operator [](int x){
return nxt[x];
}
};
struct node_at{
int nxt[AL];
int p;
char pch;
int link;
int go[AL];
node_at(){
memset(nxt, -1, sizeof(nxt));
memset(go, -1, sizeof(go));
link = p = -1;
}
int& operator [](int x){
return nxt[x];
}
};
int cntnm;
node trienm[N];
int cntqr;
node_at trieqr[N];
int add_string(string s){
int v = 0;
for (auto it : s){
int c = it - 'a';
if (trieqr[v][c] == -1){
trieqr[cntqr] = node_at();
trieqr[cntqr].p = v;
trieqr[cntqr].pch = c;
trieqr[v][c] = cntqr;
++cntqr;
}
v = trieqr[v][c];
}
return v;
}
int go(int v, int c);
int get_link(int v){
if (trieqr[v].link == -1){
if (v == 0 || trieqr[v].p == 0)
trieqr[v].link = 0;
else
trieqr[v].link = go(get_link(trieqr[v].p), trieqr[v].pch);
}
return trieqr[v].link;
}
int go(int v, int c) {
if (trieqr[v].go[c] == -1){
if (trieqr[v][c] != -1)
trieqr[v].go[c] = trieqr[v][c];
else
trieqr[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
}
return trieqr[v].go[c];
}
int add_letter(int v, int c){
if (trienm[v][c] == -1){
trienm[cntnm] = node();
trienm[v][c] = cntnm;
++cntnm;
}
return trienm[v][c];
}
vector<int> g[N];
int tin[N], tout[N], T;
void dfs_init(int v){
tin[v] = T++;
for (auto u : g[v])
dfs_init(u);
tout[v] = T;
}
int f[N];
void upd(int v, int val){
for (int i = tin[v]; i < N; i |= i + 1)
f[i] += val;
}
int get(int x){
int sum = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
sum += f[i];
return sum;
}
int sum(int v){
return get(tout[v] - 1) - get(tin[v] - 1);
}
int n, m;
int nm[N], qr[N];
vector<int> nms[N];
vector<int> reqs[N];
int ans[N];
void dfs(int v, int cur){
upd(cur, 1);
for (auto it : nms[v])
for (auto q : reqs[it])
ans[q] = sum(qr[q]);
forn(i, AL) if (trienm[v][i] != -1)
dfs(trienm[v][i], go(cur, i));
upd(cur, -1);
}
int main(){
cntqr = 0;
trieqr[cntqr++] = node_at();
cntnm = 0;
trienm[cntnm++] = node();
char buf[N];
scanf("%d", &n);
forn(i, n){
int t;
scanf("%d", &t);
if (t == 1){
scanf("%s", buf);
nm[i] = add_letter(0, buf[0] - 'a');
}
else{
int j;
scanf("%d%s", &j, buf);
--j;
nm[i] = add_letter(nm[j], buf[0] - 'a');
}
nms[nm[i]].push_back(i);
}
scanf("%d", &m);
forn(i, m){
int j;
scanf("%d%s", &j, buf);
--j;
reqs[j].push_back(i);
qr[i] = add_string(buf);
}
for (int v = 1; v < cntqr; ++v)
g[get_link(v)].push_back(v);
T = 0;
dfs_init(0);
dfs(0, 0);
forn(i, m)
printf("%d\n", ans[i]);
}