Ищем профессора, проверяем пары в массиве и зажигаем лампы: подборка задач для программистов

Question 1

Оригинал задачи на английском языке

Answer

Famous professor arrived at the conference to read a lecture. Unfortunately, you were late to the lecture and came in when coffee break started. You want to meet the professor to ask some questions, but you even don’t know his name. There are (N+1) people in a room, they might or might not know each others names.There is also one professor in the group (total N +1 people), professor does not know any of N peoples by name and all N people know professor by name.

You are given the list of people’s names (N+1). You can ask only one question from the people: «Do you know this name?».

How many maximum number of questions you need to ask to know the professor name?

Note: assume all names are unique and you know the persons by name (but don’t know if he is professor)

Question 2

Решение задачи на русском языке

Answer

Допустим, вы спрашиваете у А: «Вы знаете Б?».

Если А знает Б => А не может быть профессором.

Если А не знает Б, следовательно Б не может быть профессором.

Если вычеркивать имена из списка, то с каждым вопросом можно будет вычеркнуть одно имя. Когда останется всего два человека, следует спросить у одного из них, знает ли он второго. Если он ответит утвердительно, значит второй и есть профессор, в противном случае, профессором является отвечающий.

Получается, всего понадобится максимум N вопросов, чтобы выяснить имя профессора.

Question 3

Решение задачи на английском языке

Answer

Let’s say you ask from A that «Do you know B?»

If A knows B => A can not be a professor.

If A does not know B then B can not be a professor.

So you strike out one name from your list, so on each question you can reject one name.

When there are only two people left in the list, then you will ask first person, «Do you know the second person?». If he says yes then second person is the professor and if he says no then the first person is the professor.

Thus you need to ask a maximum of N questions to correctly figure out professor name.

Question 4

Оригинал задачи на английском языке

Answer

Given an array of N integers. The task is to find the number of pairs (i, j) such that A[i] & A[j] is odd.

Examples:

Input: N = 4A[] = { 5, 1, 3, 2 }

Output: 3

Since pair of A[] = ( 5, 1 ), ( 5, 3 ), ( 5, 2 ), ( 1, 3 ), ( 1, 2 ), ( 3, 2 )

5 AND 1 = 1, 5 AND 3 = 1, 5 AND 2 = 0,1 AND 3 = 1, 1 AND 2 = 0,3 AND 2 = 2

Total odd pair A( i, j ) = 3

Input : N = 6A[] = { 5, 9, 0, 6, 7, 3 }

Output : 6

Since pair of A[] =

( 5, 9 ) = 1, ( 5, 0 ) = 0, ( 5, 6 ) = 4, ( 5, 7 ) = 5, ( 5, 3 ) = 1,( 9, 0 ) = 0, ( 9, 6 ) = 0, ( 9, 7 ) = 1, ( 9, 3 ) = 1,( 0, 6 ) = 0, ( 0, 7 ) = 0, ( 0, 3 ) = 0,( 6, 7 ) = 6, ( 6, 3 ) = 2,( 7, 3 ) = 3

Question 5

Решение задачи на русском языке

Answer

Прямолинейное решение: проверка каждой пары и вывод подходящих пар.

Сложность по времени: O(N^2)

Лучшее решение — найти количество нечетных чисел. Решением задачи будет count * (count – 1)/2, потому что операция AND над 2-мя числами будет нечетной только в том случае, если оба числа не являются четными.

Сложность по времени: O(N)

Question 6

Решение задачи на английском языке

Answer

A brutforce is to check for every pair and print the count of pairs.

Time Complexity: O(N^2)

An better solution is to count the odd numbers. Then return count * (count – 1)/2 because AND of two numbers can be odd only if only if a pair of both numbers are odd. Time Complexity: O(N)

Question 7

Код

Answer

			// C++ program to count pairs
// with AND giving a odd number
// brutforce approach
#include 
using namespace std;
 
// Function to count number of odd pairs
int findOddPair(int A[], int N)
{
    int i, j;
 
    // variable for counting odd pairs
    int oddPair = 0;
 
    // find all pairs
    for (i = 0; i < N; i++) {
        for (j = i + 1; j < N; j++) {
 
            // find AND operation
            // check odd or even
            if ((A[i] & A[j]) % 2 != 0)
                oddPair++;
        }
    }
    // return number of odd pair
    return oddPair;
}
// Driver Code
int main()
{
 
    int a[] = { 5, 1, 3, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // calling function findOddPair
    // and print number of odd pair
    cout << findOddPair(a, n) << endl;
 
    return 0;
}


// C++ program to count pairs with Odd AND - efficient solution
#include 
using namespace std;
 
int findOddPair(int A[], int N)
{
    // Count total odd numbers in
    int count = 0;
    for (int i = 0; i < N; i++)
        if ((A[i] % 2 == 1))
            count++;
 
    // return count of even pair
    return count * (count - 1) / 2;
}
 
// Driver main
int main()
{
    int a[] = { 5, 1, 3, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // calling function findOddPair
    // and print number of odd pair
    cout << findOddPair(a, n) << endl;
    return 0;
}

Question 8

Оригинал задачи на английском языке

Answer

On a circle there are 2014 light bulbs. 2 are on, and 2012 are off. You can choose any bulb and change the neighbor’s state from on to off or from off to on. Doing so, can we get all 2014 light bulbs on? If yes, how?

Question 9

Решение задачи на русском языке

Answer

Пронумеруем лампы.

Вариант А: Если обе включенные лампы находятся в четной или нечетной позиции, мы сможем включить все лампы.

Вариант Б: Если одна из ламп находится в четной, а другая – в нечетной позиции, включить все лампы не получится.

Так происходит потому, что при каждом действии затрагиваются лампы в одинаковой позиции четности (или нечетности).

В варианте А: Предположим, начальное положение ламп таково: {0,1,0,1,0,0,0,0…..,0,0} где 1 = ВКЛ и 0 = ВЫКЛ.

Выберем вторую лампу следующую после включенной, и изменим состояние соседних для выбранной лампы. Состояние станет следующим: {0,1,0,1,1,0,1,0…..0,0}. При каждых 2-х шагах мы можем включать 4 лампы, а поскольку 2012 кратно 4, мы сможем зажечь все лампы.

В варианте Б: На каждом шаге у нас будет 2 лампы, находящиеся в разных позициях четности (четная и нечетная) и в состоянии ВЫКЛ, следовательно включить все лампы у нас не получится.

Question 10

Решение задачи на английском языке

Answer

Number the position of the bulbs.

CASE A : If both the ON bulbs are in odd positions or both in even positions, then you can make all ON.

CASE B : If one ON bulb is in even position and the other is in odd position, then you can not make all ON.

This is because any action we take impacts two bulbs of the same parity.

In CASE A : Let’s assume initial state of circuit as {0,1,0,1,0,0,0,0…..,0,0} where 1 = Switched ON and 0 = Switched OFF.

Choose second last bulb from bulb which has state =1, then 2 bulb will be lighted on either sides. Next state becomes {0,1,0,1,1,0,1,0…..0,0} so at each 2 steps we are lighting 4 bulbs, since 2012 is multiple of 4, there will come a stage where all bulbs will be ON.

In CASE B : Every move we make, results in two bulbs of opposite parity in OFF state. So it will never get out of this state.

Ищем профессора, проверяем пары в массиве и зажигаем лампы: подборка задач для программистов

Найдите профессора

Ищем пары элементов массива с оператором AND

Зажгите лампы