Problema Concurs 2

Un profesor de informatică își pregătește elevii pentru olimpiadă. El a strâns toate tipurile de algoritmi aparuti in concursuri inca de cand era el elev, n fiind numarul algoritmilor. Acestor algoritmi el le-a dat scoruri: 1, 2, 3, …, n. Se cunoaste k (k≤n), numarul de algoritmi care apar in acest tip de concursuri; k ramanand neschimbat de ani de zile. Cu o zi inainte de concurs profesorul le face elevilor sai o predictie, cam ce crede el ca s-ar da la concurs; fie aceasta vectorul a=[a[1], a[2], … a[k]], in care valorile (a[i], i=1,n) sunt distincte, a[i] fiind unul dintre algoritmi. Ceea ce efectiv se da la concurs este vectorul b=[b[1], b[2], … b[k]].

Nu conteaza ordinea in care fiecare elev isi rezolva cerintele, de aceea ordinea elementelor in multimile (a[1], a[2], …, a[k]) si (b[1], b[2], …, b[k]) este irelevanta deoarece configuratia (1, 2, 3) si configuratia (1, 3, 2) sunt formate din aceleasi tipuri de algoritmi. Configuratiile (1, 2, 3) si (1, 2, 4) sunt succesoare pentru ca nu exista o alta configuratie mai mare in sens lexicografic decat (1, 2, 3) si in acelasi timp mai mica in sens lexicografic decat (1, 2, 4).

Doi vectori x=[x[1], x[2], … x[k]] si y=[y[1], y[2], … y[k]] au distanta lexicografica 1 daca x si y reprezinta multimi succesoare in sens lexicografic. De exemplu intre multimile (1, 2, 3) si (2, 3, 4) distanta lexicografica este 5 deoarece exista 5 configuratii lexicografic succesoare intre (1, 2, 3) si (2, 3, 4) si anume: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5) si in final (2, 3, 4).

Cerință

1. Sa se afiseze 1 daca vectorul a=[a[1], a[2], …, a[k]] este mai mic decat vectorul b=[b[1], b[2], …, b[k]] in sens lexicografic, 0 daca cei doi vectori sunt egali lexicografic si -1 daca vectorul a este mai mare decat vectorul b in sens lexicografic.
2. Se cere distanta lexicografica dintre predictie (vectorul a) si realitatea din ziua concursului (vectorul b).

Date de intrare

Fisierul concurs.in va contine pe prima linie numerele n si k reprezentand n – numarul total de algoritmi si k – numarul de algoritmi care fac parte din cerintele concursului. Pe a doua linie se afla k numere naturale reprezentand predictia, pe a treia linie se afla cele k numere reprezentand ceea ce efectiv se da la concurs. Pe linia a patra este un numar natural care reprezinta numarul cerintei.

Date de ieșire

Fisierul concurs.out va contine un numar natural care reprezinta fie raspunsul la cerinta 1 fie raspunsul la cerinta 2.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 1000;
• 1 ≤ a[i] ≤ n, pentru orice i=1,k;
• 1 ≤ b[i] ≤ n, pentru orice i=1,k.

Exemple