Шифр

[Progs1024]

Вобщем надо построить массив из n количества чисел(n вводит пользователь)... но так, чтобы каждое число повторялось 3 раза или кратное 3м число раз... НО одно число встречается некратное трём число раз... Надо найти это число

[LeBron]

какие ограничения на n? При детских очень простая сортировочная или переборная задача, при больших - задача олимпиадного уровня, решение которой в случае, если неизвесно какое количество раз встречается искомое число, мне неизвесно.

[LeBron]

И еще кое-что, я не понял, что от нас требуется? написать и шифровщик, и дешифровщик? а то сначала зашифровать, а во второй части задания - розшифровать

[Progs1024]

1<=N<=300001... ну в задаче написано так. цитирую:"среди большого количества чисел спрятано секретное число, причем все числа встречаются трижды(или кратное трём число раз), кроме секретного числа, которое встречается некратное трём число раз" ...надо найти сектретное число

[LeBron]

300000? Тогда это довольно простая задача. Сложно, если, к примеру, большое ограничение по времени и маленькое по памяти, и чисел много (пример - решал для 2кратного повторения, 60 секунд, 1 число без пары вообще 2мб памяти и 100млн чисел, и для 3кратного, 60секунд, 1 число без пары вообще, 2 мб памяти, 50млн чисел).
Сдесь просто пишем быструю сортировку, а потом линейным алгоритмом обходим массив, который получится, и на ходу занимаемся поиском нужного числа. Даже при кривом кусорте должно работать примерно 0.8-0.9 секунды.

[Progs1024]

я конечно понимаю что форум для профессионалов, но я новичок... поэтому можно хотябы некоторые элементы кода для решения этой задачи?

[LeBron]

Я пока далеко не профессионал Как пишется быстрая сортирока - гугл в помощь.
По поводу элементов - проверять после сориторовки надо так

i:=1;ans:=0;nm:=1;
while (i<n)and (ans=0) do begin 
inc(i);if ar[i]<>ar[i-1] then begin 
if nm<>3 then ans:=ar[i-1];
nm:=0;end
else inc(nm);end;

теперь объясняю: у нас будет упорядоченный массив. Следовательно, все числа, которые по 3, будут и в массиве по 3 подряд. А число, которое не 3 раза - и в массиве будет не 3 раза. анс - ответ, это будет тот элемент массива, который заканчивает группу из одинаквых элементов, длинной не 3 ( к примеру, если после сортировки будет
1 1 1 2 2 2 5 5 5 12 12 12 18 18 122 122 122 - то когда дойдем до 122 - будет обрыв группы длиной, отличной от 3 (группа 18 18), поэтому ответом станет 18). нм - текущая длина группы одинаковых. Дальше думаю сами разберетесь. НУ еще объясню, что сначала первый сразу заливаю в группу длиной 1 (ведь перед ним нету других элементов), и просматриваю со второго.

[LeBron]

Еще одно хочу добавить - если дойдем до последнего элемента, а ответа не будет, то ответ - текущее значение nm (просто мы не увидели обрыва, так как группа последняя, ответом является самое большое число массива, обрыв - конец этого массива).

[Progs1024]

Числа идут не по порядку

[LeBron]

Для невнимательных повторяю еще раз - сначала быстрая сортировка, потом линейный обход.