Zadanie Szklanki ILOCAMP

Question

Siemka,

Pomoże ktoś w zadaniu Szklanki?

Narysowałem sobie kilka przykładów na kartce, próbowałem wypatrywać jakieś zalżności, ale jedyne co zdołałem wygłówkować, to, że mogę obliczyć średnią z tych wysokości i zapisać gdzieć indeksy szklanek z deficytem / nadmiarem.

Zauważyłem, że jeśli mam po jednej szklance z nadmiarem i deficytem to odpowiedzią będzie odległość między nimi. Problem pojawia się jednak, gdy szklanek z których zamierzamy odlewać / dolewać będzie więcej.

Prosiłbym o nakierowanie / pomoc w zadaniu.

 

PS. LOL, zrobiłem program obsługujący przypaek najłatwiejszy, tj jeden deficyt i nadmiar i działa mi na 40%, a testy, które nie działają różnią się o badzo mało:

kod: https://ideone.com/Nroz0y

wyniki:

Dzięki z góry za nadsyłane komentarze :D

Answer 1

Zadanko sprowadza się do jednej pętli for, z maks 10 linijkami.

Idziesz sobie forem po szklankach od tej o idx-ie 0, do tej o idx-ie n-2. W A[i] trzymasz poziom wody aktualnie w szklance. Na początku wczytujesz to z wejścia. Zauważ, że tutaj jedyne opcje jakie masz to przelanie do sąsiada z jednej strony. Nie ma tak, że do szklanki o idx-ie 0 możesz przelać z tej o idx-ie 1 i n-1, tylko jest tak, że opcje masz tylko z szklanki o idx-ie 1.

K = suma_na_wejsciu / n (tyle na końcu musi być w każdej szklance)

1 - I teraz jeśli A[i] == K, to zostawiasz, nie opłaca ci się przelwać

2 - Jeśli A[i] > K, to musisz przelać wodę do szklanki o idx-ie i+1, skoro w wszystkich na lewo(tych o mniejszych idx-ach woda już pasi)

3 - Jesli A[i] < K, to musisz przelac wodę z szklanki o idx-ie i+1 do tej o idxie i.

Przy przelewaniu dodajesz do wyniku 1

Zauważ, że for (int i = 0; i < n-1; ++i), bo w szklance o idxie n-1 już po wykonaniu tego algorytmu będzie dokładnie K wody. Oczywiście o ile dane na wejściu są poprawne (ale to chyba mamy zagwarantowane (mi tym sposobem przeszło na 100, więc chyba jest zagwarantowane))

Ciekawe jest zadanie: https://szkopul.edu.pl/problemset/problem/xApOd_fcsVrm_DV7HljFbLWq/site/?key=statement

Gdzie można przelewać z obu stron(do szklanki o idx-ie 0 możesz przelać z szklanki o idxie 1 i też o idxie n-1). Męczyłem się kiedyś z tym, ale nie umiałem tego zrobić.

Comments

a co z przypadkiem:

5

3 1 3 0 3

Zauważ, że tutaj jedyne opcje jakie masz to przelanie do sąsiada z jednej strony.

Do szklanki o idx 4 musisz przelac wode ze szklanki o idx 3 i 5.

---

Algorytm zachowa się tak. K = 10 / 5 = 2

i = 0, A[i] = 3 jest nadmiar to przelewam 1 do szklanki o idx-ie i+1, wyn = 1, stan szklanek:

2 2 3 0 3

i = 1, A[i] = 2, spoko ide dalej

i = 2, A[i] = 3 jest nadmiar to przelewam 1 do szklanki o idx-ie i+1, wyn++, stan szklanek:

2 2 2 1 3

i = 3, A[i] = 1, biorę z szklanki o idx-ie i+1, wyn++, stan szklanek: 2 2 2 2 2

W szklance o idx-ie 4 jest spoko, ale i tak tam nie idziemy.

---

Zauważ, że to musi działać, bo jeśli masz nadmiar, w szklance o idx-ie x, to napewno musisz ją przelać do tej o x+1, przy założeniu, że wszystkie wcześniejsze(x-1,x-2,x-3..) mają już rozmiar K.

---

A i jeszcze, nie napisałem, że wody nie opłaca się przelwać dwa razy przez tą samą szklankę. Bo tylko robisz sobie bezsensowny dodatkowy koszt

---

działa na 100%, więc algorytm jest odporny na takiego typu rzeczy

---

No mógłbyś jak Ci się nudzi przelwać na przemian z tej o idxie 1 do tej o idx-ie 2 za koszt 3 potem z tej o idx-ie 2 do tej o idx-ie 1 za koszt 3 itd.

No ale nie ma to zbytnio sensu.

---

@polandonion, 

Super, że przeszło.