Seorang pria tinggal di sudut barat laut (0, 0)kota dengan tinggi hdan lebar w. Setiap hari ia berjalan dari rumahnya ke perbatasan (?, w)atau (h, ?). Dalam contoh berikut, pria itu pergi ke (3, 3)hari ini.

(0, 0) +--+  +  +  . (0, 4)
          |         
       +  +--+--+  .
                |   
       +  +  +  +  .
                |   
(3, 0) .  .  .  .  . (3, 4)

Pria itu mencatat sedikit di setiap titik ( +contoh di atas). Setiap kali dia mencapai suatu titik, dia pergi ke timur jika bagian itu 1dan selatan sebaliknya. Bit dibalik setelah dia pergi. Sebagai contoh:

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)

Mengingat ukuran kota dan catatan pria itu, hitung tujuan pria itu setelah nberhari-hari.

Memasukkan:

Di baris pertama ada tiga bilangan bulat h,, wdan n.

Dalam hbaris berikut adalah wbilangan bulat, yang menunjukkan catatan pria itu.

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

Keluaran:

Dua bilangan bulat, yang menunjukkan tujuan pria itu setelah nberhari-hari.

Input sampel:

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

Output sampel:

0 4

Kode sampel:

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

Mencetak:

• Hitungan byte terendah dalam kemenangan UTF-8.
• Jika waktu menjalankan kode Anda tidak tergantung n, kurangi skor Anda hingga 50%.
  • Jangan hanya menghitung hasil 1000000000 hari atau melakukan hal yang sama bodohnya untuk mendapatkan bonus ini. Temukan algoritma yang efisien!

GolfScript, 52,5 (105 karakter dengan bonus 50%)

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

Versi ini sangat efisien dan dapat diuji secara online bahkan untuk nilai yang besar.

Ini menggunakan pendekatan yang mirip dengan solusi user2357112 .

Python 2, 192 byte * 0,5 bonus = 96

Untuk menyelesaikan masalah ini secara efisien, realisasi utama adalah bahwa kita dapat menghitung berapa kali setiap sel dikunjungi berdasarkan berapa kali sel di atas dan di sebelah kiri dikunjungi, tanpa perlu menentukan jalur yang tepat diambil. Secara efektif, kami mensimulasikan nperjalanan sekaligus dan melacak berapa kali setiap sel digunakan.

Peningkatan substansial karena pendekatan berbasis push yang terinspirasi oleh solusi 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

Sebelumnya, implementasi berbasis pull:

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

Asli, versi tidak dikoleksi:

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

Baris pertama menggunakan *operator untuk mengambil baris input pertama dalam satu variabel, dan sisanya dari input lainnya. Kemudian suatu ifungsi didefinisikan untuk dikonversi "1 2 3 4"menjadi [1, 2, 3, 4], yang diterapkan untuk keduanya ldan n. ( xdan ydisimpan untuk nanti.)

n[-1]adalah elemen terakhir n, jadi blok berikut (simulasi) dieksekusi berkali-kali. Pertama,x dan ydiinisialisasi ke nol (mereka dideklarasikan di luar blok sehingga cakupannya cukup besar), dan kemudian garis simulasi dijalankan, yang cukup jelas, tetapi inilah beberapa komentar:

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

Sunting: garis simulasi baru yang disediakan oleh Howard, terima kasih! Saya cukup yakin saya mengerti cara kerjanya tetapi saya tidak punya waktu untuk menambahkan penjelasan, jadi akan ditambahkan nanti.

Akhirnya, p x,y menampilkan angkanya, dan kita selesai!

Delphi XE3 (437 bytes || 897 874 tanpa bonus dihitung)

Ketika berpikir tentang bagaimana menyelesaikan ini dengan bonus saya memikirkan hal berikut.
Jika Anda berjalan 4 hari sel 0,0 diubah 4 kali. Sel di sebelah kanannya diubah dua kali juga sel di bawahnya.
Jika ada jumlah hari yang tidak merata dan angka dalam sel dimulai dengan 1 sel di sebelah kanan mendapat satu lebih dari sel di bawahnya, dan sebaliknya jika selnya 0.

Dengan melakukan ini untuk setiap sel, Anda dapat melihat apakah nilai akhir harus diubah oleh: Sel diubah X kali. jika X mod 2> 0 maka ubah sel.

Hasil dalam kode berikut:
{Whispers at JohnChen902} apakah saya mendapatkan suara Anda sekarang? : 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.

Tidak disatukan

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 byte * 0,5 = 106,5

Ini solusinya. Ini mirip dengan solusi user2357112 , tetapi ada beberapa perbedaan:

• Pertama, saya kirim waktu kunjungan ke kanan dan bawah, bukan menghitungnya dari atas dan kiri.
• Kedua, saya melakukan semuanya (membaca input, mengirim, melacak lokasi pria itu) secara bersamaan.
• Ketiga, saya hanya menyimpan satu baris memori.

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

Ini adalah versi yang tidak disunat:

#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 byte

Percobaan pertama saya di Code Golfing, maaf jika ada yang salah di sini! Kode yang digunakan untuk mengambil input berdasarkan kode 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

Memasukkan:

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

Keluaran:

0 4

R, 196 byte * 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)}

Tidak Disatukan:

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

Pemakaian:

f(3,4,4,matrix(c(1,0,1,0,1,0,1,0,1,1,0,0),3))
3 2