Predecir a dónde irá el hombre

17

Un hombre vive en la esquina noroeste (0, 0)de una ciudad con altura hy anchura w. Todos los días camina desde su casa hasta la frontera (?, w)o (h, ?). En el siguiente ejemplo, el hombre va a (3, 3)hoy.

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

El hombre registra un poco en cada punto ( +en el ejemplo anterior). Cada vez que llega a un punto, va hacia el este si el bit es 1y hacia el sur de lo contrario. La parte se voltea después de que se va. Por ejemplo:

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)

Dado el tamaño de la ciudad y el registro del hombre, calcule el destino del hombre después de ndías.

Entrada:

En la primera línea hay tres enteros h, wy n.

En las siguientes hlíneas hay wenteros, que denotan el registro del hombre.

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

Salida:

Dos enteros, que denotan el destino del hombre después de ndías.

Entrada de muestra:

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

Salida de muestra:

0 4

Código de muestra:

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

Puntuación:

  • El conteo de bytes más bajo en UTF-8 gana.
  • Si el tiempo de ejecución de su código es independiente n, reduzca su puntaje en un 50%.
    • No solo calcules los resultados de todos los 1000000000 días o hagas algo similarmente estúpido para obtener este bono. ¡Encuentra un algoritmo eficiente!
code-golf simulation johnchen902
fuente
2 cosas que no entiendo. La salida, a veces usa el índice 0 otras veces no. ¿Cómo funciona? ¿Debería ser como border + 1? Lo segundo es la segunda línea con puntuación. ¿Qué quiere decir eso?
Teun Pronk
El día 4 debería producir 3,2, ¿verdad?
Teun Pronk
2
Si, sin importar lo que nsea, mi código calcula los resultados de todos los 1000000000 días, luego emite el resultado de n¿Todavía obtengo el bono de -50%?
user12205
@ace ahora lo pones así, ¿tiene sentido, no? Gracias por eso: P
Teun Pronk
@TeunPronk Sí. Que es mi culpa.
johnchen902

Respuestas:

7

GolfScript, 52.5 (105 caracteres con 50% de bonificación)

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

La versión es muy eficiente y se puede probar en línea incluso para valores grandes.

Utiliza un enfoque similar a la solución de user2357112 .

Howard
fuente
1
Por favor, no pidas una explicación ;-) Ni siquiera puedo cambiarla sin romper y depurar esta bestia es horrible.
Howard
13

Python 2, 192 bytes * 0.5 bonus = 96

Para resolver este problema de manera eficiente, la realización clave es que podemos calcular cuántas veces se visita cada celda en función de la cantidad de veces que se visitan las celdas superiores y a la izquierda, sin necesidad de determinar las rutas exactas tomadas. Efectivamente, simulamos nviajes a la vez y hacemos un seguimiento de cuántas veces se usa cada celda.

Mejora sustancial debido al enfoque basado en el impulso inspirado en la solución de 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

Implementación previa basada en extracción:

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

Versión original sin golf:

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 es compatible con Monica
fuente
1
Es posible reducir el not a 1^y la larga si la condición se puede escribir f=g[i][j]^v[i][j]&1 j+=f i+=1^f.
Howard
@Howard: Gracias. Ediciones aplicadas.
user2357112 es compatible con Monica el
1
Si usted permite rtomar un parámetro ( r = lambda x: ...), entonces se puede acortar g=[r()for i in x]a g=map(r,x).
Roberto Bonvallet
@RobertoBonvallet: Sí. Asesoramiento implementado.
user2357112 es compatible con Monica el
8

Rubí, 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

La primera línea utiliza el *operador para tomar la primera línea de entrada en una variable y el resto de la entrada en otra. A continuación, una ifunción se define para convertir "1 2 3 4"en [1, 2, 3, 4], que se aplica tanto a ly n. ( xy yse guardan para más tarde)

n[-1]es el último elemento de n, por lo que el siguiente bloque (la simulación) se ejecuta muchas veces. Primero, xy yse inicializan a cero (se declaran fuera del bloque para que su alcance sea lo suficientemente grande), y luego se ejecuta la línea de simulación, lo cual es bastante explicativo, pero de todos modos aquí hay algunos comentarios:

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

Editar: nueva línea de simulación proporcionada por Howard, ¡gracias! Estoy bastante seguro de que entiendo cómo funciona, pero no tengo tiempo para agregar una explicación, por lo que se agregará más adelante.

Finalmente, p x,ygenera los números, ¡y listo!

Pomo de la puerta
fuente
Algunas ganancias básicas: cambie la nueva línea a $/y el ciclo while se puede reducir a (x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}.
Howard
4

Delphi XE3 (437 bytes || 897 874 sin bono contado)

Al pensar en cómo resolver esto con la bonificación, pensé en lo siguiente.
Si caminas 4 días, la celda 0,0 se cambia 4 veces. La celda a su derecha se cambia dos veces más que la celda debajo de ella.
Si hay un número desigual de días y el número en la celda comienza con 1, la celda de la derecha obtiene uno más que la celda de abajo, y al revés si la celda es 0.

Al hacer esto para cada celda, puede ver si el valor final debe cambiarse por: La celda se cambió X veces. si X mod 2> 0, cambie la celda.

Resultados en el siguiente código:
{Whispers at JohnChen902} ¿recibo tu voto a favor ahora? :PAG

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.

Sin golf

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
fuente
Aún no tienes mi voto. Estaba cenando. (Votado a favor)
johnchen902
4

C ++ 213 bytes * 0.5 = 106.5

Aquí está mi solución. Es similar a la solución de user2357112 , pero hay varias diferencias:

  • Primero, envío los horarios de visita a la derecha y a la parte inferior, en lugar de calcularlos desde la parte superior e izquierda.
  • En segundo lugar, hago todo (leer entradas, despachar, rastrear la ubicación del hombre) simultáneamente.
  • Tercero, mantengo solo una fila de memoria.
#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";}

Aquí está la versión sin golf:

#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
fuente
Estas tres diferencias hacen las cosas mucho más difíciles. Podemos acortar la indexación y combinar varias estructuras de datos redundantes. La lógica para impulsar las visitas hacia adelante resulta ser mucho más corta que la lógica para extraer visitas de las celdas anteriores. Las condiciones de contorno horizontal se manejan simplemente extendiendo la estructura de datos un espacio adicional a la derecha, y las condiciones de límite vertical no son un problema.
user2357112 es compatible con Monica el
He votado tu respuesta y he incorporado los conceptos a mi propio código. Hasta ahora, han eliminado 84 bytes de mi solución, una mejora del 30%.
user2357112 es compatible con Monica el
Sospecho que es posible que pueda guardar algunos bytes si no lo hace --*o;y, en cambio, cambie qué caso mueve al tipo hacia abajo y qué caso mueve al tipo hacia la derecha.
user2357112 es compatible con Monica el
@ user2357112 Implementado, pero la longitud del código aumenta debido a un error anterior (debería haber sido 218 bytes).
johnchen902
3

Python, 177 bytes

Mi primer intento en Code Golfing, ¡lo siento si me equivoqué aquí! Código utilizado para capturar la entrada en función del código del usuario2357112.

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

Entrada:

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

Salida:

0 4
segfaultd
fuente
2

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

Sin golf:

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

Uso:

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