Domácí kolo

C: Lampy

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Zadání

Zuzka jde večer ze školy dlouhou ulicí, ve které jsou pouliční lampy. Všechny lampy jsou identické, jsou ve stejné výšce a dosvítí do stejné vzdálenosti. Lampy jsou symetrické, tedy maximální dosah, kam dosvítí na pravé straně, je stejný jako maximální dosah na straně levé.

Vzdálenost mezi sousedními lampami v ulici může být různá. Zuzka si pro každou lampu zaznamenala vzdálenost od začátku ulice. Chce si spočítat minimální vzdálenost, do které musí dosvítit každá lampa, aby byla celá ulice osvětlená.

Počet lamp na ulici je N. Pro i-tou lampu máte zadánu hodnotu a_i, její vzdálenost v metrech od začátku ulice. Vaším úkolem je spočítat hodnotu X, minimální vzdálenost (opět v metrech), do které musí dosvítit všechny lampy, aby byla celá ulice osvětlená. Předpokládáme, že první lampa je hned na začátku ulice a nejvzdálenější lampa je právě na konci ulice.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku číslo N, počet lamp. Na dalším řádku je N čísel a_1, a_2, \dots, a_N, která udávají vzdálenost jednotlivých lamp od začátku ulice.

Vzdálenosti jsou nezáporná celá čísla.

Tvar výstupu

Pro každý problém vypište jeden řádek s číslem X, které udává nejmenší možnou vzdálenost, do které musí každá lampa dosvítit, aby byla ulice celá osvětlená. X může být i desetinné číslo. Desetinná čísla vypisujte s desetinnou tečkou (to za vás pravděpodobně zařídí už váš programovací jazyk).

Lehká verze

  • 1 \leq T \leq 10
  • 2 \leq N \leq 10^4
  • 0 \leq a_i \leq 10^6
  • Vzdálenosti lamp od počátku ulice, a_i, jsou seřazené od nejbližší lampy k nejvzdálenější.
  • Vzdálenosti lamp od počátku ulice jsou sudá čísla.

Těžká verze

  • 1 \leq T \leq 10
  • 2 \leq N \leq 10^4
  • 0 \leq a_i \leq 10^6
  • Vzdálenosti lamp od počátku ulice, a_i, nejsou nutně seřazené.

Ukázkový vstup

3
3
0 16 28
4
9 30 0 32
5
80 20 0 40 60

Ukázkový výstup

8
10.5
10.000

Vysvětlení ukázkového vstupu a výstupu

Podívejme se podrobněji na první příklad. Podle ukázkového výstupu stačí, když každá lampa dosvítí do vzdálenosti 8 metrů. Když si ulici projdeme celou, uvidíme, že to stačí. První lampa je na pozici 0 a dosvítí tak až do bodu, který je vzdálený od počátku ulice 8 metrů. Druhá lampa je ve vzdálenosti 16 metrů od počátku. Dosvítí tak od bodu, který je 8 metrů od počátku až do bodu, který je vzdálen 24 metrů od počátku ulice. Poslední lampa je na konci ulice ve vzdálenosti 28 metrů od začátku. Ta dosvítí za těchto okolností od bodu, který je ve vzdálenosti 20 metrů od počátku ulice, až do konce. Celá ulice tak bude osvětlená. Kdyby lampy dosvítily do kratší vzdálenosti než 8 metrů, bude bod ve vzdálenosti 8 metrů od počátku ulice neosvětlený. Správná odpověď pro první problém je tak 8.

První ukázkový vstup je příklad lehké varianty, vzdálenosti jsou seřazené a jsou to všechno sudá čísla. Druhý a třetí vstup by bylo možné najít jen u těžší verze úlohy. Připomínáme, že výsledkem mohou být i desetinná čísla a čísla celá můžete zapsat čísly desetinnými.

Máš na to!

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