Experiencia de entrevista en Amazon – Part 73

Ronda 1: Prueba en línea
Tienes M cuerdas idénticas y N pesos idénticos. Desea hacer un experimento para determinar la fuerza S de las cuerdas idénticas, probando cuántos pesos puede sostener una sola cuerda. La resistencia S de las cuerdas se define como:
1) Si una cuerda se rompe con el primer peso, S=0;
2) Si una cuerda puede sostener n pesos y se rompe a los n+1 pesos, S=n;
3) Si una cuerda puede soportar todos los N pesos, S=N.
En una prueba («prueba» significa verificar si una cuerda puede sostener una cantidad de pesos), si la cuerda se rompe, debe tomar otra cuerda para continuar el experimento; si la cuerda no se rompe, se puede utilizar para la siguiente prueba sin problema. Si usó todas las cuerdas pero aún no puede determinar la fuerza S de las cuerdas, el experimento falla.
Escriba un programa C/C++ que, dados M y N (M y N son números enteros, M>=1, N>=1), calcule el número mínimo de pruebas T necesarias para garantizar que pueda determinar S. Intente optimizar la complejidad temporal de su programa y explique:
1) ¿Qué tipo de “trucos” ha utilizado para optimizar la complejidad temporal?
2) ¿Cuál es la complejidad del tiempo sin estos “trucos” y cuál es la complejidad del tiempo con estos “trucos”?
Pista 1: si tienes un número limitado de cuerdas, no te atrevas a correr el riesgo. Por ejemplo, si M=1, su única opción es aumentar los pesos uno por uno, de 1 a N, para asegurarse de que puede determinar S en el peor de los casos. En este caso, T=N.
Sugerencia 2: si tiene muchas cuerdas, la búsqueda binaria obviamente es útil para calcular la T mínima de manera eficiente.
Ejemplo 1: M=1, N=20
Comando: calc_n_tests 1 20
Salida: 20
Ejemplo 2: M=2, N=5
Comando: calc_n_tests 2 5
Salida: 3