Skip to content
Reto #3Intermedio 2 resolvieronAbierto

El Liderazgo en la Taquería

bash · c · c++ · go · java · javascript · python · r · rust · typescript

En la famosa taquería 'El Pastor Dorado', el dueño quiere entender mejor su estructura organizacional. Se te proporcionará una lista de relaciones jefe-subordinado y tu tarea es determinar, para ciertos empleados, cuántas personas tienen a su cargo en total (contando subordinados directos e indirectos).

Entrada:

  • Un entero N (1 <= N <= 500), el número de relaciones jefe-subordinado.
  • N líneas, cada una con dos nombres separados por un espacio: Jefe Subordinado.
  • Un entero Q (1 <= Q <= 100), el número de consultas.
  • Q líneas, cada una con el nombre de un empleado a consultar.

Salida:

  • Para cada consulta, imprime un entero que represente el total de subordinados (directos e indirectos) de esa persona en una nueva línea.

Restricciones:

  • Los nombres son cadenas de hasta 20 caracteres alfanuméricos.
  • La estructura siempre forma un árbol o bosque (sin ciclos, cada subordinado tiene como máximo un jefe).
  • Si un nombre no tiene subordinados o no aparece como jefe en ninguna relación, el resultado es 0.
  • Los nombres en las consultas pueden o no haber aparecido en la lista de relaciones.

Ejemplo

Entrada
3
Don_Juan Pedro
Don_Juan Maria
Maria Jose
2
Don_Juan
Maria
Salida
3
1

Don_Juan tiene a Pedro y Maria como subordinados directos, y a Jose como indirecto (a través de Maria), sumando 3. Maria solo tiene a Jose, sumando 1.

Soluciones de la comunidad

Cada una pasó el 100% de los casos de prueba en el sandbox.

Yisuuus²python+10 karma
print(*((f := lambda u: sum(1 + f(b) for a, b in P if a == u))(q) for L in [__import__('sys').stdin.read().split()] for P in [list(zip(L[1:2*int(L[0])+1:2], L[2:2*int(L[0])+1:2]))] for q in L[2*int(L[0])+2:]), sep='\n')
i²r+10 karma
input <- scan("stdin", what="character", quiet=TRUE)

if (length(input) > 0) {
  N <- as.integer(input[1])
  idx <- 2
  
  grafo <- new.env(hash=TRUE, parent=emptyenv())
  
  for (i in seq_len(N)) {
    jefe <- input[idx]
    sub <- input[idx+1]
    
    if (exists(jefe, envir=grafo)) {
      grafo[[jefe]] <- c(grafo[[jefe]], sub)
    } else {
      grafo[[jefe]] <- sub
    }
    idx <- idx + 2
  }
 
  Q <- as.integer(input[idx])

  consultas <- input[(idx + 1):length(input)] 

  memo <- new.env(hash=TRUE, parent=emptyenv())
  
  contar_subordinados <- function(empleado) {
    if (exists(empleado, envir=memo)) return(memo[[empleado]])
    if (!exists(empleado, envir=grafo)) return(0)
    
    subordinados_directos <- grafo[[empleado]]
    total <- length(subordinados_directos)
    
    for (sub in subordinados_directos) {
      total <- total + contar_subordinados(sub)
    }
    
    memo[[empleado]] <- total
    return(total)
  }
  
  for (q in consultas) {
    cat(contar_subordinados(q), "\n")
  }
}
← Todos los retos
InicioEventosBlogRecursosCursosEquipo