Выпуск#27: ITренировка — актуальные вопросы и задачи от ведущих компаний

Ну как Вам задачки из прошлой статьи, успели решить? Ответы уже опубликованы!
А сейчас у нас новые поступления!



Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.

На этой неделе мы собрали задачи с собеседований в норвежскую компанию Opera Software.

Вопросы

1. Pay an employee using a 7 units gold rod?

An employee works for an employer for 7 days. The employer has a gold rod of 7 units. How does the employer pays to the employee so that the employee gets 1 unit at the end of everyday? The employer can make at most 2 cuts in rod.

Перевод

Сотрудник работает 7 дней. У работодателя есть золотой стержень из 7 единиц. Как работодателю заплатить работнику, чтобы работник получал 1 единицу в конце каждого рабочего дня? Работодатель может сделать не более 2 разрезов в стержне.

2. Загадка Эйнштейна

Эту задачу приписывают Альберту Эйнштейну — якобы с ее помощью он подбирал себе ассистентов. Другая почти легендарная история приписывает авторство Льюису Кероллу. Отметим, что она очень просто решается на бумаге, но если хотите хардкора — попробуйте решить в уме.

На улице стоят пять домов.
Англичанин живет в красном доме.
У испанца есть собака.
В зеленом доме пьют кофе.
Украинец пьет чай.
Зеленый дом стоит сразу справа от белого дома.
Тот, кто курит Old Gold, разводит улиток.
В желтом доме курят Kool.
В центральном доме пьют молоко.
Норвежец живет в первом доме.
Сосед того, кто курит Chesterfield, держит лису.
В доме по соседству с тем, в котором держат лошадь, курят Kool.
Тот, кто курит Lucky Strike, пьет апельсиновый сок.
Японец курит Parliament.
Норвежец живет рядом с синим домом.
Каждый из домов покрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого — свой питомец, своя любимая марка сигарет и напиток.
Вопрос: Кто пьет воду? Кто держит зебру?

Задачи

1. Product array puzzle

Given an array A of size N, construct a Product Array P (of same size) such that P is equal to the product of all the elements of A except A[i].

Input: Each testcase contains two lines of input. The first line is N. The second line contains N elements separated by spaces.

Output: For each testcase, print the Product array P.

Constraints:
1 <= T <= 10
1 <= N <= 1000
1 <= Ai <= 20

Example:
Input
5
10 3 5 6 2
Output
180 600 360 300 900
Input
2
12 20
Output
20 12

Explanation:
Testcase1: For the product array P, at i=0 we have 3*5*6*2. At i=1 we have 10*5*6*2. At i=2 we have 10*3*6*2. At i=3 we have 10*3*5*2. At i=4 we have 10*3*5*6.
So P is 180 600 360 300 900.

Перевод

Для массива A размера N создайте массив произведений P (такого же размера), чтобы P был равен произведению всех элементов A, кроме A [i].

Входные данные: каждый тестовый пример содержит две строки ввода. Первая строка — N. Вторая строка содержит N элементов, разделенных пробелами.

Выход: Для каждого теста выведите массив произведений P.

Ограничения:
1 <= T <= 10
1 <= N <= 1000
1 <= Ai <= 20

Пример:
Вход
5
10 3 5 6 2
Выход
180 600 360 300 900
Вход
2
12 20
Выход
20 12

Объяснение:
Первый тест: для массива произведений P при i = 0 имеем 3 * 5 * 6 * 2. При i = 1 имеем 10 * 5 * 6 * 2. При i = 2 имеем 10 * 3 * 6 * 2. При i = 3 имеем 10 * 3 * 5 * 2. При i = 4 имеем 10 * 3 * 5 * 6.
Таким образом, массив P состоит из элементов: 180 600 360 300 900

2. Egg Dropping Puzzle

Suppose you have N eggs and you want to determine from which floor in a K-floor building you can drop an egg such that it doesn't break. You have to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy.There are few rules given below.

• An egg that survives a fall can be used again.
• A broken egg must be discarded.
• The effect of a fall is the same for all eggs.
• If the egg doesn't break at a certain floor, it will not break at any floor below.
• If the eggs breaks at a certain floor, it will break at any floor above.

For more description on this problem see wiki page.

Input:
The first line of input is T denoting the number of testcases.Then each of the T lines contains two positive integer N and K where 'N' is the number of eggs and 'K' is number of floor in building.

Output:
For each test case, print a single line containing one integer the minimum number of attempt you need in order find the critical floor.

Constraints:
1<=T<=30
1<=N<=10
1<=K<=50

Example:
Input:
2
2 10
3 5

Output:
4
3

Перевод

Предположим, у вас есть N яиц, и вы хотите определить, с какого этажа K-этажного здания вы можете бросить яйцо так, чтобы оно не разбилось. Вы должны определить минимальное количество попыток, которое вам нужно, чтобы найти последний этаж, с которого не разобьется яйцо, используя лучшую стратегию. Ниже приведено несколько правил.

• Яйцо, которое переживет падение, можно использовать снова.
• Разбитое яйцо нужно выбросить.
• Эффект падения одинаков для всех яиц.
• Если яйцо не сломается на определенном этаже, оно не сломается ни на одном этаже ниже.
• Если яйца разбиваются на определенном этаже, они разбиваются на любом этаже выше.

Более подробное описание этой проблемы смотрите на вики-странице.

Входные данные:
Первая строка ввода — это T, обозначающая количество тестовых случаев. Каждая из T строк содержит два положительных целых числа N и K, где «N» — количество яиц, а «K» — количество этажей в здании.

Выход:
Для каждого теста выведите в отдельной строке одно целое число — минимальное количество попыток, необходимое для определения критического этажа.

Ограничения:
1 <= Т <= 30
1 <= N <= 10
1 <= K <= 50

Пример:
Входные данные:
2
2 10
3 5

Выход:
4
3

3. Travelling Salesman Problem

Given a matrix M of size N where M[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from the city 0 (0 based index) to all other cities such that you visit each city atmost once and then at the end come back to city 0 in min cost.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the matrix then in the next line are N*N space separated values of the matrix M.

Output:
For each test case print the required result denoting the min cost of the tour in a new line.

Constraints:
1<=T<=15
1<=N<=12
1<=M[][]<=10000

Example:
Input:
2
2
0 111
112 0
3
0 1000 5000
5000 0 1000
1000 5000 0
Output:
223
3000

Перевод

Дана матрица M размера N, где M [i] [j] обозначает стоимость перемещения из города i в город j. Ваша задача — совершить поездку из города 0 (индекс на основе 0) во все другие города так, чтобы вы посещали каждый город максимум один раз, а затем в конце возвращались в город 0 за минимальную стоимость.

Входные данные:
Первая строка ввода содержит целое число T, обозначающее количество тестовых случаев. Затем следуют тесты T. Каждый тестовый пример содержит целое число N, обозначающее размер матрицы, в следующей строке находятся N * N разделенных пробелами значений матрицы M.
 
Выход:
Для каждого тестового примера в новой строке выведите искомый результат, обозначающий минимальную стоимость тура.

Ограничения:
1 <= Т <= 15
1 <= N <= 12
1 <= М [] [] <= 10000

Пример:
Входные данные:
2
2
0 111
112 0
3
0 1000 5000
5000 0 1000
1000 5000 0
Выход:
223
3000

Ответы

Вопрос 1

Работодатель может заплатить за семь дней, сделав 2 разреза таким образом, чтобы у него было 3 стержня размером 1, 2 и 4.

1-й день: работодатель дает часть размером в 1 единицу.
2-й день: забирает у работника часть размером в 1 единицу, полученный в первый день, и дает часть размером в 2 единицы.
3-й день: дает часть размером в 1 единицу.
4-й день: забирает у работника часть размером в 1 и 2 единицы. Дает часть размером в 4 единицы.
5-й день: дает часть размером в 1 единицу.
6-й день: забирает у работника часть размером в 1 единицу и дает часть размером в 2 единицы.
7-й день: дает часть размером в 1 единицу.

Вопрос 2

Японец держит зебру, норвежец пьет воду.

Задача 1

int main()
{
    int maxi, n, i;
    cin >> n;
    int a[n];
    long long int z = 1;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
        z = z * a[i];
    }
    for (i = 0; i < n; i++)
        cout << z / a[i] << " ";
    cout << "\n";
}

Задача 2

#include<bits/stdc++.h>
using namespace std;
int func2(int x, int k, int n)
{

    int ans = 0, r = 1;
    for (int i = 1; i <= k; i++)
    {
        r *= x - i + 1;
        r = r / i;
        ans = ans + r;
        if (ans >= n) break;
    }
    return ans;
}
int func(int k, int n)
{
    int low = 1, high = n;
    while (low < high)
    {
        int mid = (low + high) / 2;
        if (func2(mid, k, n) < n)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int k, n;
        cin >> k >> n;

        cout << func(k, n) << endl;
    }
}

Задача 3

using namespace std;
void helper(int n, int source, vector<vector<int>>&M, vector<bool>&visited, int count, int &ans, int sum)
{
    if (count == n - 1)
    {
        ans = min(sum + M[source][0], ans);
        return;
    }

    for (int i = 1; i < n; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            helper(n, i, M, visited, count + 1, ans, sum + M[source][i]);
            visited[i] = false;
        }
    }

}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<vector<int>> M(n, vector<int>(n));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> M[i][j];
            }
        }
        vector<bool> visited(n,false);
        int ans = INT_MAX;
        helper(n, 0, M, visited, 0, ans, 0);
        cout << ans << endl;
    }
    return 0;
}