Fórum: Informatika kömal

Sziasztok!

Az i277-es feladatban, a program ahogy kirajzolta a képet, azonnal záródjon is be, vagy egy billentyűlenyomáskor záródjon be?

Köszi

Igen.

S66-ban feltehetjük-e, hogy a házakat 0-tól N-1-ig számozzuk?

Az, hogy egy feladat ismert, még nem jelenti, hogy könnyű is. Sőt, sokszor épp az ellenkezője; a sudoku szerintem pont ilyen.

OK, bár annak nem látom sok értelmét, hogy ismert feladatokat tűznek ki, mondjuk ez I jelű feladat volt, de S-ben is volt teljesen ismert probléma, mondjuk a sudoku.

A probléma spec. esete annak, amikor egész számok vannak a téglalapba írva, és keressük azt a téglalapot, amiben a számok összege a legnagyobb. Magasabb dimenzióban is láttam már kitűzve ezt a feladatot, nincs nagy újdonság benne, csak többet kell írni.

De d=2 dimenzióban is érdekes a feladat, nem ismert a bonyolultsága, nyilván n² művelet kell, de O(n³)-nél van gyorsabb algoritmus is. Talán -es, nem emlékszem.

Egy másik már érdekesebb általánosítás, amikor nem egy téglalapba, hanem egy tóruszra írjuk az egész számokat, és keressük a téglalapot amiben a számok összege a legnagyobb.

Nem is írta senki, hogy azt kell implementálni. (Remélem legalábbis, hogy nem, mert a ,,halálismert'' változatot csináltam.)

I274. Amit második megoldásnak írtok az egy O(n²*m²)-es algoritmus. De van O(n*m*min(n,m))-es megoldás is. Igazából halálismert.

A tiétek nem is hinném, hogy n=m=500 esetén lefutna egy perc alatt a gépeteken.

Igen, így már helyes a kód.

Egyébként tree[i] méretére helyes volt az n>>i. Egy bizonyítás erre: 2-hatványok összeadása miatt látható, hogy pos=u*2ⁱ-1 valamilyen u égeszre, így pos2=w*2ⁱ-1 is teljesül, de akkor pos2>>i=w-1 és n>pos2=w*2ⁱ-1 miatt (n>>i)w, kettőt összerakva (pos2>>i)<(n>>i). Talán emiatt is célszerű pos=-1-ről indulni, hogy tree[i] mérete n>>i legyen.

Ezt azért nem nevezném interval tree-nek. Amit írsz, az valójában teljesen analóg a versenyző által készített megoldással, annyi különbséggel, hogy te csak a bináris fa leveleiben "tárolsz" elemeket, illetve egy tömböt indexelsz ügyesen ahelyett, hogy külön objektumok lennének a csúcsok.

Mindenesetre ha már lekódoltad, kirakom ezt is megoldásnak, köszönjük! (Annyit módosítottam rajta, hogy a szükséges méretű tömböket foglalja le dinamikusan, ne pedig eggyel rövidebbet, mert így gyakran elszállt. Remélem, most már jó.)

Olvasva a hivatalos megoldást az S64. feladatra nekem úgy tűnt, hogy a kiírók nem ismerik az interval tree-t. Nem mellesleg sokkal egyszerűbb kódot kapunk vele, mint a feltett max. 10 pontos kód.

Megoldásom itt van: http://ideone.com/ay5q3

Az S.64. javítása épp most készült el, már ki is került.

Egyébként ugyanaz a javítási határidő/időköz, mint a többi pontversenyben: igyekszünk a következő feladat határideje előttre kijavítani, de ez nem mindig sikerül.

Szaisztok! Csak annyit szeretnék kérdezni, hogy az informatika feladatokat milyen időközönként/határidővel javítják? Hamarosan az októberi forduló beküldési határideje is lejár, de még a szeptemberi feladatok sincsenek javítva... remélem, nem költözött el az e-munkafüzet...?

Köszi a válaszokat!

Kérdés visszavonva.

Az S.65. feladattal kapcsolatban szeretném megkérdezni, hogy a második és harmadik példában biztosan helyes-e a megadott kimenet.

A feladatban leírt feltételeket/korlátokat egyfajta szerződésként tekintsd: mi garantáljuk, hogy csak ennek eleget tevő -- helyes -- bemenetekkel hívjuk meg a megoldásod, te pedig (a maximális pontszámért) garantálod, hogy a helyes bemenetekre hiba nélkül lefut és helyes választ ad a programod. (Illegális bemenetre akár el is szállhat, itt ez nem érdekes.)

Tehát ellenőrzést semmiképpen ne végezz, viszont bizonyosodj meg alaposan, hogy minden (a feladat szövege által nem kizárt) speciális esetet lekezeltél.

Új vagyok ebben a komalban, és nem tudom, hogy azt kell e vizsgalni, pl S64-nél hogy a tomb elemeinek szama nem-e kisebb a torlesek szamanal. Kell akármilyen hibaellenorzest csinalni a feladatokban?

akkor már nem egyszerűbb leszedni 2 kattintással..?

i270 pdf file érdekes, először azt hittem, hogy egy 80 évre titkosított kormánydokumentumot látok a sok fekete kitakart rész miatt. Ezt persze még gyakorolni kell, mert a kitakart email címre még rá lehet kattintani, sőt az url címre is.

Feltett s63.c kódnál fordítás nélkül találjuk meg, hogy hol kapnánk warningot -Wall-al fordítva.

Igen, a doboz és a labdák átmérői mindig egész számok.

S.62. Kérdés: A doboz átmérője illetve a labdák sugarai mindig egész számok?

Köszönöm :)

Programnyelvnek Python a legjobb szerintem - talán az egyik legkönnyebben tanulható és használható programnyelv, de nagyobb dolgokat is lehet benne írni. A www.python.org oldalról ingyenesen letölthető, itt angolul elég sok leírást is lehet találni hozzá, de magyar fordításokat is lehet találni (google).

Sziasztok!

Mi tanácsolnátok egy 7-es fiúnak,aki tök 0-ról akar egyedül programozással ismerkedni. Programnyelv, szakirodalom, ....?

Előre is kösz.

Szép megoldás, el kell ismerni.

Feltettem ide, némi megjegyzéssel együtt: http://ideone.com/aiMuI

További megjegyzések a kódhoz:

1. észrevétel: 2 ds (súlyozott) Manhattan távolság az az 1 ds (súlyozott) Manhattan távolságok összege. Így a feladat átjátszható 1 dimenzióra.

2. észrevétel: az eredeti x, illetve y koordináták között is felvétetik az optimum. Ezt könnyű belátni, mert 2 szomszédos rácspont között 1 dimenzióban a súlyozott Manhattan távolság lineárisan változik.

Volt benne némi különmunka, hogy kijöjjek a 3 for ciklussal és 1 if-fel. De sikerült.