Search
Definice: Kombinatorickou hrou budeme rozumět libovolnou hru splǔjící následující pravidla:
Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst jeho libovolný vlastní dělitel. Zjistěte, pro která N byste chtěli hrát jako první.
Hra se točí okolo lámání čokolády o rozměrech MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte). Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.
V této hře je počáteční číslo pevně dáno a je rovné 2. Hráči se střídají a při svém tahu mohou k aktuální hodnotě N přičíst jeho libovolný vlastní dělitel. Hráč, po jehož tahu hodnota N překročí 2016, vítězí. Dokážete říci, zda existuje vyhrávající strategie pro začínajícího hráče?
V láhvi jsou lístečky s čísly od 1 do 16. Hráč, který je na tahu, vyndá z lahve nějaké číslo a všechny jeho dělitele. Prohrává hráč, nemůže táhnout. Může si začínající hráč vynutit výhru?
Hra se točí okolo lámání čokolády o rozměrech 2MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte), ALE nikdy nesmí vzniknout dílek o velikosti 1×1. Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.
Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst libovolné prvočíslo (včetně 1) menší než N. Zjistěte, pro která N byste chtěli hrát jako první.
Opět se hra točí kolem lámání čokolády, ale v tomto případě jde o život! Tabulka čokolády leží na stole, rozlámaná na jednotlivé kostičky. Hráč si při svém tahu zvolí libovolný dílek čokolády a zbaští všechny dílky, které se od dané kostičky vyskytují nahoru a napravo (odebraný kus čokolády vždy tvoří obdélník o jednom či více dílků). Problém je, že dílek úplně vlevo dole je otrávený. Zkuste zjistit, zdali se jako začínající hráč můžete vyhnout otravě, pokud má tabulka čokolády tvar A) čtverce či B) obdélníku.
Na stole leží N sirek. Hrači se postupně střídají v odebírání sirek, přičemž mohou při svém tahu odebrat 1, 2, nebo 3 sirky. Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.
Na stole leží N sirek. Hrači se postupně střídají v jejich odebírání, přičemž hráč při svém tahu nesmí odebrat více sirek než kolik bylo odebráno v předchozím tahu. Začínající hráč musí odebrat alespoň jednu sirku, ale nesmí odebrat všechny (jinak by to byla pěkně nudná hra). Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.
Na stole leží 3 hromádky se 4, 2 a 1 kamenem. Hráč při svém tahu může odebrat 1 nebo 2 kameny. Hráč, který zvedne poslední kámen vyhrává.
Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů (klidně odebere celou hromádku). Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.
Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů, ale vždy alespoň jeden. Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.
Je dána řada N mincí, kde některé jsou pannou a jiné orlem vzhůru. Hráč si při svém tahu může zvolit libovolnou minci, která je pannou vzhůru, a otočit ji. Navíc, si může zvolit libovolnou minci nalevo od té první a otočit ji (ať byla orientovaná jakkoliv). Ukažte, že tato hra je ekvivalentní s předchozí hrou NIM (klasický).
Hrači stojí nad koláčem, který má na svém okraji N zářezů. Hráč, který je na tahu, si zvolí dvojici zářezů na libovolném kusu koláče a jedním tahem ho napříč těmito zářezy rozřízne. Hráč, který nemůže provést žádný řez, prohrává.
Na stole leží N hromádek sirek. i-tá hromádka obsahuje N[i] sirek. Hráč na tahu si zvolí libovolnou hromádku a odebere z ní 1, 2, nebo 3 sirky. Hráč, který odebere poslední sirku, vyhrává.
V 1. přednášce si představíme jednu z ikonických úloh a ukážeme si, jak ji efektivně řešit pomocí intervalového stromu.
V 2. přednášce si představíme (přirozené) využití intervalových stromů pro odpovídání na dotazy typu: Nalezněte minimum mezi prvky pole v zadaném intervalu.
Ve 3. přednášce si představíme speciální “intervalový strom”, který efektnivě pracuje s kumulativními součty v poli.
Na vstupu je dána permutace P přirozených čísel od 1 do N. Nalezněte počet inverzí v dané permutaci. (Inverzí rozumíme dvojici indexů (i, j) taková, že i < j a zároveň P[i] > P[j]).
Na stole leží N karet, všechny jsou otočené lícem vzhůru. Máte dánu sekvenci následujících příkazů:
Úlohy k řešení na A2OJ: Contest 28050.
Některé související kódy:
package maraton; public class Geom { static boolean isLineCircleIntersection( double Ax, double Ay, double Bx, double By, double Cx, double Cy, double Cr ) { /* line equation ax + by + c = 0 direction vector A -> B : (Bx-Ax, By-Ay) normal vector of A -> B: (Ay-By, Bx-Ax) orthogonal to direction Line equation: a = Ay-By, b = Bx-Ax, c = -a*Ax - b*Ay = -(Ay-By)*Ax - (Bx-Ax)*Ay = By*Ax-Bx*Ay distance( C, line) = |a*Cx + b*Cy + c| / sqrt(a^2 + b^2). */ double a = Ay-By; double b = Bx-Ax; double c = By*Ax-Bx*Ay; double dist = Math.abs(a*Cx + b*Cy + c) / Math.sqrt(a*a+b*b); return (dist <= Cr) ; } static int CircleCircleIntersection(double Cx, double Cy, double Cr, double Dx, double Dy, double Dr, double [] X1X2result ) { // Returns no. of intersections 0,1,2,3. Value 1 makes no sense in most cases for doubles. // X1X2result contains X1x, X1y, X2x, X2y coordinates. double distCDcenters = Math.sqrt( (Cx-Dx)*(Cx-Dx) + (Cy-Dy)*(Cy-Dy) ); // same centers if( distCDcenters == 0 ) { if( Cr == Dr ) return 3; // infinitely many intersections else return 0; // no intersection } // too far away from each other if( distCDcenters > Cr+Dr ) return 0; // one circle inside onother, no intersection if( (distCDcenters + Cr < Dr) || (distCDcenters + Cr < Dr) ) return 0; // touching outside if( distCDcenters == Cr+Dr ) { X1X2result[0] = Cx + (Dx-Cx) * Cr/distCDcenters; X1X2result[1] = Cy + (Dy-Cy) * Cr/distCDcenters; return 1; } // touching inside if( (distCDcenters + Cr == Dr) ){ // C inside D X1X2result[0] = Dx + (Cx-Dx) * (Cr+distCDcenters)/distCDcenters; X1X2result[1] = Dy + (Cy-Dy) * (Cr+distCDcenters)/distCDcenters; return 1; } if( (distCDcenters + Dr == Cr) ){ // C inside D X1X2result[0] = Cx + (Dx-Cx) * (Dr+distCDcenters)/distCDcenters; X1X2result[1] = Cy + (Dy-Cy) * (Dr+distCDcenters)/distCDcenters; return 1; } // E is the point where the line through the circle intersection points // crosses the line between the circle centers. // These lines are perpendicular to each other // Let I be the intersection, let h be the length of segment (I, E) \ // let a be the length of (C, E), let b be the length of (D E), // let d be = distCDcenters // then we have right angle triangles C E I and D E I: // (1) h^2 + a^2 = Cr^2, (2) h^2 + b^2 = Dr^2, also (3) a + b = d. // express b from (3) and substitute into difference (1)-(2), this // removes quadratic dependence and yields a easily. double d = distCDcenters; double a = (Cr*Cr - Dr*Dr + d*d) / (2*d); double h = Math.sqrt(Cr*Cr-a*a); double Ex = (Dx-Cx) * a/d; double Ey = (Dy-Cy) * a/d; double Ix = Ex + (Dy-Cy)*h/d; double Iy = Ey - (Dx-Cx)*h/d; X1X2result[0] = Ix; X1X2result[1] = Iy; Ix = Ex - (Dy-Cy)*h/d; Iy = Ey + (Dx-Cx)*h/d; X1X2result[2] = Ix; X1X2result[3] = Iy; return 2; } static boolean isSegmentIntersection (int Ax, int Ay, int Bx, int By, int Cx, int Cy, int Dx, int Dy) { int ABx = Bx - Ax ; int ABy = By - Ay; int CDx = Dx - Cx; int CDy = Dy - Cy; int det = ABy*CDx - ABx*CDy; // determinant decides linear (in)dependence if (det == 0) { // parallel vectors (linearly dependent) if ((Cx-Ax)*ABy - (Cy-Ay)*ABx != 0) // area triangle ABC return false; // parallel distinct lines // A B C D colinear, check their bounding boxes return Math.min(Ax, Bx) <= Math.max(Cx, Dx) && Math.min(Cx, Dx) <= Math.max(Ax, Bx) && Math.min(Ay, By) <= Math.max(Cy, Dy) && Math.min(Cy, Dy) <= Math.max(Ay, By) ; } // non parallel vectors, is point of intersection inside both segments? int num1 = (Ax-Cx)*CDy + CDx*(Cy-Ay); int num2 = (Cy-Ay)*ABx - ABy*(Cx-Ax); if (det < 0) return ((0 >= num1) && (num1 >= det) && (0 >= num2) && (num2 >= det)); else return ((0 <= num1) && (num1 <= det) && (0 <= num2) && (num2 <= det)); } }