Fişierul intrare/ieşire:amiba.in, amiba.outSursăLot Seniori Tulcea 2018, baraj 1
AutorAdrian BudauAdăugată deTiberiu02Tiberiu Musat Tiberiu02
Timp execuţie pe test2 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Amiba

Plictisiţi de teoriile evoluţioniste, legile fizicii cuantice şi tabla înmulţirii, fraţii amiba (trei la număr: Şeful, Slabul şi Micuţul) s-au decis să joace un joc clasic de cărţi: Război în Trei.

Regulile jocului sunt simple: fiecare din cei 3 jucători are N cărţi numerotate cu valori de la 1 la 3 * N. Toate cele 3 * N cărţi sunt distincte, iar jocul constă în N runde. La o rundă fiecare jucător alege o carte pe care să o joace. Cartea cu valoarea cea mai mare îi aduce deţinătorului A puncte, în timp ce a doua cea mai mare carte aduce B puncte (se garantează că AB).

Enervaţi de atitudinea arogantă a fratelui mai mare, Slabul şi Micuţul s-au decis să se alieze. Singurul lor scop în acest joc este să minimizeze scorul fratelui lor (Şeful), deci nu contează cât obţine fiecare independent. Din păcate, aceştia nu prea ştiu să citească ce numere sunt scrise pe cărţile lor. Astfel, singura lor strategie este să joace prima carte din mână şi să se roage la zeul Amibus să câştige.

Ştiind cărţile fiecărui jucător, precum şi ordinea în care fratele Şeful îşi joacă mâinile, scopul vostru este să selectaţi o ordine pentru ceilalţi 2 fraţi astfel încât să minimizaţi scorul primului. Dacă reuşiţi, Zeul Amibus vă va recompensa cu 100 de puncte.

Date de intrare

Fişierul de intrare amiba.in va conţine pe prima linie un număr natural T (numărul de teste), urmat de T teste. Fiecare test va fi descris prin 4 linii:

  • Pe linia 1 se vor găsi 3 numere naturale: N, A şi B cu semnificaţia din enunţ.
  • Pe linia 2 se vor găsi N numere naturale distincte din intervalul [1, 3 * N] reprezentând cărţile primului jucător (Şeful). Acesta va juca cărţile fix în ordinea dată.
  • Pe linia 3 se vor găsi N numere naturale distincte din intervalul [1, 3 * N] reprezentând cărţile celui de al doilea jucător (Slabul).
  • Pe linia 4 se vor găsi N numere naturale distincte din intervalul [1, 3 * N] reprezentând cărţile celui de al treilea jucător (Micuţul).

Date de ieşire

În fişierul de ieşire amiba.out va conţine răspunsurile pentru fiecare din cele T teste, reprezentate prin 2 linii:

  • Linia 1 va conţine N numere naturale reprezentând cărţile celui de al doilea jucător (Slabul) în ordinea în care le va juca.
  • Linia 2 va conţine N numere naturale reprezentând cărţile celui de al treilea jucător (Micuţul) în ordinea în care le va juca.

Dacă există mai multe soluţii care minimizează scorul primului jucător (Şeful), o puteţi afişa pe oricare.

Restricţii

  • T ≤ 500
  • suma valorilor lui N ≤ 1 001 000
  • A, B numere naturale cu 0 ≤ B ≤ A ≤ 1 000 000 000
  • Teste în valoare de 15 puncte vor avea doar A=1 şi B=0
  • Teste în valoare de 15 puncte vor avea doar A=1 şi B=1
  • Teste în valoare de 40 puncte vor avea T ≤ 100, suma valorilor lui N ≤ 10 000 şi N ≤ 1000
  • Teste în valoare de 60 puncte vor conţine suma valorilor lui N ≤ 101 000

Exemplu

amiba.inamiba.outExplicaţie
2
6 10 8
1 10 17 14 7 11
8 2 15 12 4 16
13 5 6 3 9 18
6 10 4
1 10 17 14 7 11
8 2 15 12 4 16
13 5 6 3 9 18
4 12 2 16 8 15
6 5 3 18 9 13
4 12 2 16 8 15
6 13 18 3 9 5
T=2, avem două teste.
Primele două linii din fişierul de ieşire reprezintă
răspunsul pentru primul test, iar următoarele două
linii reprezintă răspunsul pentru al doilea test.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?