Új hozzászólás Aktív témák
-
kovisoft
őstag
Én úgy értettem a feladat leírásából, hogy nagyobb kupacból nem rakhatsz kisebbe, csakis egy nagyobba vagy ugyanakkorába tehetsz át valahány darabot (p-ből q-ba akkor rakhatsz át x-et, ha 1≤x≤Ap≤Aq). Tehát olyan nem lehet, hogy a 24-ből átraksz 1-et egy olyanra, ahol csak 1 van. Vagy félreértettem valamit? Ha nagyobb kupacből rakhatsz át kisebbe, akkor szimplán minden kupacot átrakhatsz az A1-be, és kész, nem?
-
kovisoft
őstag
Mivel a "greedy" szerepel a tag-ek között, így valószínűleg valami mohó stratégia kell majd. Nem vagyok regisztrálva codechef-en, így ki nem próbáltam, de az alábbi legegyszerűbb módszer nem működik?
1. Vesszük mindig a legkisebb nemüres Ai-t (i>1). Ha nincs ilyen --> megoldottuk a feladatot.
2. Ha van ilyen Ai és nem nagyobb A1-nél, akkor átrakjuk az egészet az A1-be. Goto 1.
3. Ha Ai>A1, akkor vesszük a következő legkisebb nemüres Aj-t (j>1, j<>i). Ha nincs már ilyen --> nem megoldható a feladat.
4. Ha van, akkor erre átrakunk Ai-ből annyit, amennyivel Ai nagyobb A1-nél. Ezután Ai maradékát átrakjuk A1-be. Goto 1.Legfeljebb 2 lépésben kiürül egy Ai, tehát max. 2n lépés kell.
-
kovisoft
őstag
Ezt a "Kth Missing Positive Number" feladatot én is egy egyszerű módszerrel oldottam meg, és igazából nehéz elképzelni olyan nagy tömbméretet, ami még beférne a memóriába, de mégsem lehetne kivárni, hogy szimplán egyszer végigmenjen a kód a tömbön. De gondolom arra utaltál, hogy N helyett akár O(log(N)) lépésben is meg lehet oldani, hiszen ha egy tetszőleges tömbelemet nézünk, akkor annak indexéből és értékéből meghatározható, hogy hány hiányzó szám volt addig.
-
kovisoft
őstag
Én itt vagyok, meg szoktam nézni a linkjeidet, agyalok is rajtuk, csak sajnos most elég kevés az időm, úgyhogy konkrét megvalósításig még nem jutottam el. Az előző (Sliding Window Maximum) feladatra csak egy n*log(n)-es megoldást tudtam kiagyalni. Nyugtass meg, hogy nincs lineáris megoldása.
-
kovisoft
őstag
Igen, ez egy jópofa feladat, egy másik formában találkoztam már vele, ott fájlból kellett számokat beolvasni, illetve ezek közül véletlenszerűen választani egyet egyenletes valószínűséggel úgy, hogy nem tudjuk a fájl méretét és hogy hány db számot tartalmaz, csak egyszer olvashatjuk, és nem tárolhatjuk a beolvasott számokat.
Új hozzászólás Aktív témák
- MWC 2026: Újból érik a szeder az Unihertz kertjében
- Elegánsan vizezné be a munkaállomásokat az Artic
- sziku69: Fűzzük össze a szavakat :)
- Luck Dragon: Asszociációs játék. :)
- Vicces képek
- Nem lesz Redmi Note 16, évet ugrik a sorozat
- exHWSW - Értünk mindenhez IS
- Motorola Edge 50 Ultra - szépen kifaragták
- Először beszélt bővebben az új Xbox konzolról a Microsoft
- Párduc a gépben: teszten az ASUS ExpertBook Ultra
- További aktív témák...
- LG 45GR65DC-B 45 / 5120x1440 / 200HZ / VA /
- Chieftec Smart Seriels GPS-500A8 80 Plus minősítésű 500W tápegység
- Apple iPhone 13 - 85% Akku - 128GB - Független - Hibátlan
- HONOR Magic8 Lite 5G 512GB + CHOICE Cubuds - Gyári Bontatlan, 2028-ig garanciális
- HONOR Magic8 Pro 5G 12/512GB (Black) - Új, Kártyafüggetlen, 2029-ig garanciális
- GYÖNYÖRŰ iPhone 13 128GB Blue -1 ÉV GARANCIA - Kártyafüggetlen, MS4681
- GYÖNYÖRŰ iPhone SE 2020 64GB Black -1 ÉV GARANCIA - Kártyafüggetlen, MS3920
- iPhone 12 128GB Black -1 ÉV GARANCIA - Kártyafüggetlen, MS4615, 100% AKKSI
- Keresünk dokkolókat
- Apple iPhone 12 Pro Max 128GB, Kártyafüggetlen, 1 Év Garanciával
Állásajánlatok
Cég: Laptopműhely Bt.
Város: Budapest