A. PAS C3
Idea:agrim07
Try writing conditions inform of formula
A. PAS C3
For rajat to pass it should answer should be max(marks to get 4CG,marks to pass C3). which is max(marks of 4CG,12). Let marks required to pass C3 is c so following conditions should be satisfied
Which can be re -written as
But since 2*h/5 can be a float value so we need to take ceil of h*2/5 which is (2*h+(5-1))/5. So final condition is
To get ans simply take max(c,12).
(We can also check for each value from 12 to 40 and simply output first number satisfying CG>=4)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << max(12LL, (2 * c + 4) / 5 - a - b) << endl;
}
signed main() {
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
return 0;
}
Idea:pvtr
Think of three case when last letter of given string is ‘s’ , ‘m’ and ‘l’
B. Yet Another Merchandise distribution
To solve this problem we will take three cases when input string last character is S Then we need to output in descending order. And if it is M then it should be placed after all small sized merch. And if it is L then need to simply arrange in ascending and output.
For Implementation of this, in solution we used a comparator function in which we assigned a value to each string k-XS represent (-k), M represents 0 and k-XL represents +k so simply we can sort in ascending order of assigned value which will give us required array.
#include <bits/stdc++.h>
using namespace std;
int get(string &a) {
int A = 0;
if(a.size() == 1) A = 0;
else {
if(a.back() == 'S') A -= (a[0] - '0');
else A += (a[0] - '0');
}
return A;
}
bool cmp(string &a, string &b) {
if(get(a) < get(b)) return true;
return false;
}
void solve(){
int n; cin >> n;
vector<string> s(n);
for(auto &x: s)
cin >> x;
sort(s.begin(), s.end(), cmp);
for(auto &x: s) cout << x << " ";
cout << "\n";
}
int main() {
int t; cin >> t;
while(t--) solve();
}
C — Fibonacci Parity
Idea: Fremder
find pattern
In the defined Fibonacci sequence $$$s$$$, initially established with $$$s_0$$$ = ‘0’ and $$$s_1$$$ = ‘1’ , concatenating the last string with the second-to-last string yields alternating parity. consequently, for $$$s_i$$$ , if $$$i$$$ is even, the parity of $$$s_i$$$ is even, and if $$$i$$$ is odd, the parity of $$$s_i$$$ is odd.
Upon observation, it's evident that the function $$$f(s)$$$ generates the Fibonacci sequence starting from $$$f(s_2)$$$ . Given the established fact that every third Fibonacci number is even, we can conclude that $$$f(s)$$$ is even for $$$s$$$ = $$$s_{2+3i}$$$ and odd otherwise .
Now we got parity for nth element of both $$$s$$$ and $$$f(s)$$$ , compare parity of both and answer .
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;
const int N=1e5;
void solve(){
int n;
cin >> n;
bool s = ((n%2)==0);
bool fs = ((n%3)==2);
if(s == fs){
cout << "YES";
}else cout << "NO";
cout << endl;
}
signed main() {
fastio();
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
D — Subsequence Query
Idea: Fremder
prefix and suffix
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;
const int N=1e5;
void solve(){
int m, n;
cin >> n >> m;
string s, t;
cin >> s >> t;
int index = 0;
s.insert(0, "0"); t.insert(0, "0");
vector<int> pre(n + 1), suff(n + 2);
for(int i = 1; i <= n; i++) {
if(s[i] == t[index + 1] and index<m)
index++;
pre[i] = index;
}
suff.back() = index = t.size();
for(int i = n; i > 0; i--) {
if(s[i] == t[index - 1] and index>1)
index--;
suff[i] = index;
}
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
if(suff[r + 1] - pre[l - 1] < 2)
cout << "YES\n";
else
cout << "NO\n";
}
}
signed main() {
fastio();
int t = 1;
while(t--){
solve();
}
return 0;
}
E. Destroy them All
Idea:NirbhayPaliwal
Think of humans always moving in one direction say left or right.
Think of Applying Binary Search
E. Destroy Them All
Since we are asked for non-zero probability then we just need to show one single configuration of movement such that all spots get destroyed. we can think of all humans moving together to either left or right as if it is possible to destroy all spots by splitting then it will surely be possible to destroy by all humans moving in a specific direction.
Now Let's take this whole problem as n sub-problem where answer to ith problem is number humans to be deployed on ith spot.
Now if we are able to destroy all spots by deploying k number of humans then we will surely be able to do it by deploying k+1 people. Hence to solve this sub problem we apply binary search on number of humans to be deployed, And to check for any value we will maintain one variable buff number of humans which can move, use two pointers one pointing at left side of destroyed site and other at right side And if it is possible to destroy any site by placing buff on it simply destroy it and in this way if we can destroy them all then k value returns true.
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<int> a,b;
int n;
bool check(int key,int ind)
{
int s=ind-1,e=ind+1;
int buff=key+a[ind]; // extra people which can go to any site once their site is broken
while(s!=-1 || e!=n)
{
int flag=0 ;// to check buff changes
if(s!=-1)
{
if(a[s]+buff>=b[s])
{
buff+= a[s];
s--;
flag=1;
}
}
if(e!=n)
{
if(a[e]+buff>=b[e])
{
buff+= a[e];
e++;
flag=1;
}
}
if(!flag) return 0;
}
return 1;
}
signed main()
{
int T;
cin >> T;
while(T--)
{
cin >> n;
a.clear();b.clear();
a.resize(n);b.resize(n);
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++) cin >> b[i];
vector<int> ans(n);
for(int i=0;i<n;i++)
{
int lo=(b[i]-a[i]),hi=1e12;
while(hi-lo>1)
{
int mid=(hi+lo)/2;
if(check(mid,i))
{
hi=mid;
}
else
{
lo=mid+1;
}
if(check(lo,i)) ans[i]=lo;
else ans[i]=hi;
}
}
for(int i=0;i<n;i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
}
F — PAS Makeup
Idea: agrim07
Try to use DP to solve this problem
Let $$$dp[i][p][q][turn]$$$ denote the probability of Rajat winning the game, where:
- $$$i$$$ denotes the number of turns left,
- $$$p$$$ denotes the parity of Rajat’s score,
- $$$q$$$ denotes the parity of Dr. S’s score, and
- $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.
Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing even and odd elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.
The transitions will be as follows:
If it is Rajat’s turn, then there are 2 additional cases:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
Similarly, for Dr. S’s turn:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
where $$$p_n$$$ is the probability of rolling $$$n$$$.