Problematic problem

Boyov · Nov 28, 2003, 13:01

Вот задача:

На contest-е её никто не решил.
Может вы сможете

P.S. sory за jpg, просто Я copy-paste-ил из pdf.

Regards
A.

P.S. Solution is available

greka · Nov 28, 2003, 13:39

plz skonvertiruy JPG v Grayscale JPEG...

razmer slishkom velik.

Boyov · Nov 28, 2003, 13:47

Quote:

Originally posted by Greco El
plz skonvertiruy JPG v Grayscale JPEG...

razmer slishkom velik.

Sorry, но у меня тока mspaint.

greka · Nov 28, 2003, 14:06

esli N ob'ektov pokryvayut "2*Pi" uglov, to gde problema-to ?

Vot tebe JPEG s resheniem:

greka · Nov 28, 2003, 14:30

ur-e pryamoy pod zadannym uglom ne pomnyu, seychas vyvedem:

(x-x1) / (x2-x1) = (y-y1) / (y2-y1), where x1, x2, y1, x2 == const

let
x1 = 0
y1 = 0

then
x/x2 = y/y2,
i.e.

y = x*(y2/x2) = x * tg(Alfa)

nm · Nov 28, 2003, 16:53

ггарик

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

1. в условии сказано - координаты источников даны
2. там же сказано - источники света не могут быть расположены в одной точке

я бы сказал так - если это решать перебором, то наибольший вес имеют источники света расположенные ближе к стороне квадрата . (условия оговаривают 100x100). шкурой чуствую - преимущественно все источники света смотрят друг на друга .... источников, которые светят наружу из этого квадрата и не освещают другие исто-ники света - мало или нету ...

greka · Nov 28, 2003, 17:16

tak, ne mogu skachat' etot JPEG, chotb posmotret' usloviya..

esli, govorish', tochki tebe uje zadany (a oni zadany mogut byt' na 1 pryamoy..

tebe ne slojno perepechatat' toka tekst syuda ?

greka · Nov 28, 2003, 17:19

naskoka ya pomyu, tamnim usloviem bylo:

luchi ne perekryvayutsa.
?

greka · Nov 28, 2003, 17:38

наверное, так:

1. через любые 2 точки можно провести прямую (L1)
2. это означает, что строим 2 источника света так, чтоб они дополняли друг друга, как на JPEG-e.

И так - для всех остальных точек - берется одна из уже рассчитанных и одна из "available" - и делается пересчет "линии синхронизации" L2

Задача сводится к тому, чтоб найти комбинацию, когда все поространство покрыто и через все точки проведены "линии синхронизации".
Для этого и давалось 2 минуты максимум

как тебе идея, nm?

greka · Nov 28, 2003, 17:45

а о найденном решении можно узнать так:
суммируем углы синхронизации:

Angel(L1)+Angel(L2)+... == 360 (?)

/точнее - не углы, а (угол/2), что ли... /
Как углы прямой расчитывать - мы знаем.

nm · Nov 29, 2003, 12:49

tot zhe jpg s zadachkoj lezhit uzhe na
http://docs.nothing.am/xndir.jpg

nm · Nov 29, 2003, 12:51

Quote:

Originally posted by Greco El
naskoka ya pomyu, tamnim usloviem bylo:

luchi ne perekryvayutsa.
?

текст перепечатать сложно - ибо в лом

картинку я уже выложил
нет, такого условия нету

Obelix · Nov 30, 2003, 09:29

Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.

Фиби · Nov 30, 2003, 14:38

Итак, от имено тов. Агабабова:

задача на самом деле достаточно сложна.
Тут http://neerc.ifmo.ru/regional/problems/archive.rar лежат решения жюри для всех задач этого соревнования. Дано для каждой задачи несколько решений. Все решения паскаль.
Далее, для данной задачи есть специальный doc файл, где дано ее решение (мат обоснование). Итак, 3 теоремы, 2 леммы и одно следствие... нипадецки, однако!

Совсем не удивительно, что ее никто не решил

Фиби · Nov 30, 2003, 14:39

Quote:

Originally posted by Obelix
Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.

И это тоже верно. Теорема X из док файла, именно это и указывает (косвенным образом). Но этого черезчур мало для того, чтобы решить эту задачу

Nov 28, 2003, 13:01	#1
Boyov 4294967296 Join Date: Mar 2002 Location: /proc/1 Posts: 378 Rep Power: 7 Reputation: 10	Problematic problem Вот задача: На contest-е её никто не решил. Может вы сможете P.S. sory за jpg, просто Я copy-paste-ил из pdf. Regards A. P.S. Solution is available __________________ Free your mind and your OS will follow

Nov 28, 2003, 13:39	#2
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	plz skonvertiruy JPG v Grayscale JPEG... razmer slishkom velik. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 14:06	#4
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	esli N ob'ektov pokryvayut "2*Pi" uglov, to gde problema-to ? Vot tebe JPEG s resheniem: Attached Images __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 14:30	#5
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	ur-e pryamoy pod zadannym uglom ne pomnyu, seychas vyvedem: (x-x1) / (x2-x1) = (y-y1) / (y2-y1), where x1, x2, y1, x2 == const let x1 = 0 y1 = 0 then x/x2 = y/y2, i.e. y = x(y2/x2) = x tg(Alfa) __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 16:53	#6
nm ЙЦУКЕН Join Date: Jul 2002 Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77 Posts: 3,114 Rep Power: 7 Reputation: 10	ггарик ты думаешь что для такого понимяния задачи , как ты ее понял, стали бы давать ограничения на время и память ,,,, нее 1. в условии сказано - координаты источников даны 2. там же сказано - источники света не могут быть расположены в одной точке я бы сказал так - если это решать перебором, то наибольший вес имеют источники света расположенные ближе к стороне квадрата . (условия оговаривают 100x100). шкурой чуствую - преимущественно все источники света смотрят друг на друга .... источников, которые светят наружу из этого квадрата и не освещают другие исто-ники света - мало или нету ... __________________ -- Опоздавшему поросёнку сиська возле жопы.

Nov 28, 2003, 17:16	#7
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	tak, ne mogu skachat' etot JPEG, chotb posmotret' usloviya.. esli, govorish', tochki tebe uje zadany (a oni zadany mogut byt' na 1 pryamoy.. tebe ne slojno perepechatat' toka tekst syuda ? __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 17:19	#8
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	naskoka ya pomyu, tamnim usloviem bylo: luchi ne perekryvayutsa. ? __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 17:38	#9
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	наверное, так: 1. через любые 2 точки можно провести прямую (L1) 2. это означает, что строим 2 источника света так, чтоб они дополняли друг друга, как на JPEG-e. И так - для всех остальных точек - берется одна из уже рассчитанных и одна из "available" - и делается пересчет "линии синхронизации" L2 Задача сводится к тому, чтоб найти комбинацию, когда все поространство покрыто и через все точки проведены "линии синхронизации". Для этого и давалось 2 минуты максимум как тебе идея, nm? Attached Images __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 28, 2003, 17:45	#10
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	а о найденном решении можно узнать так: суммируем углы синхронизации: Angel(L1)+Angel(L2)+... == 360 (?) /точнее - не углы, а (угол/2), что ли... / Как углы прямой расчитывать - мы знаем. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Nov 29, 2003, 12:49	#11
nm ЙЦУКЕН Join Date: Jul 2002 Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77 Posts: 3,114 Rep Power: 7 Reputation: 10	tot zhe jpg s zadachkoj lezhit uzhe na http://docs.nothing.am/xndir.jpg __________________ -- Опоздавшему поросёнку сиська возле жопы.

Nov 30, 2003, 09:29	#13
Obelix панаехавший Join Date: Jun 2003 Location: форпост Posts: 4,005 Rep Power: 6 Reputation: 10	Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника. __________________ Իսկ ԴՈՒ արդեն վաճառե՞լ ես Հայրենիքդ ռուսներին: My Exchange Rate Monitor \| Իմ Արտարժույթի Մոնիտորը

Nov 30, 2003, 14:38	#14
Фиби зая Join Date: Mar 2003 Location: ... Posts: 7,738 Rep Power: 7 Reputation: 16	Итак, от имено тов. Агабабова: задача на самом деле достаточно сложна. Тут http://neerc.ifmo.ru/regional/problems/archive.rar лежат решения жюри для всех задач этого соревнования. Дано для каждой задачи несколько решений. Все решения паскаль. Далее, для данной задачи есть специальный doc файл, где дано ее решение (мат обоснование). Итак, 3 теоремы, 2 леммы и одно следствие... нипадецки, однако! Совсем не удивительно, что ее никто не решил __________________ Для того, чтоб иметь ангельский характер, надо иметь дьявольское терпение.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode