Finále

B: Roboti na přímce

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

Přímku ze zadání si představíme vodorovně, nižší čísla souřadnic budou vlevo a vyšší čísla vpravo. Levého robota si označíme Karel A, pravého Karel B (může se stát, že oba roboti začínají na stejném místě, ale to ničemu nevadí). Všimněme si, že díky rychlosti 1 m/s odpovídají časy vzdálenosti pozic, kterou snadno spočítáme jako absolutní hodnotu jejich rozdílu.

Nejprve si představme, že máme pouze jednoho robota, a rozmysleme si, jakými způsoby může sbírat balíčky a který z nich je nejvýhodnější. Například mějme robota na počáteční pozici 10 a balíčky na pozicích 6, 8, 12, 13. Robot určitě musí někdy dojet pro balíček úplně vlevo. Při tom vždy cestou sebere i ten na pozici 8, takže o něj se dále nemusíme starat. Podobně musí dojet i na pozici 13 a cestou vždy sebere balíček na pozici 12. Důležíté jsou pro nás tedy jen krajní balíčky. Určitě se vyplatí nejdřív dojet na jeden okraj a pak rovnou na ten druhý, jakékoli ježdění tam a zpátky cestu jen prodlužuje. Robot má tedy dvě možnosti: buď nejdřív dojede pro balíček úplně vlevo a pak pro balíček úplně vpravo (to mu v našem konkrétním příkladě bude trvat |10-6|+|6-13| = 11 s), nebo naopak nejdřív pro balíček úplně vpravo a pak pro balíček úplně vlevo (|10-13|+|13-6| = 10 s). Výsledek tedy dokážeme spočítat v konstantním čase.

Když máme roboty dva, můžeme si všimnout, že nemá smysl, aby se jejich trasy překrývaly. Pokud totiž někudy projede jeden z robotů, vysbírá cestou všechny balíčky, a tedy není žádný důvod, aby tam jel i druhý robot. Proto si můžeme dovolit rozdělit přímku na dvě oblasti, kdy levou z nich posbírá Karel A a pravou Karel B. Mohou nastat následující 3 možnosti. Řešením celé úlohy je nejrychlejší z nich.

  1. Karel A posbírá všechno.

    To je případ, kdy pracujeme jen s jedním robotem, takže postupujeme podle výše uvedeného rozboru. Vezmeme tedy rychlejší z variant, kdy Karel A jede nejprve úplně vlevo a pak úplně vpravo a nebo nejprve úplně vpravo a pak úplně vlevo.

  2. Karel B posbírá všechno.

    Obdobně jako v minulém případě.

  3. Karel A sbírá levou část, Karel B pravou

    V tomto případě bude nějaký balíček nejpravějším v levé části a nějaký nejlevějším v pravé části. Konkrétně vyzkoušíme všechny takové možnosti předělu. Když bude předěl mezi balíčky i a i+1, Karel A projde oblast mezi nejlevějším a i-tým balíčkem a Karel B mezi (i+1)-ním a nejpravějším. Uvnitř oblasti opět aplikujeme výše uvedený postup a vezmeme rychlejší z možností. Ale jako výsledek musíme brát vyšší z časů obou robotů.

Vidíme, že stačí jako předěly vyzkoušet všechna i od 0 do N-1. Díky tomu, že souřadnice balíčků jsou setřízené, tak hned víme, že (i+1)-ní balíček bezprostředně následuje po i-tém, a tedy v konstantním čase dokážeme spočítat výsledek.

Časová složitost celé úlohy je O(N).

Ukázkový program (Python3)

def solve():
    a,b = [int(i) for i in input().split()]
    n = int(input())
    packets = [int(i) for i in input().split()]
    A = min(a,b) # left robot
    B = max(a,b) # right robot
    left = min(packets)
    right = max(packets)

    min_dist = 2147483647 # max 32bit int
    for i in range(len(packets) - 1): # split between two packets
        dist_a = min(abs(A - left) + abs(left - packets[i]), abs(A - packets[i]) + abs(packets[i] - left))
        dist_b = min(abs(B - right) + abs(right - packets[i+1]), abs(B - packets[i+1]) + abs(packets[i+1] - right))
        if (max(dist_a, dist_b) < min_dist):
            min_dist = max(dist_a, dist_b)
    # A all
    dist_a = abs(left - right) + min(abs(A - left), abs(A - right))
    if (dist_a < min_dist):
            min_dist = dist_a
    # B all
    dist_b = abs(left - right) + min(abs(B - left), abs(B - right))
    if (dist_b < min_dist):
            min_dist = dist_b
    print(min_dist)

T = int(input())
for t in range(T):
    solve()

Ukázkový program (C++)

#include <iostream>
#include <vector>
#include <algorithm>

inline int diff(int a, int b) // distance of two points
{
	return std::abs(a - b);
}

void solve() {
	// parse input
	unsigned A, B, N;
	std::cin >> A;
	std::cin >> B;
	std::cin >> N;
	std::vector<int> packets;
	for (unsigned i = 0; i < N; i++)
	{
		int num;
		std::cin >> num;
		packets.push_back(num);
	}

	int KarelL = std::min(A, B); // left robot
	int KarelR = std::max(A, B);
	int left = *std::min_element(packets.begin(), packets.end()); // leftmost packet
	int right = *std::max_element(packets.begin(), packets.end());

	int result = INT_MAX;
	// try splitting between two packets
	for (int i = 0; i < packets.size() - 1; i++)
	{
		int dist_l = std::min( // left robot picks packets from the leftmost to i-th
			diff(KarelL, left) + diff(left, packets[i]),
			diff(KarelL, packets[i]) + diff(packets[i], left)
		);
		int dist_r = std::min( // right robot picks packets from the (i+1)-th to the rightmost
			diff(KarelR, right) + diff(right, packets[i+1]),
			diff(KarelR, packets[i+1]) + diff(packets[i+1], right)
		);
		if (std::max(dist_l, dist_r) < result)
			result = std::max(dist_l, dist_r);
	}

	// left robot picks everything
	int dist_l = std::min(
		diff(KarelL, left) + diff(left, right),
		diff(KarelL, right) + diff(right, left)
	);
	if (dist_l < result)
		result = dist_l;

	// right robot picks everything
	int dist_r = std::min(
		diff(KarelR, left) + diff(left, right),
		diff(KarelR, right) + diff(right, left)
	);
	if (dist_r < result)
		result = dist_r;

	// print result
	std::cout << result << std::endl;
}

int main() {
	int T;
	std::cin >> T;
	while (T--)
		solve();
	return 0;
}

Máš na to!

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