Domácí kolo

D: Rybníčky

Řešení (Zadání úlohy)

Úlohu lze řešit různými způsoby.

Řešení 1: Simulace

Nasimulujeme průběh záplav. V každém kroku nás zajímá, který rybníček přeteče jako další. Vytvoříme frontu rybníčků podle času přetečení. V každém kroku ubereme rybníček na začátku (ten, který právě přetekl) a upravíme pozici ve frotě toho rybníčku, kam teče jeho voda.

Ačkoli je toto řešení přirozené, implementačně je náročnejší. Aby šlo s frontou pracovat rychle, je potřeba použít vyvážený binární strom. časová složitost je pak O(N*log(N)) kde N je počet rybníčků.

Řešení 2: Binární vyhledávání

Nejdříve zjistíme čas přetečení posledního rybníčku. Ten je v rozmezí 0 až 100 000 000. Označíme tento časový interval [a, b]. Spočítáme, jestli poslední rybníček přetekl v polovině tohoto intervalu (tedy v čase a + (b - a)/2) pomocí simulace. Pokud ano, opakujeme tento postup pro první polovinu intervalu [a, b], jinak pro druhou polovinu. Interval se tím rozpůlí, takže už po malém počtu kroků získáme dostatečně přesný odhad hledaného času.

Čas přetečení všech rybníčků najdeme podobným způsobem. Časová složitost je O(N*log(V)) kde N je počet rybníčků a V maximální objem.

Řešení 3 - Optimální: Slévání

Předchozí dvě řešení seběhla, ale existuje i teoreticky lepší řešení.

U každého ryníčku si navíc pamatujeme jeho přítok. Zpočátku je to vždy jedna. Všimneme si, že když pro dva po sobě jdoucí rybníčky platí, že horní přeteče dříve i kdyby do něj nic nepřiteklo z předchozích rybníčků, potom je řešení problému stejné jako když tyto dva rybníčky nahradíme jedním, který má objem rovný součtu objemů a přítok rovný součtu přítoků původních rybníčků.

Stačí najít dvojice takových rybníčků, kde:

(objem prvního)/(přítok prvního) < (objem druhého)/(přítok druhého)

a slévat je tak dlouho, dokud existuje taková dvojice. Zůstane nám kaskáda, ve které rybníčky přetékají od posledního k prvnímu. Čas přetečení posledního rybníčku je podíl jeho objemu a přítoku. Čas přetečení všech rybníčků je podíl objemu a přítoku prvního rybníčku.

Do situace, kdy už nelze nic slít, se dostaneme takto: Sléváme od pozice i=0.

  1. Pokud lze rybníček i slít se sousedem vlevo (i - 1), slij je a začni znova krokem 1
  2. Pokud lze rybníček i slít se sousedem vpravo (i + 1), slij je a začni znova krokem 1
  3. Zvyš i o jedna.
  4. Pokud i < počet ryníčků, pokračuj krokem 1

Časová složitost algoritmu je O(N).

Binární vyhledávání - Ukázkový program (Python3)

def verifyAll(ponds, time):
    additionalWater = 0.0
    for size in ponds:
        if time + additionalWater < size:
            return False
        additionalWater = additionalWater + time - size
    return True

def verifyLast(ponds, time):
    additionalWater = 0.0
    for size in ponds:
        if time + additionalWater < size:
            additionalWater = 0.0
        else:
            additionalWater = additionalWater + time - size
    return additionalWater > 0.0


def solveAll(ponds, over = float(10**9), under = 0.0):
    middle = (over + under)/2
    if over - under < 0.0001:
        return over
    if verifyAll(ponds,middle):
        return solveAll(ponds,middle,under)
    else:
        return solveAll(ponds,over,middle)


def solveLast(ponds, over = float(10**9), under = 0.0):
    middle = (over + under)/2
    if over - under < 0.0001:
        return over
    if verifyLast(ponds,middle):
        return solveLast(ponds,middle,under)
    else:
        return solveLast(ponds,over,middle)

T = int(input())
for test in range(T):
    N = input()
    ponds = list(map(int, input().split(' ')))
    print("{0:.2f} {1:.2f}".format(solveLast(ponds), solveAll(ponds)))

Slévání - Ukázkový program (Python3)

T = int(input())
for _ in range(T):
	N = int(input())
	objem = list(map(int, input().split()))
	# slite rybnicky ukladam jako [objem, pritok]
	slite = []
	suma = [objem.pop(), 1]
	# pracuji s posloupnosti
	# [obj[0], 1], [obj[2], 1] ... suma,  slite[-1] ... 
	for obj in reversed(objem):
		#mohu tento rybnik slit s tim NAD nim?
		#vyhneme se deleni v suma[0]/suma[1] > obj/1:
		if suma[0] > obj*suma[1]:
			suma[0] += obj
			suma[1] += 1

			while slite:
				#mohu vysledny rybnik slit s tim POD nim?
				#vyhneme se deleni v suma[0]/suma[1] < slite[-1][0]/slite[-1][1]:
				if suma[0]*slite[-1][1] < slite[-1][0]*suma[1]:
					v, p = slite.pop()
					suma[0] += v
					suma[1] += p
				else:
					break
		else:
			slite.append(suma)
			suma = [obj, 1]
	slite.append(suma)

	prvni    = slite[0][0]  / slite[0][1]
	posledni = slite[-1][0] / slite[-1][1]
	print('{:.2f} {:.2f}'.format(prvni, posledni))

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)