Архив форума

ну ладно, надо же форум обновить:)))
так вот, подскажите пожалуйста, как в задаче "Шестеренки" с последнего контеста школьников (условие здесь http://acm.timus.ru/problem.aspx?space=1&num=1291 ) хранить граф? в смысле 1000 вершин, и для каждой список смежных. имеем массив 10^6 integer'ов.. на тимусе пройдет а в turbo pascal - нет. или я чего-то не понимаю?

Для начала ты наглючил в ссылке :)
А с задачкой вроде как всё просто - сказано, что циклов нет, поэтому рёбер не больше, чем n-1. Формат инпута проблем не добавляет - в процессе чтения подсчитываешь количество и выделяешь нужный кусок памяти динамически.

в ссылке не наглючил просто скобка к ней цеплялась:))
так вот в том и вопрос: максимальное число ребер = n-1 от каждой вершины или вообще в графе? а вот с динамической памятью как-то сложно... в смысле чего бы не поставить ограничения для 64К? а так спасибо за ответ:)

Максимальное число рёбер в графе без циклов = n-1. При этом никто не мешает всем рёбрам идти из одной вершины, то есть максимальное число рёбер, идущих из одной вершины, тоже n-1.
Попробуй нарисовать граф из 10 вершин и 10 рёбер, но без циклов :)
Общее утверждение для ациклических графов выглядит так: кол-во вершин = кол-во рёбер - кол-во компонент связности. Довольно просто доказывается, можешь попробовать сам или прочитать в классике.

А чего такого сложного с динамической памятью?

да нет проблем, просто...:)))
спасибо, Олег, все понял.:)))

Лично я, когда вбивал альтернативный солюшен для этой задачи для BC 3.1, быстренько вбил реализацию динамического связанного списка. Под VC 6.0, я бы не мудрствуя лукаво заюзал бы vector<int>

кому как не вам уважаемый Ден, понимать что VC6 это не для школьного контеста:)) к тому же я пишу на pascal'e--> delphi:) а чем реализация динамического связанного списка на С отличается от того что предложил Олег?

Что-то я не понимаю, что я не так сказал ;) Я сказал, как сделать. И сказал, как бы сделал, если бы компиляторы были другими. В чем были ущемлены школьники? :D Если бы я писал на Delphi, я бы тоже воспользовался динамическими массивами (SetLength и прочее). На BP 7.0 и BC 3.1 проще на контесте написать связный список ручками.
А про отличие того, что предложил я и Олег... Ну, Олег, IMHO, ничего конкретного не предложил ;)
И вообще, чего я оправдываюсь? :D

Ден, понятно, что vector<int> проще и удобнее, кто б спорил :)
Я правильно понял, что школьникам на контестах до сих пор доступны только BC3.1 & BP7.0?
Ну а насчёт конкретной задачи... можно считывать числа из строки в буфер, а потом выделять массив нужной длины.
Это тебе проще вбить список, а есть люди (ты знал, ты знал!) у которых даже необходимость написать new int[] вызывает дискомфорт.

Все косячно ;) Кто бы сомневался ;) Сейчас нет у нас софта, который бы позволял играть на 16битных компиляторах и на 32битный одновременно. Для соревнования школьников выбор был сделан, по понятным причинам, в пользу 16битных.Пусть выпьют грамм 100 коньяка перед контестом :D Это снимет чувство дискомфорта. Шютка :wink:

Олег, Ден, Павел!
написал. TL test 10
полностью переписал алгоритм - bfs O(e) как может не укладываться? может где-то считывает некорректно?..

Ясновидцев нет :wink:
Вышли исходник на FaNGBOX(at)mail.ru, подскажу

PS Таймлимиты на Timus'е ставил по решениям жюри Саша Гальперин. Ставил (если неправ, поправьте) методом умножения на 3 максимума из времен работ авторских солюшенах на тестах.

Ден
не хочется загружать невинных людей неблагодарной работой по чтению чужих исходников:)) зашлю если не будет других вариантов. решить-то хоцца:))
единственное, что мне приходит в голову, следующее.
начитавшись Ахо-Ульмана-Хопкрофта "Алгоритмы и структуры данных" я реализовывал bfs как очередь для шестерней с еще не посчитанными скоростями. но очередь я, не пойдя за авторами, реализовывал списком, т.е. оператор DEQUEUE который удаляет первый элемент из очереди, имеет время O(N). не знаю, насколько это и есть лимитирующий фактор, но все же. итак, вопрос: как же реализовывать очередь с помощью указателей? в книге непонятно:))
P.S. первый вариант решени я, не мудрствоваший лукаво, просто реализовывал волну, и результат - тот же:))

Да ну ;) Мне даже интересно ;)Странно.

Есть 2 часто встречающихся способа реализации очереди.
Первый: динамический.

Элемент очереди:

struct TQueueItem

{

      int Value; //собственно то, что мы в очереди хотим хранить

      TQueueItem* next; //ссылка на следующий элемент очереди

};

Очередь, в таком случае задается указателем на свое начало и конец

TQueueItem* top;

TQueueItem* bottom;

Приятную задачу по реализации

int OutQueue(TQueueItem** top, TQueueItem** bottom);

void InQueue(int Value, TQueueItem** top, TQueueItem** bottom);

оставим читателю ;)

Второй: статический. Применим, если есть четкие ограничения на максимальное число элементов в очереди.

Данные очереди хранятся в массиве ;)

int Queue[MAXLENGTH];

int top, bottom;

top, bottom - индексы элементов массива, являющихся началом и концом.PS Я вообще, когда вбивал солюшен, обошелся без очереди. Рекурсии мне хватило.

в Си я разбираюсь на уровне PHP(т.е. синтаксиса:)))) но то что я понял - первый способ - с указателями, второй с курсорами.
с указателями я не смог сделать, т.к. pascal почему-то не дал создать рекурсивный тип. ну,

type celltype=record

                             element:integer;

                             next:^celltype;

                     end;

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

Если память не изменяет ;)

TYPE

    PCellType = ^TCellType;

    TCellType = record

        element : integer;

        next    : PCellType;

    end;

Попробуй такой банальный тест:
1000 сцепленных по порядку шестерней. То есть 1ая со 2-ой, 2-ая с 3-ей и тд 1000 штук в одну линию. Тогда алгоритму придется сделать 1000 операций "выталкнуть из очереди", каждая из которых будет работать O(N). Итого сложность алгоритма на подобных тестах O(N^2).. Это много :)Я всегда думал, что волна, поиск в ширину и поиск с очередью - это синонимы :)

Вообще, понятно же, что можно искать рекурсивно (то есть поиском в глубину (с неявным стеком)), так как глубина рекурсии будет не больше 1000. Так что тут вообще без всяких очередей можно (и нужно) обойтись :)

черрррт сегодня длинными скучными уроками я понял, что дроби сокращал алгоритмом за O(N), где N - min из числителя и знаменателя:))) идиот! просто первый вариант писал ближе к ночи усталый:))) написал евклида щас попробую сдать:))))

Problem B Accepted:)))))))
спасибо всем кто помогал:))
ПАВЕЛ
под "просто волной" я имел в виду то, что ну... я не знаю, там нет никакой очереди, там есть фроны волны, массив меток, на каком фронте какая вершина находится и т.д.
естественно, волна и bfs это по сути одно и тоже.:)))
... а так-то прикольная задача:))
P.S. остались Конь и Псилонцы

Кстати, расскажу, как я решал задачу про коня. Это интересно, я думаю. Когда я следил за школьниками в 514 ауд. и прочитал задачу, я подумал: что за детская забава? Пусть человек, которому делать нечего, сидит и перебирает. Поскольку мне самому делать было нечего, я сел и за 15 минут нарисовал примеры, где обойти можно, и доказал, где нельзя. Ден Расковалов мне сказал, что, конечно, никто не перебирал, а бэктрекинг написали. У Прохорова валилось на 9 тесте - 7 на 7, а я себя считал крутым... пока не пришел домой. Там решил сдать задачу на Тимусе, и набивая, нашел ошибку в обходе 7 на 7. После этого я неделю обходил доску 7 на 7 (даже на парах) - исписал 5 листов бумаги, но так и не обошел. Меня запарило - я сел и написал бэктрекинг. Ну, сдал, конечно.

У меня с конем тож весело получилось :lol:
Я после контеста заявил, что у меня есть квадратный алгоритм, и Денис пообещал мне бутылку пива (!!!) за решение задачи на доске 500*500. Я радостный, в предвкушении халявы, прихожу домой, включаю ... а она, гадина, не работает!
Причем я пробовал на досках многих размеров: получил ответ для досок 499*499 и 501*501, а 500*500 - ну никак! :(
Но я пока не сдался!

Мы исписали один лист.
Повалилось, потому что Андрей говорил "d2", а я набил "b2". Когда мы это обнаружили, было уже поздно...
Так что перебором всё решается...