Feladat

Adott egy n tagú egész számokból álló sorozat: a₀, a₁, ..., a_n-1. Hívjuk az a_k, a_k+1,...,a_n-1, a₀, a₁,..., a_k-1 sorozatot ennek a k-adik elforgatottjának (0<=k<n). Úgy szeretnénk elforgatni a sorozatot, hogy az első i elem összege nemnegatív legyen minden i=1,2,...,n-re. Határozzuk meg, hogy hányféle k-ra lesz a k-adik elforgatott ilyen sorozat.

Feladat

Adjuk meg, hogy a C_n gráfban, vagyis az n hosszú körben hány párosítás található. A csúcsokat megkülönböztetjük. Párosítás alatt az élek egy csúcsdiszjunkt részhalmazát értjük, azaz néhány élt úgy, hogy semelyik kettőnek nincs közös végpontja.

Ez itt egy blog. Mégpedig egy olyan blog, amely remélhetőleg segít a komolyabb, algoritmikus jellegű programozóversenyekre való felkészülésben, mint amilyen az informatika OKTV, az olimpiai válogatóverseny, a nemzetközi diákolimpiák (a CEOI és az IOI), vagy egyetemi szinten az ACM ICPC. Hasonló felkészítést eredetileg szakkör formájában tartottam a Fazekasban, de mióta külföldön tanulok, ez nem igazán megoldható. Úgyhogy arra gondoltam, netre viszem a dolgot.

Ennek a formátumnak kétségkívül számos előnye van, például hogy nem kell időpontot egyeztetni, bárhonnan bármikor használható, vagy hogy az egyszer leadott tartalom megmarad és kereshető, nem kell ugyanazt sokszor elmondani. Ugyanakkor nincs meg hozzá az a plusz lökés, amit a szakkör ad, hogy ha már ott ül az ember, miért ne programozzon. Nekem ez nagyon hiányzott gimiben (ezért is csináltam a szakkört), mert így csak versenyeken programoztam, és kódolásban meglehetősen rutintalan maradtam. De ezen egyszerűen nem lehet neten keresztül segíteni. A blogról való fölkészüléshez tehát valamivel nagyobb önfegyelem szükséges, hogy a diák igenis leüljön kódolni. Ennek érdekében megpróbálok minél több olyan feladatot posztolni, amely online kiértékelővel tesztelhető.

Tervem sok van, időm annál kevésbé, úgyhogy majd még meglátjuk, mi sül ki ebből. Szeretnék érdekes (illetve fontos/hasznos) feladatokat mutatni, megoldásokkal, emellett pedig cikkeket írni algoritmusokról, technikákról. A végső cél az lenne, hogy akár a legalapvetőbb algoritmusok és módszerek (mint mondjuk a szélességi keresés, vagy a dinamikus programozás) ismeretének hiányában is meg lehessen tanulni innen a legfontosabbakat, amikre nemzetközi versenyeken szükség lehet. Ettől persze még nagyon messze vagyok, úgyhogy egyelőre arra koncentrálok, amire a szakkörömön is: a hazai és nemzetközi versenyek színvonalkülönbségének áthidalására. Ennek megfelelően majd a cikkek írásánál is magasabb prioritással kezelem azokat a témákat, amelyeket a magyar olimpiai felkészítés során nem, vagy nem igazán lehet megtanulni.

Kezdetben viszont cikkek sem várhatóak, csak feladatok. Ezeket egy hétre tervezem kitűzni, azaz egy hét után közlöm a megoldásukat (külön posztban), addig gondolkozzatok rajta (persze akár utána is), programozzátok le, illetve ha van rá lehetőség, teszteljétek. Valószínűleg feladatokat kitűzni is hetente fogok (gyakrabbra nem sok esély van, viszont igyekszem nem ritkábban), de hogy mikor mennyit, azt nem tudom. Minden megjegyzést szívesen fogadok, megoldásokat viszont lehetőleg ne a feladat posztjába kommenteljetek, hanem a megoldásának posztjába. A feladatokat jellemzően nem én találom ki, leginkább angol nyelvű forrásból veszem át őket. A feladatok címeit pedig minden ilyen esetben meg fogom tartani, szóval ne ijedjetek meg, ha az angolul van. A feladat szövegét mindenképp magyarul írom.

Most pedig kezdhetjük is :)