ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
25 сообщений из 261, страница 2 из 11
  2  все
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36042558
Фотография nu88
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nu88
Участник
Пытаюсь понять, в чём смысл сайтов.
Ты находишь там постановку проблемы, выполняешь решение и публикуешь там? Кроме проверки себя, в чём ещё может быть смысл?
...
Рейтинг: 0 / 0
16.06.2009, 06:49:19
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36042559
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
nu88Пытаюсь понять, в чём смысл сайтов.
Ты находишь там постановку проблемы, выполняешь решение и публикуешь там? Кроме проверки себя, в чём ещё может быть смысл?
и всё,
конечно
...
Рейтинг: 0 / 0
16.06.2009, 07:01:04
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36042566
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
ну еще можешь топырнуть пальцы (причем очень заслуженно),
мой аккаунт такой-то и такой-то смотрите; а свою хню детскую мне под нос не суйте.
Ваще-то на Западе (и в Индии, и в Китае) очень принято гордиться своим рейтингом
там никто этого не стесняется
Прямо так и пишут (место № 444 на топкодере)
Если будет умный работодатель (или сам из этой тусовки), так ваще проблем не будет.
Никто даже тестить тебя не будет.
Я не представляю, нах мне надо было бы тебя тестить если бы ты был в первой 100, хоть и на польском споже.
Смешно просто. Я знаю что человек который туда попал, он сделает что угодно.
Гавнюков конечно надо рубить. Они ничего не умеют. Они воображают, что компьютеры предназначены ну для них например. Или думают : вызубрим инструкции и пипц всем.
Они даже не знают что компьютеры предназначены для решения конкретных задач и не более.
...
Рейтинг: 0 / 0
16.06.2009, 07:37:13
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36042634
Фотография nu88
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nu88
Участник
Очень интересно, не знал. Математика всю жизнь интересовала, но к этим кругам не пренадлежал никогда ) Алгоритмы придумываю на базе высшего радиотехнического образования, никакой прикладной математики, а эти люди ведь наверное все с физ.мат.-лицеев и универов, монстры, жжесть )
Ладно, пойду александреску читать )
...
Рейтинг: 0 / 0
16.06.2009, 08:51:29
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36043083
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
RT183Индуссы кстати очень даже молодцы; они умеют работать, а не куи валять.
Они умные пацаны и у них есть очень важная черта: они не боятся ошибаться
и признавать свои ошибки .
Немного офф. Индусский код

К индусам ничего плохого не имею. Так. Ради лулз.
...
Рейтинг: 0 / 0
16.06.2009, 11:56:27
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36043214
Дмитрий16
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дмитрий16
Участник
На ум приходит только классический волновой алгоритм, расширенный до 3D.
Реализация - два стека. в первый помещаем каплю воды на уровень до которого нужно оттрассировать. Далее капля падает вниз и в стороны (т.е. во воторой стек) далее меняем стеки местами. Итого если нарисовать - то мы просто наливаем воду из определенной точки а вода далее растекается. (Кстати, красиво выглядит + трассировщики печтаных плдат в основном работают именно так.)
...
Рейтинг: 0 / 0
16.06.2009, 12:32:11
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36043561
уральский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
уральский
Гость
RT183напрмиер http://www.spoj.pl/problems/WATER/
блинский ком, с третьего раза приняла и то с большим временем исполнения (6.62) %(
банальный depth first search, без каких бы то ни было оптимизаций.
...
Рейтинг: 0 / 0
16.06.2009, 14:05:49
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36043859
Intser
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Intser
Участник
Дмитрий16На ум приходит только классический волновой алгоритм, расширенный до 3D.
Реализация - два стека. в первый помещаем каплю воды на уровень до которого нужно оттрассировать. Далее капля падает вниз и в стороны (т.е. во воторой стек) далее меняем стеки местами. Итого если нарисовать - то мы просто наливаем воду из определенной точки а вода далее растекается. (Кстати, красиво выглядит + трассировщики печтаных плдат в основном работают именно так.)

Наверное даже проще - берем один уровень, помечаем все ячейки с высотой больше как стенки, ячейки с высотой меньше - как свободное пространство. Дальше применяем волновой алгоритм для пустых ячеек - или еще что для поиска границ(учитываем дырки). Задача вырождается в задачу поиска замкнутых контуров на плоскости, количество повторений равно глубине. Продолжаем пока находится хотябы один замкнутый контур. Можно конечно оптимизировать - выкидывать заведомо дырявые контуры и т.д. Удобство в том, что можно начинать поиск как с верху, так и с низу :)
...
Рейтинг: 0 / 0
16.06.2009, 15:32:21
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044046
уральский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
уральский
Гость
IntserНаверное даже проще - берем один уровень, помечаем все ячейки с высотой больше как стенки, ячейки с высотой меньше - как свободное пространство. Дальше применяем волновой алгоритм для пустых ячеек - или еще что для поиска границ(учитываем дырки). Задача вырождается в задачу поиска замкнутых контуров на плоскости, количество повторений равно глубине. Продолжаем пока находится хотябы один замкнутый контур. Можно конечно оптимизировать - выкидывать заведомо дырявые контуры и т.д. Удобство в том, что можно начинать поиск как с верху, так и с низу :)
Это скорее к spoj-евскому варианту применимо, если я парвильно понял (выделение замкнутых контуров на максимальной высоте); а вот ТСовские дырки таким способом не учесть (точнее можно учесть, конечно, но только проделав доп работу, которая делает лишним выделение контуров), я вот про них все думал и в итоге мой вариант сливные дырки допускает, наверное потому и получилась прога на грани TLE...
...
Рейтинг: 0 / 0
16.06.2009, 16:28:58
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044312
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
maytonRT183Индуссы кстати очень даже молодцы; они умеют работать, а не куи валять.
Они умные пацаны и у них есть очень важная черта: они не боятся ошибаться
и признавать свои ошибки .
Немного офф. Индусский код

К индусам ничего плохого не имею. Так. Ради лулз.
Это потому что индусы относятся к программированию как к искусству :)
как к литературному творчеству, а Восток всегда славился своей витиеватостью.
У них тайное желание писать на санскрите;
...
Рейтинг: 0 / 0
16.06.2009, 17:28:35
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044318
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
уральскийRT183напрмиер http://www.spoj.pl/problems/WATER/
блинский ком, с третьего раза приняла и то с большим временем исполнения (6.62) %(
банальный depth first search, без каких бы то ни было оптимизаций.
а у меня 2.20с http://www.spoj.pl/status/WATER,zzz/
Но страшно сказать, это было 28-го мая 2005 года.
6.62 вообще-то многовато. Надо менять подход.
...
Рейтинг: 0 / 0
16.06.2009, 17:29:14
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044325
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
уральскийRT183напрмиер http://www.spoj.pl/problems/WATER/
блинский ком, с третьего раза приняла и то с большим временем исполнения (6.62) %(
банальный depth first search, без каких бы то ни было оптимизаций.
а у меня 2.20с http://www.spoj.pl/status/WATER,zzz/
Но страшно сказать, это было 28-го мая 2005 года.
6.62 вообще-то многовато. Надо менять подход.
...
Рейтинг: 0 / 0
16.06.2009, 17:30:40
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044407
уральский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
уральский
Гость
RT183Надо менять подход.
Ога, как я написал выше, это из-за учитывания сливных дырок, которых в SPOJ-задаче быть не может.
...
Рейтинг: 0 / 0
16.06.2009, 17:59:02
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044562
Фотография nu88
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nu88
Участник
Тот алгоритм, который в один проход всё делает, о котором я тут зарекался, он и с дырками обходится клёво. Надо будет реализовать и выложить. Блин, какие вы сайты клёвые знаете.
...
Рейтинг: 0 / 0
16.06.2009, 19:30:45
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044612
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
nu88Тот алгоритм, который в один проход всё делает, о котором я тут зарекался, он и с дырками обходится клёво. Надо будет реализовать и выложить. Блин, какие вы сайты клёвые знаете.
выложи обязательно
В смысле, запули туда
И точную ссылку на свои сабмиты
Я по временам скажу как ты решал :)
...
Рейтинг: 0 / 0
16.06.2009, 20:11:08
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044646
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
уральскийRT183напрмиер http://www.spoj.pl/problems/WATER/
блинский ком, с третьего раза приняла и то с большим временем исполнения (6.62) %(
банальный depth first search, без каких бы то ни было оптимизаций.
я глянул и увидел ты пробовал двух профессоров (я их упоминал тут) :)
Хорошая задача. Я ее потом щелкнул как орешку.
Просто опять надо ясно видеть чего и как и почему.
http://www.spoj.pl/ranks/TWOPROF/
Но нельзя сказать что простая.
...
Рейтинг: 0 / 0
16.06.2009, 20:54:23
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044653
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
Is it a tree
Тоже ничего, но она простая
...
Рейтинг: 0 / 0
16.06.2009, 20:58:52
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044656
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
а два профессора, тут уже .... гм
тут надо очень ясно мыслить (я бы сказал)
8 решивших юзеров -- это очень очень мало
...
Рейтинг: 0 / 0
16.06.2009, 21:00:31
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36044662
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
кстати первый по времени http://www.spoj.pl/ranks/TWOPROF/
Иван Катаник -- хорватская гордость. Монстрюк. Ни хухры мухры.
...
Рейтинг: 0 / 0
16.06.2009, 21:05:14
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36060766
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
alex82,
а как ты читаешь? сканфом? попробуй так, время в 2 раза точно сократится (огромный входной файл)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
int read_ui() {
    int n =  0 ;
    char c;
    while (!isdigit(c = getchar()));
    while (isdigit(c)) {
        n = n *  10  + (c - '0');
        c = getchar();
    }
    return n;
}
...
Рейтинг: 0 / 0
25.06.2009, 23:21:46
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36061868
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman S. Golubin
Участник
Пытаюсь решить http://www.spoj.pl/problems/ANALYS_T/ . Точнее, для себя я ее уже решил, но то ли что-то не учел, то ли... а там могут быть задачи, у которых ответ неправильный? :)

Исходник на c#, если интересно, могу выложить. Все варианты, которые сам нагенерировал, работают. На spoj.pl еще проблема с тем, что C# там не совсем C#, а какое-то корыто времен царя гороха.
...
Рейтинг: 0 / 0
26.06.2009, 15:24:46
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36062079
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
неправильный ответ? да считай что таких нет
зы
я эту задачу первый раз вижу поэтому ничего сказать не могу
...
Рейтинг: 0 / 0
26.06.2009, 16:30:08
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36062135
RT183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183
Участник
добавлена Blue Mary
э глухо.... ошибка у тебя, 100%
...
Рейтинг: 0 / 0
26.06.2009, 16:51:35
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36062158
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman S. Golubin
Участник
RT183,

логика, имхо, простая - если выполняется команда goto, то выйти из замкнутого круга можно только, если хотя бы одна из команд if остается активной (то есть, за текущую итерацию остается вероятность, что условие когда-нибудь выполнится). Уже гору вариантов различных рассмотрел - по этой логике все они отрабатываются полностью. Даже пробовал выводит в ответ значения из блоков print и текст "Hint: путь" - ни один из них не принимается :) Несколько часов дергал сервер, результата ноль... может взглянешь незамыленым взглядом на задачу?
...
Рейтинг: 0 / 0
26.06.2009, 16:58:06
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36062192
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman S. Golubin
Участник
Roman S. Golubin,

обнаружил такой фрагмент в тексте, который я не учитывал:

Код: plaintext
Program terminates by itself when <end> is executed.

Код: plaintext
If the program can not terminate by itself,output -1.

А я считал, что "not terminate by itself" - программа просто ушла в цикл. А она еще и завершиться же может не блоком END Сейчас попробую еще раз.
...
Рейтинг: 0 / 0
26.06.2009, 17:19:38
| Ответить | Цитировать | Написать  
25 сообщений из 261, страница 2 из 11
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36044562&tid=1344339]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 190ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 43ms
get tp. blocked users:
 1ms
others: 207ms
total:  470ms
созд. / загр.: 470ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]