Каким алгоритмом можно заполнить все озёра рельефа водой? / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?

25 сообщений из 261, страница 9 из 11

все

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36106246

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

ОЙ, МАМОЧКИ...!!!!!!

Сдаётся мне, что ответы по задаче WATER в точности совпадают с ответами по задаче TRICOUNT...
Или я совсем плох... Короче, я домой поехал, а то у меня дежа вю, похоже...

ЗЫ: или обе задачи - суть одно и то же, просто с разным графическим представлением...

...

Рейтинг:

0 / 0

23.07.2009, 17:47:12

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36106322

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

ага конечно могу (код ниже)
Я смутно помню что пытался найти точную формулу, но не смог.
Всё пытаюсь избавиться от дурацкой привычки всё решать "в голове",
вместо того чтобы взять бумагу и ручку и подумать по-настоящему.

Код: 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.

{$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.

как здоровье? ой не спрашивай; полностью отравлен
(я действительно отравился переперченной колбасой; рвало что пипц)

...

Рейтинг:

0 / 0

23.07.2009, 18:05:14

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36107758

vino

Гость

RT183.1, отравился - попробуй энтеросгель. Снимает симптомы за полчаса (намного лучше активированного угля). Сам пробовал. Хотя видел вроде более мощный сорбент.

...

Рейтинг:

0 / 0

24.07.2009, 14:10:04

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36107866

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

vinoRT183.1, отравился - попробуй энтеросгель. Снимает симптомы за полчаса (намного лучше активированного угля). Сам пробовал. Хотя видел вроде более мощный сорбент.
спасибо за хинт (никогда не слышал)

...

Рейтинг:

0 / 0

24.07.2009, 14:33:08

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110212

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1,

так как насчёт идентичности задач про квадраты и треугольники? И может ли на таких простых входных данных сказываться скорость чтения через scanf ? Djn такой код тоже не спасает, всё равно лимит по времени превышается:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

int r_d()
{
 int r= 0 ;
 char c=getchar();    
 while ((c<'0')|(c>'9')) c=getchar();           
 while ((c>='0')&(c<='9')){r=r* 10 +c-'0';c=getchar();}
 return r;
}

...

Рейтинг:

0 / 0

27.07.2009, 10:58:03

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110340

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

как это -- идентичные? чёт не догоняю
PS
Конечно метод чтения в этой задаче совершенно никак не скажется на времени.

...

Рейтинг:

0 / 0

27.07.2009, 11:31:54

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110512

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1как это -- идентичные? чёт не догоняю

1) Сравни входные данные и результаты обоих программ.
2) Обрати внимание на то, что количество элементарных фигур, которые требуют подсчёта) растёт в квадратичной зависимости от заданного входным параметром "уровня".
3) Мысленно преобразуй те же треугольники - в квадраты из первой задачи.

"Якорь мне в ж..у с проворотом, если это не то же самое!" (с)

...

Рейтинг:

0 / 0

27.07.2009, 12:10:31

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110654

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

хм..... надо будет проверить
Если это так, то на мой взгляд это удивительно
Я буду ПОТРЯСЕН

...

Рейтинг:

0 / 0

27.07.2009, 12:45:06

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110660

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1,

будь добр, сделай как можно быстрее, у меня в обоих случаях превышение времени выдаёт, хотя вычисления (ИМХО) даже проще, чем у тебя.

...

Рейтинг:

0 / 0

27.07.2009, 12:47:05

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36110988

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

не, Вадим, сорри, но чуда не случилось

для например входного 22

У Фейнмана ответ = 3795

а у ТРИКАУНТ = 2970

...

Рейтинг:

0 / 0

27.07.2009, 14:21:42

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36111731

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1,

у меня в обоих случаях SPOJ выдаёт time limit exceeded, так что проверить не могу, на компе уменя обе задачи выдают одинаковый ответ.

Не понимаю, почему так долго считает, алгоритмы, вроде, простые...

Feynman:

Код: 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.

#include <cstdio>
#include <cstdlib>

using namespace std;

int main() 
{
    int n;
    int r;
    scanf("%d", &n);
    while (n!= 0 ) 
    {
      if (n >= 4  )
      {
          r =  8  +  4  +  1  +  1 ;
          for (int i=  4 ; i <= n; i++)
          {
             r += i*i;
          }
      }
      else
      if (n ==  1 ) r =  1 ;
      else
      if (n ==  2 ) r =  5 ;
      else
      if (n ==  3 ) r =  14 ;

      printf("%d\n", r);
      scanf("%d", &n);
    }
    return EXIT_SUCCESS;
}

Tricount:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

#include <cstdio>
int main(int argc, char *argv[])
{
 int tc, lv;
 scanf("%d", &tc);
 while (tc >  0 )
 {
  scanf("%d", &lv);     
  int r =  0 ;
  for (int cl =  1 ; cl <= lv; cl++)
  {
     int z1 = lv - cl;
     int z2 = lv -  2 *cl;
     r += ((z1 +  2 )*(z1 +  1 ) + (z2 +  2 )*(z2 +  1 ))/ 2 ;
  }
  printf("%d\n", r);
  tc--;
 }
return  0 ;//EXIT_SUCCESS;
}

И ведь не wrong result выдаёт, а именно time limit exceeded !!! Где тут собака порылась, а?!!!

...

Рейтинг:

0 / 0

27.07.2009, 17:48:32

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36111764

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

не, ты не так понимаешь устройство е-джаджа
Конечно у тебя неправильные ответы, но джадж сначала смотрит на вермя,
только потом на правильность ответов

...

Рейтинг:

0 / 0

27.07.2009, 18:01:10

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36112170

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1не, ты не так понимаешь устройство е-джаджа
Конечно у тебя неправильные ответы, но джадж сначала смотрит на вермя,
только потом на правильность ответов
Што, оба неправильные? Я руками считал сперва...

...

Рейтинг:

0 / 0

27.07.2009, 22:10:32

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36112432

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

Можно попросить тебя обоим задачам скормить входные данные от 1 до 30 и дополнительно значения 1111, 2222, 3333 и выслать мне в личку? Ну, или сюда...

...

Рейтинг:

0 / 0

28.07.2009, 07:39:15

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36113125

me_dved

Участник

Сообщения: 25

Рейтинг: 0 / 0

VadimPanov
Tricount:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

 ...
 while (tc >  0 )
 {
  ...
  for (int cl =  1 ; cl <= lv; cl++)
  {
    ...
  }
  ...

И ведь не wrong result выдаёт, а именно time limit exceeded !!! Где тут собака порылась, а?!!!
Лишний вложенный цикл. Ищите сумму арифметических прогрессий через формулы суммы квадратов.

З.Ы.
Мое решение на python самое тяжеловесное по памяти среди остальных питоноводов получилось, хыхы.

...

Рейтинг:

0 / 0

28.07.2009, 12:53:31

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36113163

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Feynman:

Код: 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.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.

 1 
 1 
 2 
 5 
 3 
 14 
 4 
 30 
 5 
 55 
 6 
 91 
 7 
 140 
 8 
 204 
 9 
 285 
 10 
 385 
 11 
 506 
 12 
 650 
 13 
 819 
 14 
 1015 
 15 
 1240 
 16 
 1496 
 17 
 1785 
 18 
 2109 
 19 
 2470 
 20 
 2870 
 21 
 3311 
 22 
 3795 
 23 
 4324 
 24 
 4900 
 25 
 5525 
 26 
 6201 
 27 
 6930 
 28 
 7714 
 29 
 8555 
 30 
 9455 
 1111 
 457727556 
 2222 
- 635616601

...

Рейтинг:

0 / 0

28.07.2009, 13:11:52

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36113215

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

TRICOUNT

Код: plaintext

...

Рейтинг:

0 / 0

28.07.2009, 13:28:31

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114076

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Вадим, ну ты чё, ни то, ни другое так и не сдал?

...

Рейтинг:

0 / 0

28.07.2009, 17:18:24

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114090

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

me_dvedVadimPanov
Tricount:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

 ...
 while (tc >  0 )
 {
  ...
  for (int cl =  1 ; cl <= lv; cl++)
  {
    ...
  }
  ...

...

Рейтинг:

0 / 0

28.07.2009, 17:21:39

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114150

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

> Мое решение на python самое тяжеловесное по памяти среди остальных питоноводов получилось, хыхы.

Там в ранк-листе первые 10-20 такие монстрюки -- "оставь надежду всяк сюда входящий".
Я как-то обменялся 4-6 письмами с юзером SPIDY из Индии (он спрашивал у меня как сделать
какую-то задачу, не помню какую). Он даже не знал что scanf работает быстрее cin.
Но объективно он намного лучший прогер чем я. И вообще, индийцы молодцы.
Для меня это в основном развлекуха. Просто жизнь заставила заняться этой хренью.

...

Рейтинг:

0 / 0

28.07.2009, 17:42:04

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114222

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Но Гена Короткевич (#5) http://www.spoj.pl/ranks/users/ из мово городка
порвет их всех как детишек, включая #1. Просто ему некогда, не разорваться же
сразу на 100 фронтов

...

Рейтинг:

0 / 0

28.07.2009, 18:10:46

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114231

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

RT183.1Вадим, ну ты чё, ни то, ни другое так и не сдал?
Почему, сделал:
2583794 2009-07-23 15:43:51 Feynman accepted 0.01 2.5M C++

Треугольник тоже сделал, у меня на компе работает очень быстро и выдаёт результаты идентичные твоим. На сподже выдаёт превышение времени выполнения.
Вот код к треугольникам:

Код: 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.

#include <cstdio>
int main()
{
 long ms =  1000000 ;  
 long M[ms];
 M[ 0 ] =  0 ;
 for (long i= 1 ;i<ms;i++)
 {
  M[i] = M[i- 1 ]+i;
 }
 long tc;
 scanf("%d", &tc);
 while (tc >  0 )
 {
  long lv =  0 ;
  scanf("%d", &lv);
  long res =  0 ;    
  for (long sz =  1 ; sz <= lv; sz++)    
  {
    long pos = lv - sz +  1 ;
    if (pos >  0 ) {res += M[pos];}
    pos = lv -  2  * sz +  1 ;
    if (pos >  0 ) {res += M[pos];}
  }
  printf("%d\n", res); 
  tc--;    
 }
 return  0 ;
}

Основная идея алгоритма: построив таблицу вэкселе, я заметил, что количество обычных и перевёрнутых треугольников каждого размера для каждого заданного "уровня" соответствует строгому закону, см. рисунок. Задача, фактически, решается в экселе.
Ряд для всех размеров и ориентаций - один и тот же, но сдвинут по вертикали по простому закону, остаётся пробежаться по горизонтали для заданного входными данными уровня, суммируя значения в ячейках массива, индекс которого вычисляется на ходу.

Я использую посоветованный тобой DevC++ , но он, собака, что-то темнит с типами: скомпилированное приложение молча вылетает на первом цикле, где идёт заполнение массива, если уменьшить переменную ms до 50000 - нормально работает. При этом на сподже такого не наблюдается: если оставить в тексте программы только цикл заполнения, а остальное прибить, то сподж выдает wrong result, т.е. цикл отрабатывает нормально. Если остальное не прибивать, то - time limit exceeded. Хотя дальнейшие вычисления у меня гораздо короче твоих.
В общем, диагностика проблемы на сподже слабовата, хотелось бы видеть:
1) правильно ли отрабатывает программа
2) укладывается ли в лимит времени
3) укладывается ли в лимит памяти
именно в такой последовательности.

...

Рейтинг:

0 / 0

28.07.2009, 18:14:15

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114234

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

Не понял, картинка не прилипла...

...

Рейтинг:

0 / 0

28.07.2009, 18:15:54

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114237

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

Если бежать по строке 13, то цифры в этой строке укажут количество обычных и перевёрнутых треугольников каждого из размеров, указанных вверху. Тупо суммируя их получаем общее количество для заданной "размерности".

...

Рейтинг:

0 / 0

28.07.2009, 18:19:07

| Ответить | Цитировать | Написать

Каким алгоритмом можно заполнить все озёра рельефа водой?

#36114260

VadimPanov

Участник

Откуда: Toronto

Сообщения: 434

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

28.07.2009, 18:32:11

| Ответить | Цитировать | Написать

25 сообщений из 261, страница 9 из 11

все

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=36111764&tid=1344339]:	0ms
get settings:	8ms
get forum list:	18ms
check forum access:	3ms
check topic access:	3ms
track hit:	233ms
get topic data:	12ms
get forum data:	2ms
get page messages:	79ms
get tp. blocked users:	1ms
others:	229ms

total:	588ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы