Salvar al prisionero -- python campo con performance campo con algorithm campo con python-3.x campo con mathematics camp codereview Relacionados El problema

Save the Prisoner


9
vote

problema

Español

Una cárcel tiene prisioneros, y cada prisionero tiene un número de identificación único, s , que van desde 1 a n . Hay tan dulces que deben ser distribuidos a los prisioneros.

El carcelero decide que la forma más justa de hacer esto es sentando a los prisioneros en un círculo (ordenados por ascendiendo s ), y luego, comenzando con algunos aleatorios s , distribuya un caramelo a la vez a cada prisionero numerado secuencial hasta que se distribuyan todos los caramelos m . Por ejemplo, si el carcelero recoge prisionero s = 2, entonces su orden de distribución sería (2, 3, 4, 5, ..., N-1, N, 1, 2 , 3, 4, ...) hasta que se distribuyan todos los dulces.

Pero espera, ¡hay una captura: ¡el último dulce es envenenado! Encuentre e imprima el número de identificación del último preso para recibir un dulce para que pueda ser advertido.

Formato de entrada

La primera línea contiene un entero, T, que denota el número de casos de prueba. Las líneas subsiguientes de T contienen 3 enteros separados en el espacio: N (el número de prisioneros), m (el número de dulces) y s (la ID de prisionero), respectivamente.

Formato de salida

Para cada caso de prueba, imprima el número de identificación del prisionero que recibe el dulce envenenado en una nueva línea.

Entrada de muestra

  1 5 2 1   

Salida de muestra

  2   

Mi solución:

  test_cases = int(input())  for _ in range(test_cases):     n, m, s = map(int, input().split())      while m > 0:         m -= 1         s = n if s > n else s + 1      s = n if s < 1 else s - 1     print(s)   

Creo que BIG-O puede ser muy grande ya que m podría ser de hasta 10 ^ 9. Cuando pruebo con m = 10 ^ 9, mi terminal "mató", así que por favor ayuda!

Original en ingles

A jail has prisoners, and each prisoner has a unique id number, S, ranging from 1 to N. There are M sweets that must be distributed to the prisoners.

The jailer decides the fairest way to do this is by sitting the prisoners down in a circle (ordered by ascending S), and then, starting with some random S, distribute one candy at a time to each sequentially numbered prisoner until all M candies are distributed. For example, if the jailer picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5, ..., n-1, n, 1, 2, 3, 4, ...) until all sweets are distributed.

But waitxe2x80x94there's a catchxe2x80x94the very last sweet is poisoned! Find and print the ID number of the last prisoner to receive a sweet so he can be warned.

Input Format

The first line contains an integer, T, denoting the number of test cases. The T subsequent lines each contain 3 space-separated integers: N (the number of prisoners), M (the number of sweets), and S (the prisoner ID), respectively.

Output Format

For each test case, print the ID number of the prisoner who receives the poisoned sweet on a new line.

Sample Input

1 5 2 1 

Sample Output

2 

My solution:

test_cases = int(input())  for _ in range(test_cases):     n, m, s = map(int, input().split())      while m > 0:         m -= 1         s = n if s > n else s + 1      s = n if s < 1 else s - 1     print(s) 

I think big-O can be very large since M could be up to 10^9. When I test with M = 10^9, my terminal "killed" so please help!

              
   
   

Lista de respuestas

6
 
vote

Comentarios generales

¿Su código funciona correctamente para el pequeño número de casos de prueba? Para un ejemplo odd_sweets = sweets % prisoners 5 debe dar intuitivamente odd_sweets = sweets % prisoners 6 como respuesta. Su código parece devolver odd_sweets = sweets % prisoners 7 por alguna razón.

mejora de baja colgante

  • El código de escritura es mucho más sobre cómo obtener las respuestas . El propósito de escribir en Python es producir, claro código comprensible. ¿Entenderá lo que su código hace en medio año, qué pasa tres años? Para una inspiración de lo que Python está tratando de lograr, consulte zen de python . Python también tiene una guía más en profundidad sobre cómo formatear correctamente el código, consulte PEP 8 < / a>.

  • Nunca Use variables de una sola letra para las cosas que no sean los contadores.

  • Trate de dejarlo en claro cuál hace su función, a través de su estilo de variable y codificación. Si esto no es suficiente, include una explicación breve cuál es el propósito de su código
  • Uso Funciones y la odd_sweets = sweets % prisoners 8 Módulo

Uso de todas estas mejoras Su código ahora se puede escribir como

  odd_sweets = sweets % prisoners 9  

El documento debe acortarse, sin embargo, lo dejaré a usted.


Algoritmo mejorado

Para encontrar un algoritmo más rápido, primero intente resolver un problema más simple. asume por un momento que la guardia siempre comienza en el primer prisionero

Comenzaré mirando algunos casos especiales


Caso: sweets0

Supongamos que tenemos menos dulces que los presos. Este es el caso más simple posible, y como siempre estamos empezando en el primer prisionero, sabemos que El sweets1 'TH Preso será envenenado.


Caso: sweets2

Supongamos por otro lado que tenemos más dulces que los prisioneros. Otra forma de distribuir los dulces sería primero darle a todos una parte justa, luego comenzar a distribuir los dulces restantes.

Ejemplo: Veamos cómo funcionaría esto. Digamos que tenemos sweets3 .

  sweets4  

Una distribución justa le daría a cada prisionero $ 3 $ caramelos cada uno. Ahora hemos dejado $ 18 - 3 * 5 = 3 $ caramelos para distribuir. Haciendo eso vemos

  sweets5  

que el preso número 3 se envenenaría. ¿Cómo se vería una implementación de codificación de esta estrategia? Bueno, podemos eliminar los múltiplos de $ N $ desde $ M $ hasta llegar al punto donde sweets6 .

  sweets7  

Este algoritmo es sorprendentemente simple y parece producir los resultados correctos. El sweets8 -loop se puede realizar incluso más rápido escribiendo

  sweets9  

¿Cómo funciona esto? prisoners0 ES INTEGER DIVISION. Entonces, prisoners1 . Luego estamos multiplicando esto nuevamente por prisoners2 por lo prisoners3 . ¡Esta es nuestra parte uniforme!

  prisoners4  

Caso generalizado para prisoners5 .

Ahora que hemos resuelto el caso 99887766655443336 podemos generalizarlo un poco más. Supongamos que antes de eso tenemos prisoners7 pero ahora prisoners8 .

Todavía podemos distribuir los dulces de manera uniforme como se hace anteriormente

  prisoners9  

Tenga en cuenta que ahora estamos de pie en el número 3 de prisioneros en lugar de 1. Si tuviéramos que mover 3 pasos a la derecha, queríamos demasiado. Una solución sería primero ir a odd_sweets0 pasos hacia atrás si terminamos demasiado a la derecha. ¿Cómo sabemos si estamos demasiado lejos con el derecho? Un cheque simple es si odd_sweets1 .

  odd_sweets2  

Aquí tuvimos que tener mucho cuidado desde odd_sweets3 puede ser cero.


Presentamos el operador del módulo [ 99887776655443344 ]

Ahora, ya que otras respuestas han mencionado qué

  odd_sweets5  

está haciendo es calcular el resto después de la división entera. Ahí es un operador especial en Python que exactamente esto, odd_sweets6 . Para un ejemplo odd_sweets7 como hemos calculado muchas veces antes. Leer más sobre este operador ver ¿Cómo se trabaja en Python? .

Uso odd_sweets9 En su lugar, nuestro código ahora se puede escribir como

  sweets0  

Podemos hacer un truco más y deshacerse del ^ {} - 99887766655443351 sweets2 Mientras queremos sweets3 . Podemos hacer sweets4 en lugar de sweets5 . ¿Por qué este funciona?

  sweets6  

Ese es el código más corto más corto que puedo escribir.


Las cosas se fueron para hacer

  • Debe asegurarse de que sweets7
, sweets8 99887766555443359 son enteros positivos antes de usar el algoritmo anterior.
  • Inlcude Un documento como una breve explicación de cómo funciona el algoritmo.
  •  

    General feedback

    Does your code work properly for the small number of test cases? For an example n, m, s = 19, 23, 1 should intuitively give s = 4 as an answer. Your code seem to return 19 for some reason.

    Low hanging improvement

    • Writing code is much more about getting the right answers. The purpose of writing in Python is to produce, clear understandable code. Will you understand what your code does in half a year, what about three years? For some inspiration of what python is trying to achieve, seezen of python. Python also have a more in depth guide on how to properly format code, see PEP 8.

    • Never use single letter variables for things other than counters.

    • Try to make it clear what your function does, through your variable and coding style. If this is not enough include a short explanation what the purpose of your code is
    • Use functions and the if __name__ == "__main__": module

    Using all of these improvements your code can now be written as

    def naive_prisoner(number_of_prisoners, candy, current_prisoner):     '''     Problem:     Solves the prisoner problem:     The jailer decides the fairest way to do this is by sitting the prisoners down in a circle      (ordered by ascending S), and then, starting with some random S, distribute one candy at a time      to each sequentially numbered prisoner until all M candies are distributed. For example, if the      jailer picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5, ..., n-1, n, 1, 2, 3, 4, ...)      until all sweets are distributed.      But wait-there's a catch-the very last sweet is poisoned! Find and print the ID number of the last prisoner      to receive a sweet so he can be warned.      Algorithm:     This code naively distributes one candy for every prisoner. If the current prisoner is the last     set current prison number to 1 and continue distributing candy.     '''      for _ in range(candy-1):         if current_prisoner == number_of_prisoners:             current_prisoner = 1         else:             current_prisoner += 1     return current_prisoner  if __name__ == '__main__':      n, m, s = 5, 19, 2     print naive_prisoner(n, m, s) 

    The docstring should be shortened, however I will leave that to you.


    Improved algorithm

    To find a quicker algorithm, let us first try to solve a simpler problem. Assume for just a moment that the guard always starts at the first prisoner

    I will begin by looking at some special cases


    Case: n => m

    Assume that we have less candy than prisoners. This is the simplest possible case, and since we are always starting on the first prisoner we know that the m'th prisoner will be poisoned.


    Case: n < m

    Assume on the other hand that we have more candy than prisoners. Another way to distribute the candy would be to first give everyone a fair share, then start going around distributing the remaining candy.

    Example: Let us look at how this would work. Say we have n = 5, m = 18, s = 1.

     3   3   3   3   3 [1] [2] [3] [4] [5] 

    A fair distribution would give each prisoner \$3\$ candies each. Now we have left \$18 - 3*5 = 3\$ candies to distribute. Doing that we see

     3   3   3   3   3 [1] [2] [3] [4] [5] 

    that prisoner number 3 would get poisoned. How would a coding implementation of this strategy look? Well we can remove multiples of \$n\$ from \$m\$ until we reach the point where n > m.

    def share_evenly(number_of_prisoners, candy):     while candy > number_of_prisoners:         candy -= number_of_prisoners     print candy 

    This algorithm is surprisingly simple and seem to produce the correct results. The while-loop can be performed even faster by writing

    candy -= candy*(candy//number_of_prisoners) 

    How does this work? // is integer division. So we 18//5 = 3. We are then multiplying this again by 3 so 3*(18//3) = 15. This is our even share!

    def share_evenly(number_of_prisoners, candy):     return candy - number_of_prisoners*(candy//number_of_prisoners) 

    Generalized case for s > 1.

    Now we that we have solved the s = 1 case we can generalize it a bit further. Assume as before that we have n = 5, m = 18 but now s = 3.

    We can still distribute the candy evenly as done previously

     3   3   3   3   3 [1] [2] [3] [4] [5]          x 

    Note that we are now standing at prisoner number 3 instead of 1. If we were to move 3 steps to the right we would too far. One solution would be to first go n-1 steps backwards if we end up too far to the right. How do we know if we are too far to the right? A simple check is if prisoner > number.

    def share_evenly(number_of_prisoners, candy, prisoner):     candy -= number_of_prisoners*(candy//number_of_prisoners)     prisoner += candy - 1      if prisoner == 0:         return number_of_prisoners     elif prisoner <= number_of_prisoners:         return prisoner     else:         return prisoner - number_of_prisoners 

    Here we had to take extra care since candy - 1 might be zero.


    Introducing the modulus operator [%]

    Now as other answers have mentioned what

    candy - number_of_prisoners*(candy//number_of_prisoners) 

    is doing is calculating the remainder after integer divison. There is a special operator in Python that does excactly this, %. For an example 5%18 = 3 as we have calculated many times before. To read more about this operator see How does % work in Python?.

    Using % instead our code can now be written as

    def prisoner(number_of_prisoners, candy, prisoner):     candy %= number_of_prisoners     prisoner += candy - 1     prisoner %= number_of_prisoners      if prisoner == 0:         return number_of_prisoners     else:         return prisoner 

    We can do one more trick and get rid of the if-else bit at the end. The reason it is there is that 5%5 = 0 while we want 5%5 = 5. We can do (x-1)%n + 1 instead of x%n. Why does this work?

    def prisoner(number_of_prisoners, candy, prisoner):     candy %= number_of_prisoners     prisoner += candy - 2     return 1 + (prisoner % number_of_prisoners) 

    That is the cleanest shortest code I can write.


    Things left to do

    • You should still make sure that prisoner, number_of_prioners and candy are positive integers before using the algorithm above.
    • Inlcude a docstring as a short explanation how the algorithm works.
     
     
    8
     
    vote
    vote
    La mejor respuesta
     

    Use nombres de variables que signifiquen algo

    No puedo hacer un seguimiento de si n es el número de dulces o el número de prisioneros porque es una sola letra que no significa mucho. Tal vez s es para dulces? No, probablemente significa "inicio". ¡Bah! Muy confuso. Usando las palabras que significa que algo hace que los mejores nombres de las variables para los humanos.

    SO

      prisoners = n sweets = m first_prisoner = s   

    Ahora puedo seguir lo que está sucediendo.

    Uso Módulo!

    como Billyoyo lo puso:

    Tiene un reloj con n horas en él, la mano está apuntando actualmente a x . ¿Dónde estará señalando la mano en M HORAS?

    que es una excelente sugerencia. Si está pensando en las cosas que son periódicas Modulus será muy probable que sea útil.

    Empecemos por descubrir cuántos dulces quedan después de que todos los prisioneros reciben un número par

      odd_sweets = sweets % prisoners   

    Entonces, si tenemos 250 sweets y 200 prisoners hay 50 odd_sweets . Si tenemos 400 sweets5 y 200 prisoners Hay 0 odd_sweets ya que los dulces se distribuyeron uniformemente. Incluso si no hay suficientes dulces para ir, una vez que Modulus todavía le dará el número correcto. Entonces, si tenemos 1000 prisoners8 y 400 sweets9 (BIGS MEDIOS) HAY 400 odd_sweets = sweets % prisoners 0 Ya que no habría sido capaz de rodear una Tiempo entero para que todos sean "extraños".

    Entonces queremos saber qué prisionero obtuvo el último tratamiento

      odd_sweets = sweets % prisoners 1  

    Comenzamos agregando el número de hojas ODD_SWS a la identificación del primer prisionero. Si esos sumas a menos de la cantidad de prisioneros, la vida es buena y no nos dirigimos. Pero si obtenemos un número que es más grande que el número de prisioneros, debemos devolverlo en el rango que el módulo se hará convenientemente por nosotros.

    Entonces, si tenemos 50 odd_sweets = sweets % prisoners 2 y 200 odd_sweets = sweets % prisoners 3 y el odd_sweets = sweets % prisoners 4

    • = 20, luego 50 + 20 = 70 y somos buenos
    • = 180 luego 50 + 180 = 230, que es demasiado grande, pero luego, después de hacer un 230% 200, terminamos con 30, lo que tiene sentido

    con que todo el cálculo se puede manejar sin bucles internos.

     

    use variable names that mean something

    I can't keep track of whether n is the number of sweets or the number of prisoners because it is a single letter that doesn't mean much. Maybe s is for sweets? No it probably means "start". Bah! So confusing. Using words that mean something makes for better variable names for humans.

    So

    prisoners = n sweets = m first_prisoner = s 

    Now I can follow what's happening.

    use modulus!

    As Billyoyo put it:

    You have a clock with N hours on it, the hand is currently pointed at x. Where will the hand be pointing in M hours?

    which is an excellent hint. If you're thinking about things that are periodic modulus will very likely come in handy.

    Let's start by figuring out how many sweets are left after all of the prisoners get an even numbers

    odd_sweets = sweets % prisoners 

    So if we have 250 sweets and 200 prisoners there are 50 odd_sweets. If we have 400 sweets and 200 prisoners there are 0 odd_sweets since the candies were evenly distributed. Even if there aren't enough sweets to go around once modulus will still give you the right number. So if we have 1000 prisoners and 400 sweets (mean bums) there would be 400 odd_sweets since you wouldn't have been able to around one entire time so they're all "odd".

    Then we want to know which prisoner got the last treat

    sick_prisoner = (first_prisoner + odd_sweets) % prisoners 

    We start by adding the number of odd_sweets to the ID of the first prisoner. If those add up to less than the number of prisoners life is good and we didn't loop around. But if we get a number that is bigger than the number of prisoners we need to bring it back into range which the modulus will conveniently do for us.

    So if we have 50 odd_sweets and 200 prisoners and the first_prisoners

    • = 20 then 50+20 = 70 and we're good
    • = 180 then 50+180 = 230 which is too big, but then after doing 230%200 we end up with 30 which makes sense

    With that the entire calculation can be handled without internal loops.

     
     
         
         
    3
     
    vote

    Intenta pensarlo de esta manera en lugar:

    Tienes un reloj con N Horas, la mano está apuntada actualmente en X. ¿Dónde estará apuntando la mano en las horas de M?

    Piense en cómo lo haría con un reloj normal con solo 12 números primero, luego vea si puede solicitarlo a un reloj con cualquier cantidad de números.

    Así, por ejemplo, si la mano está a las 7, 8 horas más tarde será a las 3.

     

    Try thinking about it this way instead:

    You have a clock with N hours on it, the hand is currently pointed at x. Where will the hand be pointing in M hours?

    Think about how you would do it with a normal clock with just 12 numbers first, then see if you can apply that to a clock with any amount of numbers.

    So for example, if the hand is at 7, 8 hours later it will be at 3.

     
     

    Relacionados problema

    4  Algoritmo más rápido para adaptar la expresión matemática dada  ( Faster algorithm to tailor given mathematical expression ) 
    ¿Hay una solución más optimizada para resolver el problema declarado? Dada una matriz 'Arr' de 'n' elementos y un número 'M', encuentra el menor índice 'Z' ...

    15  Función de sine en C / C ++  ( Sine function in c c ) 
    Debido a las restricciones de software, No puedo usar las bibliotecas estándar, cmath , 9988776655544334 , plantillas, en línea o impulso . También estoy u...

    13  Plantilla de expresión para calcular la distancia euclidiana  ( Expression template to compute the euclidean distance ) 
    Estaba escribiendo un código relacionado con el geometría nuevamente y tuvo un vistazo más de cerca a mi función que se supone que calcula la distancia euclid...

    11  Números de colmena - usando goto en C ++  ( Beehive numbers using goto in c ) 
    Entiendo que el uso de orca_array.hpp4 en el código C ++ está estrictamente no aconsejado, pero a veces, realmente reduce la cantidad de líneas de código co...

    4  Verificación computacional de la conjetura de Collatz utilizando OpenCl  ( Computational verification of collatz conjecture using opencl ) 
    Esta solicitud de revisión de código sigue mi solicitud anterior Verificación computacional de Collatz Conyecture . A diferencia del programa anterior (que ...

    3  Código C ++ para encontrar la distancia entre la línea y el punto  ( C code to find distance between line and point ) 
    Así que hice este simple programa que permite a los usuarios construir puntos y líneas y luego devolver la distancia más pequeña entre un punto dado y una lín...

    6  Determinar si f (n) = n ^ 2 + 3n + 5 es divisible por 121  ( Determining if fn n2 3n 5 is ever divisible by 121 ) 
    Dado el siguiente problema: Se conjeture eso para cualquier $ N & GT; 0 $, $ N ^ 2 + 3n + 5 $ nunca es divisible por 121. Pruebe esta conjetura por ...

    2  Optimización del código para la secuencia A064604  ( Optimizing code for sequence a064604 ) 
    Estoy implementando a064604 - oeis para enteros positivos de hasta 10 mil millones. Estoy encontrando a los divisores en $ o ( sqrt n) $. Por lo tanto, ...

    3  Análisis de simetría para arreglos atómicos en un cristal  ( Symmetry analysis for atom arrangements in a crystal ) 
    Por un tiempo ahora he tenido la intención de publicar un poco de mi código Haskell aquí para que alguien pueda decirme qué partes de la biblioteca de idiomas...

    13  Numérica para un cálculo de teoría de juegos usando la utilidad esperada  ( Numerics for a game theory calculation using expected utility ) 
    Estoy tratando de replicar los resultados de Bruce B. de Mesquita (BDM) en la teoría del juego político para la predicción. Sobre la base de dónde se encuentr...




    © 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos