Какое число остается после многократного устранения идеальных квадратов?

Ответ 1

Я считаю, что следующее решение работает правильно и использует память O (1), предполагая, что вы можете удерживать целое число в O (1) пространстве. Идея состоит в том, чтобы попытаться запустить этот процесс назад, пока вы не обретете окончательное положение правильной части конфеты.

Проследим пример этой проблемы, где n = 10. Тогда получим:

1  2  3  4  5  6  7  8  9  10
X        X              X

2  3  5  6  7  8  10
X        X

3  5  7  8  10
X        X

5  7  10
X

7  10
X

10

Теперь предположим, что мы хотим вычислить конечный результат для этой проблемы. Мы знаем, что, когда мы закончили, конфеты съели в позиции 1, так как осталось только один кусочек конфеты. Поэтому попробуйте настроить его следующим образом:

1

Теперь мы знаем, что на предыдущей итерации конфеты с индексом 1, должно быть, были съедены. Это означает, что последняя конфета была фактически в положении 2 в последний раз:

?   2

На итерации до этого мы знаем, что, поскольку конфеты 1 были съедены, наша конфета должна была быть в положении 3:

?   ?   3

В этот момент мы снова возвращаем одну итерацию. Мы знаем, что конфеты 1 были съедены, но конфеты 4 тоже были съедены. Это означает, что индекс нашей конфеты должен был быть 5 на предыдущей итерации, так как, когда мы подбрасываем его до своего правильного положения, он должен был пропустить одно место для первого элемента и одно пятно для 4-го элемента:

?   ?   ?   ?   5

Повторяя эту же логику, получим, что предыдущий индекс был бы 7:

?   ?   ?   ?   ?   ?   7

Теперь, для следующего шага, мы знаем, что мы бы разбили конфеты на две позиции, потому что мы бросили 1-й и 4-й элементы. Однако это положило бы нашу конфету в позицию 9, которая была бы удалена. Это означает, что вместо этого мы помещаем конфету в положение 10:

?   ?   ?   ?   ?   ?   ?   ?   ?   10

В этот момент, поскольку осталось 10 конфет, мы знаем, что мы полностью изменили процесс и закончили. Поскольку последнее место отдыха нашей конфеты было позицией 10, мы знаем, что ответ заключается в том, что 10-я конфета - это та, которая была съедена, что идеально соответствует нашей предыдущей работе!

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

• Какой индекс - последний кусок конфеты в настоящее время? Нам нужно это знать, где остановиться.
• Сколько квадратов ниже этого индекса? Нам нужно знать, сколько элементов удаляется на каждом шаге.
• Что представляет собой следующий идеальный квадрат? Нам нужно это знать, когда количество удаляемых квадратов увеличивается каждый раз.
• Что было последним индексом, который мы исследовали? Этот алгоритм работает, запустив процесс назад, поэтому в какой-то момент мы поймем, что мы запустили его один раз слишком много. Когда это произойдет, мы должны иметь возможность "создать резервную копию" шага, чтобы перейти к последнему индексу, который не перешагнул.

Учитывая это, мы имеем следующий алгоритм:

• Установите текущий индекс на 1.
• Задайте количество меньших совершенных квадратов до 1.
• Установите следующий идеальный квадрат на 4.
• Установите последний меньший индекс равным 1.
• Пока текущий индекс меньше n:
  • Установите последний меньший индекс как текущий индекс (помните решение до сих пор).
  • Установить текущий индекс + = число меньших совершенных квадратов (запустите процесс назад на один шаг)
  • Если текущий индекс равен следующему совершенному квадрату, добавьте его к нему (крайний случай запуска его назад, если мы нажмем идеальный квадрат, мы должны пройти его один шаг).
  • Если текущий индекс больше, чем следующий идеальный квадрат (теперь на каждом шаге удаляется больше номеров):
    • Установите идеальный квадрат, чтобы быть следующим идеальным квадратом.
    • Добавьте один к числу совершенных квадратов, меньших индекса.
• Возвращает последний меньший индекс.

Для хранения всех значений требуется только память O (1).

Попробуйте пример! При n = 20, если мы работаем через формальный процесс, получаем следующее:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
X        X              X                    X 

2  3  5  6  7  8 10 11 12 13 14 15 17 18 19 20
X        X              X                    X 

3  5  7  8  10 11 13 14 15 17 18 19
X        X              X

5  7 10 11 13 14 17 18 19
X        X              X

7 10 13 14 17 18
X        X

10 13 17 18
X        X

13 17
X

17

Если мы запустим наш алгоритм, получим

 Current Index       Next Square      Smaller Squares
 1                   4                1
 2                   4                1
 3                   4                1
 5                   9                2
 7                   9                2
 10                  16               3
 13                  16               3
 17                  25               4
 21                  25               4

Так как 21 > 20, последний меньший индекс равен 17, поэтому мы возвращаем 17, что является правильным ответом!

Написано как код C, не предполагая полного переполнения:

int EatenCandyIndex(int n) {
    int currIndex = 1;
    int numSmallerSquares = 1;

    /* Rather than tracking the next square, track the root of the next
     * square.  We can just square this to get the next square.
     */
    int rootOfNextSquare = 2;

    /* The last spot where the candy would be before we had Too Much Candy. */
    int lastIndex = 1;

    while (currIndex <= n) {
        lastIndex = currIndex;

        currIndex += numSmallerSquares;
        if (currIndex == rootOfNextSquare * rootOfNextSquare)
            ++currIndex;

        if (currIndex > rootOfNextSquare * rootOfNextSquare) {
            ++numSmallerSquares;
            ++rootOfNextSquare;
        }
    }

    return lastIndex;
}

Однако, как написано, этот алгоритм не особенно эффективен. В частности, посмотрите на его поведение в примере, где n = 20. Заметим, что у нас есть три раунда, где размер шага один, два с шагом размером два и три и т.д. Вместо того, чтобы эти раунды встречаются явно, мы могли бы вместо этого вычислить сколько раундов придется выполнять с этим размером шага, а затем просто запустить все эти шаги сразу. Таким образом, у нас всегда есть один раунд с размером один, один раунд с размером два, один раунд с размером три и т.д. Для этого на каждом шаге нам нужно будет увидеть, какова наша следующая цель; это будет либо число n, либо следующий совершенный квадрат. Как только мы нашли свою цель, нам нужно посмотреть, сколько шагов требуется для ее получения. Если текущий индекс равен i, а наша цель равна t, и если размер шага равен k, тогда нам нужно взять & lceil; (t - i)/k & rceil; шаги, чтобы добраться туда. Используя симпатичный трюк с целым делением, мы можем вычислить это как

int numSteps = ((t - i) + (k - 1)) / k;

Это дает нам следующий обновленный алгоритм:

int EatenCandyIndexFaster(int n) {
    int currIndex = 1;
    int numSmallerSquares = 1;

    /* Rather than tracking the next square, track the root of the next
     * square.  We can just square this to get the next square.
     */
    int rootOfNextSquare = 2;

    while (true) {
        /* Figure out what our target is. */
        int target = min(n, rootOfNextSquare * rootOfNextSquare);

        /* See how many steps are required. */
        int numSteps = ((target - currIndex) + (numSmallerSquares - 1)) / numSmallerSquares;

        /* See where we'd end up if we took one fewer than this many steps forward. */
        int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares;

        /* Take that many steps forward. */
        currIndex += numSmallerSquares * numSteps;

        /* There is an edge case here: if we hit our number but it a perfect square,
         * we want to return the previous value.
         */
        if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare)
            return lastIndex;

        /* Otherwise, if we hit the target number exactly, return it. */
        if (currIndex == n)
            return currIndex;

        /* Otherwise, if we overshot the target number, hand back where we'd be if we
         * took one fewer step.
         */
        if (currIndex > n)
            return lastIndex;

        /* Oh well; didn't make it.  If we hit a perfect square, skip it. */
        if (currIndex == rootOfNextSquare * rootOfNextSquare)
            ++currIndex;

        ++numSmallerSquares;
        ++rootOfNextSquare;
    }
}

Эта оптимизированная версия алгоритма работает в O (& radic; N) времени и использует O (1) пространство. Причиной временной привязки является то, что каждый шаг алгоритма переходит к следующему совершенному квадрату, и только O (& radic; N) идеальные квадраты меньше N.

Надеюсь, это поможет!

Ответ 2

Другой вариант:

a = floor(sqrt(N-1))
b = min((N-1)/a, a+1)
solution = a*b+1

Или, иначе говоря,

unsigned long long eats(unsigned long long N) {
    unsigned long long r = (unsigned long long)sqrt(N-1);
    while(r*r >= N) --r;
    while(r*(r+2) < N) ++r;
    if (N <= r*(r+1)) {
        return r*r+1;
    }
    return r*(r+1)+1;
}

Доказательство следует из анализа функции next, которая дает следующую позицию любой конфеты next(n*n) = 0, так что она не является частичной функцией. Если a*a < N < (a+1)*(a+1), имеем next(N) = N - a. Таким образом, число форм n = a*(a+1) + 1 перемещается

a*(a+1)+1 -> a*a + 1 -> (a-1)*a + 1 -> ... -> 2*3 + 1 ->2*2 + 1 -> 1*2 + 1 -> 1*1 + 1 -> 0*1 + 1

Мы видим, что и числа вида a*a +1 достигают 1. Числа любой другой формы достигают квадрата, большего 1 в некоторой точке:

a*(a+1) -> a*a -> eliminated
a*(a+1) + r -> a*a + r -> (a-1)*a + r

для 2 <= r <= a. Если r = a, (a-1)*a + r = a*a - квадрат, что приводит к немедленному устранению. Если r < a, число, достигнутое после двух шагов, имеет тот же вид с тем же r. Продолжая, из этого следует, что число достигает

(r+1)*(r+2) + r -> (r+1)*(r+1) + r -> r*(r+1) + r -> r*r + r -> r*r -> elimination.

Итак, мы видели

• Число достигает точки 1 в процессе тогда и только тогда, когда оно имеет вид n*n + 1 или n*(n+1) + 1

Последнее число для первого пятна, начинающегося с N конфет, конечно, самое большое число этой формы, не превышающее N. Что и требовалось доказать.

Ответ 3

Если я сделал глупую ошибку, там есть формула для этого. Возможно, это будет упрощено, но это первый, на который я попал.

from math import floor, sqrt, ceil

def is_square(i):
    sq = int(i**0.5)
    return i == sq*sq

def brute(n):
    seq = range(1, n+1)
    while len(seq) > 1:
        seq = [x for i,x in enumerate(seq, 1) if not is_square(i)]
    return seq[0]

def dasher(n):
    w = lambda i: floor(sqrt(4*i+1))-1
    q = lambda i: ceil((i**2+3)/4)
    return q(w(n-1)+1)

И проверить:

>>> b = [brute(i) for i in range(1, 10**3)]
>>> d = [dasher(i) for i in range(1, 10**3)]
>>> b[:25]
[1, 2, 3, 3, 5, 5, 7, 7, 7, 10, 10, 10, 13, 13, 13, 13, 17, 17, 17, 17, 21, 21, 21, 21, 21]
>>> b == d
True

Ответ 4

Я думаю, что могу быть здесь.

f(n) = 1 if n = 1
f(n) = f(n-floor(sqrt(n))) + floor(sqrt(n)) if n is not a perfect square
f(n) = f(n-1) if n is a perfect square

Базовый регистр ясен. Случай "идеального квадрата" исходит из наблюдения, что если n - идеальный квадрат, он будет устранен, когда вы устраните идеальные квадраты, поэтому решение для него эквивалентно решению на один меньше, чем он, во всяком случае. Последнее происходит из наблюдения, что после удаления пол (sqrt (n)) идеальных квадратов и перенумерации вы переместили некоторые цифры влево (но в остальном ответы одинаковы). Мы можем проверить это для первых нескольких случаев...

 n Answer f(n)
 1      1    1
 2      2    f(2-1) + 1 = f(1) + 1 = 1 + 1 = 2
 3      3    f(3-1) + 1 = f(2) + 1 = 2 + 1 = 3
 4      3    f(4-1) = f(3) = 3
 5      5    f(5-2) + 2 = f(3) + 2 = 3 + 2 = 5

Доказательство этого, если оно правильно, должно быть прямым расширением, и пока я не завершу его, я оставляю его как упражнение. Вы должны проверить его на большое количество случаев и посмотреть, работает ли он; если он не работает, я удалю его.

EDIT:

Я думаю, что тенденция, которую я замечаю, и причина, по которой это работает, заключается в том, что для не квадрата n ответ никогда не может быть меньше, чем наибольший квадрат меньше n. Я думаю, причина в том, что вы никогда не сможете удалить m ^ 2 + 1, прежде чем удалить все, что меньше или равно m ^ 2. Учитывая, что приведенные выше рекуррентные соотношения почти тривиально верны.

Ответ 5

Вы знаете, что последний номер будет удален специальным номером 1. Если вы сгенерируете все числа, удаленные на 1, у вас будет набор, содержащий специальный номер. Итак, все, что вам нужно сделать, это генерировать эти числа.

Итак, давайте посмотрим, есть ли шаблон.

Пусть n равно 150

Числа, удаленные 1

r = [1, 2, 3, 5, 7, 10, 13, 17, 21, 26, 31, 37, 43, 50, 57, 65, 73, 82, 91, 101, 111, 122, 133]

Массив r [i + 1] -r [i]

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11] p >

Числа, удаленные с помощью 2

r = [4, 6, 8, 11, 14, 18, 22, 27, 32, 38, 44, 51, 58, 66, 74, 83, 92, 102, 112, 123, 134, 146]

Массив r [i + 1] -r [i]

[2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

Числа, удаленные на 9 Мы знаем, что числа, удаленные на 9, будут отличаться в первых двух элементах на 3, а первый элемент - на 9. Отсюда мы можем сгенерировать числа, которые будут удалены по этой схеме 3,3,4,4,5, 5   [9, 12, 15, 19, 23, 28, 33, 39, 45, 52, 59, 67, 75, 84, 93, 103, 113, 124, 135, 147]   [3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

import math

def getSpecial(n):
    sp = list()
    s = 1
    while((s * s) <= n):
        sp.append(s*s)
        s += 1
    return sp

def bruteForce(n):
    nu = range(n+1)
    nu.pop(0)
    while(len(nu) > 1):
        sp = getSpecial(len(nu))
        removed = list()
        for x in sp[::-1]:
            removed.append(nu.pop(x-1))
    return nu[0]

def fancyMathWitchCraft(n):
    sp = getSpecial(n)    
    oneset = [1]
    j = 0.0
    while(oneset[-1] <= n):
        oneset.append( oneset[-1] + int(1 + 1 * math.floor(j/2)) )
        j = j + 1.0

    if(oneset[-1] <= n):
        return oneset[-1]
    if(oneset[-2] <= n):
        return oneset[-2]
    if(oneset[-3] <= n):
        return oneset[-3]



def main():
    for x in range(1,2000):
        if(bruteForce(x) != fancyMathWitchCraft(x)):
            print(x, bruteForce(x), fancyMathWitchCraft(x))
    print("Done")

if __name__ == "__main__":
    main()

Доказательство этого, вероятно, связано с тем, что последний совершенный sq будет удалять только 1 число, поэтому окончательное число будет получено из самого большого непрерывного сегмента, который не будет затронут после 1-й итерации, и это будет последним сегмент. Если вы действительно хотите получить математическое подтверждение для этого, вам придется ответить на этот вопрос meta.stackoverflow

Ответ 6

n=1, eats=1  
n=2, eats=2  
n=3, eats=3  
n=4, eats=3  
n=5, eats=5  
...  

Вы видите шаблон? Придумайте формулу и докажите, что формула правильная, используя математическую индукцию

Вот код С++:

#include <iostream>
#include <cmath>

using namespace std;

bool is_perfect_square(int value)
{       
    return pow( static_cast<double>(static_cast<int>(sqrt(static_cast<double>(value)))), 2.0) == value;
}

int EatEm(int n)
{
    while (is_perfect_square(n))
    {
        n -= (static_cast<int>(sqrt(static_cast<double>(n)) - 1));
    }

    return n;
}

int main()
{           
    int res = EatEm(25);
    cout << res << endl;
    return 0;
}