Обсуждение некоторых задач, + сравнение уровня сложности(Россия И Украина) Опции

[Vinchkovsky]

В общем,смещением массива все проходит, но только к верхней границе. Тоесть, для большых чисел моя прога не подходит . Malice, тебя не очень понял, можешь подробно обяснить?
А сама задача, в общем, вполне решаема, только проблема с большыми числами .
И еще - дайте кто-то линк на FAQ про списки и дин.массивы (описание процедур), а то на факе форума нет, а в и-нете не нашел - почти все под Дельфи .
p.s. А название топика не совсем соотвествовало его теме

[Malice]

Malice, тебя не очень понял, можешь подробно обяснить?

На массивах ? Запросто.. Смотри: одно число типа byte може хранить информацию вычеркнут/нет о 8-ми числах.
Берем пример, n=7. (в одном байте чтоб) В начале массив=0
12345678 (8-не используется, по-этому ставим *)
0000000* левый младший
0101010* 1-ый проход
1101110*- 2-ой
1111110*- 3-й
Осталась 7-ка.
n=12, используется 2 байта
12345678 12345678
01010101 0101****
01110111 0111****
01111111 0111****
11111111 0111****
Осталась 9-ка
Повторюсь- т.к. все четные сразу вычеркиваются то 1 бит можно не хранить и массив сократится еще в 2 раза, что позволит организовать такой массив в TP и мы будем знать 1-ый бит результата.
Ps. Путем дальнейших логических умозаключений можно точно вычислить и следующий бит результата, что приведет к сокращению массива еще на половину и так до полного исчезновения массива как такового..

[Michael_Rybak]

Решение усложняется максимальным значением n=1 000 000. На на массивах тоже можно при желании. Допустим для того, чтобы знать вычеркнут/не вычеркнут достаточно 1-го бита, т.е. размер сокращается до 1000000/8 =125000. Пока еще не хватает. Но, учитывая, что при первом проходе быдут вычеркнуты все четные элементы, мы точно знаем, что младший бит=1 и его хранить не надо. Тогда размер массива сокращается до 125000/2 = 62500. Такой массив запросто организуется в tp.

Всеукраинки (и вроде бы областные) уже достаточно давно тестируются на fp. Так что не думаю, что эта проблема стоит.

Но!

Нам это на самом деле не нужно. Можно просто помнить, какие числа сейчас есть, и с какого числа (первого или второго) начинаем вычеркивать.

Пример:

1 2 3 4 5 6 7 8 9 10 11 - есть числа вида K+1, где 0 <= K <= 10, вычеркиваем, начиная со 2го
1 2 3 4 5 6 7 8 9 10 11 - четность меняется, теперь начнем вычеркивать с первого

1 3 5 7 9 11 - есть числа вида 2K+1, где 0 <= K <= 5, вычеркиваем, начиная с 1го
1 3 5 7 9 11 - опять начнем вычеркивать с 1го

3 7 - есть числа вида 4K+3, где 0 <= K <= 1, вычеркиваем, начиная с 1го:
3 7

7 - есть числа вида 8К+7, где 0 <= K <= 0, вычеркиваем, начиная с 1го.


После каждого прохода будут оставаться числа вида (2^p)K + t, где 1 <= t <= 2^p (чтобы выполнялось 0<=t<2^p, надо вести нумерацию с 0), а К лежит в пределах от 0 до некоторого q. Поэтому их можно хранить не массивом, а тройкой (p, t, q).

[Гость]

Вот как сделал я:

var i,first, last,pred,y,n:longint;
begin
readln(n); y:=0;
first:=0; last:=n; pred:=n;
repeat
for i:=1 to n do
if (i and y) xor first=0 then
begin write (i,' '); last:=i; end;
writeln;
first:=first+(y+1)*byte(last=pred);
pred:=last;
y:=y shl 1+1;
until (first=last) or (first>n);
writeln (last);
end.

Как мне кажется, очень логично получилось

[Malice]

Вот как сделал я:

Это я был, зайти забыл, но по стилю, имхо, и так понятно

[мисс_граффити]

И еще - дайте кто-то линк на FAQ про списки и дин.массивы (описание процедур), а то на факе форума нет, а в и-нете не нашел - почти все под Дельфи

Все о динамических структурах данных.

[Michael_Rybak]

Как мне кажется, очень логично получилось

Логично, только у тебя сложность O(N log N), а можно O(log N). Зачем цикл for внутри?

[Malice]

Логично, только у тебя сложность O(N log N), а можно O(log N). Зачем цикл for внутри?

Для вывода оставшихся чисел после каждого прохода. Использовалось при отладке

[Michael_Rybak]

Ну и last надо считать ручками. Но это уже мелочи

[Malice]

Ну и last надо считать ручками. Но это уже мелочи

Да, да. Я считал сперва, но если есть вывод всей последовательности, грех это не заиспользовать.