Državno natjecanje 2018. / Osnovna škola (8. razred) - 2. zadatak

Na nogometnom turniru sudjeluje N momčadi. Svake dvije momčadi međusobno će odigrati jednu utakmicu. Jačina i-te momčadi je Ai. Kvaliteta utakmice u kojoj igraju i-ta i j-ta momčad je umnožak Ai*Aj.

Mirko je odlučio otići na dvije utakmice na turniru. Pri tome si je postavio uvjet da se kvalitete tih utakmica razlikuju za najviše M.

Muče ga dva pitanja.

Prvo pitanje: Na koliko načina uz postavljeni uvjet, može odabrati dvije utakmice koje će gledati?

Drugo pitanje: Na koliko načina uz postavljeni uvjet, može odabrati dvije utakmice koje će gledati ako nijednu ekipu ne želi gledati dva puta?

ULAZNI PODACI

U prvom retku nalaze se prirodni brojevi N i M (1 ≤ N ≤ 800, 1 ≤ M ≤ 100 000), brojevi iz teksta zadatka.

U drugom retku nalazi se N prirodnih brojeva Ai (1 ≤ Ai ≤ 1000).

IZLAZNI PODATCI

U prvom retku ispiši cijeli broj, odgovor na prvo pitanje iz zadatka.

U drugom retku ispiši cijeli broj, odgovor na drugo pitanje iz zadatka.

PRIMJERI TEST PODATAKA

Ulaz

4 5
1 2 3 4

Izlaz

10
2

Ulaz

3 3
2 1 2

Izlaz

3
0

Ulaz

6 10
4 4 1 1 5 4

Izlaz

51
15

Objašnjenje

Opis prvog primjera:

Parovi utakmica koji zadovoljavaju postavljeni uvjet su: ((1, 2), (1, 3)), ((1, 2), (1, 4)), ((1, 2), (2, 3)), ((1, 3), (1, 4)), ((1, 3), (2, 3)), ((1, 3), (2, 4)), ((1, 4), (2, 3)), ((1, 4), (2, 4)), ((2, 3), (2, 4)) i ((2, 4), (3 4)), gdje ((x1, x2), (y1, y2)) predstavlja par utakmica kluba x1 protiv kluba x2 i kluba y1 protiv kluba y2.

Od njih su samo parovi utakmica ((1, 3), (2, 4)) i ((1, 4), (2, 3)) takvi da Mirko nijednu ekipu neće gledati dva puta.