powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
25 сообщений из 261, страница 10 из 11
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114284
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ой, Вадим, даж не знаю что сказать
Твой код у меня скомпилился и отработал на отлично.
На сподже ограничения по памяти нет (= 256 М)
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114309
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1,

Можешь сравнить по времени со своим?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114315
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[quot RT183.1
На сподже ограничения по памяти нет (= 256 М)[/quot]
Ну, у меня максимум будет размер лонга (64 бита - 8 байт) * 1000000 = 8 Мб - "ни о чём"
Почему по скорости не проходит - хз, заполнение массива идёт очень быстро, дальнейшие расчёты - минимальны. Почему не проходит по времени - загадка.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114332
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
у них машинки древние -- PIII 750MHz
Так сложилось исторически и менять их нельзя, потому что
побьются все рейтинги по скорости, а кто будет заново ри-джаджить
миллионы кодов?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114335
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1,

о, а если оно сдохнет?
Что скажешь по скорости моего алгоритма? Где может быть затык? Как тебе решение в общем?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114357
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
дык у них в запасе этих машинок вагон :)
Насчет твоего решения..... ну мне так лениво возвращаться к этой таске.....
Ты уж прости. Ты просто сам подумай
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114361
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1,

да я не прошу глубокого анализа :-) Просто, если видишь явный затык (хотя,где тут ему спрятаться) - скажи...
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114377
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Явного затыка не вижу :) Херово мне просто сейчас, на душе
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114379
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1,

опять потравился?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114411
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanovRT183.1,

опять потравился?
опять
НО
отравление -- это следствие, а не причина :)
А вот что делать с "причиной" -- ХЗ
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114534
me_dved
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1> Мое решение на python самое тяжеловесное по памяти среди остальных питоноводов получилось, хыхы.

Там в ранк-листе первые 10-20 такие монстрюки -- "оставь надежду всяк сюда входящий".

Получилось с натягом 19-е место. Разница по времени с лидером раза в 2.
RT183.1>
Я как-то обменялся 4-6 письмами с юзером SPIDY из Индии (он спрашивал у меня как сделать
какую-то задачу, не помню какую). Он даже не знал что scanf работает быстрее cin.
Но объективно он намного лучший прогер чем я. И вообще, индийцы молодцы.
Для меня это в основном развлекуха. Просто жизнь заставила заняться этой хренью.
Успехи в спортивном программировании и навыки разработки по мало связаны. На старой работе видел хорошего кодера, филолога по образованию.

Сам сейчас балуюсь олимпиадными задачками, чтобы остаток знаний после универа не растерять :)
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114540
me_dved
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс...
Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ?

470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114665
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
> Получилось с натягом 19-е место. Разница по времени с лидером раза в 2.

Я ващет имел в виду общий ранк-лист, а не конкретно по этой задаче.
У меня кажется только в одной задаче первое место, уже много лет: http://www.spoj.pl/ranks/ALIENS/
Но я в нее угрохал очень много писанины.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114671
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, те же много лет для меня остается загадкой почему все решения
на первой странице - на ссылке выше -- сделаны на паскале.
Я в принципе тоже содрал из тырнета чужой код на С++, переписал его на Паскале,
но я его сильно модифицировал.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114694
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
me_dvedVadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс...
Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ?

470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785
Это что, реальный ответ? Как посчитан?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36114699
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanovme_dvedVadimPanovКстати, попытка задать размерность массива (фактически - ограничив максимальную размерность треугольника в 50 тыс. вместо миллиона) - провалилась, :-) программа выдала выход индекса за пределы массива, что означает, что они реально скармливают на вход значения больше этих 50 тыс...
Ваша программа осилит эту задачу для N=12345678901234567890123456789012345678901234567890 ?

470419093088414443136679010148821688843634550791843540876783593536197809292222678522457652871506814637418646167210126039437869991452475862419816785
Это что, реальный ответ? Как посчитан?
плин
конечно же реальный!
Это же Питон, в нем нет ограничения на длину целых чисел
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36115633
me_dved
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1> Получилось с натягом 19-е место. Разница по времени с лидером раза в 2.

Я ващет имел в виду общий ранк-лист, а не конкретно по этой задаче.
У меня кажется только в одной задаче первое место, уже много лет: http://www.spoj.pl/ranks/ALIENS/
Но я в нее угрохал очень много писанины.
Если общий, то да... Не среднестатистические умы. По крайней мере, осилили столько задач.
RT183.1Кстати, те же много лет для меня остается загадкой почему все решения
на первой странице - на ссылке выше -- сделаны на паскале.

Странно, почему именно паскаль. Чистый С (не C++) должен шустрее работать. Быстрее только со вставками на asm'е.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36115877
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1.
Что поразительно они (топы) лупят эти задачи сотнями на многих и разных контестерах, не только на сподже (Сподж относительно молодой контестер).
2.
asm я уж точно не использовал в ALIENS -- просто добавил солидную предобработку
Кстати, как часть контестерного этикета использовать асм считается дурным тоном и не приветствуется
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36116199
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1ага конечно могу (код ниже)
Я смутно помню что пытался найти точную формулу, но не смог.
Всё пытаюсь избавиться от дурацкой привычки всё решать "в голове",
вместо того чтобы взять бумагу и ручку и подумать по-настоящему.

Код: plaintext
...


Твой код для треугольников, на паскале, прекрасно у них работает, а ОН ЖЕ, переведённый с паскаля на С, тоже даёт time limit exceeded!!! И как это понимать? Интерпретатор стал быстрее компилятора или, может, дело в размерности переменных? Типа, какая-то нестыковка в размерности переменных и всё зависает, а система снимает задачу по превышению времени?
Код: 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.
#include <cstdio>
int main()
{
 long t, i, j, mx;
 long a[ 1000000 ];
 long w;
 a[ 1 ]= 1 ;a[ 2 ]= 5 ;a[ 3 ]= 13 ;mx= 3 ;
 scanf("%d", &t);
 do
 {
  scanf("%d", &j);
  if (j > mx)
  {
   for (long i=mx+ 1 ;i=j;i++)
   {
    w=i;
    a[i]=a[i- 1 ]+( 2 *w- 1 )+((w*(w- 1 ))/ 2 );
    if ((i/ 2 * 2 -i)!= 0 ) 
    { 
     a[i]=a[i]+(((w- 3 )*(w- 1 ))/ 4 );
    }
    else
    {
     a[i]=a[i]+(((w- 2 )*(w- 2 ))/ 4 );
    }   
   } 
   mx=j;
  }

  printf("%d", a[j]);
  t--; 
   } while (t >  0 );
}
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36116244
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
чудеса... бум смотреть
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36116347
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
All answers will fit within the range of a 64-bit integer

где у меня в паскале инт64 в Си должно быть long long

и printf("%lld\n", ...)
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118004
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RT183.1,

Щас вот сравнил работу твоего кода на паскале для треугольников со своим кодом (перевёл с С на паскаль), скомпилированно всё было в дельфях. Твой код работает значительно быстрее. А вот за счёт чего - не пойму.
Твой код:
Код: 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.
{$I-, Q-, R-, S-}
var t, i, j, mx: longint;
a: array[ 1 .. 1000000 ] of int64;
w: int64;
begin
   a[ 1 ] :=  1 ; a[ 2 ] :=  5 ; a[ 3 ] :=  13 ; mx :=  3 ;
   readln(t);

   repeat
     readln(j);
    
     if j > mx then begin
        
        for i := mx +  1  to j do begin
            w := i;
            a[i] := a[i- 1 ] + ( 2  * w -  1 ) + ((w * (w -  1 )) div  2 );
            if odd(i) then 
               a[i] := a[i] + (((w -  3 ) * (w -  1 )) div  4 ) 
            else
               a[i] := a[i] + (((w -  2 ) * (w -  2 )) div  4 );
        end;
        mx := j;

     end;
     writeln(a[j]);
     dec(t); 
   until t =  0 ;

end.

Мой код:
Код: 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.
const ms =  1000000 ;
var
 M:array[ 0 ..ms- 1 ] of int64;
 pos,tc,lv,res:int64;
 sz,i:longint;
 begin

 for i:= 1  to ms- 1  do begin
  M[i]:=M[i- 1 ]+i;
 end;

 readln(tc);
 while(tc> 0 ) do begin

  readln(lv);
  res:= 0 ;

  for sz:= 1  to lv do begin
  
    pos:=lv-sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];
    
    pos:=lv- 2 *sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];

  end;
  writeln(res);
  tc:=tc- 1 ;
 end;
end.
По сути, структура - одинаковая, у меня добавлен цикл предварительного заполнения массива, но он отрабатывает мгновенно. А дальше - в обоих исходниках идёт практически одинаковый цикл с числом иераций, равным очередному входному значению (у тебя он короче на 3 итерации). А внутри цикла мои расчёты даже проще...
Отчего же тогда такая разница в производительности?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118695
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так, не понял... Отчего

Код: plaintext
printf("%lld",  128 * 256 * 256 * 256 )

выводит мне

Код: plaintext
- 2147483648 

???????(?)
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118831
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
VadimPanov,
1) у тебя на одну проверку больше (условный переход обычно замедляет расчеты)
2) заметил еще {$I-, Q-, R-, S-}, попробуй скомпилится с такими же флагами (это отключение кучи скрытого кода - проверки при расчетах, операциях ввода-вывода...)
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118890
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanovТак, не понял... Отчего

Код: plaintext
printf("%lld",  128 * 256 * 256 * 256 )

выводит мне

Код: plaintext
- 2147483648 

???????(?)
я тоже не понимаю
...
Рейтинг: 0 / 0
25 сообщений из 261, страница 10 из 11
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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