IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V < 1 2  
 Ответить  Открыть новую тему 
> Обсуждение некоторых задач, + сравнение уровня сложности(Россия И Украина)
сообщение
Сообщение #21


Пионер
**

Группа: Пользователи
Сообщений: 98
Пол: Мужской
Реальное имя: Andriy

Репутация: -  0  +


В общем,смещением массива все проходит, но только к верхней границе. Тоесть, для большых чисел моя прога не подходит no1.gif . Malice, тебя не очень понял, можешь подробно обяснить? wink.gif
А сама задача, в общем, вполне решаема, только проблема с большыми числами norespect.gif .
И еще - дайте кто-то линк на FAQ про списки и дин.массивы (описание процедур), а то на факе форума нет, а в и-нете не нашел - почти все под Дельфи nea.gif .
p.s. А название топика не совсем соотвествовало его теме wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #22


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Vinchkovsky @ 12.01.2007 10:43) *

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

На массивах ? Запросто.. Смотри: одно число типа 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. Путем дальнейших логических умозаключений можно точно вычислить и следующий бит результата, что приведет к сокращению массива еще на половину и так до полного исчезновения массива как такового.. wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #23


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Malice @ 12.01.2007 9:01) *

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


Всеукраинки (и вроде бы областные) уже достаточно давно тестируются на 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).

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #24


Гость






Вот как сделал я:
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.

Как мне кажется, очень логично получилось smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #25


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Гость @ 12.01.2007 15:00) *

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

Это я был, зайти забыл, но по стилю, имхо, и так понятно smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #26


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #27


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Гость @ 12.01.2007 14:00) *

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


Логично, только у тебя сложность O(N log N), а можно O(log N). Зачем цикл for внутри?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #28


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 12.01.2007 15:49) *

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

Для вывода оставшихся чисел после каждого прохода. Использовалось при отладке smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #29


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ну и last надо считать ручками. Но это уже мелочи smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #30


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 12.01.2007 16:09) *

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

Да, да. Я считал сперва, но если есть вывод всей последовательности, грех это не заиспользовать. wink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V < 1 2
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 14:59
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name