Problem on discrete mathematics - C ++

Navigation
1

I have this problem to solve, about Pigeon House Principle. However, it has 25% error and only has an input sample.

  

For some unknown reason, Rangel only has one pair of socks of each color.

     

Today he is late to go to college and still needs to get a pair of socks, but the socks are all messed up.

     

Given the number of pairs of socks in Rangel's drawer, he wants to know how many socks he needs to get at least to have at least one pair of the same color.

     

Entry:
  Each case is composed of a single integer N (1 ≤ N ≤ 105) corresponding to the number of pairs of socks in the drawer.

     

Output:
  You should print a line with a single integer that matches the minimum amount of socks that Rangel needs to pick up.

Example Input: 1

Output example: 2 

#include <iostream>

using namespace std;

int main()
{
    int N = 0;

    cin >> N;

    if( N == 0 ){
        cout << 0 << endl;
    }else if( N == 1 ){
        cout << (N * 2) << endl;
    }else{
        cout << (N * 2) - 1 << endl;
    }

    return 0;
}
    
asked by anonymous 05.11.2018 / 00:19

2 answers

3

As I mentioned in commentary the problem is simpler than I was imagining. Rangel only has a pair of socks of each color. So assuming it has for example 3 pairs of socks, and therefore N = 3 , we have this:

Now looking at this image, how many socks do you have to take out to make sure you have a pair?

The answer is 4, because with bad luck if you choose only 3 you can have one of each color, but the fourth one will certainly pair with one you already have.

Then the code is no more than returning N + 1 as output: 

#include <iostream>

using namespace std;

int main(){
    int N = 0;
    cin >> N;
    cout << N + 1;
    return 0;
}
    
05.11.2018 / 02:27
1

No formulas are required to use the Pigeon House Principle .

  

See the examples below.

Imagine that I have 3 pigeon houses. If I own 4 pigeons, then surely in some house there will be more than one pigeon. If the number of pigeons is greater than the number of houses, there will certainly be some house with more than one pigeon. It has been thinking of examples like this that the principle is called Pigeon House Principle .

Imagine that I have black, brown, white and gray socks. Certain day lacked light in my house and I need to withdraw the minimum amount of socks to ensure there will be AT LEAST two socks of the same color. Now, let's think about the worst case, that is, think that you are the most unlucky person in the world.

There are 4 possible colors. Therefore, 4 socks are not enough, because I could remove a black sock, a brown, a white and a gray. But in the fifth half there is no escape: she must repeat some of the colors mentioned. So with 5 socks I'm sure I'll have AT LEAST a pair of socks of the same color. It may even be that I have (luckily) more than two socks of the same color, but at least two I guarantee.

  

In the great majority of problems, you have to imagine that you are the most unlucky person in the world, you have to think in the worst case.

Let's go another example .

In a drawer, there are 4 black socks, 2 white socks, 8 gray socks. What is the minimum quantity of socks I need to remove from this drawer to ensure that I have at least two different colored socks?

Let's think about the worst case scenario? Now, if I am wanting to remove two socks of different colors, it is bad luck to get several socks of the same color. As I am VERY RARELY, I start to get gray socks (because it is the one with the most amount). I'm so unlucky I get 8 gray socks consecutively.

Once I get 8 gray socks, there's no way out. The next sock has to be of another color. So 9 socks is the minimum amount of socks to ensure that we will have at least two different colored socks. It may even be that out of the 9 socks I have more than two socks with different colors, but that is luck and not certainty.

Another example.

How many people do you need to have in an auditorium to be sure (I SAID SURE !!!) that at least two of them are celebrating the SAME day?

I do not want to say that they were born in the same year, only that they make a birthday the same day.

Before writing the answer, I want to think a moment with you (if you have not already answered by yourself). Let's see: if there are two people, there is obviously no guarantee that the two will have a birthday the same day. More likely it will not be so. But, besides probable (or not probable), the fact is that we are looking for CERTAIN. And with two people in the auditorium, we could never be sure that both were born the same day.

The same would happen if there were three people. Or ten. Or fifty. Not? Or a hundred. Or two hundred. Or up to three hundred !!! Because? Why, although with three hundred people in an auditorium there are likely to be two who celebrate their respective birthdays on the same day, we still can not guarantee or guarantee that what we want is right. It's just that we could have the RANDOM that everyone had been born on different days of the year. We are approaching an interesting point in the conversation ...

Because if there were 365 people in the auditorium, we would not be able to make sure two of them celebrate the same day. It could happen that all of them were born on every possible day of a year. Even worse: not even 366 (because of leap years). It may be that just the 366 people in the auditorium cover exactly every possible day of a year without repetition.

However, there is a categorical argument: if there are 367 people in the auditorium, there is no escaping: at least two have to make a birthday on the same day.

Of course, we do not know who these people are, or whether there are more than two that meet the requested property. There may be more ... more, but that does not interest us. The guarantee is that with 367 people, we solve the problem.

fonte

    
05.11.2018 / 23:33
How to set values of an array attribute? Send data to the database according to the select tag via PHP [closed]