A. In Search of an Easy Problem
As the name suggest it is an easy problem all what is needed is to take a string s as input and print Mohamed Salah
#include<iostream>
using namespace std;
int main()
{
string str;cin>>str;
cout<<"Mohamed Salah";
}
C. P vs. NP
If $$$a$$$%$$$b=0$$$ ($$$a$$$ is divisible by $$$b$$$), just print $$$0$$$. Otherwise, we need exactly $$$b − a$$$%$$$b$$$ moves to make zero remainder of $$$a$$$ modulo $$$b$$$. % is the modulo operation.
#include<iostream>
using namespace std;
int main(){
int t = 1; cin >> t;
while(t--){
int a,b;
cin >> a >> b;
if(!(a%b)) cout<<"0\n";
else cout<<b-(a%b)<<"\n";
}
return 0;
}
F. N and T
In this problem we want to find a number that is divisible by t and has n digits. But we found a series of problems:
n can be 100 -> there is no data type that handles such a big number (long long take up to pow(2,64))
How can I easily get a number divisible by t
The answer is t itself and
what about multiplying the number by 10 until I get the desired length? why 10: multiplying by 10 will keep the divisibility state (2x10 is divisible by 2 and 2x10x10 is still divisible by 2....)
so the answer will be the t multiplied by 10 until I reach the desired length. -> problem 2 solved
multiplying by 10 means adding 0 to the end of the number (2x10 = 20, 330x10 = 3300)
so we can print the t followed by zeros -> problem 1 solved
but when I will print -1? the answer is if the number of digits in t is less than n as the smallest number is divisble by t is t itself
#include <iostream>
#include <vector>
using namespace std ;
int32_t main() {
int n,t;cin>>n>>t;
if(t == 10 && n== 1){
cout<<"-1";
}else{
cout<<t;
n--;
if(t == 10)n--;
for (int i = 0; i < n; ++i) {
cout<<"0";
}
}
}
H. Strange Sort
The key for solving this problem is the observation that the frequency of any element will not exceed 1000 (The maximum number of elements) The solution steps will be as follows
- Sort the elements in reversed order.
- Iterate from 1 to n (number of elements) for all numbers if the frequency of number equal to i print the number i times
- This grantees that the elements is printed in the increasing order in frequency and if there is two elements with the same frequency they will be printed in decreasing order
- Here we still have one problem we can't calculate frequency for negative values in array so we will use two arrays one for positive as usual and another one for negative if the number less than zero we will store its frequency in neg_freq array in its as follows if i = -5 neg_freq[5]++;
time complexity for this solution is O(n^2) as we iterate over all elements n times
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int neg_freq[1001]={0}, pos_freq[1001] = {0}; // array for positive and array for negative
int n;
cin >>n;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
if(a[i] > 0)
pos_freq[a[i]]++;
else
neg_freq[-a[i]]++;
}
sort(a, a+n);
reverse(a, a+n);
for (int i = 1; i <= n; ++i) {
for(int j = 0; j < n; j++){
if(a[j] > 0){
if(pos_freq[a[j]] == i){
for(int k = 0; k < i; k++){
cout<<a[j]<<' ';
}
pos_freq[a[j]] = 0;
}
}else{
if(neg_freq[-a[j]] == i){
for(int k = 0; k < i; k++){
cout<<a[j]<<' ';
}
neg_freq[-a[j]] = 0;
}
}
}
}
return 0;
}
I. Save Khaled's life !!!
The Solution is to check the sum for each cell. For each cell (i , j) we can iterate over all elements in its diagonals calculate the sum and save the maximum. We have four different directions to go to
- top right each cell in this direction (i, j) the next one is (i-1, j+1)
- bottom left each cell in this direction (i, j) the next one is (i+1, j-1)
- top left each cell in this direction (i, j) the next one is (i-1, j-1)
- bottom right each cell in this direction (i, j) the next one is (i+1, j+1)
here at each cell the maximum number of elements to loop over is mx(m, n) so the time complexity is O(n*m*max(n, m))
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int t;
cin >>t;
while(t--){ // our test cases
int n, m;
cin >> n >> m;
int a[n][m];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
int mx = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
int now = 0;
int ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj--; // top left direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj--; // bottom left direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj++; // top right direction
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj++; // bottom right direction
}
now-=a[i][j]*3; // we have added a[i][j] to sum 4 times. we need to add it only one time, so we subtract 3*a[i][j]
mx = max(mx, now); // save maximum sum in mx
}
}
cout << mx << endl;
}
return 0;
}
J. Salma Has Cakes and You Don't!
Not finished yet
#include<bits/stdc++.h>
using namespace std;
void fast(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main()
{
fast();
int n, m;
cin >> n >> m;
int arr[n];
for(int i = 0; i<n; i++){
cin >> arr[i];
}
int freq[100005]={0},pref[n+1];
pref[n] = 0;
for(int i = n-1; i>=0; i--){
if(freq[arr[i]] == 0)
pref[i] = pref[i+1] + 1;
else
pref[i] = pref[i+1];
freq[arr[i]]++;
}
int q;
while(m--){
cin >> q;
cout<<pref[q-1]<<"\n";
}
return 0;
}