[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Роби  XML
Forum Index » Задачи од национални натпревари
Author Message
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

Може некој да ми даде идеа за задачава?
[MSN]
MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

Главната идеја е да ја делиме околината (divide & conquer) на помали правоаголници се додека не стигнеме до правоаголник за кој сигурно знаеме дека, сите раскрсници кои се наоѓаат во него се збунувачки или сите не се.

Нека имаме функција f(r, c) која враќа листа на раскрсници со ознаки (сини кругчиња) кои се најблиски до раскрсницата (r, c). Тогаш, за секој правоаголник (rx, cx, ry, cy), важи ->
      ако f(rx, cx) = f(rx, cy) = f(ry, cx) = f(ry, cy) = X,
      тогаш f(r, c) = X за секоја раскрсница во правоаголникот (rx, cx, ry, cy).

Значи, (рекурзивниот) алгоритам е


This message was edited 1 time. Last update was at 18/03/2012 22:55:52

jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

На примерот даден на сликата, ќошовите на најголемиот правоаголник имаат само по една најблиска означена раскрсница, па според горниот алгоритам во најголемиот правоаголник нема збунувачки раскрсници, што не е точно... Некако не го сфаќам алгоритамот...
[MSN]
MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

Хмм, кажав дека функцијата f(r, c) враќа листа на раскрсници со ознаки (сини кругчиња) кои се најблиски до раскрсницата (r, c), и дека тој резултат треба да го споредуваш за еднаквост.

Да го разгледаме примерот од сликата - ги означив раскрсниците со ознаки (сините кругчиња) со броевите од 1 до 4.

Сега, f(ќоше горе лево) = {3} (бидејќи 3 е најблиска раскрсница), f(ќоше горе десно) = {4}, f(ќоше доле лево) = {1}, f(ќоше доле десно) = {2}. Како што гледаш, не се сите листи исти, па продолжуваме со алгоритамот така што го делиме овој правоаголник на четири помали.

Да разгледаме сега еден помал правоаголник - означен на сликата (горе лево):

За ова правоаголниче, f(ќоше горе лево) = {3}, f(ќоше горе десно) = {3}, f(ќоше доле лево) = {3}, f(ќоше доле десно) = {3}. Како што гледаш, сите листи се исти. Тука, бидејќи листите вратија по само една раскрсница, ниту една од раскрсниците во правоаголникот не се збунувачки.

Да разгледаме сега, уште еден помал правоаголник - означен на сликата (лево средина):

За ова правоаголниче, f(ќоше горе лево) = {1, 3}, f(ќоше горе десно) = {1, 3}, f(ќоше доле лево) = {1, 3}, f(ќоше доле десно) = {1, 3}. Како што гледаш, сите листи се исти (всушност, бидејќи имаме само еден ред - ќошевите горе лево и доле лево, како и ќошевите горе десно и доле десно се исти). Тука, бидејќи листите вратија повеќе од една раскрсница (вратија две -> 1 и 3), сите раскрсници во правоаголникот се збунувачки.

Се надевам дека сега е појасно

This message was edited 2 times. Last update was at 22/03/2012 13:50:15

bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

@MOI кодот ми заглавува на најголемиот правоаголник, т.е не го дели на помали.
MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

@bedzo: не ја анализирав целата програма, ама ако си пресметал minn за (rx, ry), зошто тоа ти влијае на 3те други ќошиња ((rx, y1), ...) - види ја втората слика што јас ја прикачив - ако растојанието minn кај едното ќоше (горе лево) е на пример 10 и со тоа си го пополнил векторот a, не би требало minn да има, никакво, влијание на пополнувањето на другите вектори - b, c и d. Ти, некако, очекуваш дека растојанието од една раскрсница со ознаки (сино кругче) треба да е еднакво до сите ќошеви.

Исто, внимавај на именувањето (ти сметаш дека X се редовите, а Y колоните), но всушност (R се редовите, а C колоните) - мислам дека ќе сфатиш што зборувам - во алгоритамот (rx, cx, ry, cy) означува правоаголник со ќошеви (rx, cx) и (ry, cy), а не правоаголник со ќошеви (rx, ry) и (cx, cy). Имаш ваква грешка уште во почетокот на програмата - ако делиш на половина како што ти е напишано во програмата [(rx+ry)/2, (cx+cy)/2] наместо d(1, N, 1, M), веројатно треба да биде d(1, 1, N, M). Ќе треба да ги смениш параметрите и кај другава функција f.

This message was edited 1 time. Last update was at 22/03/2012 18:07:06

bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Ау ама сум се зафркнал со ова координатите... Благодарам на забелешката
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

@MOI извинете, моја грешка, мојата функција f(r,c) враќаше само број на најблиски раскрсници (во горниов случај, за сите 4 ќоша ми враќа 1, и затоа резултатот ми излегуваше 0)... Фала
[MSN]
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team