Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main(args: Array<String>) {
val T = readLine()!!.toInt()
for (t in 1..T) {
val (n, x) = readLine()!!.split(' ').map { it.toLong() }
println(x * 2)
}
}
1194B - Очередная задача про кресты
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int q;
cin >> q;
forn(_, q){
int n, m;
cin >> n >> m;
vector<string> s(n);
forn(i, n)
cin >> s[i];
vector<int> cntn(n), cntm(m);
forn(i, n) forn(j, m){
cntn[i] += (s[i][j] == '.');
cntm[j] += (s[i][j] == '.');
}
int ans = n + m;
forn(i, n) forn(j, m){
ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
}
cout << ans << "\n";
}
return 0;
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
int q;
string s, t, p;
int cnt[30];
int main() {
cin >> q;
for(int iq = 0; iq < q; ++iq){
cin >> s >> t >> p;
memset(cnt, 0, sizeof cnt);
for(auto x : p)
++cnt[x - 'a'];
bool ok = true;
int is = 0, it = 0;
while(is < s.size()){
if(it == t.size()){
ok = false;
break;
}
if(s[is] == t[it]){
++is, ++it;
continue;
}
--cnt[t[it] - 'a'];
++it;
}
while(it < t.size()){
--cnt[t[it] - 'a'];
++it;
}
if(*min_element(cnt, cnt + 30) < 0)
ok = false;
if(ok) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include <bits/stdc++.h>
using namespace std;
int n, k;
inline bool read() {
if(!(cin >> n >> k))
return false;
return true;
}
void solve() {
bool win = true;
if(k % 3 == 0) {
int np = n % (k + 1);
if(np % 3 == 0 && np != k)
win = false;
} else {
int np = n % 3;
if(np == 0)
win = false;
}
puts(win ? "Alice" : "Bob");
}
int main(){
int T; cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
1194E - Посчитайте четырехугольники
Идея: adedalic
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N = 10009;
const int INF = 1000000009;
int n;
vector <pair<int, int> > vs[N], hs[N];
int f[N];
vector <int> d[N];
void upd(int pos, int x){
for(; pos < N; pos |= pos + 1)
f[pos] += x;
}
int get(int pos){
int res = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
res += f[pos];
return res;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
const int D = 5000;
int main() {
cin >> n;
for(int i = 0; i < n; ++i){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 += D, y1 += D, x2 += D, y2 += D;
if(y1 == y2)
hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) );
else
vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) );
}
long long res = 0;
for(int y = 0; y < N; ++y) for(auto s : hs[y]){
for(int i = 0; i < N; ++i) d[i].clear();
memset(f, 0, sizeof f);
int l = s.first, r = s.second;
for(int x = l; x <= r; ++x) for(auto s2 : vs[x])
if(s2.first <= y && s2.second > y) {
d[s2.second].push_back(x);
upd(x, 1);
}
for(int y2 = y + 1; y2 < N; ++y2){
for(auto s2 : hs[y2]){
int cur = get(s2.first, s2.second);
res += cur * (cur - 1) / 2;
}
for(auto x : d[y2]) upd(x, -1);
}
}
cout << res << endl;
return 0;
}
1194F - Эксперт по кроссвордам
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int MOD = int(1e9) + 7;
inline int norm(int a) {
if(a >= MOD) a -= MOD;
if(a < 0) a += MOD;
return a;
}
inline int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
inline int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a) {
return binPow(a, MOD - 2);
}
int n;
li T;
vector<li> t;
inline bool read() {
if(!(cin >> n >> T))
return false;
t.resize(n);
fore(i, 0, n)
cin >> t[i];
return true;
}
vector<int> f, inf;
int C(int n, li k) {
if(k > n || k < 0)
return 0;
return mul(f[n], mul(inf[k], inf[n - k]));
}
inline void solve() {
f.resize(n + 5);
inf.resize(n + 5);
f[0] = inf[0] = 1;
fore(i, 1, sz(f)) {
f[i] = mul(i, f[i - 1]);
inf[i] = mul(inf[i - 1], inv(i));
}
int sumC = 1;
li bd = T;
int pw2 = 1, i2 = (MOD + 1) / 2;
vector<int> p(n + 1, 0);
fore(i, 0, n) {
pw2 = mul(pw2, i2);
sumC = norm(mul(2, sumC) - C(i, bd));
li need = t[i];
if(bd > i + 1) {
li sub = min(bd - i - 1, need);
bd -= sub, need -= sub;
}
li rem = min(bd + 1, need);
fore(k, 0, rem)
sumC = norm(sumC - C(i + 1, bd - k));
bd -= rem;
p[i] = mul(sumC, pw2);
}
int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD);
cout << ans << endl;
// cerr << mul(ans, binPow(2, n)) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1194G - Очередная мемная задача
Идея: vovuh
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int n;
int numPos[10], denPos[10];
int num, den;
const int MOD = 998244353;
struct halfState
{
int carry;
int mask;
bool comp;
halfState() {};
halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {};
};
bool operator <(const halfState& x, const halfState& y)
{
if(x.carry != y.carry) return x.carry < y.carry;
if(x.mask != y.mask) return x.mask < y.mask;
return x.comp < y.comp;
}
bool operator ==(const halfState& x, const halfState& y)
{
return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp;
}
bool operator !=(const halfState& x, const halfState& y)
{
return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp;
}
halfState go(const halfState& s, int pos, int digit, bool isNum)
{
int newDigit = digit * (isNum ? num : den) + s.carry;
int newCarry = newDigit / 10;
newDigit %= 10;
int newMask = s.mask;
int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]);
if(maskPos != -1) newMask |= (1 << maskPos);
bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp);
return halfState(newCarry, newMask, newComp);
}
struct state
{
halfState numState;
halfState denState;
state() {};
state(halfState numState, halfState denState) : numState(numState), denState(denState) {};
void norm()
{
if(numState.mask & denState.mask)
numState.mask = denState.mask = 1;
};
bool valid()
{
return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0);
};
};
bool operator <(const state& x, const state& y)
{
if(x.numState != y.numState) return x.numState < y.numState;
return x.denState < y.denState;
}
state go(const state& s, int pos, int digit)
{
halfState newNum = go(s.numState, pos, digit, true);
halfState denNum = go(s.denState, pos, digit, false);
state res(newNum, denNum);
res.norm();
return res;
}
int add(int x, int y)
{
return (x + y) % MOD;
}
int ans = 0;
void calcFixed(int x, int y)
{
num = x;
den = y;
for(int i = 0; i <= 9; i++)
numPos[i] = denPos[i] = -1;
int cnt = 0;
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
if(i * y == j * x)
{
numPos[i] = denPos[j] = cnt++;
}
vector<map<state, int> > dp(102);
dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1;
for(int i = 0; i <= 100; i++)
for(auto x : dp[i])
{
state curState = x.first;
int curCount = x.second;
for(int j = 0; j <= 9; j++)
{
state newState = go(curState, i, j);
dp[i + 1][newState] = add(dp[i + 1][newState], curCount);
}
}
for(auto x : dp[101])
{
state curState = x.first;
int curCount = x.second;
if(curState.valid())
ans = add(ans, curCount);
}
}
int main()
{
string s;
cin >> s;
int len = s.size();
reverse(s.begin(), s.end());
for(int i = 0; i < len; i++)
{
a[i] = s[i] - '0';
}
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
if(__gcd(i, j) == 1)
calcFixed(i, j);
cout << ans << endl;
}