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

int main(){
	int t; cin >> t;
	for(int i = 0; i < t; i++){
		long long n, s; 
		cin >> n >> s;
		cout << s / (n * n) << "\n";
	}
	return 0;
}

It can be proven that (try to prove it!) if some $$$k$$$ works, then $$$k=\displaystyle \left \lfloor \frac{n-1}{2} \right \rfloor$$$ has to work. This means that there is always an answer using $$$n$$$ or $$$n-1$$$ elements, depending on parity.

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

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <long long> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		sort(a.begin(), a.end());
		vector <long long> prefix_sums = {0};
		for(int i = 0; i < n; i++){
			prefix_sums.push_back(prefix_sums.back() + a[i]);
		}
		vector <long long> suffix_sums = {0};
		for(int i = n - 1; i >= 0; i--){
			suffix_sums.push_back(suffix_sums.back() + a[i]);
		}
		bool answer = false;
		for(int k = 1; k <= n; k++){
			if(2 * k + 1 <= n){
				long long blue_sum = prefix_sums[k + 1];
				long long red_sum = suffix_sums[k];
				if(blue_sum < red_sum){
					answer = true;
				}
			}
		}
		if(answer) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Actually, there is no problem in repeating $$$1$$$, $$$2$$$, or any other power of two. This is because it can be proven that (try to prove it!) those sums are not optimal.

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

const long long MAXAI = 1000000000000ll;

int get_first_bit(long long n){
	return 63 - __builtin_clzll(n);
}

int get_bit_count(long long n){
	return __builtin_popcountll(n);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		long long n; cin >> n;
		//Computing factorials <= MAXAI
		vector<long long> fact;
		long long factorial = 6, number = 4;
		while(factorial <= MAXAI){
			fact.push_back(factorial);
			factorial *= number;
			number++;
		}
		//Computing masks of factorials
		vector<pair<long long, long long>> fact_sum(1 << fact.size());
		fact_sum[0] = {0, 0};
		for(int mask = 1; mask < (1 << fact.size()); mask++){
			auto first_bit = get_first_bit(mask);
			fact_sum[mask].first = fact_sum[mask ^ (1 << first_bit)].first + fact[first_bit];
			fact_sum[mask].second = get_bit_count(mask);
		}
		long long res = get_bit_count(n);
		for(auto i : fact_sum){
			if(i.first <= n){
				res = min(res, i.second + get_bit_count(n - i.first));
			}
		}
		cout << res << "\n";
	}
	
	return 0;
}

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

const int MAXN = 400005;

vector<int> g[MAXN];

bool vis[MAXN];
int pa[MAXN];

//DFS to compute the parent of each node
//parent of node i is stored at pa[i]
void dfs(int v){
	vis[v] = 1;
	for(auto i : g[v]){
		if(!vis[i]){
			pa[i] = v;
			dfs(i);
		}
	}
}

pair<int, int> dp[MAXN][2];

//Computes the value of function f, using dp
//the second coordinate of the pair is negated (to take maximums)
pair<int, int> f(int x, int y){
	pair<int, int> & res = dp[x][y];
	if(res.first >= 0) return res;
	res = {y, y ? -((int) g[x].size()) : -1};
	for(auto i : g[x]){
		if(i != pa[x]){
			pair<int, int> maxi = f(i, 0);
			if(y == 0) maxi = max(maxi, f(i, 1));
			res.first += maxi.first;
			res.second += maxi.second;
		}
	}
	return res;
}

vector<int> is_good;

//Recursive construction of the answer
//is_good[i] tells whether vertex i is good or not.
void build(pair<int, int> value, int v){
	if(value == f(v, 0)){
		is_good[v] = 0;
		for(auto i : g[v]){
			if(i != pa[v]){
				build(max(f(i, 0), f(i, 1)), i);
			}
		}
	}else{
		is_good[v] = 1;
		for(auto i : g[v]){
			if(i != pa[v]){
				build(f(i, 0), i);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v; 
		cin >> u >> v; u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if(n == 2){
		cout<<"2 2\n1 1\n";
		return 0;
	}
	pa[0] = -1;
	dfs(0);
	for(int i = 0; i < n; i++) dp[i][0] = {-1, -1}, dp[i][1] = {-1, -1};
	pair<int, int> res = max(f(0, 0), f(0, 1));
	cout << res.first << " " << -res.second << "\n";
	is_good.resize(n);
	build(res, 0);
	for(int i = 0; i < n; i++){
		if(is_good[i]) cout << g[i].size() << " ";
		else cout << "1 ";
	}
	cout << "\n";
	return 0;
}

This solution uses the fact that $$$m\le 10^6$$$, other solutions do not use this, and work for much larger values of $$$m$$$ (like $$$m\leq 10^{18}$$$, but taking the answer modulo some big prime number). Try to solve the problem with this new constraint!

#include <bits/stdc++.h>
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
using namespace std;
typedef long long ll;

const int MAXM = 1000006;

const int MAXLOGN = 20;

bool visited_mul[MAXM * MAXLOGN];

int main(){
	ll n, m; cin >> n >> m;
	vector<ll> mul_quan(MAXLOGN);
	ll current_vis = 0;
	fore(i, 1, MAXLOGN){
		fore(j, 1, m+1){
			if(!visited_mul[i * j]){
				visited_mul[i * j] = 1;
				current_vis++;
			}
		}
		mul_quan[i] = current_vis;
	}
	ll res=1;
	vector<ll> vis(n + 1);
	fore(i, 2, n+1){
		if(vis[i]) continue;
		ll power = i, power_quan = 0;
		while(power <= n){
			vis[power] = 1;
			power_quan++;
			power *= i;
		}
		res += mul_quan[power_quan];
	}
	cout << res << "\n";
	
	return 0;
}

#include <bits/stdc++.h>
#define fore(i, a, b) for(int i = a; i < b; ++i)
using namespace std;
 
const int MAXN = 1010;

//c[i][j] = number of cards player i has, with the number j
int c[MAXN][MAXN];
 
//extras[i] is the stack of repeated cards for player i.
vector<int> extras[MAXN];
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n;
	fore(i, 0, n){
		fore(j, 0, n){
			int x; cin >> x; x--;
			c[i][x]++;
			if(c[i][x] > 1) extras[i].push_back(x);
		}
	}
	vector<vector<int>> res;
	//First part
	while(true){
		//oper will describe the next operation to perform
		vector<int> oper(n);
		//s will be the first non-diverse player
		int s = -1;
		fore(i, 0, n){
			if(extras[i].size()){
				s = i;
				break;
			}
		}
		if(s == -1) break;
		//last_card will be the card that the previous player passed
		int last_card = -1;
		fore(i, s, s + n){
			int real_i = i % n;
			if(extras[real_i].size()){
				last_card = extras[real_i].back();
				extras[real_i].pop_back();
			}
			oper[real_i] = last_card;
		}
		res.push_back(oper);
		fore(i, 0, n){
			int i_next = (i + 1) % n;
			c[i][oper[i]]--;
			c[i_next][oper[i]]++;
		}
		fore(i, 0, n){
			int i_next = (i + 1) % n;
			if(c[i_next][oper[i]] > 1) extras[i_next].push_back(oper[i]);
		}
	}
	//Second part
	fore(j, 1, n){
		vector<int> oper;
		fore(i, 0, n) oper.push_back((i - j + n) % n);
		fore(i, 0, j) res.push_back(oper);
	}
	cout << res.size() << "\n";
	for(auto i : res){
		for(auto j : i) cout<< j + 1 << " ";
		cout << "\n";
	}
	return 0;
}