Ну как Вам задачки из прошлой статьи, успели решить? Ответы уже опубликованы!
А сейчас у нас новые поступления!
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.
На этой неделе мы собрали задачи с собеседований в норвежскую компанию Opera Software.
1. Pay an employee using a 7 units gold rod?
2. Загадка Эйнштейна
1. Product array puzzle
2. Egg Dropping Puzzle
3. Travelling Salesman Problem
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
А сейчас у нас новые поступления!
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства 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.
Ограничения:
Пример:
Вход
Выход
Вход
Выход
Объяснение:
Первый тест: для массива произведений 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
Входные данные: каждый тестовый пример содержит две строки ввода. Первая строка — 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» — количество этажей в здании.
Выход:
Для каждого теста выведите в отдельной строке одно целое число — минимальное количество попыток, необходимое для определения критического этажа.
Ограничения:
Пример:
Входные данные:
Выход:
- Яйцо, которое переживет падение, можно использовать снова.
- Разбитое яйцо нужно выбросить.
- Эффект падения одинаков для всех яиц.
- Если яйцо не сломается на определенном этаже, оно не сломается ни на одном этаже ниже.
- Если яйца разбиваются на определенном этаже, они разбиваются на любом этаже выше.
Более подробное описание этой проблемы смотрите на вики-странице.
Входные данные:
Первая строка ввода — это T, обозначающая количество тестовых случаев. Каждая из T строк содержит два положительных целых числа N и K, где «N» — количество яиц, а «K» — количество этажей в здании.
Выход:
Для каждого теста выведите в отдельной строке одно целое число — минимальное количество попыток, необходимое для определения критического этажа.
Ограничения:
1 <= Т <= 30
1 <= N <= 10
1 <= K <= 50Пример:
Входные данные:
2
2 10
3 5Выход:
4
33. 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.
Выход:
Для каждого тестового примера в новой строке выведите искомый результат, обозначающий минимальную стоимость тура.
Ограничения:
Пример:
Входные данные:
Выход:
Входные данные:
Первая строка ввода содержит целое число 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Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
LeshaRB
Про стержень
anton19286
То есть сдача разрешена? Работник явно не гаишник.
Задачку надо ещё чуть усложнить, вторым резом делить стержень на четыре куска.
jmdorian
Capacitor10n
Такие задачки можно посмотреть на braingames.ru.
Там же можно померятся набранными очками. На самом ресурсе спойлеры не найти, вроде бы.
Задачки побиты на категории (по мне самые интересные логические).
Перечисленные в статье вроде бы тоже есть.
Вот запомнившаяся (с друзьями прям пару дней тупили в нее, кто быстрее решит), ТЫК:
Подлые оккупанты захватили деревню мегамозгов, выстроили их друг за другом в колонну так, что каждый последующий видит всех предыдущих. На каждого мегамозга надели колпак черного или белого цвета так, что ни один мегамозг не видит свой колпак. Начиная с самого последнего (того, который видит всех, кроме себя), у каждого мегамозга по очереди спрашивают цвет его колпака. Если он ошибается, его убивают. Неизвестно, чем бы всё это закончилось, если бы мегамозги заранее не договорились, как минимизировать число убитых. Сколько мегамозгов гарантированно выживет?
jmdorian
Capacitor10n
Подсказка (скорее уточнение) полуспойлер :)))
jmdorian
Capacitor10n
Подправил свой ответ чуть раньше Вашего вопроса, посмотрите еще раз предыдущий комент.
dikkini
первый гном считает количество черных шапок впереди стоящих, если четное называет черный, следующий гном считает цвета если четность изменилась — называет другой цвет, если не изменилась называет тот же цвет что и предыдущий
jmdorian
Capacitor10n
Выживают все (выживание последнего в скобочках).
На первом говорящем белый колпак.
2 + 2 + 1 + 1 + X = 6 Скажет черный (помер).
2 + 2 + 1 + 1 + 1 + X= 7 Скажет белый (выжил).
На первом говорящем черный колпак.
1 + 1 + 1 + 2 + X = 5 Скажет белый (Помер).
1 + 1 + 1 + 1 + 2 + X = 6 Скажет черный (выжил).
dikkini
б б ч ч б ч ч б
1 спрашивают — он считает количество б = 3, ч = 4, называет б, так как нечет — не убили (повезло)
2 считает количество б = 2, четность изменилась на нем, значит он изменил четность, значит у него такой же цвет шапки, так как он помнит, что договорились, что 1 назовет тот цвет, который нечет, называет б — не убили
3 считает количество б = 2, не изменилась, называет ч — не убили
4 считает количество б = 2, не изменилась, называет ч — не убили
5 считает количество б = 1, изменилась, называет б — не убили
6 считает количество б = 1, не изменилась, называет ч — не убили
7 считает количество б = 1, не изменилась, называет ч — не убили
8 считает количество б = 0, изменилась, называет б — не убили
Количество не важно, порядок не важен.
Capacitor10n
О! Ответы можно проверить там же на ресурсе зарегистрировавшись.
За правильные ответы начисляют очки в зависимости от сложности задачи.
hd_keeper
Свернуть стержень в спираль на 1.75 оборотов, и разрезать двумя ударами крест-накрест, под прямым углом. Получится как раз 7 кусков. Тут предполагается, что стержень гнётся.
anton19286
на 3 оборота и хвостик. рубануть раз
hd_keeper
Да, можно и на 1 разрез, выйдет 3.5 оборота.
Ac0olA Автор
Интересная идея! А если стержень не гнётся?)
anton19286
тогда за 2 удара можно разрубить на 4 части и платить 15 дней
BASic_37
А вот зебру сразу однозначно с ходу не вычислить, только методом подстановки возможных вариантов, не представляю как это делать в уме без таблички…
Зебру держит японец.