Google Analytics Report… on USS Enterprise

Lt. Comandantul Data de pe nava USS Enterprise, este un mare web-designer. El s-a gândit că ar vrea să știe cât de accesate sunt paginile de pe site-urile pe care el le-a făcut pentru echipajul navei. Cum în spațiu ei nu au acces la Google Analytics ar vrea să îl ajutați. Pentru asta o să vă dea un fișier cu toate accesările paginilor, și voi trebuie să întocmiți un clasament al celor mai vizionate site-uri. Dar cum acest fișier poate conține foarte multe site-uri el s-a gândit să vă ajute și să ceară decât site-urile care se află pe anumite poziții.

Cerință

Dându-se un fișier cu toate accesările care s-au făcut pe server trebuie întocmit topul celor mai vizionate pagini de către IP-uri distincte (adică de pe calculatoare distincte). Numele fișierelor de intrare și iesire vor fi transmise ca argumente ale liniei de comandă (./executabil in out). În fișierul de intrare aveți la începutul acestuia două numere N și Q.

N reprezintă numărul de accesări
Q numărul de poziții care se cer afișate

Pe următoarea linie sunt două valori datalimita și timplimita.

Următoarele N linii vor conține înregistrări despre accese la pagini de forma

Data Timp IP Pagina

Data – reprezintă ziua la care a fost făcut accesul
Timp – momentul de timp din zi la care a fost făcut accesul
IP – ip-ul de la care s-a făcut accesul
Pagina – adresa paginii care a fost accesată

Pe ultima linie a fișierului vom avea Q valori care reprezintă pozițiile din top care vor fi afișate. Afișarea se va face în ordinea cerută.

Cum nava spațială USS Enterprise este de foarte mult timp în spațiu, acest fișier conține înregistrări foarte vechi, care nu mai sunt de actualitate. Pentru a avea informații utile nu vom ține cont de înregistrările făcute anterior datei limită și a timpului limită. Adică toate înregistrările care au data mai mică decât data limită (sau data egală cu data limită și timpul mai mic decât timpul limită) vor fi ignorate la întocmirea raportului.

Data s-a gândit la faptul că două pagini distincte pot avea același număr de accesari distincte și atunci a zis că este necesar să rețină și numărul total de accesări, și acesta să fie al 2-lea criteriu de sortare al raportului. Dar cum și după acest criteriu putem avea pagini cu același număr de accese distincte și același număr total de accesări ca un al 3-lea criteriu aceste pagini se vor ordona crescător în ordine lexicografică.

Răspunsul unei interogări va fi de forma

Pagina Accese_Distincte Accese_Totale

Pagina – adresa paginii care a fost accesată
Accese_Distincte – numărul de accesări de la IP-uri distincte
Accese_Totale – numărul total de accesări

Dacă se cere o poziție mai mare decât numărul total de pagini distincte se va afișa -1.

Formatul datelor de intrare

$N$

$Q$

$DataLimita$

$TimpLimita$

$Data_{1}$

$Timp_{1}$

$IP_{1}$

$Pagina_{1}$

$...$

$Data_{N}$

$Timp_{N}$

$IP_{N}$

$Pagina_{N}$

$p_{1}$

$p_{2}$

...

$p_{Q}$

N, Q, DataLimita, TimpLimita sunt cele din enunț.
Data = data la care s-a înregistrat accesul
Timp = momentul din zi la care s-a înregistrat accesul
IP = Adresa IP de la care s-a înregistrat accesul
Pagina = Pagina care a fost accesată
p_i = poziția cu numărul i dintre cele cerute

Formatul datelor de ieșire

Q linii reprezentând răspunsul la fiecare interogare (pe linia i răspunsul la interogarea i).

Restricții și precizări

0 <= N <= 100 000
0 <= Q <= 10 000
1 <= Lungime pagina <= 100
IP-ul se va da de forma A₁.A₂.A₃.A₄ unde: 0 <= A_i <= 255
Data se va da sub forma An-Luna-Zi unde: An este din 4 cifre (ex: 1987), Luna este din 2 cifre (ex: 07), Zi este din 2 cifre (ex: 27).
Timpul se va da sub forma Ora:Minut unde: Ora este din 2 cifre (ex: 01), Minut este din 2 cifre (ex:30).

Exemplu

Intrare

10 5
2010-10-01 00:00
2010-11-27 19:27 192.168.0.1 www.google.ro
2010-09-27 19:27 192.168.0.2 www.google.ro
2010-11-27 19:27 192.168.1.3 www.google.ro
2010-10-01 19:27 192.168.0.3 www.google.ro
2010-11-27 19:27 192.168.0.5 www.abcnet.ro
2010-11-27 19:27 192.168.0.6 www.google.fr
2010-11-27 19:27 192.168.0.7 www.yahoo.com
2010-11-15 19:27 192.168.0.7 www.yahoo.com
2010-10-01 00:00 192.168.0.1 www.google.ro
2010-11-27 19:27 192.168.0.2 www.google.ro
1 5 3 2 4

Ieșire

www.google.ro 4 5
-1
www.abcnet.ro 1 1
www.yahoo.com 1 2
www.google.fr 1 1

Explicații

Topul este următorul:

google.ro 4 5
yahoo.com 1 2
abcnet.ro 1 1
google.fr 1 1

Primul loc este www.google.ro pentru că are 4 accesări distincte. Celelalte pagini au toate 1 accesare distinctă dar www.yahoo.com are 2 accesări în total și va fi înainte celorlalte care au 1 accesare în total. Între ultimele 2 s-a făcut departajare pe baza lexicografică și cum www.abcnet.ro este mai mic lexicografic va fi pe poziția a 3-a iar ultimul va fi www.google.fr .

Autor: Bogdan-Cristian Drutu

Data: 21.12.2010