Algoge Judge

Fotografisanje

Points: 1

Time limit: 1.0s

Memory limit: 127M

Problem type

Anastasija je kupila nov fotoaparat i želi da postane fotograf. Kako bi započela svoju fotografsku karijeru odlučila je da prvog dana fotografiše svoje drugare, besplatno.

Ona ima ukupno $N$ ~N~ drugara koje će fotografisati tog dana i oni su numerisani brojevima od $1$ ~1~ do $N$ ~N~. Svako od njenih drugara joj je rekao vreme u tom danu kada bi on želeo da ga Anastasija fotografiše. Dan ima $10^9$ ~10^9~ trenutaka koji su označeni celim brojevima od $1$ ~1~ do $10^9$ ~10^9~. Ona u jednom trenutku može fotografisati više ljudi, ako su svi oni izrazili želju da se fotografišu u istom trenutku.

Anastasija želi da poboljša ovaj raspored. Pošto nema mnogo vremena ona bira samo jednog drugara i briše njegov termin za fotografisanje. Ona zatim bira novi termin za njega istog dana u intervalu od $1$ ~1~ do $10^9$ ~10^9~, takav da najveća pauza između dva uzastopna fotografisanja bude što manja. Pritom, dozvoljeno je da upiše isti termin kao onaj koji je prethodno bio upisan.

Pomozite Anastasiji i umesto nje odaberite kom drugaru će da promeni termin i koje je vreme novog fotografisanja, kako ona ne bi gubila vreme i pripremila se što bolje za naporan prvi radni dan.

Ako ima više rešenja ispisati bilo koje.

Opis ulaza

U prvoj liniji standardnog ulaza se nalazi jedan ceo broj, $N$ ~N~, koji predstavlja broj Anastasijinih drugara koji će se fotografisati. U narednoj liniji se nalazi niz $T$ ~T~ od $N$ ~N~ celih broejeva, gde $T_i$ ~T_i~ predstavlja vreme za fotografisanje $i$ ~i~-tog drugara. Niz $T$ ~T~ je dat u neopadajućem poretku.

Opis izlaza

U jedinoj liniji standardnog izlaza se nalaze dva cela broja $X$ ~X~ i $Y$ ~Y~ gde $X$ ~X~ predstavlja indeks drugara koji menja termin, a $Y$ ~Y~ novo vreme za njegovo fotografisanje.

Primer 1

Ulaz

3
2 6 7

Izlaz

1 5

Primer 2

Ulaz

3
2 4 4

Izlaz

1 4

Primer 3

Ulaz

3
28 28 28

Izlaz

2 28

Objašnjenje primera

U prvom primeru je najbolje prvog drugara premestiti u trenutak 5 i tada je minimalna pauza 1. Moguće je i premestiti ga u trenutak 6 ili 7, ali opet je minimalna pauza 1.

U drugom primeru je najbolje prvog drugara premestiti u trenutak 4 i tako neće biti pauze između termina za fotografisanje.

U trećem primeru nema pauze između fotografisanja i najbolje je sve ostaviti kako je bilo.

Ograničenja

U svim test primerima važi:

Niz $T$ ~T~ je sortiran neopadajuće.
$2 \leq N \leq 2 \cdot 10^5$ ~2 \leq N \leq 2 \cdot 10^5~
$1 \leq T_i \leq 10^9$ ~1 \leq T_i \leq 10^9~

Test primeri su podeljeni u 4 disjunktne grupe:

U test primerima vrednim 20 poena: $N = 3$ ~N = 3~.
U test primerima vrednim 20 poena: Razlika najmanjeg i najvećeg člana niza $T$ ~T~ je $1$ ~1~.
U test primerima vrednim 20 poena: $N \leq 100$ ~N \leq 100~
U test primerima vrednim 40 poena: nema dodatnih ograničenja.

Comments

0

iva_here_ commented on June 4, 2021, 12:58 a.m. ← edited →

Imam jedno pitanje: zasto u editorial-u pise pogresno uputstvo?

Pogresni deo glasi: Ukoliko se najveća razlika susednih članova niza pojavljuje na početku, odnosno na kraju niza, moguće je prostim izjednačavanjem prvog sa drugim članom niza, odnosno poslednjeg sa pretposlednjim članom u potpunosti eliminisati tu razliku.

Greska se lako moze uociti na test-primeru:

4

2 4 5 8

Najveca razlika je izmedju clanova 5 i 8 (a taj par brojeva se i nalazi na samom kraju niza). Naime, mi necemo menjati 8 u 5 (jer je tada maksimalna razlika 2), vec cemo menjati 8 u 3 i tako dobiti niz vremena 2 3 4 5, gde je maksimalna razlika 1. Nadam se da sam na neki nacin doprinela poboljsanju sajta. Pozdrav!

0

mihailot commented on June 11, 2021, 9:52 p.m.

Deo koji tvrdiš da je pogrešan nije kompletno rešenje zadatka, već samo razmišljanje koje vodi ka rešenju. U narednim pasusima se objašnjava i kompletno rešenje, koje podrazumeva upravo onaj postupak koji ti navodiš u svom primeru. Pozdrav :)