Рубрики

Головоломка 29 | (Загадка автомобильного колеса)

Головоломка : автомобиль имеет 4 шины и 1 запасное колесо. Каждая шина может проехать максимум 20000 миль, прежде чем износиться. Какое максимальное расстояние может проехать автомобиль, прежде чем вас заставят купить новую шину? Вам разрешается менять шины (используя запасное колесо) неограниченное количество раз.

Ответ : 25000 км

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

Пусть четыре шины будут обозначены как A, B, C и D, а запасное колесо — S.

  1. 5000 км: замените A на S. Остальные расстояния (A, B, C, D, S): 15000, 15000, 15000, 15000, 20000.
  2. 10000 км: верните A в исходное положение и замените B на S. Остальные расстояния (A, B, C, D, S): 15000, 10000, 10000, 10000, 15000.
  3. 15000 км: верните B в исходное положение и замените C на S. Остальные расстояния (A, B, C, D, S): 10000, 10000, 5000, 5000, 10000.
  4. 20000 км: верните C в исходное положение и замените D на S. Остальные расстояния (A, B, C, D, S): 5000, 5000, 5000, 0, 5000.
  5. 25000 км: каждая шина полностью изношена.

Все шины используются в полную силу.

Связанный вопрос интервью Амазонки

Есть n карандашей, каждый из которых имеет длину l. Каждый может написать 4 километра. После написания 4 километров он имеет длину l / 4. Можно объединить 4 карандаша, которые имеют длину l / 4 и можно сделать 1 карандаш. Нельзя сделать карандаш из кусочков, если оставшихся кусков 3, 2 или 1, но можно включать эти оставшиеся кусочки, когда это необходимо.
Напишите отношение, не зависящее от l, длины данного карандаша, для того, сколько можно написать из n карандашей.

Примеры:

Input: 4
Output: 20

Рекурсивный подход:
Предположим, что мы используем 3 карандаша, которые будут 12 и генерируют 3 использованных карандаша, теперь, если оставшиеся карандаши больше нуля, по крайней мере 1 неиспользованный карандаш можно использовать с этими 3 неиспользованными карандашами, чтобы написать 4, и это сгенерирует еще 1 неиспользованный карандаш. Это будет повторяться.

if(n-3 >= 1){
  f(n) = f(n-3) + 12 + 4
} 
else{
  // Used pencil that cannot be used
  f(n) = 4 + 4 
}

Ниже приведена реализация вышеуказанного подхода:

int count(int n)

{

    if (n < 4) {

        return (n * 4);

    }

    else {

        return (16 + count(n - 3));

    }

}

Математический подход O (1):
Выше отношение может быть оптимизировано в O (1)

// x is max no of time we can 
//subtract 3 without n-3 <= 3
n - 3 + x <= 3     
x  >  (n-3)/3
i.e. n/3 - 1 if it divides exactly
else n/3

Ниже приведена реализация вышеуказанного подхода:

// C ++ программа для поиска отношения, независимого от l
// длина данного карандаша, за сколько
// могу писать из n карандашей.

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция найти не карандаши

int count(int n)

{

    int x = (n / 3) - 1;

    if (n % 3) {

        x++;

    }

    return (4 * x + 4 * n);

}

  
// Функция драйвера

int main()

{

    int n = 5;

    cout << count(n) << endl;

}

Выход:

24

Рекомендуемые посты:

Головоломка 29 | (Загадка автомобильного колеса)

0.00 (0%) 0 votes