Форум Всеукраїнської інтернет-олімпіади NetOI

xXx · 2005-11-19 14:06:32

Pavel написав:
Angry Coder написав:
итого если мы умеем искать положение карточки с заданым числом за О(1) (а это легко)
Вот к этому и вопрос КАК?

Просто заведём доп. массив, где индекс - это заданное число, а значение - это положение...

Ivan · 2005-11-19 14:06:41

Newpatience можно за n и без геммороя

Kero · 2005-11-19 14:07:51

Как?

Angry Coder · 2005-11-19 14:13:27

Pavel написав:
Angry Coder написав:
итого если мы умеем искать положение карточки с заданым числом за О(1) (а это легко)
Вот к этому и вопрос КАК?

1)прямая индексация A[65536][2], где в А[i] храним номера карточек, на которых написано число i.
2)если хочется меньше памяти то хэш-таблица с таким же принципом.

Pavel · 2005-11-19 14:14:11

xXx написав:
Просто заведём доп. массив, где индекс - это заданное число, а значение - это положение...

И где ты его поместишь (128к по моим подсчетам), память не резиновая

У angry вообще 256к

Відредаговано Pavel (2005-11-19 14:17:25)

Kero · 2005-11-19 14:17:45

n*log(n) операций вообще-то

Відредаговано Kero (2005-11-19 14:18:02)

xXx · 2005-11-19 14:19:07

Pavel написав:
xXx написав:
Просто заведём доп. массив, где индекс - это заданное число, а значение - это положение...
И где ты его поместишь (128к по моим подсчетам), память не резиновая

У меня объём кеша больше...А ОЗУ то вообще 256Мб!!!
Да, а если озу всё таки не позволяет выделить такое количество, то для этого нужно использовать хеш-таблицы...

Відредаговано xXx (2005-11-19 14:21:08)

Maestro · 2005-11-19 14:20:20

Blamblam:

Код:

 var n,i:byte;
begin
  read(n);
  for i:=1 to n do write(random(2));
end.

Kero · 2005-11-19 14:24:25

Maestro написав:
Blamblam:
Код:
 var n,i:byte;
begin
  read(n);
  for i:=1 to n do write(random(2));
end.

Геніально!!!!

Pavel · 2005-11-19 14:24:29

Я не знаю обьем динамической памяти в анси с
Но борланд 7.0 вроде больше 64 своих и около 80 динамической не дает

Maestro · 2005-11-19 14:26:49

65 kb своих и 650 kb динамической.

Maestro · 2005-11-19 14:29:26

Но если не писать {$M} то проверялка выделяет всю оперативу компа (а там немало).

Pavel · 2005-11-19 14:30:28

Читерство

Anna · 2005-11-19 14:30:57

Maestro написав:
Blamblam:
Код:
 var n,i:byte;
begin
  read(n);
  for i:=1 to n do write(random(2));
end.

И как, работает?

DeusEx · 2005-11-19 14:31:01

Мне памяти хватило бы и для 20000н и 30000 а вот времени - не уверен . Вообщем все задачи счетные и легкие. Только вот пасьянсы я бы смог отнести к средней задаче.

Maestro · 2005-11-19 14:32:32

Anna написав:
И как, работает?

Когда как

Angry Coder · 2005-11-19 14:33:11

2 xXx:
в тесте 160 4 140 80
при угле 1.039877
проекции 140.000000 84.461612
значит разместить невозможно.

Pavel · 2005-11-19 14:35:27

Angry Coder написав:
2 xXx:
в тесте 160 4 140 80
при угле 1.039877
проекции 140.000000 84.461612
значит разместить невозможно.

Диагональ карты больше диагонали стола не войдеть

Pavel · 2005-11-19 14:37:38

может имелось в сиду 160 40 140 80

DeusEx · 2005-11-19 14:48:47

Pavel написав:
может имелось в сиду 160 40 140 80

все равно ответ 0

Angry Coder · 2005-11-19 14:51:14

именно 160 4 140 80. ответ 0.
на 160 40 140 80 тоже ответ 0. но это действительно очевидно.

xXx · 2005-11-19 14:53:48

Angry Coder написав:
2 xXx:
в тесте 160 4 140 80
при угле 1.039877
проекции 140.000000 84.461612
значит разместить невозможно.

угол в чём? в радианах? в градусах?
я не знаю, может у меня calc.exe глючит, но проекции совершенно другие получились...

Відредаговано xXx (2005-11-19 14:55:40)

DeusEx · 2005-11-19 14:57:14

какие еще проекции? вы что? задача решается элементарно - просто проводим окружность с центром совпадающим с центром стола и диаметром равным диагонали карты, находим точки пересечения и растояния между ними, наименьшее растояние - это наибольшая ширина карты с таким диаметром, если класть карту не горизонтально. Горизонтальный вариант проверяется вообще в одну строчку.

Pavel · 2005-11-19 14:58:16

посмотри по диагоналям. Диагональ карты больше. Ну никак не влезет

Pavel · 2005-11-19 14:59:30

DeusEx написав:
какие еще проекции? вы что? задача решается элементарно - просто проводим окружность с центром совпадающим с центром стола и диаметром равным диагонали карты, находим точки пересечения и растояния между ними, наименьшее растояние - это наибольшая ширина карты с таким диаметром, если класть карту не горизонтально. Горизонтальный вариант проверяется вообще в одну строчку.

Именно так. самое простое решение

Форум Всеукраїнської інтернет-олімпіади NetOI

#26 2005-11-19 14:06:32

Re: Обсудим решения

Pavel написав:

Angry Coder написав:

#27 2005-11-19 14:06:41

Re: Обсудим решения

#28 2005-11-19 14:07:51

Re: Обсудим решения

#29 2005-11-19 14:13:27

Re: Обсудим решения

Pavel написав:

Angry Coder написав:

#30 2005-11-19 14:14:11

Re: Обсудим решения

xXx написав:

#31 2005-11-19 14:17:45

Re: Обсудим решения

#32 2005-11-19 14:19:07

Re: Обсудим решения

Pavel написав:

xXx написав:

#33 2005-11-19 14:20:20

Re: Обсудим решения

Код:

#34 2005-11-19 14:24:25

Re: Обсудим решения

Maestro написав:

Код:

#35 2005-11-19 14:24:29

Re: Обсудим решения

#36 2005-11-19 14:26:49

Re: Обсудим решения

#37 2005-11-19 14:29:26

Re: Обсудим решения

#38 2005-11-19 14:30:28

Re: Обсудим решения

#39 2005-11-19 14:30:57

Re: Обсудим решения

Maestro написав:

Код:

#40 2005-11-19 14:31:01

Re: Обсудим решения

#41 2005-11-19 14:32:32

Re: Обсудим решения

Anna написав:

#42 2005-11-19 14:33:11

Re: Обсудим решения

#43 2005-11-19 14:35:27

Re: Обсудим решения

Angry Coder написав:

#44 2005-11-19 14:37:38

Re: Обсудим решения

#45 2005-11-19 14:48:47

Re: Обсудим решения

Pavel написав:

#46 2005-11-19 14:51:14

Re: Обсудим решения

#47 2005-11-19 14:53:48

Re: Обсудим решения

Angry Coder написав:

#48 2005-11-19 14:57:14

Re: Обсудим решения

#49 2005-11-19 14:58:16

Re: Обсудим решения

#50 2005-11-19 14:59:30

Re: Обсудим решения

DeusEx написав:

Нижній колонтитул