Задача
Хочу обсудить одну задачу с киевской олимпиады KPI_OPEN
возможно кто то там был и все видел:) Мы эту задачу решили, но хотелось бы увидеть ваше решение Итак задача Я ее предисторию как там не буду рассказывать, а сразу к делу. вводится размер матрицы N, и сама матрица из нулей и единиц строки обозначают людей, и столбцы их профессии единица в i строке и j столбце обозначает что i человек может иметь j профессию. 0 - соответственно не может. Надо определить однозначно ли определяется сочетание людей и профессий. Если да вывести 1, если нет или вообще не определяется вывести 0. Сложность еще в том что N может достигать 2000, а время выполнения программы 1 сек. |
Ответ: Задача
Если не ошибаюсь, такая задача разбиралась у меня в универе в рамках дискретной математики.
Только что-то решения не припоминаю. |
Ответ: Задача
У нас в универе не разбираются такие задачи)
а вообще она со студенческой олимпиады алгоритм сам не сложный (это задач в том туре одна из простых) главное оптимизировать чтобы на большом N прошла тест по времени |
Ответ: Задача
А вообще это задача определения единственности полного парасочетания в двудольном графе)
Если кто хочет могу кинуть еще, они по сложнее |
Ответ: Задача
7 минут подождал решения, не выдержал и написал.
Наверное олимпиаду сдал за 15 минут? |
Ответ: Задача
Я же сказал что это самая легкая
я тебе сейчас дам самую сложную не будешь ты так говорить и еще насчет решения ты покажи его я сказал он для 2000 тысяч должен считать не более секунды вот одна из сложных http://kpi-open.org/static/uploads/t.../village_r.pdf |
Ответ: Задача
Цитата:
|
Ответ: Задача
Можно ли при таких ограничениях (для каждого человека сказано кем он может быть а кем нет) однозначно определить профессию каждого
|
Ответ: Задача
Цитата:
Сейчас посмотрю ваши сложные задачи PS нет, не смогу: Хотя присмотрелся - только некоторых букв не хватает :) попробую расшифровать |
Ответ: Задача
Мистер Розовый, а зачем в этом коде тридэ, задний буффер и рандом?
|
Ответ: Задача
Вложений: 1
Цитата:
|
Ответ: Задача
типичная комбинаторика, к программированию на мой взгляд имеет опосредованное отношение.
|
Ответ: Задача
Ну насчет алгоритмики да, это не олимпиада по технологиям
но даже в асм такие задачи и насчет перебора , такое при больших не посчитается за 1 секунду у тебя рекурсия (пусть и с нормальной динамикой) в которой двойной цикл (в котором ксати в вызывается рекурсия) там было 2-3 команды которые сделали рекурсивно (возможно как и у тебя я не вникал в твой алгоритм) которые укладывались еле еле (0.8-0.9 секунды) и при этом они долго долбились над оптимизированием)) сам автор этого не предполагал, он обьяснил что "блин а компьютеры стали слишком быстрые)" и по идее при небольшом увеличении количества деревень тот переборный алгоритм не работает а у автора был комбинаторный алгоритм который написала всего одна команда из венгрии to Павел: сразу в массиве проффесии не распределены, т.е может быть так: 1 0 0 1 1 0 1 1 1 но по этому массиву мы все равно однозначно определяем работы а значит нужно не 2000*2000, а 2000^3 так как мы для каждой строки должны ее вычесть из каждой другой строки (а выбераем каждый раз строку с одной единицей) |
Часовой пояс GMT +4, время: 04:42. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot