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)\).
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;
}
}#include <iostream>
#include <algorithm>
using namespace std;
// zbir brojeva x i y po modulu n
long long zm(long long x, long long y, long long n) {
return ((x % n) + (y % n)) % n;
}
// proizvod brojeva x i y po modulu n
long long pm(long long x, long long y, long long n) {
return ((x % n) * (y % n)) % n;
}
// vrednost izraza (z * x) mod (z * y)
long long pmp(long long x, long long y, long long z) {
return z * (x % y);
}
// izracunavanje Bezuovih koeficijenata prosirenim Euklidovim
// algoritom - nakon primene funkcije vazi:
// s*a + t*b = nzd(a, b)
// pri cemu funkcija vraca vrednost nzd(a, b)
long long bezu(long long a, long long b, long long& s, long long& t) {
long long r0 = a, r1 = b;
long long s0 = 1, s1 = 0;
long long t0 = 0, t1 = 1;
while (r1 > 0) {
long long q = r0 / r1;
long long tmp;
tmp = r0;
r0 = r1;
r1 = tmp - q*r1;
tmp = s0;
s0 = s1;
s1 = tmp - q*s1;
tmp = t0;
t0 = t1;
t1 = tmp - q*t1;
}
s = s0; t = t0;
return r0;
}
// kineska teorema o ostacima za dva broja
bool kto(long long a1, long long n1, long long a2, long long n2,
long long& r) {
long long m1, m2;
// izracunavamo Bezuove koeficijente tako da je m1*n1 + m2*n2 = nzd(n1, n2)
long long d = bezu(n1, n2, m1, m2);
// proveravamo da li resenje postoji
if (a1 % d != a2 % d)
return false;
// resenje je (a1*m2*(n2/d) + a2*m1*(n1/d)) % (n1*n2/d),
// ali zbog prekoracenja sve operacije radimo po modulu
long long n = (n1 / d) * n2;
r = zm(pmp(pm(a1, m2, n), n1, n2 / d),
pmp(pm(a2, m1, n), n2, n1 / d), n);
// popravak ako je resenje eventualno negativno
if (r < 0)
r += n;
return true;
}
int main() {
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;
}
}
return 0;
}