Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 28.11.2003, 13:01   #1
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Question Problematic problem

Вот задача:



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


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


Regards
A.

P.S. Solution is available
Reply With Quote
Old 28.11.2003, 13:39   #2
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

plz skonvertiruy JPG v Grayscale JPEG...

razmer slishkom velik.
Reply With Quote
Old 28.11.2003, 13:47   #3
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

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

razmer slishkom velik.
Sorry, но у меня тока mspaint.
Reply With Quote
Old 28.11.2003, 14:06   #4
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

Vot tebe JPEG s resheniem:
Attached Thumbnails
clipboard01.jpg  
Reply With Quote
Old 28.11.2003, 14:30   #5
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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)
Reply With Quote
Old 28.11.2003, 16:53   #6
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

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

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



я бы сказал так - если это решать перебором, то наибольший вес имеют источники света расположенные ближе к стороне квадрата . (условия оговаривают 100x100). шкурой чуствую - преимущественно все источники света смотрят друг на друга .... источников, которые светят наружу из этого квадрата и не освещают другие исто-ники света - мало или нету ...
Reply With Quote
Old 28.11.2003, 17:16   #7
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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 ?
Reply With Quote
Old 28.11.2003, 17:19   #8
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

naskoka ya pomyu, tamnim usloviem bylo:

luchi ne perekryvayutsa.
?
Reply With Quote
Old 28.11.2003, 17:38   #9
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

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

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

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

как тебе идея, nm?
Attached Thumbnails
clipboard02_dir.jpg  
Reply With Quote
Old 28.11.2003, 17:45   #10
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

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

/точнее - не углы, а (угол/2), что ли... /
Как углы прямой расчитывать - мы знаем.
Reply With Quote
Old 29.11.2003, 12:49   #11
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

tot zhe jpg s zadachkoj lezhit uzhe na
http://docs.nothing.am/xndir.jpg
Reply With Quote
Old 29.11.2003, 12:51   #12
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

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

luchi ne perekryvayutsa.
?

текст перепечатать сложно - ибо в лом
картинку я уже выложил
нет, такого условия нету
Reply With Quote
Old 30.11.2003, 09:29   #13
панаехавший
 
Obelix's Avatar
 
Join Date: 06 2003
Location: форпост
Age: 30
Posts: 4,007
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.
Reply With Quote
Old 30.11.2003, 14:38   #14
зая
 
Фиби's Avatar
 
Join Date: 03 2003
Location: ...
Age: 33
Posts: 7,738
Downloads: 0
Uploads: 0
Reputation: 6 | 0
Default

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

задача на самом деле достаточно сложна.
Тут http://neerc.ifmo.ru/regional/problems/archive.rar лежат решения жюри для всех задач этого соревнования. Дано для каждой задачи несколько решений. Все решения паскаль.
Далее, для данной задачи есть специальный doc файл, где дано ее решение (мат обоснование). Итак, 3 теоремы, 2 леммы и одно следствие... нипадецки, однако! Совсем не удивительно, что ее никто не решил
Reply With Quote
Old 30.11.2003, 14:39   #15
зая
 
Фиби's Avatar
 
Join Date: 03 2003
Location: ...
Age: 33
Posts: 7,738
Downloads: 0
Uploads: 0
Reputation: 6 | 0
Default

Quote:
Originally posted by Obelix
Почему то мне кажется, что в окончательной конфигурации лучи должны быть друг-другу паралельны - точнее луч каждого источника должен быть паралелен лучу другого источника.
И это тоже верно. Теорема X из док файла, именно это и указывает (косвенным образом). Но этого черезчур мало для того, чтобы решить эту задачу
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 17:34.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.