|
| [8] Róbert Gida | 2016-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 Gida | 2016-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 |
|
|
|
| [4] Róbert Gida | 2016-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 |
|
|
| [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!
|
|
