KöMaL - Középiskolai Matematikai és Fizikai Lapok
Belépés
Regisztráció
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Játékszabályok
Technikai info
TeX tanfolyam
Regisztráció
Témák

Rendelje meg a KöMaL-t!

KöMaL Füzetek 1: Tálalási javaslatok matematika felvételire

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Fórum - Informatika OKTV

  Játékszabályok    Technikai információ    TeX tanfolyam    Elfelejtettem a jelszavam    Témák  

Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[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!

  Játékszabályok    Technikai információ    TeX tanfolyam    Elfelejtettem a jelszavam    Témák  

Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley