It is always possible to rearrange the candies, unless candies of one specific color appears too often.

Let $$$x$$$ be the color with the highest number of candies. In case of ties, $$$x$$$ could be any of the candidates. Denote the number of candies with color $$$x$$$ as $$$a$$$.

Conclusion: The answer to the problem is YES if and only if there are no more than $$$n^2 - n$$$ candies of color $$$x$$$; — in other words, $$$a\le n^2 - n$$$ holds.

Proof of necessity: If there are more than $$$n^2 - n$$$ candies of color $$$x$$$, then there are less than $$$n$$$ candies not of color $$$x$$$. Since there are $$$n$$$ rows, at least one row will have no candies not of color $$$x$$$; therefore, such a row will be filled with candies of color $$$x$$$, violating the restrictions.

Proof of sufficiency: If there are no more than $$$n^2 - n$$$ candies of color $$$x$$$, we can always construct a solution with the method below.

First, if $$$a \lt n$$$ holds, then we can arrange the candies arbitrarily because no color has enough candies to fill a row or a column.

Otherwise, $$$n\le a\le n^2 - n$$$ holds.

We can put candies of color $$$x$$$ in $$$a_{1,1},a_{2,2},\ldots,a_{n,n}$$$. This will take $$$n$$$ candies of color $$$x$$$. Next, we choose $$$n$$$ candies not of color $$$x$$$ arbitrarily. We will put them at $$$a_{1,2},a_{2,3},\ldots,a_{n-1,n},a_{n,1}$$$. Lastly, we arrange other candies that have not yet been arranged arbitrarily. Since in the first step we put a candy of color $$$x$$$ in each row and column, and in the second step we put a candy not of color $$$x$$$ in each row and column, each row and column contains at least candies of two colors, satisfying the constraints.

#include<bits/stdc++.h>
#define F(i,x,y) for (int i=(x);i<=(y);i++)
#define R(i,x,y) for (int i=(x);i>=(y);i--)
#define p2i pair<int,int>
#define ll long long
#define fi first
#define se second
#define nb(x) (1<<((x)-1))
#define x1 __melody1
#define x2 __melody2
#define y1 __melody3
#define y2 __melody4
#define iosoptim ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
 
const bool MT = 1;
int n,cnt[10005];
void ygg(){
    cin>>n;
    int tmp;
    bool flag=1;
    F(i,1,n*n) {
        cin>>tmp;
        ++cnt[tmp];
        if (cnt[tmp]>n*(n-1)) flag=0;
    }
    if (flag) cout<<"YES\n";
    else cout<<"NO\n";
}
void mark() {
    F(i,1,n*n) cnt[i]=0;
}
int main (){
#ifdef ONLINE_JUDGE
    iosoptim
#endif
    int testcases=1;
    if(MT) cin>>testcases;
    while(testcases--){
        ygg();
        mark();
    }
    return 0;
}

good (likes:1,option1) mid (likes:1,option2) bad (likes:1,option3) didn't solve (likes:1,option4)

For the sake of simplicity, let's assume all cards have different costs. If multiple cards have the same cost, we break ties by their initial position in the deck (the earlier card is considered to have a lower cost for the purpose of the strategy).

The optimal strategy: If the win-condition is among the first $$$k$$$ cards, then we play it. Otherwise, we play the card in the first $$$k$$$ places with the lowest cost. Proof of optimality is shown below.

Lemma: If at any time, the win-condition is placed at position $$$x \gt k$$$, the cost used before the win-condition is played again is at least the sum of the costs of $$$x-k$$$ cards with the lowest costs out of all the $$$x-1$$$ cards placed before the win-condition. Our strategy reaches this minimum value.

Proof:

Since playing any card in front of the win-condition moves the win-condition 1 place toward the front, we need to play $$$x-k$$$ normal cards before the win-condition is playable.

Before the win-condition moves to position $$$k$$$ and becomes playable, every card placed before the win-condition can be played at most once, and every card placed at the back of the win-condition cannot be played. Therefore, the cost used is at least the sum of the first $$$x-k$$$ lowest costs of the cards initially placed before the win-condition. We mark the $$$x-k$$$ cards placed before the win-condition with the lowest costs.

Among all the $$$x-1$$$ cards placed before the win-condition, exactly $$$k-1$$$ cards are not marked, so whenever before the win-condition is played the first time, at least one marked card will be in the first $$$k$$$ places. Therefore, our strategy will always play a marked card in the first $$$x-k$$$ plays since their costs are always lower than not marked ones. Since each marked card can be only played for at most once, after $$$x-k$$$ plays we will play each marked card once, which achieves the lower bound described above.

Therefore, the lemma is proven.

Now, let $$$A$$$ be the sum of the costs of $$$p-k$$$ cards with the lowest costs placed before the win-condition. Let $$$B$$$ be the sum of the costs of $$$n-k$$$ cards with the lowest costs, without considering the win-condition.

By the above lemma, the cost spent before playing the win-condition the first time is at least $$$A$$$. After it is played each time, it always gets placed at position $$$n$$$, so the cost spent before playing the win-condition another time is at least $$$B$$$. Our strategy achieves the minimum.

Therefore, the cost used to play the win-condition any non-negative number of times is minimized, which proves the optimality of the strategy.

The answer is $$$\lfloor \dfrac{m-A-a_p}{B+a_p}\rfloor + 1$$$ if $$$m-A-a_p\ge 0$$$. Otherwise, the answer is $$$0$$$.

The value of $$$A$$$ and $$$B$$$ can be calculated with a priority queue in $$$O(n\log n)$$$. Therefore, the overall time complexity is $$$O(n\log n)$$$.

Alternatively, you may simulate the strategy above directly; the time complexity will be $$$O(nm)$$$, which is also sufficient to pass.

#include<bits/stdc++.h>
#define F(i,x,y) for (int i=(x);i<=(y);i++)
#define R(i,x,y) for (int i=(x);i>=(y);i--)
#define p2i pair<int,int>
#define ll long long
#define fi first
#define se second
#define nb(x) (1<<((x)-1))
#define x1 __melody1
#define x2 __melody2
#define y1 __melody3
#define y2 __melody4
#define iosoptim ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

const bool MT = 1;
int n,k,p,a[100005];
ll m;
void ygg(){
	cin>>n>>k>>p>>m;
	F(i,1,n) cin>>a[i];
	multiset<int> opt;
	F(i,1,k-1) opt.insert (a[i]);
	F(i,k,p-1) {
		opt.insert (a[i]);
		m-=*opt.begin ();
		opt.erase (opt.begin ());
	}
	m-=a[p];
	if (m<0) {
	    cout<<0<<"\n";
	    return;
	}
	ll sum=a[p];
	opt.clear ();
	F(i,1,n) {
		if (i!=p) opt.insert (a[i]);
	}
	F(i,1,n-k) {
		sum+=*opt.begin ();
		opt.erase (opt.begin ());
	}
	cout<<1+m/sum<<"\n";
}
void mark() {

}
int main (){
#ifdef ONLINE_JUDGE
	iosoptim
#endif
	int testcases=1;
	if(MT) cin>>testcases;
	while(testcases--){
		ygg();
		mark();
	}
	return 0;
}

good (likes:2,option1) mid (likes:2,option2) bad (likes:2,option3) didn't solve (likes:2,option4)

Notice that the value of $$$S$$$ does not affect your decision. This meant for integer $$$i\in[1,n-1]$$$ the decision of tasks $$$[1,i]$$$ does not affect the decision of tasks $$$[i+1,n]$$$.

Let $$$f_i$$$ be the answer for considering tasks $$$[i,n]$$$ only and assuming that $$$S=1$$$. It holds that $$$f_i=\max(f_{i-1},f_{i-1}\cdot(1-\frac{p_i}{100})+c_i)$$$, and $$$f_1$$$ is the answer needed.

#include<bits/stdc++.h>
#define ld long double
using namespace std;
const int N=1e5+5;
ld c[N],p[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int cv,pv;
		cin>>cv>>pv;
		c[i]=cv,p[i]=pv/100.0;
	}
	ld ans=0;
	for(int i=n;i>=1;i--){
		ans=max(ans,ans*(1-p[i])+c[i]);
	}
	cout<<fixed<<setprecision(10)<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	for(int i=1;i<=T;i++) solve();
}

good (likes:3,option1) mid (likes:3,option2) bad (likes:3,option3) didn't solve (likes:3,option4)

If a solution exists, it must be unique.

Assume a solution exists, construct the graph accordingly, and verify afterward that it satisfies all given conditions.

Consider the necessary and sufficient condition for the existence of a directed edge $$$ u \to v $$$.

Two conditions must hold:
1. Node $$$ v $$$ must be reachable from $$$ u $$$.
2. There must be no intermediate node $$$ w $$$ such that $$$ u $$$ can reach $$$ w $$$ and $$$ w $$$ can reach $$$ v $$$.

Implementing this directly yields an $$$ O(n^3) $$$ solution, which is sufficient for D1. One can further optimize it to $$$ O\left(\frac{n^3}{\omega}\right) $$$ using bitsets, though this is not required for this subtask.

Let $$$ R_u $$$ denote the set of nodes reachable from $$$ u $$$, excluding $$$ u $$$ itself.

Let $$$ s_u $$$ denote the number of nodes reachable from $$$ u $$$. Among all nodes in $$$ R_u $$$, let $$$ v $$$ be the one with the largest $$$ s_v $$$. What can we infer?

It can be proven that the edge $$$ u \to v $$$ must exist in the solution.

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e4+5;
int n, id[N], cnt[N];
bool vs[N], e[N][N];
struct Dsu {
	int fa[N];
	void init(int n) {
		for (int i = 1; i <= n; i++) fa[i] = i;
	}
	int find(int x) {
		if (x == fa[x]) return x;
		return fa[x] = find(fa[x]);
	}
	void merge(int x, int y) {
		fa[find(x)] = find(y);
	}
} dsu;
bool reach[N];
vector<int> tree[N];
void search(int u) {
	reach[u] = 1;
	for (int v : tree[u]) {
		search(v);
	}
}
void solve(int tid) {
	cin >> n;
	for (int i = 1; i <= n; i++) cnt[i] = 0, tree[i].clear();
	for (int u = 1; u <= n; u++) {
		id[u] = u;
		string s;
		cin >> s;
		for (int v = 1; v <= n; v++) {
			e[u][v] = s[v-1]-'0';
			cnt[u] += e[u][v];
		}
	}
	sort(id + 1, id + n + 1, [&](int u, int v) {
		return cnt[u] > cnt[v];
	});
	vector<pair<int, int >> edges;
	for (int u = 1; u <= n; u++) {
		for(int i = 1; i <= n; i++) {
			vs[i] = false;
		}
		vs[u] = true;
		for (int i = 1; i <= n; i++) {
			int v = id[i];
			if (!vs[v] && e[u][v]) {
				edges.push_back({u, v});
				if(edges.size() >= n) {
					cout << "No" << "\n";
					return ;
				}
				for (int w = 1; w <= n; w++) {
					if (e[v][w]) {
						vs[w] = true;
					}
				}
			}
		}
	}
	if (edges.size() != n - 1) {
		cout << "No" << "\n";
		return ;
	}
	sort(edges.begin(), edges.end());
	dsu.init(n);
	for (auto [u, v] : edges) {
		dsu.merge(u, v);
		tree[u].push_back(v);
	}
	int flag = 1;
	for (int i = 1; i <= n; i++) flag &= (dsu.find(i) == dsu.find(1));
	if (!flag) {
		cout << "No" << "\n";
		return ;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) reach[j] = 0;
		search(i);
		for (int j = 1; j <= n; j++) {
			if (reach[j] != e[i][j]) {
				cout <<  "No" << "\n";
				return ;
			}
		}
	}
	cout<< "Yes\n";
	for (auto [u, v] : edges) {
		cout << u << ' ' << v << '\n';
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++) solve(i);
	return 0;
}

good (likes:4,option1) mid (likes:4,option2) bad (likes:4,option3) didn't solve (likes:4,option4)