#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int int_ceil(int x, int d){
	return (x + d - 1) / d;
}
 
void solve(){
	int n, x, y, t;
	cin >> n >> x >> y >> t;
	int ans = int_ceil(n, x + y);
	if (t * x <= n){
		ans = min(ans, int_ceil(n - t * x, x + 10 * y) + t);
	}
	cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve(){
	int n;
	cin >> n;
	if (n % 2 == 0){
		for (int i = 0; i < n; i += 2){
			cout << (i + 2) << ' ' << (i + 1) << ' ' << (i + 1) << ' ' << (i + 2) << ' ';
			cout << (i + 1) << ' ' << (i + 2) << ' ' << (i + 2) << ' ' << (i + 1) << ' ';
		}
	}
	else{
		cout << "3 3 2 1 1 2 1 2 2 3 1 3 ";
		for (int i = 3; i < n; i += 2){
			cout << (i + 2) << ' ' << (i + 1) << ' ' << (i + 1) << ' ' << (i + 2) << ' ';
			cout << (i + 1) << ' ' << (i + 2) << ' ' << (i + 2) << ' ' << (i + 1) << ' ';
		}
	}
	cout << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;

mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
 
#define int long long

bool check(vector<int> &a){
	int n = a.size() / 4;
	vector<vector<int>> p(n);
   
	for (int i = 0; i < 4 * n; i++){
	  p[a[i]].push_back(i);
	}
	for (int i = 0; i < n; i++){
	  if (p[i].size() != 4){
		return false;
	  }
	  if (p[i][1] - p[i][0] == p[i][2] - p[i][1] || 
		  p[i][3] - p[i][2] == p[i][2] - p[i][1] || 
		  p[i][3] - p[i][2] == p[i][1] - p[i][0]){
		return false;
	  }
	}
	return true;
  }
 
void solve(){
	int n;
	cin >> n;
	vector<int> a;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 4; j++){
			a.push_back(i);
		}
	}
	while(!check(a)){
		shuffle(a.begin(), a.end(), rng);
	}
	for (int x : a){
		cout << x + 1 << ' ';
	}
	cout << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int INF = 1000000007;
 
void solve(){
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
 
	int val_ans = INF;
	string ans(n, '0');
 
	for (int i = 0; i <= n; i++){
		string t = s;
		string cur_ans(n, '0');
		int cur_k = k;
 
		for (int j = 0; j < i; j++){
			if (t[j] == '(' && cur_k > 0){
				cur_ans[j] = '1';
				t[j] = ')';
				cur_k--;
			}
		}
		for (int j = n - 1; j > i; j--){
			if (t[j] == ')' && cur_k > 0){
				cur_ans[j] = '1';
				t[j] = '(';
				cur_k--;
			}
		}
		int val_cur = 0;
		int bal = 0;
		for (int j = 0; j < n; j++){
			if (bal > 0 && t[j] == ')'){
				val_cur += 2;
				bal--;
			}
			else if (t[j] == '('){
				bal++;
			}
		}
		if (val_ans > val_cur){
			val_ans = val_cur;
			ans = cur_ans;
		}
	}
 
	cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int INF = 1000000007;
 
void solve(){
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
 
	vector<int> pref_open(n + 1);
	vector<int> pref_close(n + 1);
 
	for (int i = 0; i < n; i++){
		pref_open[i + 1] = pref_open[i] + (s[i] == '(');
		pref_close[i + 1] = pref_close[i] + (s[i] == ')');
	}
 
	int total_close = pref_close[n];
 
	int pos = n;
	for (int i = 0; i < n; i++){
		if (pref_open[i] + total_close - pref_close[i] <
			pref_open[pos] + total_close - pref_close[pos]){
				pos = i;
		}
	}
 
	string ans(n, '0');
	for (int i = 0; i < pos; i++){
		if (k > 0 && s[i] == '('){
			ans[i] = '1';
			k--;
		}
	}
	for (int i = pos; i < n; i++){
		if (k > 0 && s[i] == ')'){
			ans[i] = '1';
			k--;
		}
	}
 
	cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
 
	auto b = a;
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for (int i = 0; i < n; i++){
		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
	}
 
	vector<vector<int>> blocks(n);
	vector<int> cntb(n);
 
	for (int i = 0; i < n; ){
		int j = i;
		while(i < n && a[i] == a[j]){
			i++;
		}
		blocks[a[j]].push_back(i);
		blocks[a[j]].push_back(i - 1);
 
		blocks[a[j]].push_back(j);
		blocks[a[j]].push_back(j - 1);
		cntb[a[j]]++;
	}
 
	auto check = [&](int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= n){
			return 0;
		}
		swap(a[x], a[y]);
		vector<int> cnt(n);
		for (int i = 0; i < n;){
			int j = i;
			while(i < n && a[i] == a[j]){
				i++;
			}
			cnt[a[j]]++;
		}
		swap(a[x], a[y]);
		for (int i = 0; i < n; i++){
			if (cnt[i] > 1){
				return 0;
			}
		}
		return 1;
	};
 
	for (int i = 0; i < n; i++){
		if (cntb[i] > 1){
			if (cntb[i] > 3){
				cout << "NO\n";
				return;
			}
			bool ok = 0;
			sort(blocks[i].begin(), blocks[i].end());
			blocks[i].erase(unique(blocks[i].begin(), blocks[i].end()), blocks[i].end());
			for (int x : blocks[i]){
				for (int y : blocks[i]){
				    if (x < y){
					    ok |= check(x, y);
				    }
				}
			}
			if (!ok){
				cout << "NO\n";
				return;
			}
			break;
		}
	}
 
	cout << "YES\n";
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) (int)(a.size())

#ifdef LOCAL
#define __lg(n) log2(n)
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128;

template<typename T>
using PQ = priority_queue<T, vector<T>, greater<>>;

const int N = (1 << 18);

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    iota(all(p), 1);
    int k = 0;
    while ((1 << (k)) <= n) ++k;
    vector<string> s(n);
    for (int i = 0; i < k; ++i) cin >> s[i];
    map<string, int> used;
    int pp = 1;
    for (int i = 0; i < k; ++i) pp *= 3;
    for (int i = 0; i < n; ++i) {
        string z;
        for (int j = 0; j < k; ++j) z += s[j][i];
        if (*max_element(all(z)) == '0') {
            cout << 0 << '\n';
            return;
        }
        if (used[z]) {
            cout << 0 << '\n';
            return;
        }
        used[z] = 1;
    }
    vector<bitset<N>> cum(k);
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cum[i][j] = bool(s[i][j] - '0');
        }
    }
    vector<bitset<N>> ed((1 << k));
    ed[0].set();
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int i = 0; i < k; ++i) {
            if ((1 << i) & mask) {
                ed[mask] = ed[mask - (1 << i)] & cum[i];
                break;
            }
        }
    }

    auto get_mask = [&](int mask1, int mask2) -> int {
        int res = 0;
        int pw = 1;
        for (int i = 0; i < k; ++i) {
            if (mask2 & (1 << i)) {
                res += 2 * pw;
            } else if (mask1 & (1 << i)) {
                res += pw;
            }
            pw *= 3;
        }
        return res;
    };

    auto from_mask = [&](int val) -> pair<int, int> {
        int pw = 1;
        for (int i = 0; i < k - 1; ++i) {
            pw *= 3;
        }
        int mask1 = 0, mask2 = 0;
        for (int i = k - 1; i >= 0; --i) {
            int ost = val % pw;
            int tmp = val / pw;
            val = ost;
            if (tmp == 2) {
                mask1 += (1 << i), mask2 += (1 << i);
            } else if (tmp == 1) {
                mask1 += (1 << i);
            }
            pw /= 3;
        }
        return {mask1, mask2};
    };

    vector<ll> dp(pp, 0);
    dp[0] = 1;
    ll ans = 0;
    for (int mask = 0; mask < pp; ++mask) {
        if (dp[mask] == 0) continue;
        auto gd = from_mask(mask);
        int mask1 = gd.first, mask2 = gd.second;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (mask1 & (1 << i)) {
                ++cnt;
            }
        }
        if (cnt == k) {
            ans += dp[mask];
            continue;
        }
        int deg = k - 1 - cnt;
        if (n & (1 << deg)) {
            for (int i = 0; i < k; ++i) {
                if ((1 << i) & mask1) continue;
                auto mask_res = get_mask(mask1 + (1 << i), mask2 + (1 << i));
                dp[mask_res] += dp[mask];
            }
        } else {
            for (int i = 0; i < k; ++i) {
                if ((1 << i) & mask1) continue;
                auto tmp_bit = ed[mask2] & cum[i];
                if (dp[mask] != 0 && tmp_bit.none()) {
                    dp[get_mask(mask1 + (1 << i), mask2)] += dp[mask];
                }
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve(){
	int n;
	cin >> n;
 
	int k = 1;
	while((1 << k) <= n){
		k++;
	}
 
	vector<string> s(k);
	for (int i = 0; i < k; i++){
		cin >> s[i];
	}
	vector<pair<int, int>> ord(k, {0ll, 0ll});
	for (int i = 0; i < k; i++){
		auto& [x, ind] = ord[i];
		ind = i;
		for (int j = 0; j < n; j++){
			x += (s[i][j] == '1');
		}
	}
	sort(ord.rbegin(), ord.rend());
 
	vector<int> fact(k + 1);
	fact[0] = 1;
	for (int i = 1; i <= k; i++){
		fact[i] = fact[i - 1] * i;
	}
 
	vector<int> p(n);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < k; j++){
			int bit = s[ord[j].second][i] - '0';
			p[i] ^= (bit << j);
		}
	}
	sort(p.begin(), p.end());
	if (p[0] != 1){
		cout << 0 << '\n';
		return;
	}
	for (int i = 1; i < n; i++){
		if (p[i] != p[i - 1] + 1){
			cout << 0 << '\n';
			return;
		}
	}
 
	vector<int> cnt(n + 1);
	for (auto [x, ind] : ord){
		cnt[x]++;
	}
 
	int ans = 1;
	for (int i = 0; i <= n; i++){
		ans *= fact[cnt[i]];
	}
	cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

#include<bits/stdc++.h>
 
using namespace std;
 
//#define int long long
 
const int INF = 1000000007;
 
void solve(){
	int n, a, b;
	cin >> n >> a >> b;
 
	int g = gcd(a, b);
	a /= g;
	b /= g;
 
	vector<int> d1, d2;
	for (int i = 1; i * i <= a; i++){
		if (a % i == 0){
			d1.push_back(i);
			if (i * i != a){
				d1.push_back(a / i);
			}
		}
	}
 
	for (int i = 1; i * i <= b; i++){
		if (b % i == 0){
			d2.push_back(i);
			if (i * i != b){
				d2.push_back(b / i);
			}
		}
	}
 
	sort(d1.begin(), d1.end());
	sort(d2.begin(), d2.end());
 
	int sz1 = d1.size();
	int sz2 = d2.size();
 
	vector<vector<int>> to_d1(sz1, vector<int> (sz1, -1));
	for (int i = 0; i < sz1; i++){
		int u = 0;
		for (int j = i; j >= 0; j--){
			while(u < i && d1[i] > d1[u] * d1[j]){
				u++;
			}
			if (d1[i] % d1[j] == 0 && d1[i] / d1[j] == d1[u]){
				to_d1[i][j] = u;
			}
		}
	}
 
	vector<vector<int>> to_d2(sz2, vector<int> (sz2, -1));
	for (int i = 0; i < sz2; i++){
		int u = 0;
		for (int j = i; j >= 0; j--){
			while(u < i && d2[i] > d2[u] * d2[j]){
				u++;
			}
			if (d2[i] % d2[j] == 0 && d2[i] / d2[j] == d2[u]){
				to_d2[i][j] = u;
			}
		}
	}
 
	vector<vector<int>> dels_d1(sz1);
	for (int i = 0; i < sz1; i++){
		for (int j = 0; j <= i; j++){
			if (d1[i] % d1[j] == 0){
				dels_d1[i].emplace_back(j);
			}
		}
	}
 
	vector<vector<int>> dels_d2(sz2);
	for (int i = 0; i < sz2; i++){
		for (int j = 0; j <= i; j++){
			if (d2[i] % d2[j] == 0){
				dels_d2[i].emplace_back(j);
			}
		}
	}
 
	vector<vector<int>> dp(sz1, vector<int> (sz2, -1));
 
	auto go = [&](auto&& self, int x, int y) -> int{
		if (dp[x][y] != -1){
			return dp[x][y];
		}
		if (x == 0 && y == 0){
			return 0;
		}
		dp[x][y] = INF;
 
		for (int dx : dels_d1[x]){
			for (int dy : dels_d2[y]){
				if (dx == 0 && dy == 0){
					continue;
				}
				dp[x][y] = min(dp[x][y], max(d1[dx], d2[dy]) + self(self, to_d1[x][dx], to_d2[y][dy]));
			}
		}
		return dp[x][y];
	};
 
	cout << go(go, sz1 - 1, sz2 - 1) << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	//cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача