Wytypuj, dokąd pójdzie mężczyzna

17

Mężczyzna mieszka w północno-zachodnim rogu (0, 0)miasta o wysokości hi 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, 1a 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 ndniach.

Wejście:

W pierwszym wierszu są trzy liczby całkowite, h, wi n.

W kolejnych hwierszach znajdują się wliczby całkowite oznaczające rekord mężczyzny.

h <= 1000, w <= 1000, n <= 1000000000

Wynik:

Dwie liczby całkowite, oznaczające cel mężczyzny po ndniach.

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!
johnchen902
źródło
2 rzeczy, których nie rozumiem. Dane wyjściowe, czasem używasz indeksu 0, innym razem nie. Jak to działa? Czy powinno to być jak border + 1? Drugą rzeczą jest druga linia z punktowaniem. Co masz na myśli?
Teun Pronk
Dzień 4 powinien dać wynik 3,2, prawda?
Teun Pronk
2
Jeśli, bez względu na wszystko n, mój kod oblicza wyniki wszystkich 1000000000 dni, a następnie wypisuje wynik n, czy nadal otrzymuję premię -50%?
user12205
@ace teraz to tak ujmujesz, czy to ma sens, prawda? Dzięki za to: P
Teun Pronk
@TeunPronk Tak. To moja wina.
johnchen902

Odpowiedzi:

7

GolfScript, 52,5 (105 znaków z 50% bonusem)

~](;(\((2$(1,*+\@/{]zip 0\{~@@+.2$!+2/\@+.2/\@[\1&]}%zip~@;}%\;[{.0=0=\1${{1>}%}{1>}if.{~}%}do;].1-,n@0-,

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 .

Howard
źródło
1
Proszę nie pytać o wyjaśnienia ;-) Nie mogę nawet tego zmienić bez zepsucia, a debugowanie tej bestii jest okropne.
Howard
13

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 symulujemyn 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 :

r=lambda:map(int,raw_input().split())
h,w,n=r()
v=[n]+w*[0]
x=y=0
for i in range(h):
 for j,b in enumerate(r()):
    if i-x==j-y==0:d=v[j]&1^b;x+=d;y+=1^d
    f=v[j]+b>>1;v[j]-=f;v[j+1]+=f
print x,y

Poprzednia implementacja oparta na ściąganiu:

r=lambda i:map(int,raw_input().split())
h,w,n=r(0)
x=range(h)
g=map(r,x)
v=[w*[0]for i in x]
v[0][0]=n-1
for i in x:
 for j in range(w):v[i][j]+=(i and(v[i-1][j]+(1^g[i-1][j]))/2)+(j and(v[i][j-1]+g[i][j-1])/2)
i=j=0
while i<h and j<w:f=g[i][j]^v[i][j]&1;j+=f;i+=1^f
print i,j

Oryginalna, nie golfowa wersja:

h, w, n = map(int, raw_input().split())
grid = [map(int, raw_input().split()) for i in xrange(h)]

# Determine the number of times each cell was visited in the first n-1 trips
visits = [[0]*w for i in xrange(h)]
visits[0][0] = n-1
for i in xrange(h):
    for j in xrange(w):
        if i:
            # Count visits from above cell
            visits[i][j] += (visits[i-1][j] + (not grid[i-1][j])) // 2
        if j:
            # Count visits from left cell
            visits[i][j] += (visits[i][j-1] + grid[i][j-1]) // 2

# Flip the bits corresponding to each cell visited an odd number of times
for i in xrange(h):
    for j in xrange(w):
        grid[i][j] ^= visits[i][j] & 1

# Figure out where the final trip ends
i = j = 0
while i < h and j < w:
    if grid[i][j]:
        j += 1
    else:
        i += 1

print i, j
user2357112 obsługuje Monikę
źródło
1
Możesz skrócić not do 1^i długi, jeśli warunek można zapisać f=g[i][j]^v[i][j]&1 j+=f i+=1^f.
Howard
@Howard: Dzięki. Zastosowane zmiany.
user2357112 obsługuje Monikę
1
Jeśli zezwolisz rna pobranie parametru ( r = lambda x: ...), możesz skrócić g=[r()for i in x]do g=map(r,x).
Roberto Bonvallet,
@RobertoBonvallet: Tak. Porada wdrożona.
użytkownik2357112 obsługuje Monikę
8

Ruby, 159 143

n,*l=$<.read.split$/
i=->a{a.split.map &:to_i}
x=y=l.map!{|k|i[k]}
(n=i[n])[-1].times{x=y=0
(x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}
p x,y

W pierwszym wierszu *operator pobiera pierwszy wiersz danych wejściowych w jednej zmiennej, a resztę danych wejściowych w drugiej. Wówczas ifunkcja definiuje się konwersji "1 2 3 4"INTO [1, 2, 3, 4], który jest stosowany do obu li n. ( xiy są zapisywane na później.)

n[-1]jest ostatnim elementem n, więc następujący blok (symulacja) jest wykonywany tyle razy. Po pierwsze, xi ysą 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:

l[x][y]<1?            is it zero (less than one)?
x+=l[x][y]=1          if it's zero, set it to one, and (conveniently) we can add that to x
:y+=(l[x][y]=0)+1     otherwise, set it to zero, add one, and add that to y
 while x<n[0]&&y<n[1] keep doing this while we're still inside the array

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,ywyprowadza liczby i gotowe!

Klamka
źródło
Kilka podstawowych wygranych: zmień znak nowej linii $/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]}.
Howard
4

Delphi XE3 (437 bajtów || 897 874 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

uses SysUtils,Classes,idglobal;var a:TArray<TArray<byte>>;b:TArray<TArray<int64>>;h,w,x,y,t:int16;n:int64;s:string;r:TStringList;tra:byte;begin r:=TStringList.Create;readln(h,w,n);h:=h-1;w:=w-1;for y:=0to h do begin readln(s);r.Add(StringReplace(s,' ','',[rfReplaceAll]));end;SetLength(a,h);SetLength(b,h);for y:=0to h do begin SetLength(a[y],w);SetLength(b[y],w);for x:=1to Length(r[y])do a[y][x-1]:=Ord(r[y][x])-48;end;b[0][0]:=n-1;for Y:=0to h do for X:=0to w do begin t:=b[y][x];if x<w then b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);if y<h then b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);end;for Y:=0to h do for X:=0to w do if b[y][x]mod 2=1then a[y][x]:=iif(a[y][x]=1,0,1);y:=0;x:=0;repeat a[y][x]:=iif(a[y][x]=1,0,1);if a[y][x]=1then inc(y) else inc(x);until(y>h)or(x>w);write(Format('%d %d',[y,x]));end.

Bez golfa

uses
  SysUtils,Classes,idglobal;
var
  a:TArray<TArray<byte>>;
  b:TArray<TArray<int64>>;
  h,w,x,y,t:int16;
  n:int64;
  s:string;
  r:TStringList;
  tra:byte;
begin
  r:=TStringList.Create;
  readln(h,w,n);
  h:=h-1;w:=w-1;
  for y:=0to h do
  begin
    readln(s);
    r.Add(StringReplace(s,' ','',[rfReplaceAll]));
  end;
  SetLength(a,h);
  SetLength(b,h);
  for y:=0to h do
  begin
    SetLength(a[y],w);
    SetLength(b[y],w);
    for x:=1to Length(r[y])do
      a[y][x-1]:=Ord(r[y][x])-48;
  end;
  b[0][0]:=n-1;
  for Y:=0to h do
    for X:=0to w do
    begin
      t:=b[y][x];
      if x<w then
        b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);
      if y<h then
        b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);
    end;
  for Y:=0to h do
    for X:=0to w do
      if b[y][x]mod 2=1then
        a[y][x]:=iif(a[y][x]=1,0,1);
  y:=0;x:=0;
  repeat
    a[y][x]:=iif(a[y][x]=1,0,1);
    if a[y][x]=1then
      inc(y)
    else
      inc(x);
  until(y>h)or(x>w);
  write(Format('%d %d',[y,x]));
end.
Teun Pronk
źródło
Nie dostałeś jeszcze mojego głosu. Jadłam obiad. (Upvoted)
johnchen902
4

C ++ 213 bajtów * 0,5 = 106,5

Oto moje rozwiązanie. Jest podobny do rozwiązania user2357112 , ale istnieje kilka różnic:

  • Najpierw wysyłam czas wizyty na prawo i na dole, zamiast obliczeniowych je od góry i po lewej stronie.
  • Po drugie, robię wszystko (odczytywanie danych wejściowych, wysyłanie, śledzenie położenia mężczyzny) jednocześnie.
  • Po trzecie, mam tylko jeden rząd pamięci.
#include <iostream>
int o[1001],h,w,r,c,i,j,t,u;int main(){std::cin>>h>>w>>*o;for(;i<h;i++)for(j=0;j<w;)std::cin>>t,u=o[j],o[j]/=2,u%2&&o[j+t]++,r-i|c-j||((u+t)%2?r:c)++,o[++j]+=u/2;std::cout<<r<<" "<<c<<"\n";}

Oto wersja bez golfa:

#include <iostream>
using namespace std;
int o[1001];
int main(){
    int h, w, n;
    cin >> h >> w >> n;
    o[0] = n;
    int r = 0, c = 0;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            bool t;
            cin >> t;
            int u = o[j];
            o[j + 1] += u / 2;
            o[j] = u / 2;
            if(u % 2)
                (t ? o[j + 1] : o[j])++;
            if(r == i && c == j)
                ((u + t) % 2 ? r : c)++;
        }
    cout << r << " " << c << endl;
}
johnchen902
źródło
Te trzy różnice sprawiają, że rzeczy stają się znacznie prostsze. Możemy skrócić indeksowanie i połączyć kilka zbędnych struktur danych. Logika przekazywania wizyt do przodu okazuje się znacznie krótsza niż logika pobierania wizyt z poprzednich komórek. Poziome warunki brzegowe są obsługiwane po prostu przez rozszerzenie struktury danych o dodatkową przestrzeń po prawej stronie, a warunki brzegowe pionowe nie stanowią problemu.
użytkownik2357112 obsługuje Monikę
Zatwierdziłem twoją odpowiedź i włączyłem koncepcje do mojego własnego kodu. Do tej pory zabrali 84 bajty z mojego rozwiązania, co stanowi poprawę o 30%.
user2357112 obsługuje Monikę
Podejrzewam, że możesz być w stanie zaoszczędzić trochę bajtów, nie robiąc tego --*o;, i zamiast tego zmieniając, który przypadek przesuwa faceta w dół, a który przypadek przesuwa faceta w prawo.
user2357112 obsługuje Monikę
@ user2357112 Zaimplementowano, ale długość kodu wzrosła z powodu poprzedniego błędu (powinno być 218 bajtów).
johnchen902
3

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.

l=lambda:map(int,raw_input().split())
h,w,n=l()
m=[l() for i in[1]*h]
while n>0:
 n-=1;x=y=0
 while x!=w and y!=h:
  if m[y][x]>0:m[y][x]=0;x+=1
  else:m[y][x]=1;y+=1
print y,x

Wejście:

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0

Wynik:

0 4
segfaultd
źródło
2

R 196 bajtów * 0,5 = 98

f=function(h,w,n,x){I=J=rep(1,n);for(i in 1:h)for(j in 1:w){M=which(I==i&J==j);N=length(M);if(N){z=seq(1,N,by=2);if(x[i,j])z=-z;f=M[-z];s=M[z];I[f]=i;J[f]=j+1;I[s]=i+1;J[s]=j}};cat(I[n]-1,J[n]-1)}

Nie golfowany:

f=function(h,w,n,x) {
  I = J = rep(1,n)

  for(i in 1:h) for(j in 1:w) {
    M = which(I==i&J==j)
    N = length(M)
    if (N) {
      z = seq(1,N,by=2)
      if (x[i,j]) z = -z
      f = M[-z]
      s = M[z]
      I[f] = i
      J[f] = j+1
      I[s] = i+1
      J[s] = j
    }
  }
  cat(I[n]-1, J[n]-1)
}

Stosowanie:

f(3,4,4,matrix(c(1,0,1,0,1,0,1,0,1,1,0,0),3))
3 2
lambruscoAcido
źródło