Join Us
Loading Similar Posts
Entering edit mode
1.Tom And Holes
As you know Tom always wants to catch Jerry. This time he is planning to dig M holes on a straight track. Digging one unit deep hole take one unit of time. Since Tom is lazy cat, he asks N fellow cats for help. Tom assigns each N cats some consecutive holes to dig. Two cats will not dig same hole. Tom is very keen in catching Jerry, so he wants to assign holes to each cat optimally such that total time required to dig holes is minimum. But since Tom is weak in mathematics, can you help him find minimum amount of time required to dig all holes if he assigns holes to cats optimally.
INPUT:
First line contains T: Number of test cases
For each test case:
- first line denotes two integers N M: ie Number of Cats and Number of holes
- Next line contains M space separated integers denoting depth of each hole.
OUTPUT:
For each test case, output on new line, minimum
amount of time required to dig all holes.
constraints:
1<= T <= 10
1< N <= M < 100000
1< depth of holes < 10000
Sample Input:
1
3 10
5 3 20 16 18 1 10 10 9 8
Sample Output:
37
Explanation:
Ideal distribution of holes for all cats are ->
- cat1 = (5,3,20)
- cat2 = (16,18, 1)
- cat3= (10,10,9,8)
Note: although below distribution of holes yields a
maximum time of 34 which is lesser than answer, but
since consecutive holes are not assigned to cats below
distribution is an invalid distribution.
cat1=>(20,9,3,1) total time = 33
cat2=>(18,10,5) total time = 33
cat3=>(16,10,8) total time = 34
Sample Input 2:
2
4 5
1 2 3 4 5
2 2
1 1
Sample Output 2:
5
12. Luffy Adventure to grand line
One day, Luffy is on an adventure and comes across a stone bridge that takes him to the grand line. The stone bridge has each stone labeled with a random
String of characters S. Luffy has to cross the bridge by jumping only onto special characters else if he jumps on any other character he falls into the ocean
Now make sure he steps on all stones labeled with special characters on the way. Obviously, he has to take multiple consecutive jumps throughout this path.
He is interested in finding out the maximum length of a single jump, he has to take to cross the stone bridge. Each character on the bridge is at a distance of 1. Formally, consider that Luffy is initially located directly at the start of the bridge. His goal is to reach the end the bridge. In every jump, Luffy jumps anywhere on the next stone with a special character on the bridge. If Luffy cannot cross the bridge then return -1.
Note: All characters apart from [A..Z] [a...z] are treated as special characters
Constraints:
let's assume the length of 'S' is 'n'
0 < n < 106
Sample Input:
S = "ABK@2azxy@gk"
Sample Output :
5
Explanation:
Sample Input:
S = "ABCSD"
Sample Output :
-1
3.Bert's sequence
Bert has a fascination for sequences, he found a very nice problem with natural number sequences. He has a number n, which indirectly implies that he has an integer sequence of [1, 2, 3, .., n - 1]. Now he asks Ernie to remove the minimum amount of elements from this sequence, such that the product of all integers in the resulting sequence becomes congruent to 1 mod n. [i.e., if product of the resultant sequence is p, then p % n is 1]
NOTE:
1. For all practical purposes, consider the product of
an empty sequence to be 1.
2. If there are multiple solutions, return the
lexicographically smallest one.
3. Return the array in increasing order only.
Input
An integer (n) will be given as the argument of the
function that you need to complete.
Output
Return an integer array of relevant size.
Entering edit mode
//Luffy Adventurer to Grandline
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
int j=-1,r=0;
for(int i=0;i<n;i++)
{
if( (0<=s[i]-'a' && s[i]-'a' <=25) || (0<=s[i]-'A' && s[i]-'A'<=25))
{
continue;
}
else
{
r=max(r,i-j);
j=i;
}
}
if(r==0)
cout<<-1<<endl;
else
{
r=max(r,n-j);
cout<<r<<endl;
}
return 0;
}
Entering edit mode
Quesion Number :1) Tom and Holes
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool solve(vector<ll>&arr,ll n,ll m,ll mid){
ll c = 1;
ll sum = 0;
for(int i=0;i<n;i++){
if(c>m){
return 0;
}
if(sum + arr[i] > mid){
c++;
if(c>m){
return 0;
}
sum = arr[i];
if(sum >mid){
c++;
}
}
else{
sum+=arr[i];
}
}
return c<=m;
}
ll f(vector<ll>&arr,ll n,ll m){
ll sum = 0;
ll maxi = arr[0];
for(auto i:arr){
maxi = min(maxi,i);
sum+=i;
}
ll s = maxi;
ll e = sum;
ll ans = 0;
while(s<=e){
ll mid = s + (e-s)/2;
if(solve(arr,n,m,mid)){
ans = mid;
e = mid - 1;
}
else{
s = mid + 1;
}
}
return ans;
}
int main() {
ll t;
cin>>t;
while(t--){
ll n,m;
cin>>m>>n;
vector<ll>arr(n);
for(ll i=0;i<n;i++){
cin>>arr[i];
}
cout<<f(arr,n,m)<<endl;
}
return 0;
}
Entering edit mode
Question Number: 3) Bert's Sequence
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ll n;
cin>>n;
ll ans = 0;
map<ll,bool>mp;
ll prod = 1;
for(ll i = 1;i<=n;i++){
if(__gcd(i,n)!=1){
mp[i]=1;
continue;
}
prod = (prod*i)%n;
}
if(prod%n == 1){
cout<<n - mp.size()<<endl;
for(ll i = 1;i<=n;i++){
if(mp.find(i)!=mp.end()){
continue;
}
cout<<i<<" ";
}
cout<<endl;
return 0;
}
ll x = prod%n;
mp[x]=1;
cout<<n-mp.size()<<endl;
for(ll i = 1;i<=n;i++){
if(mp.find(i)!=mp.end()){
continue;
}
cout<<i<<" ";
}
cout<<endl;
return 0;
}
Entering edit mode
Problem 1: Tom and Holes
A simple binary search problem of category MinMax. Here is a link of almost similar problem: https://codeforces.com/edu/course/2/lesson/6/3/practice/contest/285083/problem/B
Here is a working solution for problem - 1: https://ideone.com/YqAdwD
Entering edit mode
Problem 3: Bert's sequence
Here is a working code: https://ideone.com/QMagss
Remove all the multiples of 7 from the sequence. Then find the value after multiplying all the remaining values under (mod 7).
Now what ever is the value of the product of all the numbers just remove the largest number in the sequence with congruent value after performing modulus operation under 7.
Entering edit mode
PROBLEM 2
#include <iostream>
using namespace std;
int luffy_adv(string s ){
int init=-1;
for(int i=0; i<s.size(); i++){
if(!isalpha(s[i])){
init = i;
break;
}
}
if(init == -1){
return -1;
}
int ans = init+1 ;
for(int i=init; i<s.size(); i++){
if(!isalpha(s[i])){
ans = max(ans,i-init);
init = i ;
}
}
return ans ;
}
int main()
{
// cout<<"Hello World";
string s ;
cin>>s;
int ans = luffy_adv(s);
cout<<ans;
return 0;
}
Entering edit mode
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int good(int n,int m,vector<ll>&v,ll time)
{
int c=1;
ll s=0;
for(int i=0;i<m;i++)
{
if(v[i] > time)
return false;
if(s+v[i] > time)
{
s=v[i];
c++;
}
else
{
s+=v[i];
}
}
return c<=n;
}
int main()
{
int n,m;
cin>>m>>n;
vector<ll> v(m);
for(int i=0;i<m;i++)
cin>>v[i];
ll l=0,r=1e9;
while(l<r)
{
ll time=l+(r-l)/2;
if(good(n,m,v,time))
{
r=time;
}
else
l=time+1;
}
cout<<r<<endl;
return 0;
}
```
Entering edit mode
//Tom and Holes
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int good(int n,int m,vector<ll>&v,ll time)
{
int c=1;
ll s=0;
for(int i=0;i<m;i++)
{
if(v[i] > time)
return false;
if(s+v[i] > time)
{
s=v[i];
c++;
}
else
{
s+=v[i];
}
}
return c<=n;
}
int main()
{
int n,m;
cin>>m>>n;
vector<ll> v(m);
for(int i=0;i<m;i++)
cin>>v[i];
ll l=0,r=1e16;
while(l<r)
{
ll time=l+(r-l)/2;
if(good(n,m,v,time))
{
r=time;
}
else
l=time+1;
}
cout<<r<<endl;
return 0;
}
