Problemi 099
Kërkesa
Një qytet (le të themi Manhattan) i ka rrugët paralele me njëra tjetrën dhe të baraslarguara, në drejtimin veri-jug dhe lindje-perëndim, të tilla që formojnë një rrjetë të rregullt. Le të themi që kjo rrjetë ka formë katrore dhe le ti numërojmë rrugët në drejtimin veri-jug me numrat 0, 1, 2, …, Q, dhe po ashtu edhe rrugët në drejtimin lindje-perëndim me numrat 0, 1, 2, …, Q. Njerëzit në një moment të caktuar ndodhen në një kryqëzim rrugësh, p.sh. (0, 0) ose (1, 2), dhe shkojnë në destinacion në rrugën më të shkurtër, duke lëvizur sipas drejtimit të rrugëve.
Ti do që të shkosh te një piceri e famshme, por nuk e di se ku ndodhet. Ndërkohë, P nga shokët e tu janë gjithashtu në lëvizje dhe ti mendon se shumica e tyre po shkojnë pikërisht aty. Me anë të një programi që keni instaluar në celular ti mund të shikosh vendndodhjen e secilit prej tyre, p.sh. (x0, y0) dhe drejtimin në të cilin po lëvizin: N (north/veri) është drejtimi rritës i boshtit y, S (south/jug) drejtimi zbritës i boshtit y, E (east/lindje) drejtimi rritës i boshtit x, W (west/perëndim) drejtimi zbritës i boshtit x.
Gjeni kordinatat ku mund të ndodhet piceria. Nëse disa pozicione janë të mundshme, zgjidhni atë që ka kordinatat më të vogla.
Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/000000000012295c
Shembull
$ cat input.txt
3
1 10
5 5 N
4 10
2 4 N
2 6 S
1 5 E
3 5 W
8 10
0 2 S
0 3 N
0 3 N
0 4 N
0 5 S
0 5 S
0 8 S
1 5 W
$ python3 prog.py < input.txt
Case #1: 0 6
Case #2: 2 5
Case #3: 0 4Për çdo rast testimi jepen fillimisht numrat P dhe Q, pastaj janë P rreshta që përmbajnë kordinatat (x, y) dhe drejtimin e personave.
Në rastin e parë kemi vetëm një person në pozicionin (5, 5), i cili po shkon drejt veriut. Atere të gjitha pikat me kordinata y > 5 janë të mundshme, por si përgjigje zgjidhet ajo që i ka kordinatat më të vogla: (0, 6).
Në rastin e dytë janë 4 persona, të gjithë duke lëvizur në drejtim të pozicionit (2, 5). Nuk ka pozicion tjetër që të ketë 4 persona që mund të jenë duke shkuar drejt tij.
Në rastin e tretë, 6 nga 8 personat po shkojnë drejt pozicionit (0, 4). Nuk ka ndonjë pozicion tjetër që të ketë kaq shumë persona që mund të jenë duke shkuar drejt tij.
Zgjidhja 1
for t in range(int(input())):
P, Q = [int(i) for i in input().split()]
M = [[0 for i in range(Q+1)] for j in range(Q+1)]
for p in range(P):
x, y, d = input().split()
x = int(x)
y = int(y)
x1, x2, y1, y2 = 0, Q+1, 0, Q+1
if d == 'N': y1 = y + 1
if d == 'S': y2 = y
if d == 'E': x1 = x + 1
if d == 'W': x2 = x
for i in range(x1, x2):
for j in range(y1, y2):
M[i][j] += 1
x, y, nr = 0, 0, 0
for i in range(Q+1):
for j in range(Q+1):
if M[i][j] > nr:
x, y, nr = i, j, M[i][j]
print('Case #{}: {} {}'.format(t+1, x, y))Sqarime
Kjo zgjidhje mban një matricë me përmasa (Q+1)x(Q+1), dhe për çdo person të dhënë shton +1 te vendmbërritjet e mundshme ku ai mund të jetë duke shkuar. Në fund gjejmë atë pozicion që ka numrin e personave më të madh (dhe kordinatat x dhe y sa më të vogla).
Koha e kësaj zgjidhje është e rendit \(O(P*Q^2)\), kurse hapësira që zë në kujtesë e rendit \(O(Q^2)\). Për vlera të mëdha të Q kjo zgjidhje nuk është e përshtatshme.
Zgjidhja 2
for t in range(int(input())):
P, Q = [int(i) for i in input().split()]
Px = []
Py = []
for i in range(P):
x, y, d = input().split()
if d == 'E' or d == 'W':
Px.append((int(x), d))
else:
Py.append((int(y), d))
X = [0 for i in range(Q+1)]
for (x, d) in Px:
r1, r2 = (0, Q+1)
if d == 'E':
r1 = x + 1
else:
r2 = x
for i in range(r1, r2):
X[i] += 1
Y = [0 for i in range(Q+1)]
for (y, d) in Py:
r1, r2 = (0, Q+1)
if d == 'N':
r1 = y + 1
else:
r2 = y
for i in range(r1, r2):
Y[i] += 1
print('Case #{}: {} {}'.format(t+1, X.index(max(X)), Y.index(max(Y))))Sqarime
Mund të vëmë re se në këtë problem drejtimet X dhe Y janë të pavarur nga njëri-tjetri. Dmth kur një person po lëviz në drejtimin E ose W, vetëm kordinata x e tij ka rëndësi, dhe ndikon në përcaktimin e kordinatës x të destinacionit, kurse kordinata y e tij nuk ka ndikim. E njëjta gjë nëse lëviz në drejtimin N ose S, vetëm kordinata y e tij ka rëndësi kurse kordinata x nuk ka rëndësi. Kështu që kordinatat x dhe y të destinacionit mund ti gjejmë në mënyrë të pavarur nga njëra-tjetra.
Kjo bën që për të gjetur zgjidhjen të mos mbajmë një matricë me përmasa (Q+1)x(Q+1), por dy lista me përmasa (Q+1). Si rezultat, hapësira në kujtesë që duhet për këtë zgjidhje është e rendit \(O(Q)\). Por gjithashtu edhe koha e zgjidhjes është e rendit \(O(P*Q)\).
Zgjidhja 3
def min_key_max_value(D):
''' Return the minimum key that has the max value '''
min_key, max_value = 0, 0
for k in D.keys():
if (D[k] > max_value) or (D[k] == max_value and k < min_key):
min_key, max_value = k, D[k]
return min_key
for t in range(int(input())):
P, Q = [int(i) for i in input().split()]
Px = []
Py = []
for i in range(P):
x, y, d = input().split()
if d == 'E' or d == 'W':
Px.append((int(x), d))
else:
Py.append((int(y), d))
X = {0:0}
for (x, d) in Px: X[x+1] = 0
for (x, d) in Px:
for k in X.keys():
if (d == 'E' and x < k) or (d == 'W' and k < x):
X[k] += 1
Y = {0:0}
for (y, d) in Py: Y[y+1] = 0
for (y, d) in Py:
for k in Y.keys():
if (d == 'N' and y < k) or (d == 'S' and k < y):
Y[k] += 1
print('Case #{}: {} {}'.format(t+1, min_key_max_value(X), min_key_max_value(Y)))Sqarime
Kjo zgjidhje bazohet në faktin që jo të gjitha kordinatat x nga 0 në Q janë të mundshme si përgjigje. Meqenëse problemi na kërkon kordinatën më të vogël, atere si përgjigje e mundshme mund të jetë pika 0 ose pikat (x+1), ku x është kordinata e një prej personave që po lëvizin në drejtimin W-E. E njëjta gjë mund të thuhet edhe për kordinatat y.
Si rezultat kjo zgjidhje ka një kohë të rendit \(O(P^2)\) dhe hapësirë në kujtesë të rendit \(O(P)\), të cilat janë më të mira se zgjidhja e mëparshme nëse P < Q.
Zgjidhja 4
def min_key_max_value(D):
''' Return the minimum key that has the max value '''
min_key, max_value = 0, 0
for k in D.keys():
if (D[k] > max_value) or (D[k] == max_value and k < min_key):
min_key, max_value = k, D[k]
return min_key
for t in range(int(input())):
P, Q = [int(i) for i in input().split()]
Px = {}
Py = {}
for i in range(P):
x, y, d = input().split()
if d == 'E' or d == 'W':
p = Px.get(int(x), {'W': 0, 'E': 0})
p[d] += 1
Px[int(x)] = p
else:
p = Py.get(int(y), {'S': 0, 'N': 0})
p[d] += 1
Py[int(y)] = p
Kx = sorted(Px.keys())
W = sum([Px[k]['W'] for k in Kx])
X = {0: W}
for k in Kx:
W -= Px[k]['W']
W += Px[k]['E']
X[k+1] = W - Px.get(k+1, {'W': 0, 'E': 0})['W']
Ky = sorted(Py.keys())
S = sum([Py[k]['S'] for k in Ky])
Y = {0: S}
for k in Ky:
S -= Py[k]['S']
S += Py[k]['N']
Y[k+1] = S - Py.get(k+1, {'S': 0, 'N': 0})['S']
print('Case #{}: {} {}'.format(t+1, min_key_max_value(X), min_key_max_value(Y)))Sqarime
Nqs personat që po lëvizin në drejtimin X i rendisim sipas kordinatës x të tyre, atere është e mundur që përgjigjen për drejtimin X ta gjejmë në kohë lineare. Por vetë renditja faktikisht ka një kohë pak më shumë se lineare, kështu koha e kësaj zgjidhje është e rendit \(O(P*log(P))\) që është më e mirë se zgjidhja e mëparshme. Kurse hapësira në kujtesë është prapë e rendit \(O(P)\).
Detyra
Një shkop kërcimi pogo ka një sustë në fund dhe me të mund të hidhesh nga një vend në një vend tjetër, duke qëndruar mbi të. Por shkopi që ju kanë bërë dhuratë është i veçantë sepse herën e parë kërcen me një largësi 1 njësi, herën e dytë 2 njësi, herën e tretë 3 njësi, e kështu me radhë. Ju mund të kërceni në një nga këto drejtime: veri, jug, lindje, perëndim.
Nqs ndodheni në pikën (0, 0), si mund të shkoni në pikën (X, Y)? Si mund të shkoni me sa më pak kërcime?
Boshti X është sipas drejtimit S-N (jug-veri) dhe boshti Y është sipas drejtimit W-E (perëndim-lindje). Pika (X, Y) është e ndryshme nga (0, 0).
Referenca: https://code.google.com/codejam/contest/2437488/dashboard#s=p1&a=1
Shembull
$ cat input.txt
2
3 4
-3 4
$ python3 prog.py < input.txt
Case #1: ENWSEN
Case #2: ENSWNVini re që në rastin e parë ka edhe një rrugë tjetër që është më e shkurtër: WNSEN