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!

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 .

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

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!

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.

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;
}

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

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