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

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

Известный профессор прибыл с лекцией на конференцию. К сожалению, вы не успели на лекцию и пришли уже во время перерыва. Вы хотели бы задать профессору несколько вопросов, но не знаете даже его имени. В комнате N+1 человек, они могут знать или не знать имена других гостей. Также присутствует один профессор (всего людей N+1), профессор не знает ничьего имени, но все знают имя профессора.

У вас есть поименный список присутствующих (N+1). Вы можете задавать только один вопрос: «Вы знаете это имя?».

Какое максимальное количество вопросов потребуется задать, чтобы узнать имя профессора?

Примечание Предположим, что все имена уникальны и вы знаете присутствующих по именам (но не знаете, является ли человек профессором).

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)

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

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

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

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

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

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.

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

Дан массив из N целых чисел. Задача: найти количество таких пар (i, j), при которых результат побитовой операции A[i] & A[j] является нечётным.

Пример:

Вход: N = 4
A[] = { 5, 1, 3, 2 }

Выход: 3

Все пары чисел в 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

Всего пар с нечетным результатом A( i, j ) = 3

Вход: N = 6
A[] = { 5, 9, 0, 6, 7, 3 }

Выход: 6

Всего пар в 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

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 = 4
A[] = { 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 = 6
A[] = { 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

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

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

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

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

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

Time ComplexityO(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)


// 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;
}

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

2014 ламп расположены по кругу, 2 из них включены, 2012 — выключены. Вы можете выбрать любую лампу и изменить состояние соседних с ней на противоположное — включить погасшую или погасить включенную. Получится ли таким образом зажечь все 2014 ламп? Если да, то как?

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?

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

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

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

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

В варианте А: Предположим, начальное положение ламп таково: {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 лампы, находящиеся в разных позициях четности (четная и нечетная) и в состоянии ВЫКЛ, следовательно включить все лампы у нас не получится.

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.

Подобрали три теста для вас:
— А здесь можно применить блокчейн?
Серверы для котиков: выберите лучшее решение для проекта и проверьте себя.
Сложный тест по C# — проверьте свои знания.

Также рекомендуем: