Link to the contest: https://mirror.codeforces.com/contests/397164 (Problems are at 1300- difficulty).
A. Another Sanity Check, Why Not?
Idea: FazeCT
First, you have to check if $$$n$$$ is in one of the following $$$3$$$ ranges: $$$48 \le n \le 57$$$, $$$65 \le n \le 90$$$, $$$97 \le n \le 122$$$.
If no, then output "Lmao".
Else, use char() to output the character associated with the number $$$n$$$.
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin >> n;
if(n<48 || (n>57 && n<65) || (n>90 && n<97) || n>122) cout << "Lmao" << endl;
else cout << char(n) << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
B. Seghhhhhhhhh
Idea: Onirique
If the length of the given string s is odd, then the answer is $$$NO$$$, since adding two strings cannot do that. Otherwise, let $$$n$$$ be the length of the string. Let's go through the first half of the string, comparing whether its first and $$$\frac{n}{2} + 1$$$ characters are equal, its second and $$$\frac{n}{2} + 2$$$ characters are equal, and so on. If the characters in any pair are not equal, the answer is $$$NO$$$, otherwise — $$$YES$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for(int tc=0;tc<t;tc++) {
string s;
cin >> s;
bool ok = true;
if (s.length() % 2 == 0) {
for(int i=0;i<s.length()/2;i++)
if (s[i] != s[i + s.length() / 2])
ok = false;
} else
ok = false;
cout << (ok ? "YES" : "NO") << endl;
}
}
C. Sleepover
Check every students who have someone directly next to him in ALL $$$4$$$ directions (Left, Right, Up, Down).
You don't have to check $$$4$$$ sides of the grid.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll t;
cin >> t;
vector<vector<int>> arr;
int index[26][26] = { 0 };
int count = 0;
for (int i = 0; i < t; ++i) {
vector<int> arr1;
for (int j = 0; j < 2; ++j) {
int tmp;
cin >> tmp;
arr1.push_back(tmp);
}
arr.push_back(arr1);
index[arr[i][1]][arr[i][0]] = 1;
}
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (index[i][j] == 1) {
if (i == 25 || j == 25 || i == 0 || j == 0) {
continue;
}
else {
if ((index[i + 1][j] == 1) && (index[i - 1][j] == 1) && (index[i][j + 1] == 1) && (index[i][j - 1] == 1)) {
++count;
}
}
}
}
}
cout << count << endl;
}
D. Just A Game Of Cards
Idea: FazeCT
Big Mink always lose in this game, but he can make his points maximum possible by placing the cards in a non-decreasing order, so that in each pair of cards, the point Big Mink gets is not too differ from the point Smol Mink gets.
In other words, the array should be sorted in a non-decreasing order. Then the total point Big Mink can get is the sum of even-positioned elements in that array.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int main()
{
int n; cin >> n;
vector<ll> v(n);
for(auto &x:v) cin >> x;
sort(all(v));
ll res=0;
for(int i=0;i<n;i+=2) res+=v[i];
cout << res;
}
E. Isolated Classrooms
Idea: FazeCT
Consider every connected components of the grid, take the one that has the most 'C'.
Here you can use DFS or BFS to traverse every cells of the grid.
//--------------------------------------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//--------------------------------------------------------------------
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> oset;
//find by order, order of key.
//usage: oset p; p.insert(x); p.order_of_key(x);
//less, less_equal.
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const int inf=INT_MAX;
const ll infll=LLONG_MAX;
const ll mod = 1e9+7;
//--------------------------------------------------------------------
int n,m,cur;
vector <string> grid(50);
vector <vector<bool>> vis(50, vector <bool> (50,0));
vector <int> dx={0,0,1,-1};
vector <int> dy={1,-1,0,0};
bool valid(int i,int j)
{
return (i>=0 && i<n && j>=0 && j<m);
}
void dfs(int i,int j)
{
if(!valid(i,j)) return;
if(grid[i][j]=='#' || vis[i][j]) return;
vis[i][j]=1;
cur+=(grid[i][j]=='C');
for(int k=0;k<4;k++) dfs(i+dx[k],j+dy[k]);
}
void solve()
{
vector <vector<bool>> rst(50, vector <bool> (50,0));
vis=rst;
cin >> n >> m;
for(int i=0;i<n;i++) cin >> grid[i];
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!vis[i][j] && grid[i][j]=='.')
{
cur=0;
dfs(i,j);
res=max(res,cur);
}
}
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc; cin >> tc;
while(tc--)
solve();
}
F. Baby Counting
Idea: Onirique
Just output $$$a + b$$$, nothing too special.
Remember to use Long Long though.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll a,b;
cin >>a>>b;
cout<<a+b<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t;
cin >>t;
while(t--)
solve();
}
G. 266 Massacre
Idea: Onirique
The idea is simple, just count prime numbers that is not greater than $$$n$$$, then plus 1 to the solution. This can be proved mathematically, but you can also observe this from playing with small cases.
Although $$$1$$$ is not a prime number, but a pair of $$$(1, n)$$$ always has $$$GCD$$$ equals to $$$1$$$. Hence, $$$1$$$ should be added to the set.
Here, the troubles happen. Time limit doesn't allow you to calculate for each $$$n$$$ in the input. In this particular case, you will have to implement Sieve of Eratosthenes to pre-count the amount of prime numbers that is not greater than $$$n$$$ for every $$$n$$$ from $$$2$$$ to $$$10^6$$$.
Afterwards, implement a simple prefix sum to calculate the final answer.
//--------------------------------------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//--------------------------------------------------------------------
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> oset;
//find by order, order of key.
//usage: oset p; p.insert(x); p.order_of_key(x);
//less, less_equal.
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const int inf=INT_MAX;
const ll infll=LLONG_MAX;
const ll mod = 1e9+7;
//--------------------------------------------------------------------
vector <int> v(1e6+1,1);
vector <int> pf(1e6+1,0);
void solve(int &t)
{
int n; cin >> n;
cout << "Case #" << t << ": " << pf[n] << endl;
t++;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i=2;i*i<=1e6;i++)
{
if(v[i]==1)
{
for(int j=i*i;j<=1e6;j+=i) v[j]=0;
}
}
int sum=0;
for(int i=1;i<=1e6;i++)
{
sum+=v[i];
pf[i]=sum;
}
int tc; cin >> tc;
int t=1;
while(tc--)
solve(t);
}
H. Bitwide XORperation
Idea: FazeCT
First, you have to bear these two XOR properties in mind:
Self-Inverse: $$$n \oplus n = 0$$$
Identity Element: $$$0 \oplus n = n$$$
Let's talk about the problem from this point. Suppose that we are going to change the number $$$a_i$$$, then the Bitwise XOR of all other elements is $$$A_i = a_1 \oplus a_2 \oplus \ldots \oplus a_{i-1} \oplus a_{i+1} \oplus \ldots \oplus a_{n-1} \oplus a_n$$$.
Here, according to Self-Inverse property of Bitwise XOR, $$$a_i$$$ should be changed to $$$A_i$$$ to get $$$0$$$ as a result of Bitwise XOR-ing every elements in the array.
In conclusion, compute minimum possible value of $$$|A_i - a_i|$$$.
//--------------------------------------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//--------------------------------------------------------------------
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> oset;
//find by order, order of key.
//usage: oset p; p.insert(x); p.order_of_key(x);
//less, less_equal.
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const int inf=INT_MAX;
const ll infll=LLONG_MAX;
const ll mod = 1e9+7;
//--------------------------------------------------------------------
void solve()
{
int n; cin >> n;
vector <ll> v(n);
ll r=0;
for(auto &x:v)
{
cin >> x;
r^=x;
}
ll res=infll;
for(int i=0;i<v.size();i++) res=min(res,abs((r^v[i])-v[i]));
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc; cin >> tc;
while(tc--)
solve();
}
I. Crazy About Ice-Cream
Idea: FazeCT
The answer is the length of shortest stick multiplies the length of second longest stick.
The shortest stick is used to form the width of the rectangular space. Similarly, the second longest stick is used to form the length of the rectangular space.
#include <bits/stdc++.h>
using namespace std;
//--------------------------------------------------------------------
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
const int inf=INT_MAX;
const ll mod = 1e9+7;
//--------------------------------------------------------------------
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--)
{
vector <ll> v(4);
for(auto &x:v) cin >> x;
sort(all(v));
cout << ll(v[0]*v[2]) << endl;
}
}
J. Email Check
Give it 110%, try harder. Check every single constraints given in the statement.
//--------------------------------------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//--------------------------------------------------------------------
typedef long long ll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> oset;
//find by order, order of key.
//usage: oset p; p.insert(x); p.order_of_key(x);
//less, less_equal.
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const int inf=INT_MAX;
const ll infll=LLONG_MAX;
const ll mod = 1e9+7;
//--------------------------------------------------------------------
bool check(char c)
{
return (c=='.' || c=='_' || c=='-');
}
void solve()
{
//Input:
string s; cin >> s;
int n=s.length();
//Checking 1st condition:
if(n<6 || n>319) return cout << "NO" << endl, void();
int idx=s.find('@');
if(idx==string::npos) return cout << "NO" << endl,void();
//Checking prefix and domain (also the condition "exactly one @"):
string prefix=s.substr(0,idx);
string domain=s.substr(idx+1);
if(prefix.length()<1 || prefix.length()>64) return cout << "NO" << endl, void();
if(domain.length()<4 || domain.length()>254) return cout << "NO" << endl, void();
if(check(prefix[prefix.length()-1]) || check(prefix[0])) return cout << "NO" << endl, void();
for(int i=0;i<prefix.length()-1;i++) if(check(prefix[i]) && check(prefix[i+1])) return cout << "NO" << endl, void();
if(check(domain[domain.length()-1]) || check(domain[0])) return cout << "NO" << endl, void();
for(int i=0;i<domain.length()-1;i++) if(check(domain[i]) && check(domain[i+1])) return cout << "NO" << endl, void();
int lastdot=domain.rfind('.');
if(lastdot==string::npos) return cout << "NO" << endl, void();
string lastportion=domain.substr(lastdot+1);
if(lastportion.length()<2) return cout << "NO" << endl, void();
for(int i=0;i<lastportion.length();i++) if(lastportion[i]<97 || lastportion[i]>122) return cout << "NO" << endl, void();
int cnt=0;
for(int i=0;i<n;i++)
{
if(!check(s[i]) && !(s[i]>=48 && s[i]<=57) && !(s[i]>=97 && s[i]<=122) && s[i]!='@') return cout << "NO" << endl, void();
else if(s[i]=='@') cnt++;
}
if(cnt!=1) return cout << "NO" << endl, void();
return cout << "YES" << endl, void();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc; cin >> tc;
while(tc--)
solve();
}
K. Loli Basement
Idea: Onirique
This problem can be approached in several ways, here is one of them.
Let's say that lolis leave the basement at time moments $$$1, 2 , …, n$$$, and let $$$c_i$$$ be time when loli $$$a_i$$$ left the basement.
For instance, in the first example we had $$$a = ⟨3, 5, 2, 1, 4⟩$$$ and $$$b = ⟨4, 3, 2, 5, 1⟩$$$. Then, $$$c = ⟨2, 4, 3, 5, 1⟩$$$: loli $$$3$$$ entered first and left at time $$$2$$$, so $$$c_1 = 2$$$; loli $$$5$$$ entered second and left and time $$$4$$$, so $$$c_2 = 4$$$; and so on.
Note that $$$c$$$ is a permutation, and it can be very useful for us. It turns out that we can use $$$c$$$ to easily determine if loli $$$a_i$$$ must be punished.
Specifically, loli $$$a_i$$$ must be punished if $$$c_i$$$ is smaller than $$$max(c_1, c_2, …, c_{i−1})$$$.
Why is that? Recall that loli $$$a_i$$$ must be punished if there exists a loli that entered the basement earlier and left the basement later. If a loli entered the basement earlier, it must be $$$a_j$$$ such that $$$j \lt i$$$. If a loli left the basement later, it must be that $$$c_j \gt c_i$$$.
Therefore, now we can just go from left to right, keeping the maximum of $$$c_1, c_2, …, c_{i−1}$$$ to compare it to $$$c_i$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
ll n;
cin>>n;
vector < int > arr(n) , arr1(n);
for(int i = 0 ; i < n ; i++) {
cin>>arr[i];
}
for(int i = 0 ; i < n ; i++) {
cin>>arr1[i];
}
map < int , int > mp;
ll ans = 0 ;
int i = 0 ;
int j = 0 ;
while(i < n && j < n ){
if(arr[i] == arr1[j] ){
i++;
j++;
}
else {
if(mp[arr[i]] == 0 ) ans++;
else{
i++;
continue;
}
mp[arr1[j]]++;
j++;
}
}
cout<<ans<<endl;
}
int main()
{
ll t;
//cin >> t;
t = 1;
while (t--) solve();
}
L. Coding Battle
Firstly, we need to choose the set of $$$\frac{n}{2}$$$ students to be in the first group (the other half is going to the second one). The number of ways to do that is $$$C_n^{\frac{n}{2}}$$$.
Then we need to set some order of students in both groups, but we don't want to forget about rotation (because rotation can lead us to counting the same ways several times). So, the number of ways to arrange students inside one group is $$$(\frac{n}{2}−1)!$$$. This is true because we just "fixed" who will be the first in the group, and place others in every possible order. So, we need to multiply our initial answer by this value twice because we have two groups.
And, finally, we have to divide our answer by $$$2$$$ because we counted "ordered" pairs (i.e. we distinguish pairs of kind $$$(x, y)$$$ and $$$(y, x)$$$ but we don't have to do that). So, the final answer is $$$C_n^{\frac{n}{2}}⋅(\frac{n}{2}−1)!⋅(\frac{n}{2}−1)!$$$ divided by $$$2$$$. This formula can be reduced to $$$\frac{n!}{\frac{n}{2}^2.2}$$$.
Additionally, you could also find the sequence of answers in OEIS.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll t;
cin >> t;
ll ans = 1;
for (int i = 1; i < t; ++i) {
ans *= i;
}
cout << ans / (t / 2) << endl;
}



