Программистская.

[Sirion]

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

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

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

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

[buka]

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

[moonlight]

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

[moonlight]

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

[buka]

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

[moonlight]

По теореме Ферма сумма двух кубов никогда не даст третий. Но может ли сумма каких-то к кубов быть равна сумме к других кубов - не знаю...

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

[zhekas]

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

[moonlight]

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

[zhekas]

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

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

[General]

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

[General]

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

[Sirion]

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

[General]

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

[Sirion]

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

Операция xor коммуникативна

хоть не коммуникабельна))

[General]

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