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

Срочно в номер! Возрождение рубрики ITренировки. Мы вновь собрали вопросы и задачи, задаваемые на собеседованиях в IT-компании.



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

Сегодня у нас задачи — очень разного уровня сложности — с собеседований в индийскую компанию Flipkart. Ну что, прошли собес?

Вопросы

1. Thief, Treasure and 2 Doors

A thief has just found a pair of ancient treasure caves. One of the caves is filled with unbelievable treasure and the other has a fire breathing monster that will eat anyone who opens that cave.
One cave has a black door decorated with diamonds and the other cave has a brown door decorated with sapphires.
Each of the doors has an engraved description on top. The descriptions say:

Black Door: Monster is here.
Brown Door: Only One Door speaks the truth.

Which door should the thief open?

Перевод

Вор только что нашел пару древних пещер. Одна из пещер заполнена невероятными сокровищами, а в другой находится огнедышащий монстр, который съест любого, кто откроет эту пещеру.
Вход в первую пещеру преграждает черная дверь, украшенная бриллиантами, а в другую — коричневая дверь, украшенная сапфирами.
Каждая из дверей имеет выгравированное описание сверху. Описания гласят:

Черная дверь: монстр здесь.
Коричневая дверь: только одна дверь говорит правду.

Какую дверь должен открыть вор?

2. Find ages of daughters

Alok has three daughters. His friend Shyam wants to know the ages of his daughters. Alok gives him first hint.

1. The product of their ages is 72. Shyam says this is not enough information Alok gives him a second hint.
2. The sum of their ages is equal to my house number. Shyam goes out and look at the house number and tells “I still do not have enough information to determine the ages”. Alok admits that Shyam can not guess and gives him the third hint
3. The oldest of the girls likes strawberry ice-cream. Shyam is able to guess after the third hint.

Can you guess what are the ages of three daughters?

Перевод

У Алока трое дочерей. Его друг Шиям хочет знать возраст его дочерей. Алок дает ему первый намек.

1. Произведение их возрастов составляет 72. Шиям говорит, что этой информации недостаточно, тогда Алок даёт ему вторую подсказку.
2. Сумма их возрастов равна номеру моего дома. Шиям выходит, смотрит на номер дома и говорит: «Мне все еще не хватает информации, чтобы определить возраст». Алок признает, что Шиям не сможет догадаться, и поэтому дает ему третью подсказку.
3. Старшая из девушек любит клубничное мороженое. Только после третьей подсказки у Шияма получилось угадать возраст дочерей.

Можете ли вы угадать, каков возраст каждой из трёх дочерей?

Задачи

1. Tom and Jerry

Since very long time Tom and Jerry have been fighting with each other for a piece of Cheese. So finally you came to rescue and decided that the result of the fight will be decided by a mathematical game, in which you will write a number N (1 <= N <= 10^6). Tom and Jerry will play the game alternatively and each of them would subtract a number n [n < N] such that N % n = 0.
The game is repeated turn by turn until the one, who now cannot make a further move looses the game.
The game begins with Tom playing first move. It is well understood that both of them will make moves in optimal way. You are to determine who wins the game.

Input: the first line of each test case consists of N the number.
Output: print 1 if Tom wins and print 0 if Jerry wins in a separate line.

Constraints:
1 <= N <= 10^6

Sample:
Input: 2 / Output: 1
Input: 4 / Output: 1

Перевод

На протяжении долгого времени Том и Джерри боролись друг с другом за кусок сыра. Вы решили помочь им быстро определять победителя. Результат поединка будет решаться в математической игре, в которой вы будете писать число N (1 <= N <= 10^6). Том и Джерри будут играть в игру поочередно. Каждый из них вычтет число n [n < N] так, что N % n = 0.
Игра продолжается до тех пор, пока один из участников может сделать ход. Тот, кто не сможет сделать последний ход, проигрывает.
Игра начинается с того, что Том делает первый ход. Понятно, что оба они будут делать ходы оптимальным образом. Вы должны определить, кто победит в игре.

На вход подается: первая строка ввода каждого теста состоит из числа N.
Выводить программа должна: 1, если победит Том; 0, если Джерри выиграет. В отдельной строке.

Ограничения:
1 <= N <= 10 ^ 6

Пример
Ввод: 2 / Вывод: 1
Ввод: 4 / Вывод: 1

2. N meetings in one room

There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room?

Input:
The first line of input consists number of the test cases. The description of T test cases is as follows:
The first line consists of the size of the array, second line has the array containing the starting time of all the meetings each separated by a space, i.e., S [i]. And the third line has the array containing the finishing time of all the meetings each separated by a space, i.e., F [i].
Output:
In each separate line print the order in which the meetings take place separated by a space.

Constraints:
1 ≤ T ≤ 70
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000

Example:
Input:
2
6
1 3 0 5 8 5
2 4 6 7 9 9
8
75250 50074 43659 8931 11273 27545 50879 77924
112960 114515 81825 93424 54316 35533 73383 160252
Output:
1 2 4 5
6 7 1

Перевод

В фирме есть одна переговорная. Существует N встреч в форме (S [i], F [i]), где S [i] — время начала встречи i, а F [i] — время окончания встречи i.
Задача — разместить максимальное количество встреч в переговорной.

Входные данные:
Первая строка ввода содержит количество тестов. Описание тестов выглядит так:
• первая строка состоит из размера массива;
• вторая строка имеет массив, содержащий время начала всех встреч S[i], каждое из которых разделено пробелом;
• третья строка содержит массив, содержащий время окончания всех встреч F[i], каждое из которых разделено пробелом.
Вывод:
в каждой отдельной строке выведите порядок, в котором проходят собрания, через пробел.

Ограничения:
1 ≤ T ≤ 70
1 ≤ N ≤ 100
1 ≤ S [i], F [i] ≤ 100000

Пример:
Ввод:
2
6
1 3 0 5 8 5
2 4 6 7 9 9
8
75250 50074 43659 8931 11273 27545 50879
77924 112960 114515 81825 93424 54316 35533 73383 160252
Выход:
1 2 4 5
6 7 1

3. Inversion of array

Given an array of positive integers. The task is to find inversion count of array.
Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, the size of array. The second line of each test case contains N elements.
Output: Print the inversion count of array.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 107
1 ≤ C ≤ 1018

Example:
Input:
1
5
2 4 1 3 5
Output:
3

Перевод

Дан массив натуральных чисел. Задача — найти количество инверсий массива.
Количество инверсий: для массива количество инверсии указывает, насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, то количество инверсий равно 0. Если массив отсортирован в обратном порядке, то количество инверсий является максимальным.
Формально два элемента a[i] и a[j] образуют инверсию, если a[i] > a[j] и i < j.

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

Ограничения:
1 ≤ T ≤ 100
1 ≤ N ≤ 10 7
1 ≤ C ≤ 10 18

Пример:
Ввод:
1
5
2 4 1 3 5
Выход:
3

Ну, как и обещали! На вопросы многие смогли ответить, а вот с задачками, видимо, было по-сложнее! :)

Ответы

Вопрос 1

Ответ: в черную дверь.
Решение: давайте посмотрим на описание на коричневой двери «только одна дверь говорит правду». Это можно быть правдой или неправдой.
Сценарий 1: Описание на коричневой двери является правдой. Тогда описание на черной двери («монстр здесь») должно быть ложью. Это означает, что пещера с черной дверью содержит сокровища!
Сценарий 2: описание на коричневой двери ложно. Тогда либо оба описания ложны, либо оба истинны. Оба описания не могут быть правдой, поскольку это невозможно и не согласовано. Это означает, что оба описания являются ложными. Опять же, сокровище в черной двери.

Вопрос 2

Ответ: возраст дочерей: 3 года, 3 года и 8 лет.
Решение: 1) Для начала, сказано, что произведение возрастов равно 72.
Найдём все возможные варианты, при которых произведение будет равно 72:

• 1 * 1 * 72 = 72
• 1 * 2 * 36 = 72
• 1 * 3 * 24 = 72
• 1 * 4 * 18 = 72
• 1 * 6 * 12 = 72
• 1 * 8 * 9 = 72
• 2 * 2 * 18 = 72
• 2 * 3 * 12 = 72
• 2 * 4 * 9 = 72
• 2 * 6 * 6 = 72
• 3 * 3 * 8 = 72
• 3 * 4 * 6 = 72

Этого, конечно же, недостаточно, чтобы дать точный ответ.
Далее Шиям смотрит на номер дома (какой номер — не сообщается) и всё равно не может дать точный ответ. Просуммируем все найденные ранее варианты:

• 1 + 1 + 72 = 74
• 1 + 2 + 36 = 39
• 1 + 3 + 24 = 28
• 1 + 4 + 18 = 23
• 1 + 6 + 12 = 19
• 1 + 8 + 9 = 18
• 2 + 2 + 18 = 22
• 2 + 3 + 12 = 17
• 2 + 4 + 9 = 15
• 2 + 6 + 6 = 14
• 3 + 3 + 8 = 14
• 3 + 4 + 6 = 13

Очевидно, что одна из сумм и есть номер дома. Так как Шиям не смог точно ответить, делается однозначный вывод, что номер дома — 14, так как вариантов с этим результатом — два.

• 2 + 6 + 6 = 14
• 3 + 3 + 8 = 14

3) Из третьей подсказки следует понять, что есть старшая дочь (не несколько, а одна), поэтому из двух вариантов, которые мы нашли на втором шаге, только один подходит.

Задача 1

Lolohaev правильно мыслил!
Ответ: (n - 1) % 2
Решение:

using System;
public class TomJerry {
	static public void Main () {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.printIn((n - 1) % 2);
	}
}

Задача 2

В решении использован Жадный алгоритм (Greedy algorithm).

#include <bits/stdc++.h>
using namespace std;
 
struct Activity
{
    int start, finish, index;
};

bool activityCompare(Activity s1, Activity s2)
{
    return s1.finish < s2.finish;
}

int main()
{
    int t, n, i, j;
    cin >> t;
    while (t--)
    {
        cin >> n;
        Activity arr[n];
        for (i = 0; i < n; i++)
        {
            cin >> arr[i].start;
            arr[i].index = i;
        }

        for (i = 0; i < n; i++)
            cin >> arr[i].finish;
        sort(arr, arr + n, activityCompare);

        i = 0;
        cout << arr[i].index + 1 << " ";
        for (int j = 1; j < n; j++)
        {
            if (arr[j].start >= arr[i].finish)
            {
                cout << arr[j].index + 1 << " ";
                i = j;
            }
        }
        cout << endl;
    }
    return 0;
}

Задача 3

#include<iostream>
using namespace std;
int merge(int* arr, int* LArr, int* RArr, int m, int n)
{
    int i = 0, j = 0, k = 0;
    int count = 0;
    while (i < m && j < n)
    {
        if (LArr[i] <= RArr[j])
            arr[k++] = LArr[i++];
        else
        {
            arr[k++] = RArr[j++];
            count = count + m - i;
        }
    }
    while (i < m)
        arr[k++] = LArr[i++];
    while (j < n)
        arr[k++] = RArr[j++];
    return count;
}
int mergeSort(int* arr, int start, int end)
{
    if (start > end)
        return 0;
    if (start == end)
        return 0;
    if (start == end - 1)
    {
        if (arr[start] <= arr[end])
            return 0;
        else
            swap(arr[start], arr[end]);
        return 1;
    }

    int mid = (start + end) / 2;
    int* LArr = new int[mid + 1];
    int* RArr = new int[end - mid];
    int i;
    for (i = start; i <= mid; i++)
        LArr[i] = arr[i];
    for (i = mid + 1; i <= end; i++)
        RArr[i - (mid + 1)] = arr[i];


    int count = 0;
    count += mergeSort(LArr, 0, mid);
    count += mergeSort(RArr, 0, end - mid - 1);
    count += merge(arr, LArr, RArr, mid + 1, end - mid);

    delete[] LArr;
    delete[] RArr;
    return count;
}

int main()
{
    int t, n,*arr;
    cin >> t;
    while (t--)
    {
        cin >> n;
        arr = new int[n];
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        cout << mergeSort(arr, 0, n - 1) << endl;
    }
}