Mężczyzna mieszka w północno-zachodnim rogu (0, 0)
miasta o wysokości h
i szerokości w
. Codziennie idzie ze swojego domu do granicy (?, w)
lub (h, ?)
. W poniższym przykładzie mężczyzna idzie do (3, 3)
dzisiaj.
(0, 0) +--+ + + . (0, 4)
|
+ +--+--+ .
|
+ + + + .
|
(3, 0) . . . . . (3, 4)
Mężczyzna nagrywa trochę w każdym punkcie ( +
w powyższym przykładzie). Za każdym razem, gdy osiąga punkt, idzie na wschód, jeśli kawałek jest, 1
a na południe inaczej. Po wyjściu kawałek się przewraca. Na przykład:
Day 1: 1--0 1 1 Day 2: 0 1 1 1 Day 3: 1--1--1--1-- Day 4: 0 0 0 0
| | |
0 1--0 0 0 0 1 0 1 0 1 0 1--0 1 0
| | |
1 0 1--0 1--0 0 1 0 1 0 1 0 1--0 1
| | |
Destination: (3, 3) Destination: (3, 1) Destination: (0, 4) Destination: (3, 2)
Biorąc pod uwagę wielkość miasta i historię mężczyzny, oblicz cel mężczyzny po n
dniach.
Wejście:
W pierwszym wierszu są trzy liczby całkowite, h
, w
i n
.
W kolejnych h
wierszach znajdują się w
liczby całkowite oznaczające rekord mężczyzny.
h <= 1000, w <= 1000, n <= 1000000000
Wynik:
Dwie liczby całkowite, oznaczające cel mężczyzny po n
dniach.
Przykładowe dane wejściowe:
3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
Przykładowe dane wyjściowe:
0 4
Przykładowy kod:
#include <iostream>
using namespace std;
bool d[1000][1000];
int main(){
int h, w, n;
cin >> h >> w >> n;
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
cin >> d[i][j];
int i, j;
while(n--)
for(i = 0, j = 0; i < h && j < w;){
bool &b = d[i][j];
d[i][j] ? j++ : i++;
b = !b;
}
cout << i << " " << j << endl;
}
Punktacja:
- Najniższa liczba bajtów w wygranych UTF-8.
- Jeśli czas działania kodu jest niezależny
n
, zmniejsz swój wynik o 50%.- Nie obliczaj wyników wszystkich 1000000000 dni ani nie rób niczego równie głupiego, aby otrzymać ten bonus. Znajdź wydajny algorytm!
code-golf
simulation
johnchen902
źródło
źródło
n
, mój kod oblicza wyniki wszystkich 1000000000 dni, a następnie wypisuje wynikn
, czy nadal otrzymuję premię -50%?Odpowiedzi:
GolfScript, 52,5 (105 znaków z 50% bonusem)
Wersja jest bardzo wydajna i może być testowana online nawet pod kątem dużych wartości.
Wykorzystuje podejście podobne do rozwiązania user2357112 .
źródło
Python 2, 192 bajty * 0,5 premii = 96
Aby skutecznie rozwiązać ten problem, kluczową realizacją jest to, że możemy obliczyć, ile razy każda komórka jest odwiedzana na podstawie liczby odwiedzin komórek powyżej i po lewej stronie, bez potrzeby określania dokładnych ścieżek. Skutecznie symulujemy
n
podróże jednocześnie i sprawdzamy, ile razy każda komórka jest używana.Znacząca poprawa dzięki podejściu opartemu na push zainspirowanemu rozwiązaniem johnchen902 :
Poprzednia implementacja oparta na ściąganiu:
Oryginalna, nie golfowa wersja:
źródło
not
do1^
i długi, jeśli warunek można zapisaćf=g[i][j]^v[i][j]&1 j+=f i+=1^f
.r
na pobranie parametru (r = lambda x: ...
), możesz skrócićg=[r()for i in x]
dog=map(r,x)
.Ruby,
159143W pierwszym wierszu
*
operator pobiera pierwszy wiersz danych wejściowych w jednej zmiennej, a resztę danych wejściowych w drugiej. Wówczasi
funkcja definiuje się konwersji"1 2 3 4"
INTO[1, 2, 3, 4]
, który jest stosowany do obul
in
. (x
iy
są zapisywane na później.)n[-1]
jest ostatnim elementemn
, więc następujący blok (symulacja) jest wykonywany tyle razy. Po pierwsze,x
iy
są inicjowane do zera (są one zadeklarowane na zewnątrz bloku, tak że ich zakres jest wystarczająco duży), a następnie linia symulacja jest wykonywany,co jest dość oczywiste, ale tu jest jakiś komentarz i tak:Edycja: nowa linia symulacyjna dostarczona przez Howarda, dzięki! Jestem pewien, że rozumiem, jak to działa, ale nie mam czasu, aby dodać wyjaśnienie, więc zostanie ono dodane później.
Na koniec
p x,y
wyprowadza liczby i gotowe!źródło
$/
na, a pętlę while można zmniejszyć do(x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}
.Delphi XE3 (437 bajtów ||
897874 bez uwzględnienia premii)Myśląc o tym, jak rozwiązać ten problem z premią, pomyślałem o następujących kwestiach.
Jeśli idziesz 4 dni, komórka 0,0 zmienia się 4 razy. Komórka po prawej jest zmieniana dwukrotnie tak samo, jak komórka pod nią.
Jeśli liczba dni jest nieparzysta, a liczba w komórce zaczyna się od 1, komórka po prawej stronie dostaje o jeden więcej niż komórka poniżej, i odwrotnie, jeśli komórka ma wartość 0.
Robiąc to dla każdej komórki, możesz sprawdzić, czy wartość końcowa powinna zostać zmieniona przez: Komórka została zmieniona X razy. jeśli X mod 2> 0, to zmień komórkę.
Rezultaty w następującym kodzie:
{Szepty na JohnChen902} Czy dostaję teraz twoją opinię? : P
Bez golfa
źródło
C ++ 213 bajtów * 0,5 = 106,5
Oto moje rozwiązanie. Jest podobny do rozwiązania user2357112 , ale istnieje kilka różnic:
Oto wersja bez golfa:
źródło
--*o;
, i zamiast tego zmieniając, który przypadek przesuwa faceta w dół, a który przypadek przesuwa faceta w prawo.Python, 177 bajtów
Moja pierwsza próba w Code Golfing, więc przepraszam, jeśli coś mi się nie udało! Kod używany do przechwytywania danych wejściowych na podstawie kodu user2357112.
Wejście:
Wynik:
źródło
R 196 bajtów * 0,5 = 98
Nie golfowany:
Stosowanie:
źródło