Osuwiska

W tym wyzwaniu Twoim zadaniem jest przewidzieć zakres szkód spowodowanych przez ogromne osuwiska. Używamy do tego następującego uproszczonego dwuwymiarowego modelu, parametryzowanego przez wysokość początkową h >= 0 i współczynnik krytyczny c > 0 . Zaczynasz od klifu wysokości hi zakłada się, że teren jest całkowicie płaski nieskończenie po lewej i po prawej stronie. Dla h = 6, jak wygląda sytuacja w tym:

##########
##########
##########
##########
##########
##########
-----------------------

Są -to nieruchome podłoże skalne i #niestabilna gleba. Jeśli różnica wysokości między dwiema sąsiednimi kolumnami jest większa niż c, następuje osunięcie się ziemi : górne cjednostki gleby z lewej kolumny spadają do następnych ckolumn po prawej, po jednej do każdej. Najbardziej wysunięta na prawo niepusta kolumna na rysunku jest niestabilna c = 2, więc następuje osunięcie się ziemi:

#########
#########
##########
##########
##########
############
-----------------------

Kolumna jest nadal niestabilna, co powoduje drugie osunięcie się ziemi:

#########
#########
#########
#########
############
############
-----------------------

Teraz kolumna po jego lewej stronie stała się niestabilna, dlatego zostaje tam wywołane nowe osunięcie się ziemi:

########
########
#########
###########
############
############
-----------------------

Po tym klif znów jest stabilny. Zaletą tego modelu jest to, że kolejność przetwarzania osuwisk nie ma znaczenia: wynik końcowy jest taki sam.

Zadanie

Twój program otrzymuje parametry całkowite hi cjako dane wejściowe (kolejność nie ma znaczenia, ale musisz podać go w odpowiedzi) i powinien on wypisać całkowitą liczbę kolumn , na które ma wpływ osuwisko. Oznacza to liczbę kolumn w powstałym stabilnym klifie, którego wysokość jest ściśle pomiędzy 0a h. W powyższym przykładzie poprawne wyjście to 4.

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Są one podane w formacie h c -> output.

0  2  -> 0
2  3  -> 0
6  2  -> 4
6  6  -> 0
10 1  -> 10
15 1  -> 14
15 2  -> 11
15 3  -> 6
40 5  -> 16
80 5  -> 28
80 10 -> 17

CJam, 62 57 bajtów

O ile widzę, jest to zupełnie inne podejście do wdrożenia rozwiązania niż odpowiedź aditsu.

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,

Dane wejściowe mają postać h c

Przykład:

80 5

Wydajność:

28

Jak to działa

Logika jest tutaj dość prosta, z kilkoma sztuczkami służącymi do zmniejszenia rozmiaru kodu.

• Uzyskaj tablicę długości h + 1( + 1dla h = 0przypadku), z której każdy element ma hreprezentować klif
• Rozpocznij iterację od najbardziej odpowiedniego indeksu tej tablicy
  • Jeśli dwa elementy z bieżącego indeksu różnią się więcej niż c
    • Usuń cz bieżącego elementu indeksu
    • Dodaj 1do kolejnych celementów tablicy z bieżącego indeksu
    • Ustaw bieżący indeks równy długości tej nowej tablicy
    • To gwarantuje, że najpierw ustabilizujemy kamienie po prawej stronie bieżącego indeksu
  • w przeciwnym razie zmniejsz bieżący indeks
• Kiedy uderzymy w lewy skrajny indeks, upewniamy się, że wszystkie sąsiednie indeksy mają cróżnicę mniejszą lub równą
• Usuń dowolny 0lub hwartości z tablicy i uzyskać długość.

Rozszerzenie kodu

q~:C;:HaH)*H){(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h-H-,
q~:C;:HaH)*H)
q~:C;:H                  "Read the input, evaluate it, store height in H and coeff. in C";
       aH)*              "Wrap the height number in an array and repeat it H + 1 times";
           H)            "Put H+1 on stack, representing the current index of iteration";
{(:I\_@>2<:-C>{I0a*C~)+C1a*+]z1fb_,}I?}h
(:I\_@>2<:-C>
(:I                      "Decrement the current index and store it in I";
   \_                    "Swap to put array on top and make 1 copy";
     @>2<                "Get the two elements starting from Ith index";
         :-              "Get the difference. The best part of this approach is that";
                         "For the right most index, where there is only element, it";
                         "returns the element itself, which is the expected difference";
           C>            "Check if difference is greater than C";
{I0a*C~)+C1a*+]z1fb_,}   "This block will be executed when the difference is more than C";
 I0a*                    "Get an array of I length and all elements 0";
     C~)+                "Get -C value and append it to the above array";
         C1a*+           "Get C length array of 1s and concat with the above array";
              ]          "Wrap the two arrays, the cliff and the above one in an array";
               z1fb      "Transpose to get number pairs and add those pairs. For example";
                         "If we are at the right most index with H = 80 and C = 5,";
                         "The right section of the cliff looks like:";
                         "[ ... 80 80 80 80 80] and the array created in above step";
                         "looks like [ ... 0 0 0 0 -5 1 1 1 1 1]. After z, we have:";
                         "[ ... [80 0] [80 0] [80 0] [80 0] [80 -5] [1] [1] [1] [1] [1]]";
                         "After 1fb we get [ ... 80 80 80 80 75 1 1 1 1 1]";
                   _,    "Take a copy of the above resultant array and take its length";
I?                       "If difference was not greater than C, put I on stack";
                         "Now we either have the decremented index or new array length";
                         "on stack."
{ ... }h                 "This is a do while loop which makes sure that we iterate to";
                         "the left of the array. This loops runs till the top stack";
                         "element is 0 while not popping the top element";
        -H-,             "After the loop, we have the final cliff array and 0 on stack";
                         "Remove any 0 elements from the array, then remove any H";
                         "elements from the array and then take length to get the";
                         "number of columns which were modified";

Wypróbuj online tutaj

CJam - 70

q~:C;:H0]H*$W%{[__W<\1>]z{~-}%{C>}#):I{I(_2$=C-tC,{I+_2$=)t}/}0?}h-H-,

Wypróbuj na http://cjam.aditsu.net/

Wyjaśnienie:

q~                    read and evaluate the input
:C;                   store the 2nd number in C and remove
:H                    store the first number in H
0]H*                  make an array [H 0] and repeat it H times
$W%                   sort and reverse, obtaining [(H H's) (H 0's)] (initial cliff)
{                     loop...
    [__W<\1>]         make an array with the cliff without the first column
                      and the cliff without the last column
    z{~-}%            subtract the 2 arrays to get the height differences
    {C>}#             find the index of the first height diff. greater than C
    ):I               increment and store in I
    {                 if the value is non-zero (i.e. landslide occurring)
        I(_2$=C-t     subtract C from the corresponding column height
        C,            make an array [0 1 ... C-1]
        {             for each of those numbers
            I+        add I, obtaining a column index where some soil falls
            _2$=)t    increment the column height
        }/            end loop
    }0?               else break outer loop; end if
}h                    ...while the condition is true
-H-                   remove all 0 and H from the final stable cliff
,                     count the remaining columns

hOperator sprawdza ostatnią wartość na stosie bez usuwania go. Jeśli wystąpił osunięcie się ziemi, wartością jest tablica klifowa, która przyjmuje wartość true, ponieważ nie jest pusta. Jeśli nie, ostatnia wartość to 0 (fałsz).
Tak więc w przypadku osuwiska pętla jest kontynuowana z tablicą na stosie, w przeciwnym razie kończy się z 0 wciśniętym za tablicą. To 0 jest następnie usuwane z tablicy przez następnego -operatora.

Python, 200 190 174

h,c=input();q=[h]*h+[0]*h
try:
 while 1:
    d=[b-a for a,b in zip(q[1:],q)];g=max(d);a=d.index(g)
    for i in range(c):q[a+1+i]+=1/(g>c);q[a]-=1
except:print sum(h>i>0for i in q)

Wersja rozszerzona:

h, c = input()
# Initialize the heights
q = [h]*h + [0]*h
try:
    while 1:
        # Difference between the heights
        d = [b-a for a,b in zip(q[1:],q)]
        # It may error here, when h == 0, but thats okay
        g = max(d)
        a = d.index(g)
        for i in range(c):
            # This is the termination condition, when g <= c
            q[a+1+i] += 1 / (g>c)
            # Save the newline; also move this line to after termination
            q[a] -= 1
except:
    # Count all heights that have changed
    print sum(h > i > 0 for i in q)

Edycja: Po pewnej optymalizacji wyeliminowałem nieporęczne zakończenie pętli przez przerwanie (oszczędza 1 bajt). Zmieniono także slajd z opartego na wycinku na oparty na pętli.

Python 2 - 194 158 bajtów

h,c=input()
b=l=[h]*h+[0]*h
while b:
 b=0
 for i in range(len(l)-1):
  if l[i]-l[i+1]>c:
    for j in range(c):l[i-~j]+=1
    l[i]-=c;b=1
print sum(h>e>0for e in l)

(Zauważ, że interpreter przeceny SE przekształca dosłowne tabulatory na 4 spacje. Linie 7 i 8 tego programu mają tylko jedną tabulację [tj. Jeden bajt] wcięcia.)

hNajpierw pobiera dane wejściowe na standardowe wejście . Na przykład:

$ ./landslide.py <<< '6, 2'
4

Ten program przeszedł wiele ulepszeń. Edytowałem tę odpowiedź, aby wyjaśnić niektóre z ważniejszych zmian, ale robiła się dość długa. Możesz sprawdzić historię edycji, jeśli jesteś ciekawy.

Wyjaśnienie

Po pierwsze, hi csą odczytywane ze standardowego wejścia. W Pythonie 2 input()jest równoważne eval(raw_input())i dlatego proszę o przecinek oddzielający liczby. input()daje zwrot krotki ints, konwersja nie jest wymagana.

Następnie tworzona jest lista liczb całkowitych. To jest 2*hdługie Pierwsza połowa to, ha druga połowa to 0. Nie mam żadnego uzasadnienia, aby wykazać, że to wystarczy, aby zasymulować nieskończone hs po lewej i 0 po prawej. Po prostu natknąłem się na to i działa dla wszystkich przypadków testowych, więc jeśli ktoś może znaleźć dane wejściowe, to nie działa, chętnie to zmienię. W każdym razie ta lista jest wywoływana l, ale wywoływana jest inna jej kopia b.

bwartość nie ma znaczenia, liczy się tylko to, że jest prawdą. Niepusta lista jest prawdziwa, a jedynym sposobem na bopróżnienie jest tu h0, w którym to przypadku poprawna odpowiedź jest nadal drukowana. W każdym innym przypadku bmusi być prawdomówna, aby zapewnić, że wejdziemy w while b:pętlę. Jednak pierwszą rzeczą, która dzieje się w pętli, jest ustawienie bna 0, wartość falsey. Podczas każdego powtórzenia pętla bmusi być specjalnie ustawiona z powrotem na prawdę, inaczej pętla się zakończy.

Reszta pętli to rzeczywista symulacja. Jest to bardzo naiwne, w zasadzie jest to tłumaczenie kodu opisu problemu. Jeśli jakikolwiek element ljest cwiększy niż element następujący po nim, jest odejmowany przez, ca kolejne celementy mają 1 dodany do nich. (Nawiasem mówiąc i+1+j, zastosowana tutaj magia bitowa jest po prostu krótszym sposobem pisania .) Podczas dokonywania tych transformacji bjest ustawiona na 1. Za pierwszym razem, gdy żadne transformacje nie zostaną wykonane, bpozostanie 0 i pętla się zakończy.

Każde prawdziwe wyrażenie ocenia na True, a kiedy próbujesz wykonać matematykę, Trueto ocenia na 1. To samo dotyczy wartości False0. 0. Ostatni wiersz programu używa każdego elementu ljak ew wyrażeniu h>e>0i sumuje wynik. Daje to liczbę kolumn większą niż 0, ale niższą niż pierwotna wysokość klifu, czyli o wartość, o którą pyta pytanie. Jest drukowany i program kończy pracę.

Haskell, 163 156 151 bajtów

h#c=sum[1|e<-(until=<<((==)=<<))s$r h++r 0,e`mod`h/=0]where r=replicate$h+1;s w@(x:y:z)|x==0=w|x>c+y=x-c:map(+1)(take c(y:z))++drop c(y:z)|1<2=x:s(y:z)

Zastosowanie: h#cnp. 6#2Które wyjścia 4.

Jak to działa: funkcja pomocnika swykonuje pojedyncze osunięcie się ziemi. Powtarzaj, sdopóki dane wyjściowe już się nie zmienią. Policz dotknięte elementy.

Znaleziono funkcję „stosuj, aż dane wyjściowe się nie zmienią” (tj. until=<<((==)=<<)) W Stackoverflow .

Mathematica, 108 104 100 97 95

f=Max@#-Min@#&[0Range@#2//.{x___,k:##..&[a_,{#}],a_,y___}:>Sort@{x,##&@@({k}-1),a+#,y}/.{}->0]&

Stosowanie:

f[c, h]

Przykład:

f[5, 80]

28

C # 303 295

To działa!

Ale to jest ....

int q(int n,int c){var s=Enumerable.Repeat(n,n).ToList();s.Add(0);var d=new HashSet<int>();var g=true;while(g){g=false;for(int i=s.Count-1;i>0;i--){int z=i;int y=i-1;if((s[y]-s[z])>c){s[y]-=c;d.Add(y);g=true;for(int j=1;j<=c;j++){s[y+j]++;d.Add(y+j);if(s[s.Count-1]>0)s.Add(0);}break;}}}return d.Count;}

Muszę znaleźć nowy język;)

Sprawdzę to CJam ...

Ulepszony:

int q(int n,int c){var s=Enumerable.Repeat(n,n).ToList();s.Add(0);var d=new HashSet<int>();var g=1>0;while(g){g=1<0;for(int i=s.Count-1;i>0;i--){int z=i,y=i-1;if((s[y]-s[z])>c){s[y]-=c;d.Add(y);g=1>0;for(int j=1;j<=c;j++){s[y+j]++;d.Add(y+j);if(s[s.Count-1]>0)s.Add(0);}break;}}}return d.Count;}