====== ACM MARATON 2016 ======

===== Kombinatorické hry =====

**Definice:** Kombinatorickou hrou budeme rozumět libovolnou hru splǔjící následující pravidla:
  - Hru hrají dva hráči, kteří se střídají v tazích.
  - Počet stavů, ve kterých se hra může nacházet, je vždy konečný.
  - Pravidla hry stanovují pro každého hráče v libovolném stavu hry jaké další tahy může zahrát.
  - Hra končí vítězně pro hráče, který zahrál naposledy, tedy prohrává ten hráč, který na začátku svého tahu nemá žádný platný tah. 
  - Hraje se s úplnou informací a bez náhody. 

<note>Pokud narazíme na hru, která nesplňuje výše uvedená pravidla, tak se nelekněte. Tato definice strikně vymezuje typy her, jež jsou naším primárním cílem se naučit řešit (hrát optimálně).</note>

<note tip> V některých níže uvedených hrách naschvál uvádím něco na způsob: //Zjistěte, pro které N, byste chtěli začínat.//. Tím bych chtěl trochu napovědět, že pokud hráči hrájí optimálně, stavy hry se budou dělit na (V)yhrávající a (P)rohrávající z pohledu začínajícího hráče. Zkuste při řešení nalézt pravidlo, podle kterého se jednotlivé stavy hry dělí na V a P a tím se nakonec dopracovat k odpovědi.
</note>

==== Hra #1: Odečítání dělitelů ====

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 #2: Lámání čokolády I ====

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.

==== Hra #3: Přičítání dělitelů ====
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?

==== Hra #4: Čísla v lahvi ====
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 #5: Lámání čokolády II ====

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 1x1. 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.

==== Hra #6: Odečítání prvočísel ====

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í.

==== Hra #7: Lámání čokolády III (Chomp) ====

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.

==== Hra #8: Odebírání sirek ====

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.

<note important>Následující 2 hry jsou zde uvedeny pro zajímavost, proto se je prosím nesnažte řešit, pokud neznáte odpovědi pro všechny hry uvedené výše.</note>

==== Hra #9: Odebírání sirek II ====

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.


==== Hra #10: Odebírání sirek III (Fibonacci Nim) ====

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.


==== Hra #11: Odebírání z hromádek ====
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á. 

==== Hra #12: Klasický NIM ====
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ě.

==== Hra #13: Upravený NIM ====
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ě.

==== Hra #14: Otáčení mincí ====

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 #15: Krájení koláče ====

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á.

==== Hra #16: Odebírání sirek IV ====
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á.

==== Zdroje ====

  * [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]]
  * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]]
  * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]]
  * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]]
  * Kombinatorické hry - krátká ilustrace ({{:courses:a4b36acm:combigames.pdf| pdf}}, {{:courses:a4b36acm:combigames.ppt| ppt}})
  * Nimbers (Sprague-Grundyho čísla) - ukázková úloha  ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{:courses:a4b36acm:pizza.pdf| s řešením}})
  * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]]

===== Intervalové stromy =====

V 1. [[https://docs.google.com/presentation/d/1352wnxlrrj9Z_CbBiDJvYYzlzFeewXV2x1jDkFee3aQ/edit?usp=sharing|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. [[https://docs.google.com/presentation/d/1CYN9f18bB2rZT0UtriKWoBh2IegniOvNdQvUT1fxaQY/edit?usp=sharing|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. [[https://docs.google.com/presentation/d/1D4beTIdSdPyBD_6ClYpxAhpIFweIwSxHErxwuLa0Glg/edit?usp=sharing|přednášce]] si představíme speciální "intervalový strom", který efektnivě pracuje s kumulativními součty v poli.

==== Úloha #1: Počet inverzí ====
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]).

==== Úloha #2: Rub či líc ====
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ů:
  * T <i> <j>: otoč všechny karty na pozicích i, i + 1, ..., j
  * Q <j>: odpověz na otázku: Je karta na pozici j lícem vzhůru?


===== Trocha geometrie =====

**Úlohy k řešení na A2OJ:** [[https://a2oj.com/standings?ID=28050| Contest 28050]].

**Některé související kódy:**

<code C>
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));
}


}
</code>