Problemi 074

Kërkesa

Ani po ecën me kalë në një rrugë të drejtë që shkon nga perëndimi në lindje. Ajo ndodhet në kilometrin 0 kurse vend-mbërritja e saj ndodhet në kilometrin D, ku kilometrat përgjatë rrugës shënohen nga perëndimi në lindje.

Janë edhe N kuaj të tjerë që po udhëtojnë në të njëjtën rrugë. Të gjithë ata do të vazhdojnë të udhëtojnë përgjithmonë, dhe të gjithë ndodhen midis Anit dhe vend-mbërritjes së saj. Fillimisht kali i ndodhet në kilometrin \(K_i\) dhe ecën me shpejtësinë e tij maksimale prej \(S_i\) kilometra në orë.

Kuajt janë shumë të sjellshëm dhe kali \(H_1\) nuk e parakalon një kalë tjetër \(H_2\) që ndodhet përpara tij. Dy ose më shumë kuaj mund të ndodhen në të njëjtën pikë për një kohë të çfarëdoshme; kuajt mund ti konsiderojmë sikur janë pika me përmasa të papërfillshme. Kuajt, përveç atij të Anit, vazhdojnë të ecin me shpejtësinë e tyre maksimale sa kohë që rruga para tyre është e lirë, por nqs u del përpara ndonjë kalë më i ngadaltë, atere e ulin shpejtësinë e tyre që të jetë njësoj me atë të kalit që kanë përpara.

Kurse kali i Anit nuk ka ndonjë shpejtësi maksimale dhe mund të ecë me një shpejtësi të çfarëdoshme që Ani mund të zgjedhë, sa kohë që përpara nuk i del ndonjë kalë më i ngadaltë. Për të pasur një udhëtim sa më të shtruar për veten dhe për kalin e saj, Ani do që të zgjedhë një shpejtësi të tillë që të mos ta ndryshojë shpejtësinë deri sa të arrijë në fund të udhëtimit, dhe të mos kalojë asnjë kalë tjetër. Cila është shpejtësia më e madhe që mund të zgjedhë?

Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000000130/0000000000000524

Shembull

$ cat input.txt
3
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

$ python3 prog.py < input.txt
Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

Dy rreshtat e parë janë D dhe N, pastaj për N rreshtat që vijojnë kemi \(K_i\) dhe \(S_i\).

Në rastin e parë më rrugë ndodhet vetëm një kalë shumë i ngadaltë, i cili do të arrijë vend-mbërritjen e Anit pas 25 orësh. Çdo shpejtësi më e madhe se 101 km/orë do bënte që Ani ta kalonte këtë kalë para se të mbërrinte në destinacion.

Në rastin e dytë janë 2 kuaj në rrugë. Ai më i shpejti e arrin më të ngadaltin te kilometri 240, pas 2 orësh. Pastaj të dy kuajt do të vazhdojnë të ecin me shpejtësinë e atij të ngadaltit edhe për një orë tjetër, deri sa të arrijnë në destinacionin e Anit, te kilometri 300. Shpejtësia më e madhe që mund të zgjedhë Ani pa kaluar ndonjë prej kuajve është 100 km/orë.

Zgjidhja

for t in range(int(input())):
    d, n = map(int, input().split())
    time_max = 0
    for i in range(n):
        k, s = map(int, input().split())
        time = (d - k) / s
        if time > time_max:
            time_max = time
    print('Case #{}: {:f}'.format(t+1, d / time_max))

Sqarime

Ky problem duket shumë i vështirë po ta krahasojmë me zgjidhjen, që nuk ka veçse 9 rreshta.

Shpejtësinë maksimale të mundshme kali i Anit mund ta ketë vetëm atere kur arrin në destinacion në të njëjtin moment me kalin që ka përpara (të cilin po e quajmë A). Kali A ose do arrijë në destinacion pa qenë i detyruar ta ulë shpejtësinë gjatë rrugës (dhe kështu do jetë kali i vetëm që e kufizon shpejtësinë e Anit), ose do ta ulë shpejtësinë në një pikë të caktuar për shkak të kalit që ka përpara (le ta quajmë B). E njëjta gjë vlen edhe për kalin B: ose do arrijë në destinacion duke ecur me shpejtësinë e tij maksimale, ose do jetë i detyruar ta ulë shpejtësinë gjatë rrugës për shkak të kalit që ka përpara. E kështu me radhë. Kështu që do jetë një kalë i vetëm kufizues që e përcakton se sa shpejt mund ta arrijë destinacionin kali i Anit. Mund të vërtetohet që ky është kali i vetëm që ka rëndësi, kurse të tjerët mund të mos ti marrim parasysh.

Është e qartë që kuajt në lindje të kalit kufizues mund të mos ti marrim parasysh sepse do kalojnë te destinacioni përpara se kali kufizues të vejë atje. Po kuajt që ndodhen midis Anit dhe kalit kufizues? Nga mënyra se si e përkufizuam kalin kufizues e dimë që çdo kalë i ndërmjetëm do ta arrijë kalin kufizues përpara destinacionit. (Nëse ndonjëri nuk e arrin, atere ky do ishte kali kufizues). E zëmë se Ani zgjedh një shpejtësi me të cilën arrin në destinacion në të njëjtën kohë me kalin kufizues. Një shpejtësi më e madhe se kjo do ishte e pamundur. Gjithashtu me një shpejtësi të tillë nuk mund të parakalojë ndonjë nga kuajt e ndërmjetëm, sepse kuajt e ndërmjetëm e arrijnë kalin kufizues përpara destinacionit, kurse kali i Anit e arrin atë pikërisht në destinacion.

Kështu që nqs gjejmë kalin kufizues zgjidhja është e thjeshtë: ec me një shpejtësi të tillë që të mbërrish në destinacion në të njëjtën kohë me kalin kufizues. Për të gjetur se cili është kali kufizues llogarisim se sa kohë i duhet secilit prej kuajve që të mbërrijë në destinacion prej aty ku është. Pikërisht kali që ka kohën më të madhe është kali kufizues. Këtë kohë mund ta përdorim për të llogaritur shpejtësinë e kalit të Anit.

Kjo zgjidhje e ka kohën të rendit \(O(N)\).

Detyra

Një kompani ka një strukture hierarkike si kjo në figurë:

Në krye është pronari i cili nuk varet nga askush, pastaj janë menaxherët, të cilët kanë disa vartës dhe varen nga një menaxher tjetër ose nga pronari, pastaj janë të punësuarit e thjeshtë, të cilët nuk kanë vartës. Kjo strukturë mund të paraqitet duke treguar për çdo person përgjegjësin e tij në këtë mënyrë: 0 1 1 2 2 3 Personi 1 nuk varet nga askush, prandaj përgjegjësi i tij është shënuar me 0. Personat 2 dhe 3 varen nga personi 1, personat 4 dhe 5 varen nga personi 2, dhe personi 6 varet nga personi 3.

Bëni një program që merr paraqitjen e hierarkisë në këtë formë dhe gjen se kush janë punonjësit e thjeshtë.

Referenca: https://www.codechef.com/problems/CHEFDETE

Shembull

$ cat input.txt
2
6
0 1 1 2 2 3
13
0 1 2 3 1 3 5 7 1 9 9 10 11

$ python3 prog.py < input.txt
4 5 6
4 6 8 12 13