ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
25 сообщений из 261, страница 6 из 11
  6  все
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094122
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
VadimPanovRT183.1,

Извини, ничего не понял из твоего поста. Можешь сказать другими словами?
ну другими словами:
сишарп на тех задачах катастрофически не укладывается в тайм-лимит
не на всех конечно, но в большинстве случаев
...
Рейтинг: 0 / 0
16.07.2009, 17:37:56
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094151
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нормально. Задачка-то АЛГОРИТМИЧЕСКАЯ. Значит перевес будет не у Ассемблерщика а у математика. Грамотно написанная прога заполенния озёр водой будь-то C# или Java может порвать С++. Вы только дайте ей хорошие объёмы. Не 10х10 клеточек, 64000х64000. И рельеф надо сделать посложнее. С хорошим лабиринтом.

P.S. Если-б не моя щас загруженность работой тоже посидел-бы парочку вечеров. Пооптимизировал.

Всего!
...
Рейтинг: 0 / 0
16.07.2009, 17:48:30
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094168
Фотография С0ВЕСТЬ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
С0ВЕСТЬ
Участник
maytonНормально. Задачка-то АЛГОРИТМИЧЕСКАЯ. Значит перевес будет не у Ассемблерщика а у математика. Грамотно написанная прога заполенния озёр водой будь-то C# или Java может порвать С++. Вы только дайте ей хорошие объёмы. Не 10х10 клеточек, 64000х64000. И рельеф надо сделать посложнее. С хорошим лабиринтом.

P.S. Если-б не моя щас загруженность работой тоже посидел-бы парочку вечеров. Пооптимизировал.

Всего!
+1
тоже самое что оптимизировать и селекты :)
...
Рейтинг: 0 / 0
16.07.2009, 17:58:54
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094266
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
SPOJ ваще очень френдли контестер в этом смысле.
Там и сишарп потянет.
А вот саратовский... они уже годы как уперлись рогом,
настолько суровые тайм-лимиты.
Я даже как-то написать хотел им: типа, завязывайте.
Потом забил.
Но все-таки они зря это. Там трудно чему-то научиться.
...
Рейтинг: 0 / 0
16.07.2009, 18:43:36
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094667
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
rmull
VadimPanov
И как они учитывают разную скорость для разных языков? Одно дело С++, другое - тот же C#...

Никак. 7 секунд - общий time limit для всех языков. Но в случае с C# это не должно быть проблемой, потому что он практически не уступает по скорости C++.
А я, вот, попробовал запостить их решение задачи TEST, который они приводят здесь , и для C# в их варианте получил время аж 0.17, и был где-то в середине списка из нескольких сотен решений. В то время как лучшие показали время 0.00... Даже слегка оптимизированное решение для шарпа дало 0.16, т.е. разница по скорости - огромная, и C# там отнюдь не в лидерах... Так - нечестно :-( ...
...
Рейтинг: 0 / 0
17.07.2009, 07:52:17
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094672
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
mayton,

Что скажешь насчёт задачи TEST, см. мой пост выше?
Асен пень, что на асме можно наворотить так, что и за год не посчитает. Но при прочих равных условиях C# там проигрывает. Надо мерить не время, а операции, а вот как это сделать - вопрос...
...
Рейтинг: 0 / 0
17.07.2009, 07:55:20
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094674
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
rmull
Какая у вашего решения сложность? У меня решение со сложностью O(n*m*log(n*m)) на C++ выполняется за 0.11 секунд.

А как ты вывел эту формулу? Я бы тоже посчитал для своего алгоритма...
Они бы хоть отображали, какое время в итоге, а то больше 7 и всё, а вдруг там 7.01 ? :-)
или 100.01 ...
...
Рейтинг: 0 / 0
17.07.2009, 07:57:31
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094675
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
RT183.1VadimPanovRT183.1,

Извини, ничего не понял из твоего поста. Можешь сказать другими словами?
ну другими словами:
сишарп на тех задачах катастрофически не укладывается в тайм-лимит
не на всех конечно, но в большинстве случаев
Во, щас всё понял! Чудеса!!! :-)
...
Рейтинг: 0 / 0
17.07.2009, 07:58:08
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094750
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
VadimPanovC# в их варианте получил время аж 0.17, и был где-то в середине списка из нескольких сотен решений. В то время как лучшие показали время 0.00... Даже слегка оптимизированное решение для шарпа дало 0.16, т.е. разница по скорости - огромная, и C# там отнюдь не в лидерах... Так - нечестно :-( ...
Извини, Вадим но я не понимаю ЧТО мы измеряем? При таких коротких таймингах мы просто замеряли бут-страп Runtime-среды и сопряжение с библиотеками ввода-вывода (STDIN, STDOUT).

Или я ошибаюсь в понимании контекста твоего вопроса.
...
Рейтинг: 0 / 0
17.07.2009, 09:16:10
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094768
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
VadimPanovrmull
Какая у вашего решения сложность? У меня решение со сложностью O(n*m*log(n*m)) на C++ выполняется за 0.11 секунд.

А как ты вывел эту формулу? Я бы тоже посчитал для своего алгоритма...
Они бы хоть отображали, какое время в итоге, а то больше 7 и всё, а вдруг там 7.01 ? :-)
или 100.01 ...
у них правило: снимать задачу после 2 тайм лимитов
Т.е. если дано 7 сек то 14 секунд ее рубят
Правда как это может помочь не знаю :0
...
Рейтинг: 0 / 0
17.07.2009, 09:26:21
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36094818
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
mayton, меня не пускают на ПТ, но сказать про Достоевского хочется.
Больной на голову человек, он любил только себя, он хихикал убивая старушку.
Толстой его именно так и оценивал: психически не здоровый.
Вся его русская речь это намеренное искажение.
Я ни одного его романа не осилил (впрочем, как и Толстого)
Вот Чехов, это да..... Никто так не мог и не сможет писать.
...
Рейтинг: 0 / 0
17.07.2009, 09:50:01
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095127
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
mayton
Извини, Вадим но я не понимаю ЧТО мы измеряем? При таких коротких таймингах мы просто замеряли бут-страп Runtime-среды и сопряжение с библиотеками ввода-вывода (STDIN, STDOUT).

Или я ошибаюсь в понимании контекста твоего вопроса.
Я тоже не понимаю, что они там меряют.
У меня программа отрабатывает задание с 10-ю одинаковыми матрицами размера 170 х 102 за 0.25 сек.

Поскольку используется рекурсия, то бОльшего размера матрицы вызывают переполнение стека, а у них - не вызывают, значит, они юзают небольшие матрицы, но - много. Я так думаю.
И сколько там заданий, чтобы загрузить алгоритм на 7 сек?

Больше 280 штук у меня получается... Или как?
...
Рейтинг: 0 / 0
17.07.2009, 11:25:34
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095186
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не о том. Я про этот исходник.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
using System;
using System.IO;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamWriter outbuff = new StreamWriter(Console.OpenStandardOutput());
            byte[] buf = new byte[ 300 ];
            int read = Console.OpenStandardInput().Read(buf,  0 ,  300 ),idx= 0 ;
            char t;
            while (true)
            {
                t = (char)buf[idx];
                if (t == '4' && buf[idx +  1 ] == '2') break;
                outbuff.Write(t);
                idx++;
            }
            outbuff.Flush();
        }
    }
}
...
Рейтинг: 0 / 0
17.07.2009, 11:42:55
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095224
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
VadimPanovmayton
Извини, Вадим но я не понимаю ЧТО мы измеряем? При таких коротких таймингах мы просто замеряли бут-страп Runtime-среды и сопряжение с библиотеками ввода-вывода (STDIN, STDOUT).

Или я ошибаюсь в понимании контекста твоего вопроса.
Я тоже не понимаю, что они там меряют.
У меня программа отрабатывает задание с 10-ю одинаковыми матрицами размера 170 х 102 за 0.25 сек.

Поскольку используется рекурсия, то бОльшего размера матрицы вызывают переполнение стека, а у них - не вызывают, значит, они юзают небольшие матрицы, но - много. Я так думаю.
И сколько там заданий, чтобы загрузить алгоритм на 7 сек?

Больше 280 штук у меня получается... Или как?
у тя просто очень мало опыта
Будет опыт и все вопросы сами отпадут
...
Рейтинг: 0 / 0
17.07.2009, 11:56:53
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095731
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
maytonЯ не о том. Я про этот исходник.

Что-то я запутался. Ты сам-то про что говоришь? :-)
...
Рейтинг: 0 / 0
17.07.2009, 14:27:25
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095748
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
RT183.1
у тя просто очень мало опыта
Будет опыт и все вопросы сами отпадут
Как набрать опыт, если не понятно, как оно устроено? У меня-то на компе всё быстро работает, а там - нет...
Кстати, вот в этой задаче, нужно считать количество квадратов ОДИНАКОВОГО размера или одновременно квадраты могут быть РАЗНОГО размера?
Они привели данные в примере для 1, 2 и 8, было бы ещё для 3 - понятнее стало бы.
Да и если такая разница по скорости в языках, то какой интерес?
...
Рейтинг: 0 / 0
17.07.2009, 14:31:35
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095776
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
Кстати, вот насчёт времени , как они считают. Ясен пень, будет зависеть от языка.

PS: у меня такое ощущение, что я сам с собой тут разговариваю... Ау, есть тут кто?...
...
Рейтинг: 0 / 0
17.07.2009, 14:41:31
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095834
qaqaqa88
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
qaqaqa88
Гость
авторКстати, вот в этой задаче, нужно считать количество квадратов ОДИНАКОВОГО размера или одновременно квадраты могут быть РАЗНОГО размера?
Ну пример же там есть, длинна разная может быть, но я так понял, что квадраты могут иметь как-бы общие клетки тоже.
...
Рейтинг: 0 / 0
17.07.2009, 15:01:22
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36095895
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VadimPanov
Участник
qaqaqa88авторКстати, вот в этой задаче, нужно считать количество квадратов ОДИНАКОВОГО размера или одновременно квадраты могут быть РАЗНОГО размера?
Ну пример же там есть, длинна разная может быть, но я так понял, что квадраты могут иметь как-бы общие клетки тоже.
Сколько квадратов ты насчитал при длине стороны - 3? Я насчитал 34:
"сам весь" - 1
"все мелкие внутри" - 9
"Один крупный в углу, остальные пять вокруг двух его сторон" (4 комбинации, 6*4) - 24

итого - 34

Или я не прав?
...
Рейтинг: 0 / 0
17.07.2009, 15:21:22
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36096030
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
VadimPanov,

я про то, что нельзя использовать сравнение С# и Java приложений с запуском executable. И так ясно, что раскрутка старта процесса в Unix происходит мгновенно, в Windows - чуть медленнее, а платформы Java и С# поднимаются и JIT-компилятся несколько секунд. Если мы хотим сравнивать ЧИСТОЕ время работы алгоритма, то надо внутрь приложения ставить чекпоинты. В противном случае цифры получаются несоответствующие действительности, особенно на коротких по времени расчётах (не более минуты например).
...
Рейтинг: 0 / 0
17.07.2009, 16:07:32
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36096084
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
VadimPanovRT183.1
у тя просто очень мало опыта
Будет опыт и все вопросы сами отпадут
Как набрать опыт, если не понятно, как оно устроено? У меня-то на компе всё быстро работает, а там - нет...
Кстати, вот в этой задаче, нужно считать количество квадратов ОДИНАКОВОГО размера или одновременно квадраты могут быть РАЗНОГО размера?
Они привели данные в примере для 1, 2 и 8, было бы ещё для 3 - понятнее стало бы.
Да и если такая разница по скорости в языках, то какой интерес?
конечно разного, просто все они должны быть квадратами
Но эта задача из разряда где ну скорость ваще значения не имеет
Есть тип задач где важна именно скорость (т.е. в этом их соль)
...
Рейтинг: 0 / 0
17.07.2009, 16:26:22
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36096396
qaqaqa88
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
qaqaqa88
Гость
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
#include<stdio.h>

int main(int argc, char* argv[]){

	int *tempPnt;
	int testNum =  0 ;
	int num;

	int *input;
	
	do	{
		scanf("%i", &num);
				
		if (!num) break;

		tempPnt = new int[testNum+ 1 ];
			for (int i =  0 ; i < testNum; i++)	{
				tempPnt[i] = input[i];
			}
			
		if (testNum) delete [] input;

		tempPnt[testNum++] = num;
		input = tempPnt;
		
	}	while ( 1 );

		
	int n;
	long int sum;

	for (int i =  0 ; i < testNum; i++) {
		n = input[i];
		sum =  0 ;
			for (int j = n; j; j--) sum += (n-j+1)*(n-j+1);
		printf("%li\n", sum);
	}

	return  0 ;
}

0,01 sec / 2,6Mb Сейчас буду думать как улучшать...Я так понял надо делать свитч на 100 элементов...))
...
Рейтинг: 0 / 0
17.07.2009, 18:52:08
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36096777
rmull
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rmull
Участник
VadimPanovrmull
Какая у вашего решения сложность? У меня решение со сложностью O(n*m*log(n*m)) на C++ выполняется за 0.11 секунд.

А как ты вывел эту формулу? Я бы тоже посчитал для своего алгоритма...

Алгоритмическая сложность - базовое понятие в теории алгоритмов. О ней написано в любой книге по алгоритмам. В простейшем случае надо найти самый большой набор вложенных циклов, и перемножить максимальное количество итераций каждого из циклов.
...
Рейтинг: 0 / 0
18.07.2009, 12:30:20
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36096817
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
qaqaqa88Я так понял надо делать свитч на 100 элементов...))
Не вздумай
...
Рейтинг: 0 / 0
18.07.2009, 13:48:02
| Ответить | Цитировать | Написать  
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36097117
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот неплохая карта для тестов. Когда наскучит развлекаться со сливом воды за границы этого виртуального мира, условия можно изменить. Я-бы ввёл искуственный "забор" шириной в 1 пиксел по периметру, и с определённой высотой. Её можно взять как нормированную 0.5 от минимального и макс. значения высот, либо как половину объёма всех высот (здесь надо взять численный интегральчик).

Заодно проверим, что первый потонет с случае всемирного потепления.



Как преобразовать её в текстовый формат высот, я думаю, объяснять не стоит.
...
Рейтинг: 0 / 0
18.07.2009, 22:47:18
| Ответить | Цитировать | Написать  
25 сообщений из 261, страница 6 из 11
  6  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36096777&tid=1344339]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 185ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 71ms
get tp. blocked users:
 1ms
others: 197ms
total:  492ms
созд. / загр.: 492ms
x
x
Закрыть


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