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

Задачи на логику: помогите таракану, посчитайте множители и побудьте диспетчером

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

Обложка поста Задачи на логику: помогите таракану, посчитайте множители и побудьте диспетчером

Таракан на стене

Маленький таракан карабкается по стене высотой 10 метров. Таракан начал путь с подножия стены. Каждый час он может проползти 1 метр в высоту и затем немедленно скатывается на ⅔ метра вниз. Сколько часов понадобится таракану, чтобы достичь вершины стены?

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

A small cockroach is climbing on the wall which height is 10 meters. Cockroach starts his way from the foot of this wall. Every hour the cockroach is able to climb up 1 meter, then immediately slide back down 2/3 meter. How many hours does it take for the cockroach to get the top of the wall?

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

Ответ: 28 часов.

Таракан проходит ⅓ метра в час, за исключением 28 часа, когда он уже достигнет вершины за первый подход, так что скатывание вниз не будет считаться.

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

28 hours.
The cockroach is travelling at ⅓ meter per hour, except on the 28th hour the cockroach has already reached the top of the wall, so it will not slide down the 2/3 meter.

Найдите количество простых множителей для каждого числа в диапазоне [0, K]

Вход: N = 4
Выход : 0 1 1 1
Количество простых множителей для 1 — 0
Количество простых множителей для 2 — 1
Количество простых множителей для 3 — 1
Количество простых множителей для 4 — 1

Вход: 6
Выход: 0 1 1 1 1 2
Количество простых множителей для 1 — 0
Количество простых множителей для 2 — 1
Количество простых множителей для 3 — 1
Количество простых множителей для 4 — 1
Количество простых множителей для 5 — 1
Количество простых множителей для 6 — 2
2, 3 и 5 сами являются простыми. Для 4 единственный простой множитель — 2. Для 6 простых множителей два — 2 и 3.

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

Given a number K, find the number of distinct prime factors for all numbers in the range [1, K].

Example:
Input : N = 4
Output : 0 1 1 1
Number of distinct Prime Factors of 1 is 0
Number of distinct Prime Factors of 2 is 1
Number of distinct Prime Factors of 3 is 1
Number of distinct Prime Factors of 4 is 1

Input : 6
Output : 0 1 1 1 1 2
Number of distinct Prime Factors of 1 is 0
Number of distinct Prime Factors of 2 is 1
Number of distinct Prime Factors of 3 is 1
Number of distinct Prime Factors of 4 is 1
Number of distinct Prime Factors of 5 is 1
Number of distinct Prime Factors of 6 is 2
2, 3 and 5 are themselves prime. The only prime factor of 4 is 2.The two prime factors of 6 are 2 and 3.

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

Одно из возможных решений базируется на Решете Эратосфена. Мы будем просматривать все числа в заданном диапазоне, и, при нахождении простого числа, будем увеличивать количество простых множителей в его произведениях:

			// Программа для поиска  количества
// простых множителей
// для всех чисел в диапазоне [1, N]
using System;
 
class GFG
{
static void printDistinctPFs(int n)
{
    // массив для хранения
    // количества произведений
    long []factorCount = new long[n + 1];
 
    // true если индекс 'i' является простым
    bool []prime = new bool[n + 1];
 
    // инициализируем количество
    // произведений как равное 0
    for (int i = 0; i <= n; i++)
    {
        factorCount[i] = 0;
        prime[i] = true; // используется в Решете
    }
 
    for (int i = 2; i <= n; i++)
    {
 
        // условие сработает только 
        // если 'i' - простое,
        // следовательно для произведений всех
        // простых чисел 
        // указывает prime в false
        if (prime[i] == true)
        {
             
            // Число простое
            factorCount[i] = 1;
             
            // количество множителей простого числа равно 1
            for (int j = i * 2; j <= n; j += i)
            {
 
                // увеличиваем factorCount
                // для всех произведений i
                factorCount[j]++;
 
                // и изменяем признак простого
                // числа в false
                prime[j] = false;
            }
        }
    }
 
    // Выводим результат
    for (int i = 1; i <= n; i++)
    Console.Write(factorCount[i] + " ");
}
 
// Основная программа
public static void Main ()
{
    int n = 20; // ввод
    printDistinctPFs(n);
}
}
		
Решение задачи на английском языке

One of the possible answers is based on Sieve of Erathosthenes. We’ll review all numbers in given range and whenever we mark number as prime, we also increment count of prime factors in its multiples.

Минимальное количество самолётов

На удаленном острове находится аэропорт. Этот аэропорт является базой для неограниченного количества одинаковых самолетов. Топливная емкость каждого самолета позволяет облететь ровно ½ земного шара вдоль большого круга. Самолеты имеет возможность дозаправки в воздухе без потери скорости и горючего. Хотя количество топлива тоже неограничено, едиственным его источником является этот остров.

Какое минимальное количество самолетов нужно, чтобы облететь земной шар, с учетом того, что каждый самолет должен безопасно вернуться в аэропорт?

Обратите внимание:

  1. Можно игнорировать затраты горючего на ускорение, потери при испарении топлива и пр.
  2. Поскольку все самолеты должны вернуться в аэропорт — нельзя передать все топливо с одного самолета на другой.
  3. Предполагается, что дозаправка — чрезвычайно быстрый процесс.
Оригинал задачи на английском языке

On very distant island, there is an airport. The airport is the home base of an unlimited number of identical aircrafts. Each aircraft has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The airplanes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel.

What is the fewest number of planes necessary to get one plane all the way around the world assuming that all of the plane must return safely to the airport?

Notes:

1) Ignore extra fuel consumption as a result of acceleration, evaporation of fuel, etc.
2) All the planes have to make it back safely, so you can’t give all your fuel away to another plane.
3) Assume that refuelling is an extremely fast process.

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

Ответ: 3 самолёта.

Представим 3 самолёта (A, B и C). А собирается облететь вокруг Земли. Все три самолета стартуют в одно время и в одном направлении. После ⅙ пути, В передает треть топлива С и возвращается домой, где заправляется и снова взлетает следом за А и С. С продолжает лететь рядом с А, пока они не пройдут ¼ всей дистанции. В этой точке С заправляет А до полного бака, так что А теперь может долететь до ¾ окружности Земли. У С теперь осталось лишь треть своего бака, этого недостаточно, чтобы вернуться на базу. Но первый “вспомогательный” самолет В будет в нужной точке чтобы дозаправить его, и оба вспомогательных самолета смогут безопасно долететь до базы.

Таким же образом, полностью заправленные В и С вылетают навстречу А. В снова дозаправляет С и возвращается на базу, чтобы пополнить бак. С встречает А в точке, когда А пролетел ¾ дистанции. Все три самолета могут долететь до аэропорта, при условии, что дозаправка будет проводиться аналогично первой части полёта.

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

The fewest number of aircraft is 3!

Imagine 3 aircraft (A, B and C). A is going to fly round the world. All three aircraft start at the same time in the same direction. After 1/6 of the circumference, B passes 1/3 of its fuel to C and returns home, where it is refueled and starts immediately again to follow A and C.

C continues to fly alongside A until they are 1/4 of the distance around the world. At this point C completely fills the tank of A which is now able to fly to a point 3/4 of the way around the world. C has now only 1/3 of its full fuel capacity left, not enough to get back to the home base. But the first ‘auxiliary’ aircraft reaches it in time in order to refuel it, and both ‘auxiliary’ aircraft are the able to return safely to the home base.

Now in the same manner as before both B and C fully refueled fly towards A. Again B refuels C and returns home to be refueled. C reaches A at the point where it has flown 3/4 around the world. All 3 aircraft can safely return to the home base, if the refueling process is applied analogously as for the first phase of the flight.

Следите за новыми постами
Следите за новыми постами по любимым темам
7К открытий7К показов