Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Informatika OKTV

Szeretnél hozzászólni? Jelentkezz be.
[9] Róbert Gida2016-02-12 20:39:04

Ez valójában O(c*N)-es alg. ahol c=gyerektelenek száma, de kis módosítással az előbbi bonyolultság is elérhető.

Előzmény: [8] Róbert Gida, 2016-02-12 20:33:42
[8] Róbert Gida2016-02-12 20:33:42

"A megoldás becsült lépésszáma a bemenet elemszámának (az összes személyek N számának) négyzetével arányos."

Egy ultra rövid megoldás ami minden bemenetet megoldott, top. sorrend nélkül: https://ideone.com/eYoIY1

, ez ráadásul O(&tex;\displaystyle n+\sum _{gy} ősökszáma(gy))&xet; időben fut, ahol az összegzés a gyerektelenekre megy. Ez persze még mindig &tex;\displaystyle O(N^2)&xet;-es a legrosszabb esetben. Szintén az érdekes véletlen inputokra:

7.11/1Helyes0.003 sec

7.22/2Helyes0.003 sec

8.11/1Helyes0.008 sec

8.22/2Helyes0.008 sec

9.11/1Helyes0.020 sec

9.22/2Helyes0.020 sec

10.11/1Helyes0.038 sec

10.22/2Helyes0.038 sec

Előzmény: [2] Schmieder László, 2016-02-09 22:06:15
[7] Róbert Gida2016-02-11 09:47:12

Kicsivel gyorsabb: https://ideone.com/GCdW8k. Ötlet: a (top. sorrend szerinti) első gyerektelentől balra lehetnek csak a közös ősök, továbbá cin/cout lecserélése scanf/printf-re. Az érdekesebb (véletlen) inputokra:

7.11/1Helyes0.002 sec

7.22/2Helyes0.002 sec

8.11/1Helyes0.005 sec

8.22/2Helyes0.005 sec

9.11/1Helyes0.015 sec

9.22/2Helyes0.015 sec

10.11/1Helyes0.014 sec

10.22/2Helyes0.014 sec

Előzmény: [6] Róbert Gida, 2016-02-10 22:51:18
[6] Róbert Gida2016-02-10 22:51:18

Itt van: https://ideone.com/QWOfvU.

Előzmény: [5] jonas, 2016-02-10 22:34:27
[5] jonas2016-02-10 22:34:27

De hol a megoldásod? Nem látom. Vagy titkos?

Előzmény: [4] Róbert Gida, 2016-02-10 22:11:41
[4] Róbert Gida2016-02-10 22:11:41

Saját megoldásom rá (szintén &tex;\displaystyle O(N^2)&xet;-es algoritmus, de bitoperációkkal gyorsítva) a szerveren mindegyik feladatot megoldja, legfeljebb 0.023 másodperc alatt. (kár hogy az eredménylistában az időket nem mutatják, csak a pontszámot).

Teszt#Pont...Üzenet...Futási idő

1.11/1Helyes0.001 sec

1.20/0Helyes0.001 sec

2.11/1Helyes0.002 sec

2.21/1Helyes0.002 sec

3.11/1Helyes0.001 sec

3.21/1Helyes0.001 sec

4.11/1Helyes0.002 sec

4.22/2Helyes0.002 sec

5.11/1Helyes0.001 sec

5.22/2Helyes0.001 sec

6.11/1Helyes0.001 sec

6.22/2Helyes0.001 sec

7.11/1Helyes0.004 sec

7.22/2Helyes0.004 sec

8.11/1Helyes0.009 sec

8.22/2Helyes0.009 sec

9.11/1Helyes0.017 sec

9.22/2Helyes0.017 sec

10.11/1Helyes0.023 sec

10.22/2Helyes0.023 sec

Előzmény: [2] Schmieder László, 2016-02-09 22:06:15
[3] jonas2016-02-10 11:11:25

Könnyítésnek elárulom, hogy a Családfa feladat a 2014/2015 3. korcsoport 3. forduló feladatsorából a 3. feladat.

Előzmény: [2] Schmieder László, 2016-02-09 22:06:15
[2] Schmieder László2016-02-09 22:06:15

A 2014/15. évi INFO OKTV egyik döntős feladatára keresünk megoldásokat. A Családfa feladat (http://nemes.inf.elte.hu/nemes_archivum.html#2015) egy megoldása megjelent a 2016. évi februári számban.

A közölt megoldás egyszerű, a versenyen is megállta volna a helyét, a megadott időkorláton belül helyes eredményt adott (http://mester.inf.elte.hu - Haladó - Körmentes gráfok - Családfa).

A megoldás becsült lépésszáma a bemenet elemszámának (az összes személyek N számának) négyzetével arányos. Szeretnénk hatékonyabb algoritmust készíteni, ezért várjuk az ötleteket!