#include <iostream>
#include <vector>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, m, k;
		cin >> n >> m >> k;
		int ans = 0;
		vector<int> v1(n);
		for (int i = 0; i < n; i++) {
			cin >> v1[i];
		}
		int o;
		for (int j = 0; j < m; j++) {
			cin >> o;
			for (int i = 0; i < n; i++) {
				if ((o + v1[i]) <= k) ans++;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    for i in range(n - 2):
        if a[i] < 0:
            print('NO')
            return
        op = a[i]
        a[i] -= op
        a[i + 1] -= 2 * op
        a[i + 2] -= op
    if a[-1] != 0 or a[-2] != 0:
        print('NO')
    else:
        print('YES')
    

for _ in range(int(input())):
    solve()

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    long long t;
    cin>>t;
    for(long long c=0;c<t;c++){
	long long n;
	cin >> n;
	string s;
	cin >> s;
	vector<long long> va;                 
	for (string sul : {"mapie", "pie", "map"}) {
		for (size_t pos = 0; (pos = s.find(sul, pos)) != string::npos;) {
			s[pos + sul.length() / 2] = '?';
			va.push_back(pos + sul.length() / 2);
		}
	}
	cout << va.size() << endl;
    }
	return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <iostream>
#include <set>

using namespace std;

int main()
{
    int t; cin >> t;
    while (t--) {
        int n, m, a; cin >> n >> m >> a;
        set <int> q[2];
        int ix = 0;
        q[ix].insert(a);
        while (m--) {
            int x; char ch; cin >> x >> ch;
            while (!q[ix].empty()) {
                int u = *(q[ix].begin());
                q[ix].erase(u);
                if (ch == '?' || ch == '0') {
                    q[ix ^ 1].insert((u + x - 1) % n + 1);
                }
                if (ch == '?' || ch == '1') {
                    q[ix ^ 1].insert((u - x - 1 + n) % n + 1);
                }
            }
            ix ^= 1;
        }
        cout << q[ix].size() << '\n';
        for (auto& x : q[ix]) {
            cout << x << ' ';
        }
        cout << '\n';
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;


int main() {

    int t = 1;
    cin >> t;
    while (t--) {
        int N, M, K, D;
        cin >> N >> M >> K >> D;
        vector<long long> a(N);
        for (int i = 0; i < N; i++) {
            vector<long long> dp(M, 1e9);
            vector<int> v(M);
            multiset<long long> mst = {1};
            dp[0] = 1;
            cin >> v[0];
            for (int j = 1; j < M - 1; j++) {
                cin >> v[j];
                dp[j] = *mst.begin() + v[j] + 1;
                if (j - D - 1 >= 0)
                    mst.erase(mst.find((dp[j - D - 1])));
                mst.insert(dp[j]);
            }
            cin >> v.back();
            dp.back() = 1 + *mst.begin();
            a[i] = dp.back();
        }

        long long cur = 0;
        for (int i = 0; i < K; i++)
            cur += a[i];

        long long mn = cur;

        for (int i = K; i < N; i++) {
            cur += a[i] - a[i - K];
            mn = min(cur, mn);
        }
        cout << mn << endl;
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

def solve():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    d = [int(x) for x in input().split()]
    f = [int(x) for x in input().split()]
    d.sort()
    f.sort()

    m1, m2 = 0, 0
    ind = -1
    for i in range(1, n):
        e = a[i] - a[i - 1]
        m2 = max(m2, e)
        if m2 > m1:
            m1, m2 = m2, m1
            ind = i - 1

    ans = m1

    target = (a[ind] + a[ind + 1]) // 2
    for model in d:
        l, r = 0, k - 1
        while r - l > 1:
            mid = (r + l) // 2
            if model + f[mid] <= target:
                l = mid
            else:
                r = mid
        ans = min(ans, max(m2, abs(model + f[l] - a[ind]), abs(model + f[l] - a[ind + 1])))
        ans = min(ans, max(m2, abs(model + f[r] - a[ind]), abs(model + f[r] - a[ind + 1])))
    print(ans)


for _ in range(int(input())):
    solve()

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

#include<bits/stdc++.h>

using LL = long long;
using ld = long double;

using namespace std;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);


    int _ = 0, __ = 1;
    cin >> __;

    for (int _ = 0; _ < __; ++_) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        map<int, int> clrs;
        int idx = n + 1;
        for (int i = 0; i < m; ++i) {
            int u, v, c;
            cin >> u >> v >> c;
            g[u].push_back({v, c});
            g[v].push_back({u, c});
            if (!clrs.count(c)) {
                clrs[c] = idx;
                idx++;
            }
        }
        int s, t;
        cin >> s >> t;
        
        if (s == t) 
        {
            cout << 0 << endl;
            continue;
        }

        vector<set<int>> bg(n + clrs.size() + 3);

        for (int i = 1; i <= n; ++i) {
            for(auto &[to, c] : g[i])
            {
                int clr_v = clrs[c];
                bg[i].insert(clr_v);
                bg[clr_v].insert(i);

                bg[to].insert(clr_v);
                bg[clr_v].insert(to);
            }
        }

        vector<int> used(bg.size());
        vector<int> d(bg.size(), -1);
        auto bfs = [&](int v)
        {
            queue<int> q;
            q.push(v);
            used[v] = 1;
            d[v] = 0;
            while (!q.empty())
            {
                auto from = q.front();
                q.pop();
                for (auto& to : bg[from])
                {
                    if (!used[to])
                    {
                        q.push(to);
                        used[to] = 1;
                        d[to] = d[from] + 1;
                    }
                }
            }
        };
        bfs(s);
        if (d[t] > 0) cout << d[t] / 2 << endl;
        else cout << -1 << endl;


    }

    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Что если гвоздь с веревкой один?

Какой длины должна быть веревка, чтобы доставать до земли?

#include <iostream>

using namespace std;


int main() {
	int test_cases;
	cin >> test_cases;

	for (int test_case = 0; test_case < test_cases; test_case++) {
		int n;
		cin >> n;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			if (a > b)
				ans++;
		}
		cout << ans << endl;
	}

	return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Какое условие победы необходимо проверить?

#include <iostream>
#include <vector>
#include <string>


using namespace std;

int main() {
	int test_cases;
	cin >> test_cases;
	for (int test_case = 0; test_case < test_cases; test_case++) {
		vector<string> v(3);
		for (int i = 0; i < 3; i++)
			cin >> v[i];
		string ans = "DRAW";
		for(int i = 0; i < 3; i++) {
			if (v[i][0] == v[i][1] && v[i][1] == v[i][2] && v[i][0] != '.')
				ans=v[i][0];
		}
		for (int i = 0; i < 3; i++) {
			if (v[0][i] == v[1][i] && v[1][i] == v[2][i] && v[0][i] != '.')
				ans=v[0][i];
		}
		if (v[0][0] == v[1][1] && v[1][1] == v[2][2] && v[0][0] != '.')
			ans=v[0][0];
		if (v[0][2] == v[1][1] && v[1][1] == v[2][0] && v[0][2] != '.')
			ans=v[0][2];
		cout << ans << endl;
	}
	return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Какой оптимальный порядок решения задач?

t₁ ≤ t₂ ≤ t₃ ≤ ... ≤ t_m

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ttt;
    cin >> ttt;
    while(ttt--){
        int n, m, h;
        cin >> n >> m >> h;
        pair<int, long long> rud;
        int ans = 1;
        for(int i = 0; i < n; i++){
            vector<int> cur(m);
            for(int j = 0; j < m; j++){
                cin >> cur[j];
            }
            std::sort(cur.begin(), cur.end());
            int task_cnt = 0;
            long long penalty = 0, sum = 0;
            for(int j = 0; j < m; j++){
                if (sum + cur[j] > h) break;
                sum += cur[j];
                penalty += sum;
                task_cnt++;
            }
            if (i){
                if (make_pair(-task_cnt, penalty) < rud) ans++;
            } else rud = {-task_cnt, penalty};
        }
        cout << ans << '\n';
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Рассмотрите треугольники в порядке снизу вверх.

Что делать, если треугольник пересекается со следующим?

Трапеция

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10); cout.setf(ios::fixed);
    int ttt;
    cin >> ttt;
    while (ttt--) {
        int n, d, h;
        cin >> n >> d >> h;
        vector<int> y(n);
        for(int i = 0; i < n; i++){
            cin >> y[i];
        }
        long double ans = (long double)d * h / 2.0;
        for (int i = 0; i + 1 < n; ++i) {
            if (y[i + 1] >= y[i] + h) ans += (long double)d * h / 2.0;
            else{
                long double d2 = (long double)d * (y[i] + h - y[i + 1]) / h;
                long double nh = y[i + 1] - y[i];
                ans += (d + d2) / 2.0 * nh;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

1 + k + k² + k³ + ... + k^p

Какое максимальное значение k может достигаться при заданных ограничениях?

Можем ли мы заранее для каждого n определить, существует ли подходящее k?

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

set<long long> nums;

int main() {

    for (long long k = 2; k <= 1000; ++k) {
        long long val = 1 + k;
        long long p = k*k;
        for (int cnt = 2; cnt <= 20; ++cnt) {
            val += p;
            if (val > 1e6) break;
            nums.insert(val);            
            p *= k;
        }
    }



    int _ = 0, __ = 1;
    cin >> __;

    for (int _ = 0; _ < __; ++_) {
        long long n;
        cin >> n;
        

        if (nums.count(n)) cout << "YES" << endl;
        else cout << "NO" << endl;

    }


    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

1 + k + k² + k³ + ... + k^p

Какое максимальное значение k может достигаться при заданных ограничениях?

Можем ли мы заранее определить, существует ли подходящее k для некоторых n и снежинок с количеством слоев от 4 и более?

Как отдельно проверить снежинки с тремя слоями?

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

set<long long> nums;

int main() {

    for (long long k = 2; k <= 1000000; ++k) {
        long long val = 1 + k;
        long long p = k*k;
        for (int cnt = 3; cnt <= 63; ++cnt) {
            val += p;
            if (val > 1e18) break;
            nums.insert(val);
            if (p > (long long)(1e18) / k) break;
            p *= k;
        }
    }



    int _ = 0, __ = 1;
    cin >> __;

    for (int _ = 0; _ < __; ++_) {
        long long n;
        cin >> n;
        if (n < 3)
        {
            cout << "NO" << endl;
            continue;
        }
        long long d = 4*n - 3;
        long long sq = sqrt(d);
        long long sqd = -1;
        for (long long i = max(0ll, sq - 5); i <= sq + 5; ++i) {
            if (i*i == d)
            {
                sqd = i;
                break;
            }
        }
        if (sqd != -1 && (sqd - 1) % 2 == 0 && (sqd - 1) / 2 > 1)
        {
            cout << "YES" << endl;
            continue;
        }

        if (nums.count(n)) cout << "YES" << endl;
        else cout << "NO" << endl;

    }


    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Как изменится количество объектов каждого типа после превращения мимика?

Что будет, когда все текущие объекты одинаковые?

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
	int test_cases;
	cin >> test_cases;
	for (int test_case = 0; test_case < test_cases; test_case++) {
		int n;
		cin >> n;
		vector<int> v(n);
		map<int, int> m;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			m[v[i]]++;
		}
		vector<int> elements_to_erase;
		int ans;
		for (int i = 0; i < 5; i++) {
			if (v.size() - elements_to_erase.size() == 1) {
				cout << "! " << ans << endl;
				break;
			}
			cout << "- " << elements_to_erase.size() << " ";
			for (int j = 0; j < elements_to_erase.size(); j++) {
				cout << elements_to_erase[j] << " ";
			}
			cout << endl;
			vector<int> new_v;
			map<int, int> new_m;
			for (int j = 0; j < v.size() - elements_to_erase.size(); j++) {
				int x;
				cin >> x;
				new_v.push_back(x);
				new_m[x]++;
			}
			elements_to_erase.clear();
			int tm = -1;
			for (auto& k : new_m) {
				if (k.second > m[k.first]) {
					tm = k.first;
				}
			}
			if (tm != -1) {
				for (int j = 0; j < new_v.size(); j++) {
					if (new_v[j] != tm)
						elements_to_erase.push_back(j + 1);
					else
						ans = j + 1;
				}
				m.clear();
				m[tm] = new_m[tm];
			}
			v = new_v;
		}
	}
	return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Битовые маски

Взвешенный граф

Алгоритм Дейкстры

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int ttt;
    cin >> ttt;
    while (ttt--) {
        int n, m;
        cin >> n >> m;
        bitset<10> tmp;
        cin >> tmp;
        int s = (int) tmp.to_ulong();
        vector<pair<pair<int, int>, int>> edges(m);
        for (int i = 0; i < m; i++) {
            cin >> edges[i].second;
            cin >> tmp;
            edges[i].first.first = ((1 << n) - 1) ^ (int) tmp.to_ulong();
            cin >> tmp;
            edges[i].first.second = (int) tmp.to_ulong();
        }
        vector<int> dist(1 << n, INT_MAX);
        dist[s] = 0;
        set<pair<int, int>> q = {{0, s}};
        while (!q.empty()) {
            auto [d, v] = *q.begin();
            q.erase(q.begin());
            for (int i = 0; i < m; i++) {
                int to = v & edges[i].first.first;
                to |= edges[i].first.second;
                if (dist[to] > d + edges[i].second) {
                    q.erase({dist[to], to});
                    dist[to] = d + edges[i].second;
                    q.insert({dist[to], to});
                }
            }
        }
        if (dist[0] == INT_MAX) dist[0] = -1;
        cout << dist[0] << '\n';
    }
    return 0;
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача