Bilijar - Rešenje

Slučajevi kada se loptica ispaljuje paralelno sa ivicom stola su trivijalni i mogu se jednostavno direktno razrešiti. Pretpostavimo zato da je loptica ispaljena duž neke kose prave.

Obeležimo sa $r_x$ početno horizontalno rastojanje koje loptica pređe od njenog početnog položaja do leve tj. desne ivice stola ka kojoj se kreće čim se ispali. Rastojanje $r_x$ biće jednako nuli ako se loptica već nalazi na levoj ili desnoj ivici, biće jednako $x$ ako se loptica ispaljuje nalevo ili $m-x$ ako se ispaljuje nadesno. Tokom svog kretanja loptica se nalazi na levoj ili na desnoj ivici stola kada horizontalno pređe rastojanje $r_x$ , nakon toga kada dodatno pređe jednu širinu stola (kada pređe $r_x + m$ ), nakon toga kada dodatno pređe još jednu širinu stola (kada pređe $r_x + 2m$ ) i tako dalje. Dakle, loptica će biti na levoj ili desnoj ivici kada je dužina njenog pređenog puta u horiznotalnom pravcu jednako $r_x + k_xm$ , za neko celobrojno $k_x$ . Pošto je početno rastojanje $r_x$ do najbliže ivice uvek manje od širine stola $m$ , loptica će biti na levoj ili desnoj ivici ako i samo ako je ostatak pri deljenju horizontalnog rastojanja sa $m$ jednak $r_x$ . Slično, loptica će biti na gornjoj ili donjoj ivici stola ako i samo ako je ostatak pri deljenju vertikalnog rastojanja sa $n$ jednak $r_y$ , gde je $r_y$ početno rastojanje do gornje ili donje ivice ka kojoj je loptica ispaljena. Pošto je intenzitet horizontalne i vertikalne komponente brzine uvek jednak, ukupno horizontalno i vertikalno pređeno rastojanje biće uvek jednako. Dakle, loptica će biti u rupi kada horizontalno i vertikalno pređe najmanje rastojanje $r$ takvo da je ostatak pri deljenju $r$ sa $m$ jednako $r_x$ i kada je ostatak pri deljenju $r$ sa $n$ jednako $r_y$ .

Kada su $r_x$ i $r_y$ jednaki nuli (kada se loptica na početku nalazi u rupi), $r$ će biti NZS brojeva $m$ i $n$ .

Kada nisu, onda se $r$ može odrediti primenom Kineske teoreme o ostacima. Obratimo pažnju na to da brojevi $m$ i $n$ ne moraju biti uzajamno prosti, tako da se ne možemo direktno pozvati na osnovni oblik teoreme. Neka je $d$ najveći zajednički delilac brojeva $m$ i $n$ . Može se dokazati da lopta upada u rupu ako i samo ako brojevi $r_x$ i $r_y$ imaju isti ostatak pri deljenju sa $d$ .

Dokažimo prethodno tvrđenje. Zaista, pretpostavimo da je $r_x = q_x\cdot d + r'_x$ i da je $r_y = q_y\cdot d + r'_y$ , za $0 \leq r_x', r_y' < d$ . Ako bi postojao broj $r$ koji bi davao ostatak $r_x$ pri deljenju sa $m$ i ostatak $r_y$ pri deljenju sa $n$ , važilo bi da je $r = q_m\cdot m + r_x = q_n\cdot n + r_y$ . Pošto je $d$ delilac brojeva $m$ i $n$ važilo bi da je $q_m\cdot (m'\cdot d) + q_x\cdot d + r'_x = q_n (n'\cdot d) + q_y\cdot d + r'_y$ . Zato razlika $r'_x - r'_y$ mora biti deljiva sa $d$ , a pošto su oba ta broja manja od $d$ , oni moraju biti jednaki. Dakle, ako rešenje postoji, ostatak pri deljenju brojeva $r_x$ i $r_y$ sa $d$ mora biti isti. Dokaz suprotnog smera je konstruktivan i dat je u nastavku.

Ako brojevi $r_x$ i $r_y$ daju isti ostatak pri deljenju sa $d$ , tada zadatak možemo rešiti malo modifikovanom primenom Kineske teoreme o ostacima. Tvrdimo da će postojati jedinstven broj manji od najvećeg zajedničkog sadržaoca brojeva $m$ i $n$ (koji je jednak $(m\cdot n) / d$ ) koji pri deljenju sa $m$ daje ostatak $r_x$ , a pri deljenju sa $n$ daje ostatak $r_y$ .

Korišćenjem Bezuove teoreme izrazimo $d = c_m \cdot m + c_n \cdot n$ , za neke celobrojne koeficijente $c_m$ i $c_n$ . Skraćivanjem sa $d$ dobijamo da je $c_m \cdot (m/d) + c_n \cdot (n/d) = 1$ . Traženo rešenje je broj $(r_x \cdot c_n \cdot (n / d) + r_y \cdot c_m \cdot (m / d)) \,\mathrm{mod}\,((m\cdot n) / d)$ .

Prikaži kompletan kôd

int m, n, x, y, vx, vy;
cin >> m >> n >> x >> y >> vx >> vy;
if (vx == 0 && vy == 0)
  // loptica stoji
  cout << "-1" << endl;
else if (vx == 0) {    // loptica se krece samo vertikalno
  if (x != 0 && x != m)
    cout << "-1" << endl;
  else if (vy > 0)
    cout << x << " " << m << endl;
  else
    cout << x << " " << 0 << endl;
} else if (vy == 0) {  // loptica se krece samo horizontalno
  if (y != 0 && y != n)
    cout << "-1" << endl;
  else if (vx > 0)
    cout << m << " " << y << endl;
  else
    cout << 0 << " " << y << endl;
} else {               // loptica se krece dijagonalno
  // horizontalno rastojanje potrebno da loptica dodje do leve ili
  // desne ivice
  int rx = (vx > 0 ? (m - x) : x) % m;
  // vertikalno rastojanje potrebno da loptica dodje do gornje ili
  // donje ivice
  int ry = (vy > 0 ? (n - y) : y) % n;
  // horizontalno i vertikalno rastojanje koje loptica predje dok ne
  // upadne u rupu
  long long r;
  // rastojanje odredjujemo primenom KTO
  if (!kto(rx, m, ry, n, r))
    // loptica nikada ne upada u rupu
    cout << "-1" << endl;
  else {
    // prva ivica koju loptica dodirne
    int prva_ivica_x;        // 0 je leva, a 1 je desna
    if (x == 0)              // vec je na levoj ivici
      prva_ivica_x = 0;
    else if (x == m)         // vec je na desnoj ivici
      prva_ivica_x = 1;
    else                     // zavisi od brzine
      prva_ivica_x = vx < 0 ? 0 : 1;
    int prva_ivica_y;        // 0 je donja, a 1 je gornja
    if (y == 0)              // vec je na donjoj ivici
      prva_ivica_y = 0;
    else if (y == n)         // vec je na gornjoj ivici
      prva_ivica_y = 1;
    else                     // zavisi od brzine
      prva_ivica_y = vy < 0 ? 0 : 1;
    // broj prelaza stola koja loptica napravi
    long long broj_prelaza_x = (r - rx) / m;
    long long broj_prelaza_y = (r - ry) / n;
    // koordinate na kojima se loptica nalazi
    int rupax = (prva_ivica_x + broj_prelaza_x) % 2 == 0 ? 0 : m;
    int rupay = (prva_ivica_y + broj_prelaza_y) % 2 == 0 ? 0 : n;
    cout << rupax << " " << rupay << endl;
  }
}