Codeforces 1593C - Save More Mice [ EXPLANATION + TUTORIAL + SOLUTION ]

 

1593C - Save More Mice

Tutorial

Let's solve the problem using a linear search. Let m be the number of mice we are trying to save. Then it is more efficient to save m mice such that they are the closest ones to the hole. Let ri be the distance from the i-th mouse to the hole (ri=n−xi). Denote R:=∑i=1mri. Let's prove that these mice will be saved if and only if R<n.
The necessary condition. Suppose we can save the mice and R≥n. Since only one mouse can be moved in one second, the following will happen: m−1 of mice will already be saved and one mouse will have to be saved. When it's been q seconds, then the distance from the cat to the hole will be equal to n−q, and the distance from the mouse to the hole will be equal to R−q (since all other mice are already in the hole, their distances to the hole are equal to 0, so the sum of the distances from all mice to the hole at the current time is exactly equal to the distance to the hole from one remaining mouse). Since R−q≥n−q, the distance from the mouse to the hole is greater than or equal to the distance from the cat to the hole. But this cannot be, because both the mice and the cat move only to the right, and all mice met by the cat are eaten. So, R<n.
Sufficient condition. Suppose R<n. If R=0, then all the mice are already in the hole, i.e. they are saved. Suppose R>0. Let's move any mouse, then the cat. Suppose the cat ate at least one of the mice. This mouse is definitely not the one that was moved. Then the distance from it to the eaten mouse was equal to 1, i.e. the distance from it to the hole was equal to the distance from the eaten mouse to the hole plus 1. The distance from the moved mouse to the hole was at least 1. So, R≥rs+rm, where rs=n−1 is the distance from the eaten mouse to the hole, rm≥1 is the distance from the moved mouse to the hole. So, R≥n−1+1=n, but it's false. Therefore, none of the mice will be eaten on the first move. Then the distance from the cat to the hole will be equal to n−1, the total distance from the mice to the hole will be equal to R−1. R−1<n−1, i.e. now we have to solve a similar problem for smaller R and n. So R will be gradually decreased to 0, while no mouse will be eaten. So, if R<n, all the mice will be saved.
Thus, to solve the problem, we need to find the maximum m such that the sum of the distances from the m nearest mice to the hole is less than n.

Explanation 

Solution

    

    //Codeforces 1593C - Save More Mice

    #include<bits/stdc++.h>

    using namespace std;

    int main()

    {  

    int t, n, k;

    cin>>t;

    while(t--)

    {

        cin >> n >> k;

        vector<int> v(k);

        for (int i = 0; i < k; i++)

            cin >> v[i];

        sort(v.rbegin(), v.rend());

        int count=0;

        long long sum=0;

        while (count < v.size() && sum + n - v[count] < n)

        {

            sum += n - v[count++];

        }

        cout<<count<<endl;

       

     }

        return 0;

    }

[PDF] Object-Oriented Programming in C++ (4th Edition) by Robert Lafore

[PDF] Object-Oriented Programming in C++ (4th Edition) by Robert Lafore 

Object-Oriented Programming in C++ begins with the basic principles of the C++ programming language and systematically introduces increasingly advanced topics while illustrating the OOP methodology. While the structure of this book is similar to that of the previous edition, each chapter reflects the latest ANSI C++ standard and the examples have been thoroughly revised to reflect current practices and standards.

Codeforces 750A - New Year and Hurry

Problem Link - https://codeforces.com/contest/750/problem/A

Editorial

Do you see what is produced by the following piece of code?

int total = 0;
for(int i = 1; i <= n; ++i) {
	total += 5 * i;
	printf("%d\n", total);
}

We iterate over problems (a variable i denotes the index of problem) and in a variable total we store the total time needed to solve them. The code above would print numbers 5, 15, 30, 50, ... — the i-th of these numbers is the number of minutes the hero would spend to solve easiest i problems.

Inside the loop you should also check if there is enough time to make it to the party, i.e. check if total + k <= 240.

Solution

        

    #include<bits/stdc++.h>

    using namespace std;

    int main()

    {  

    int n,k; int count=0; int sum=0;

    cin>>n>>k;

    for(int i=1; i<=n; i++)

    {

        sum += 5*i;  

        if(sum>240-k) break;

        count +=1;

    }

    cout<<count<<endl;

    return 0;

    }

Computer Programming Book by Tamim Shahriar Subeen pdf

If you want to learn Programming with C, you can download this book in Bangla language. This book will help you to learn the basic of C language in a proper way.This book is for anyone who love programming.

click here↓

Download

Button Styles

UVA 11350 - Stern-Brocot Tree(solution)

problem link:- Stern-Brocot Tree

submit link:- Submit

code ref:- c++ language, bfs-tree

#include<bits/stdc++.h>
using namespace std;

UVA 406 - Prime Cuts(solution)

To read problem (সমস্যা পড়তে ক্লিক কর) → uva 406 - Prime Cuts

To submit (সাবমিট করতে ক্লিক কর) → Submit(uva 406)

Solution:

কম্পিউটার প্রোগ্রামিং বই - সমস্যা ৬৮

                       সমস্যা - ৬৮ ( শব্দ গণনা ১ ) 

সমস্যা পড়তে ক্লিক কর  → শব্দ গণনা ১

সাবমিট করতে ক্লিক কর →  সাবমিট ( শব্দ গণনা ১ )


Solution:

#include<string>
#include<iostream>
#include<sstream>
using namespace std;

Starting with PYTHON!

Let's become a programmer with Python!

 

At the very first, we are going to print ' Hello World ' which is the first code of every programmer.

Now, Open your Python Interpreter on your computer.

Here is a sample line of code that can be executed in Python:

print ("Hello, World!")

You can just as easily store a string as a variable and then print it to stdout:

my_string = "Hello, World!"
print(my_string)

#Happy_Coding :)

challenge 7- বয়স

#Problem setter : MC Rudra

Challenge 6 - মজার খেলা

Challenge 5 - বৃত্ত নিয়ে ১

চল আজকে একটু ভিন্ন ধরণের সমস্যা সমাধান করি ।
ধর, তোমাকে একটি বৃত্তের ব্যসার্ধ ও দুটি জ্যা দেওয়া হল। এবারে বলা হলো যে কোন জ্যা টি কেন্দ্রের সবচেয়ে নিকটে অবস্থিত তা নির্নয় কর।  পারবে ?
চেষ্টা করে ফেলা যাক।

Problem Setter: Fahim Ahmed

Download Hello BGPSC apk!

Download our android app

Download Now

Challenge -4

টেস্ট কেস সম্পর্কে আমরা আগে জেনেছি এখন নিচের প্রব্লেম টি সল্ভ করি

#Problem setter : MC Rudra