Форум умных людей

Суть задачи такова: представим, что нам нужно написать программу, которая последовательно считывает с клавиатуры n целых чисел (каждое из которых не меньше единицы и не больше n) и определяет, являются ли они перестановкой чисел от 1 до n. Число n известно заранее, до написания программы.

Обычно такое пишется довольно просто. Можно, например, взять массив из n элементов, заполнить его нулями, а затем, считав число, присваивать соответствующему элементу единичку. Если в итоге все элементы стали единичными - значит, перестановка. Нет - значит нет.

Но тут нас поджидает засада: у нас ограничена память. У нас есть только две переменные типа unsigned short (принимающих значения от 0 до 2¹⁶-1), причём одна из них используется как счётчик цикла, и ничего другого мы с ней сделать не можем.

Как нам проверить, являются ли введённые числа перестановкой? И для какого максимального N мы сможем это сделать?

1. В принципе, если суммировать числа в виде к^к, то сумма будет уникальной, но много не насуммируешь :)
2. Я подумаю или можно просуммировать кубы. По теореме Ферма сумма двух кубов никогда не даст третий. Но может ли сумма каких-то к кубов быть равна сумме к других кубов - не знаю...
3. В принципе можно суммировать в виде (n-k)*n^k-1. Тогда сумма в n-ичной системе счисления будет: 012345...(n-2)(n-1) и надо найти максимальное n, если эта сумма < 2¹⁶
Вопрос - или нельзя найти что-то компактнее чем п.1 или п.3...

Можно 27. Если больше то это очень интересно.

В условии сказано что одна из переменных используется как счётчик цикла и больше с ней мы сделать ничего не можем. Я на это не обратил внимание и на цикл взял из неё 5 бит а остальные 11 вместе с 16 из второй переменной использовал для записи единичек. Если этого делать нельзя то решение отменяется. Но в этом случае непонятно зачем переменная цикла имеет тип unsigned short.   

В принципе можно суммировать в виде 2^k-1
Это эквивалентно установке в 1 k-ого бита (что по-видимому имел в виду moonlight).
Тогда для 16-и разрядного числа можно иметь 16 чисел - от одного до 16.
Есть ли возможность бОльшей компактности?
В принципе если не ограничивать размер самой программы - то можно :)
Можно вообще обойтись без ячеек, построив n! ветвей программы,  :) но это уже будет безобразие, конечно :angry:

таких вариантов очень много.
например 1³ + 2³ + 4³ + 8³ + 9³ + 12³  =  3³ + 5³ + 6³ + 7³ + 10³ + 11³

Вопрос в том насколько ограничена n. Если n - ограничена только типом переменной, то всё вышепредложенное не работает

Есть такой вариант.
N=11.
Находим сумму значений f(n)=n⁴+4n³+6n²+6n.
Сумма 60830 получается только если все n различны.

а если n порядка 2^16

А что если этой переменной делать xor (счётчик xor  введённое число)?

Ведь и вправду! (честно, раньше эта задача мне не встречалась). Операция xor коммуникативна и ассоциативна. И, т.к. n xor n = 0, то номера и введённые числа должны себя взаимно уничтожить, если введённые числа являются перестановкой номеров и переменная 2 обратится в 0.

контрпример
n=5, ввод: 3,3,3,3,1

Действительно... Спасибо, подумаю. Но наверняка побитовые операции вовлечены.

кстати, чуть не проглядел
хоть не коммуникабельна))

ой, тьфу, коммутативна, конечно же

{цикл i = [1 ; n]
     a = a XOR i XOR x
} 

{цикл i = [1 ; n]
     a = a XOR i XOR x
}