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

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.

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.

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.