Написать пост

Избавляемся от шляп, ищем расстояния в массиве и нули в факториале — подборка задач для программистов

Аватар Андрей Приб
Андрей Приб

Джинны, шляпы, расстояния в массиве и нули в факториале — всё это в новой подборке задач для программистов.

Обложка поста Избавляемся от шляп, ищем расстояния в массиве и нули в факториале — подборка задач для программистов

Джинн и шляпы

На острове проживает группа людей. Появившийся джинн собрал всех и надел магические шляпы (или шляпу) некоторым людям (т. е., минимум одну шляпу). Волшебная природа шляпы проявляется в том, что она видима другими людьми, но не видна самому носителю. Чтобы избавиться от шляпы, обладатели (и только они) должны нырнуть в реку ровно в полночь. Если всего человек — N, а шляп — С, сколько времени займет избавление от шляп? Люди не могут сообщать друг другу о наличии шляпы (любым способом).

Примечание Джинн не сообщил, сколько шляп он надел.

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

A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat(s) on some people’s heads (i e , at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are N people and C hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

Note: Genie does not tell how many hats she has put.

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

Рассмотрим сначала простые случаи:

c = 1: в этом случае, человек со шляпой увидит, что ни у кого больше нет шляп и вычислит, что следовательно, он сам является носителем шляпы.

с = 2: каждый обладатель шляпы увидит только одного человека со шляпой, все остальные будут видеть шляпы у обоих. Если бы шляпа была одна — ситуация разрешилась бы в первую ночь, но в этом случае никто не пойдет купаться, не зная, что у него есть шляпа. На второй день люди, видящие одну шляпу догадаются, что и сами являются обладателями шляп и во вторую ночь нырнут оба.

с = 3: в этом случае носитель шляпы увидит двух человек со шляпой, все остальные будут видеть 3 шляпы. Если бы шляп было 1 или 2 — были бы люди, нырнувшие в первую или во вторую ночь. Поскольку этого не произошло, носители шляп догадаются, что количество шляп – 3, и в третью ночь все обладатели шляп пойдут купаться.

Аналогичным образом можно увидеть, что для удаления всех C шляп потребуется C дней.

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

Lets take some simple cases first

c = 1: in this case person who has hat on his head can see that no one else has hat on their head, so he will understand that he is the one with hat.

c = 2: in this case person with hat will see one other person with hat, rest all will see two hats. Now had there been only 1 hat, this case would have been solved on very first day, but in this case no one will go on first night, so the guy who see one hat will understand that there must be one hat on his head, so both of them will go underwater on second night.

c = 3: in this case person with hat will see two hats and rest all will see three hats, now had there been 1 or 2 hats some guys would have gone on first or second night, thus on third day guys who see 2 hats will understand that they have hats on their head and they will all go underwater on third night.

Similarly we can see that it will take c days to remove all hats.

Максимальное расстояние между элементами массива

Дан массив с повторяющимися элементами. Задача — найти максимальное расстояние между двумя вхождениями элемента.

Примеры:

Вход: arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Выход: 10

// максимальное расстояние для 2 это 11-1 = 10
// максимальное расстояние для 1 это 4-2 = 2
// максимальное расстояние для 4 это 10-5 = 5

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

Given an array with repeated elements, the task is to find the maximum distance two occurrences of an element.

Examples:

Input : arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output: 10

// maximum distance for 2 is 11-1 = 10
// maximum distance for 1 is 4-2 = 2
// maximum distance for 4 is 10-5 = 5

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

Простое решение — перебирать элементы по одному, находить первое и последнее вхождения в массиве, и считать разницу позиций в качестве максимального расстояния. Временная сложность при этом подходе будет O(n^2).

Эффективное решение — использовать хэш-таблицу. Идея заключается в том, чтобы пройти входной массив, сохраняя индекс первого вхождения элементов в хэш-таблице. Для каждого последующего вхождения находить разницу между индексом элемента и индексом первого вхождения. Если эта разница больше текущего результата — обновить результат.

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

A simple solution for this problem is to one by one pick each element from array and find its first and last occurence in array and take difference of first and last occurence for maximum distance. Time complexity for this approach is O(n2).

An efficient solution for this problem is to use hashing. The idea is to traverse input array and store index of first occurrence in a hash map. For every other occurrence, find the difference between index and the first index stored in hash map. If difference is more than result so far, then update the result.

Код
			# Python program to find maximum distance between two
# same occurrences of a number.
  
# Function to find maximum distance between equal elements
def maxDistance(arr, n):
      
    # Used to store element to first index mapping
    mp = {}
  
    # Traverse elements and find maximum distance between
    # same occurrences with the help of map.
    maxDict = 0
    for i in range(n):
  
        # If this is first occurrence of element, insert its
        # index in map
        if arr[i] not in mp.keys():
            mp[arr[i]] = i
  
        # Else update max distance
        else:
            maxDict = max(maxDict, i-mp[arr[i]])
  
    return maxDict
  
# Driver Program
if __name__=='__main__':
    arr = [3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2]
    n = len(arr)
    print maxDistance(arr, n)

Нули в факториале числа 100

Сколько замыкающих нулей в 100! (факториал числа 100)?

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

How many trailing zeroes are there in 100! (100 factorial) ?

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

Для каждого множителя, кратного 10, будет добавлен один замыкающий ноль; также для каждого множителя, заканчивающегося на 5, будет добавлен один ноль (поскольку 5*2 = 10, а двоек в этой последовательности достаточно). Необходимо также не забывать о повторениях:

10, 20,…., 90 = 9 нулей

100 = 2 нуля

5, 15, 25……95 = 10 нулей

и ещё дополнительная 5 в числах 25, 50 и 75 = 3 нуля

итого 9+2+10+3 = 24 нуля.

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

For every factor of 10, there will be one trailing zero similarly for every factor of 5 there will be one trailing zero (as 5*2 =10, and there are enough number of 2’s). But we have to take care of repetitions.

10, 20,…., 90 = 9 zeros

100 = 2 zeros

5, 15, 25……95 = 10 zeros

and 1 extra 5 in each of 25, 50 and 75 = 3 zeros

so total 9+2+10+3 = 24 zeros.

6К открытий6К показов