Születésnap (Megoldás)
Versenyek > IOI > 2005 > 2. nap
Szakkörök > BDG Szakkör > 2006/2007 > 7. óra
Címkék > Feladat
Versenyek > IOI > 2005 > 2. nap
Szakkörök > BDG Szakkör > 2006/2007 > 7. óra
Címkék > Feladat
Algoritmusok
Két különböző algoritmust adunk. A legnagyobb tesztadatra csak a hatékonyabb
változat fut emberi időn belül.
1. "Négyzetes"
A megadott permutációt $2n$-féle módon helyezhetjük el az asztal körül, és
minden esetben $n$-nel arányos lépésben kiszámolhatjuk a káoszt. Így egy
$O(n^2)$ futási idejű algoritmushoz jutunk.
2. "Lineáris"
A megadott permutáció egyetlen elhelyezése alapján adjuk meg a káosz minimumát.
$O(n)$ futási idejű algoritmushoz jutunk.
Kódok
mb_szul.c (Mészáros Balázs, C)
pt_szul.pas (Peregi Tamás, Pascal)
tb_szul.cs (Tihanyi Balázs, C#, lineáris!)
pt_szul.pas (Peregi Tamás, Pascal)
tb_szul.cs (Tihanyi Balázs, C#, lineáris!)