Finále

B: Roboti na přímce

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

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Roboti Karel a Karel žijí na své přímce (souřadnicové ose). Dnes se z nebe na osu sneslo N balíčků, které chtějí posbírat. Je jedno, který z robotů každý balíček sebere, ale dohromady musejí sebrat všechny. Roboti se na přímce mohou míjet. Zjistěte, jak nejrychleji mohou posbírat všechny balíčky. Rychlost robotů je 1 m/s a balíček seberou okamžitě. Jakmile je sebrán poslední balíček, roboti končí (nevrací se zpět na startovní pozici).

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 dvě čísla oddělená mezerou, která udávají pozice robotů. Na druhém řádku je jedno číslo N. Na třetím řádku je N mezerou oddělených souřadnic balíčků. Souřadnice balíčků jsou setříděné od nejmenší po největší. Všechny souřadnice jsou udávané v metrech a jsou to celá čísla, která se vejdou do 32-bitového integeru.

Tvar výstupu

Pro každý problém vypište na samostatný řádek jedno číslo, které udává, kolik nejméně sekund robotům sbírání balíčků zabere.

Lehká verze

  • T ≤ 10
  • N ≤ 1 000

Těžká verze

  • T ≤ 10
  • N ≤ 1 000 000

Ukázkový vstup

1
5 12
3
3 8 13

Ukázkový výstup

6

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

První robot Karel pojede ze své počáteční pozice 5 doleva pro balíček na pozici 3, to mu bude trvat 2 sekundy. Druhý robot Karel sebere zbývající balíčky. To udělá nejlépe tak, že nejdřív pojede pro balíček úplně vpravo a pak teprve pro ten na souřadnicích 8. Celkem jim to bude trvat 6 sekund.

Máš na to!

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