Solutii ACM ICPC - Faza Nationala 2014-2015

Distanta

Se observa ca cel mai scurt drum este cel in care nu isi schimba de loc directia (alege o directie si merge drept in aceea). De aici deducem ca punctul de intersectie de sosire este intersectia dintre dreapta data si verticala sau orizontala ce trece prin punctul de plecare. Se alege distanta minima dintre punctul de plecare si aceste doua puncte de intersectie.

Paralelogram2

Solutia se bazeaza pe o observatie simpla: mijloacele laturilor unui patrulater formeaza intotdeauna un paralelogram (pentru demonstratie se poate arata ca laturile opuse sunt paralele doua cate doua deoarece sunt paralele cu diagonalele patrulaterului. (QED)

ABCacm

Problema este una clasica de exponentiere rapida.