Verseny feladat,robotok összegyűjtése
2020-03-18T08:19:36+01:00
2020-03-18T16:59:18+01:00
2022-07-20T16:12:03+02:00
  • Szóval tegyük fel, bámely i,j re létezik olyan műveletsor ami egyesíti őket k-ban. Ezután k és a C
    (k-n kívül legtöbb robotot tartalmazó város) egyesítő műveletét megnézzük hogy kitaláltuk e már.Ha megvan végrehajtjuk, ha nincs megkeressük és eltároljuk(500*500 as mátrixban,melynek minden eleme egy vector bool okkal töltve 0 zöld 1 piros).Ha egy ilyen keresés eredménytelen, akkor nem lehet.
    A keresés pedig bináris fával,zöld után hol lesz az 1. hol a 2.,piros után.Ha egy ág ismételni akar,akkor ott azt lezárjuk.(itt már egyszerű a vizsgálat, 500*500 as bool tömb)
    Ha a 2 megegyezik keresés vége.
    Ha nincs több ág program vége.
    Ez így már működhet.
    De még mindig kétséges nekem kicsit a hatékonysága...Te erre gondoltál?
    Mutasd a teljes hozzászólást!
  • Na mármost ahhoz hogy létezzen egy olyan műveletsor amely után minden robot egy helyen van, biztos hogy minden (i,j) csúcspárra is léteznie egy műveletsornak ami után a kezdetben i és j helyen álló robotok egy csúcsba kerülnek. Ez alapján próbálj gondolkozni.
    Mutasd a teljes hozzászólást!
  • Vagy minden csúcsból indítsak egy zöld és egy piros robotot,és a zöld mindig zöldre a piros mindig pirosra megy?
    Mutasd a teljes hozzászólást!
  • Marmint pl higy hol lesz a kezdetben 1 es és kezdetben 3 as robot x gombnyomás után?
    Mutasd a teljes hozzászólást!
  • Akkor mondok egy nagyobb segítséget, vizsgálj robot párokat.
    Mutasd a teljes hozzászólást!
  • Hát most nagyon nincs más ötletem sajnos. :)
    Mutasd a teljes hozzászólást!
  • Nyelő itt a végső csúcsot jelenti ahol a robotok összegyűlnek a gombnyomássorozat után.
    Mutasd a teljes hozzászólást!
  • 1. Igen, ez igaz, de ha jobban belegondolsz annyira nem mond el sokat a gráfról hiszen csak azt zárja ki, hogy a zöld részgráf illetve a piros részgráf se álljon csak körökből.
    2. Ez nem feltétlenül szükséges, az viszont igaz hogy A és B tetszőleges csúcsokra legalább A-ból B-be vagy B-ből A-be el kell tudni jutni, viszont ez is igazából azt mondja ki hogy összefüggő legyen a gráf ami nyilván szükséges.
    3. A nyelő definíciója nem tiszta számomra, hogy itt mit nevezünk annak.
    Mutasd a teljes hozzászólást!
  • Pontosítom, a gráf bármely pontjából el lehessen jutni nyelő esélyes pontba.
    Mutasd a teljes hozzászólást!
  • Az utolsó lépés előtt , nem lehet a nyelőben egy robot sem.
    Mutasd a teljes hozzászólást!
  • Az is higy  a gráf bármely pontjából bárhova el lehessen jutni.
    Mutasd a teljes hozzászólást!
  • Az biztos hogy kell legyen legalább egy olyan csúcs amibe ugyanabból a színből több él megy be.Még gondolkodok kicsit :)
    Mutasd a teljes hozzászólást!
  • Egy hint: mi biztosan szükséges feltétele annak hogy egy városba kerülhessenek a robotok? (hint2: 500 az viszonylag kicsi...) Illetve ez elégséges-e?
    Mutasd a teljes hozzászólást!
  • A feladat csatolva.
    Algoritmusom:
    Azt veszem hogy az adott lépés után a csúcsok mely halmazában van az összes robot.Ez kezdetben az összes csúcs közös halmaza.Egy zöld nyomás után is megnézem ezt , piros után is.És ezekre az állapotokra ismétlem az eljárást amíg egyelemű halmazt nem kapok. 2.Feladatleírásbeli példa szerint:
    Kezdetben: 1 2 3 4
    1 2 3 4 -> z ->1 2 3 4 VOLT(ág vége)
    1 2 3 4 -> p ->2 3 OK
    2 3 -> z  -> 3 4 OK
    2 3 -> p -> 2 3 VOLT
    3 4 -> z -> 1 4 OK
    3 4 -> p -> 2 3 VOLT
    1 4 -> z -> 1 2 OK
    1 4  -> p -> 3 KÉSZ
    A nagy probléma hogy lehet végtelen ciklus , és lehet hogy ugyanazt amiről már tudjuk hogy nem lehet kiszámolja megint,így a hatékonyságnak sajnos lőttek.
    Ha lehetne valahogy egy pl: 1 4 7 19 halmazról gyorsan ellenőrizni hogy volt e már,nagyon jól működne.

    Mivel max 500 szám van arra gondoltam hogy az első 500 primszámot rendelem az 1. 2. 3. ... csúcsokhoz,és a halmaz tagjainak primmegfelelőit összeszorzom,és egy igaz-hamis tömbön bejelölöm a szorzat eredményét és ezt csak egy halmaz adja,és egy halmaz mindig ugyanazt adja.De így akár 500 faktor is kijöhet ami nagyon sok.De ha mindig moduloznám 10Millióval akkor lehet jó lenne.

    Viszont ez így ,már tuti nem működne úgy tűnik...

    Szóval van e ötletetek
    - gyors ellenőrzésre?
    - más algoritmusra?

    Amiken még gondolkodtam:
    -2 gráfnak veszem
    -Matekozás pl. csak akkor lehet nyelő egy csúcs ha legalább egy színből legalább 2 megy bele... és hasonló szabályok alkotása.
    -Ugyenez fordítva(felteszem minden csúcsra hogy ott végződik,hol volt az összes robot ha z utolso zold volt, hol ha piros volt,addig amíg az 1 2 3 4 ... n halmazt nem kapom.)
    Mutasd a teljes hozzászólást!
    Csatolt állomány
Címkék
abcd