Diferente pentru problema/bfs2 intre reviziile #4 si #9

Nu exista diferente intre titluri.

Diferente intre continut:

Copiii de la 402 au auzit clopoţelul şi au ieşit repede afară să se joace. Văzând un stâlp foarte mare în mijlocul terenului ei s-au gândit la următorul joc. Iniţial s-au împărţit în fete şi băieţi (în număr de $M$, respectiv $N$) şi s-au aşezat astfel:
!=problema/bfs2?gang1.jpg!
p=. !problema/bfs2?gang1.jpg!
Stâlpul e în poziţie verticală (înclinare $0$). Fiecare jucător are o anumită forţă ($B[i]$ - forţa băiatului $i$, $F[i]$ - forţa fetei $i$). Jocul decurge astfel: la fiecare pas, fie băiatul cel mai apropiat de stâlp, fie fata cea mai apropiată de stâlp, va arunca mingea spre stâlp (băiatul spre dreapta, fata spre stânga), după care va ieşi din joc. După orice aruncare, stâlpul se va înclina suplimentar în partea opusă aruncătorului cu o valoare egală cu forţa acestuia. Bineînţeles, cu cât forţa aruncătorului este mai mare, cu atât stâlpul se va înclina mai mult. Mai mult, stâlpul nu va reveni la înclinarea iniţială după aruncare.
Stâlpul e în poziţie verticală (înclinare $0$). Fiecare jucător are o anumită forţă ( $B[i]$ - forţa băiatului $i$, $F[i]$ - forţa fetei $i$). Jocul decurge astfel: la fiecare pas, fie băiatul cel mai apropiat de stâlp, fie fata cea mai apropiată de stâlp, va arunca mingea spre stâlp (băiatul spre dreapta, fata spre stânga), după care va ieşi din joc. După orice aruncare, stâlpul se va înclina suplimentar în partea opusă aruncătorului cu o valoare egală cu forţa acestuia. Bineînţeles, cu cât forţa aruncătorului este mai mare, cu atât stâlpul se va înclina mai mult. Mai mult, *stâlpul nu va reveni la înclinarea iniţială după aruncare.*
!=problema/bfs2?gang2.jpg!
p=. !problema/bfs2?gang2.jpg!
Cu toate acestea, pentru ca jocul să nu capete întorsături neplăcute de situaţie, stâlpul nu are voie niciodată să fie înclinat cu o valoare strict mai mare decât $S$ (în niciuna din părţi), atât în timpul jocului, cât şi la finalul acestuia.
h2. Date de intrare
Fişierul $bfs.in$ conţine pe prima linie trei numere $N, M$ şi $S$ reprezentând numărul de băieţi, numărul de fete şi înclinarea maximă admisă a stâlpului. Pe a doua linie se vor găsi $N$ numere naturale reprezentând forţele băieţilor. Pe a treia linie se vor găsi $M$ numere naturale reprezentând forţele fetelor. Pe a patra linie se va găsi $Q$ reprezentând numărul de interschimbări efectuate. Urmează $Q$ linii de forma $“[B|F] x y”$ (fără ghilimele), unde $[B|F]$ reprezintă în ce grup se face interschimbarea, iar $x$ şi $y$ reprezintă poziţiile între care se realizează interschimbarea.
Fişierul $bfs2.in$ conţine pe prima linie trei numere $N, M$ şi $S$ reprezentând numărul de băieţi, numărul de fete şi înclinarea maximă admisă a stâlpului. Pe a doua linie se vor găsi $N$ numere naturale reprezentând forţele băieţilor. Pe a treia linie se vor găsi $M$ numere naturale reprezentând forţele fetelor. Pe a patra linie se va găsi $Q$ reprezentând numărul de interschimbări efectuate. Urmează $Q$ linii de forma $“[B|F] x y”$ (fără ghilimele), unde $[B|F]$ reprezintă în ce grup se face interschimbarea, iar $x$ şi $y$ reprezintă poziţiile între care se realizează interschimbarea.
h2. Date de ieşire
Fişierul $bfs.out$ conţine $Q$ linii, astfel pe linia $i$ aflându-se valoarea $1$, dacă jocul se poate termina cu succes dupa primele $i$ interschimbări şi $0$ în caz contrar.
Fişierul $bfs2.out$ conţine $Q$ linii, astfel pe linia $i$ aflându-se valoarea $1$, dacă jocul se poate termina cu succes dupa primele $i$ interschimbări şi $0$ în caz contrar.
h2. Restricţii
* $1 ≤ N, M, Q ≤ 100 000$
* $1 ≤ B[i], F[i], S ≤ 109,$ pentru orice $i$
* $1 ≤ B[i], F[i], S ≤ 10^9^,$ pentru orice $i$
* Pentru fiecare schimbare se garantează că $|x - y| = 1$
* Se garantează că, înainte de efectuarea primei interschimbări, jocul se poate termina cu succes.
* Pentru teste în valoare de $10$ puncte $N, M ≤ 100$ şi  $Q ≤ 250$
* Pentru alte teste în valoare de $20$ puncte $N,M ≤ 2500$ şi  $Q ≤ 6000$
* Pentru alte teste în valoare de $65$ puncte $N,M ≤ 100000$ şi  $Q ≤ 35000$
* *Se garantează că, înainte de efectuarea primei interschimbări, jocul se poate termina cu succes.*
* Pentru teste în valoare de $10$ puncte $N, M ≤ 100$ şi $Q ≤ 250$
* Pentru alte teste în valoare de $20$ puncte $N,M ≤ 2500$ şi $Q ≤ 6000$
* Pentru alte teste în valoare de $65$ puncte $N,M ≤ 100000$ şi $Q ≤ 35000$
h2. Exemplu
table(example). |_. bfs2.in |_. bfs2.out |
|
6 3 30000
|6 3 30000
15000 15000 60000 30000 29805 56555
60000 60000 57187
14
B 2 3
F 2 3
F 2 3
|
0
|0
1
0
1

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.