Кто знает как решаются задачи типа "считалки"? Т.е. есть от 1 до N людей (по кругу) где каждый K-ый из оставшихся выбывает из строя и необходимо найти последнего оставшегося или вывести список выбывания(в зависимоти от условия).

Я бы делал это в лоб:

1) В Java загоняем  N персонажей в Vector, в языках не имеющих такой фичи придется использовать массив, но тогда процедура удаления элемента будет несколько длиннее. Длина массива на данный момент D = N
2) Присваиваем M = K
3) if(M <= D) goto 6
4) M = M - D
5) goto 3
6) Выводим информацию об удалении персонажа стоящено, на данный момент, под номером M и удаляем его из массива. Если это не Vector пишем процедуру смещения всех стоящих после него на шаг
влево и уменьшаем размер массива на единицу. Если Vector, все это делается в один шаг. Так или иначе получается D = D - 1
7) if(D = 1) goto 10
8) D = D + K - 1 (отнимать единицу здесь нужно т.к. члены массива сдвинулись и номер выбывшего уже занят кем-то еще)
9) goto 3
10) Выводим информацию о последнем оставшемся
11) Идем пить пиво

Кажется нигде не ошибся  

В лоб задачу не рашают.

Решение задачи аналитически есть у Кнута в конкретной математике.

А любители решить в лоб, могут решить задачу длЯ 10^100 человек.

N - количество детей.
T - номер оставшегося

N  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
T  1  1  3   1  3  5  7  1  3  5   7   9  11 13 15  1  3  ...  
 
Эксперементальным путем устанавливаем закономерность:
t(1)=1
t(2*n)=2*t(n)-1 при n>=1
t(2*n+1)=2*t(n)-1 при n>=1
Если n=2^n(два в степени n)+q? где 2^m - наибольшая степень 2, не превосходящая N, a q - разность N- 2^m, то номер оставшегося ребенка вычисляется по формуле: t(2^m+q)=2*q+1 при m>=0 и 0<=q<=2^m.

По крайней мере так написанов С. Окулов "Основы программирования".

Все так, решение "в лоб" для большого числа персонажей заставит комп серьезно потрудиться. 

Но ведь предложенное аналитическое решение дает только номер последнего оставшегося. FireSnake же спрашивал и про то, как получить список выбывания.

Предложите другой алгоритм пересортировки списка. Он, возможно, будет работать быстрее моего (я все-таки этой задачей не загружался, а предложил то, что лежит на поверхности), но все равно займет значительное время.

ЗЫ: А 10^100 человек не бывает Максимум чуть больше 6*10^9.    Бактерий наверное бывает, но они врядли в детские считалки играют  и моим алгоритмом уж точно пользоваться не будут

Это сообщение отредактировал(а) _Y_ - 17.12.2006, 11:44

Плавно съехали с задачи про считалку.
5859267andrey, комбинаторика...   
Теперь о считалке- периодическую функцию придумай, например на основе синуса. По ней и отсеивай людей. по оси абсцисс откладывай число, а по ординат- человека. При этом sup этой функции будет равен числу людей. К примеру функция 

вопрос по размену выделил в одну тему: http://forum.vingrad.ru/topic-127865.html

Идея с синусом кажется не верной. Может поделитесь доказательством, дабы убить сомнения?

что именно кажется не верным?
Начинаем.
Синусойда высотой "количество человек".
Берем, допустим её первые несколько периодов.Например от нуля до 20*pi.
Делим это на количество человек. Получаем шаг.
Идем с этим шагом по абсциссам и получаем ординаты. Пусть есть массив участников. Присвоим каждому целое значение на оси ординат. На каждый шаг получаем значение синусоиды. Находим промежуток целых значений, в котором лежит это значение. Вычеркиваем из массива. Так делаем пока не останется один участник.
Единственная проблемма- сосчитать шаг, чтобы два значения синусоиды за два шага не попадали в один промежуток по оси ординат. Но это, ИМХО, дело техники.

СУВ, SoWa

Пример такой задачи на С++.
Здесь.

Что б никто не спорил относительно ограничений - вот эта задача:

on-line judge

Кто получит АС поделитесь своими соображениями

FireSnake, я уже поделился, смотри ссылку выше.

Результат работы программы:

Я использовал Skip-List с соотношением 10/10000.
Список из 10 элементов, а в списке масив из из 10000 элементов (чтобы ускорить удоление). Время работы где-то O(N*log n*log n) (0.671 сек).