Rompecabezas matemático: Área de anillos concéntricos

Question

El problema que aparece a continuación apareció en la última ronda de Google Code Jam:

---

María ha sido contratada por la empresa Ghastly Chemicals Junkies (GCJ) para que les ayude a fabricar bullseyes. Una diana consiste en una serie de anillos concéntricos (anillos centrados en el mismo punto), y suele representar una diana de tiro con arco. GCJ está interesada en fabricar dianas blancas y negras.

María comienza con t mililitros de pintura negra, que utilizará para dibujar anillos de 1cm de grosor (un centímetro). Un anillo de 1cm de grosor es el espacio entre dos círculos concéntricos cuyos radios difieren en 1cm.

María dibuja el primer anillo negro alrededor de un círculo blanco de radio r cm. Luego repite el siguiente proceso mientras tenga suficiente pintura para hacerlo:

María imagina un anillo blanco de 1 cm de grosor alrededor del último anillo negro. A continuación, dibuja un nuevo anillo negro de 1 cm de grosor alrededor del anillo blanco. Observa que cada "anillo blanco" es simplemente el espacio entre dos anillos negros. El área de un disco con radio de 1cm es de cm2. Se necesita un mililitro de pintura para cubrir el área de cm2. ¿Cuál es el número máximo de anillos negros que puede dibujar María? Ten en cuenta que:

• María sólo dibuja anillos completos. Si la pintura restante no es suficiente para dibujar un anillo negro completo, deja de pintar inmediatamente.
• Siempre habrá suficiente pintura para dibujar al menos un anillo negro.

Entrada

La primera línea de la entrada da el número de casos de prueba, T. Siguen T casos de prueba. Cada caso de prueba consta de una línea que contiene dos números enteros separados por espacios: r y t.

Salida

Para cada caso de prueba, se imprime una línea que contiene "Caso #x: y", donde x es el número de caso (empezando por el 1) e y es el número máximo de anillos negros que María puede dibujar.

**Sample Input**    
5
1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000

**Sample Output**  
Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49

---

Las entradas eran muy grandes, por lo que un enfoque de fuerza bruta no lo resolvería a tiempo. Miré las mejores soluciones, y la mayoría utilizó una variación de la fórmula siguiente:

2*R*X + (2*X-1)*X <= T

donde R es el radio del primer círculo blanco, X es el número total de anillos que puede pintar y T son los mililitros de tinta que tiene disponibles. Para encontrar la respuesta, básicamente hay que hacer una búsqueda binaria buscando la mayor X que haga que la ecuación sea verdadera.

Mi pregunta : ¿De dónde viene esa fórmula? ¿Es posible explicar cómo es que esto resuelve el problema, en términos simples? Cualquier luz que pueda arrojar será apreciada.

Answer 1

El anillo con radios $r_1<r_2$ tiene área $\pi(r_2^2-r_1^2)$ . Así que requiere $r_2^2-r_1^2$ mililitros de pintura. Cuando $r_2-r_1=1$ tenemos que $r_2^2-r_1^2=(r_2-r_1)(r_2+r_1)=r_2+r_1=2r_1+1$ .

Ahora bien, si su $n$ La franja negra es un anillo con radios $r_1(n)=r+2(n-1)$ y $r_2(n)=r_1(n)+1$ y la pintura necesaria es $$2r_1(n) +1= 2r + 1 + 4(n-1)$$

Así que, después de $M$ rayas, se habrá agotado:

$$\sum_{n=1}^M \left(2r+1+4(n-1)\right)=(2r+1)M + 4\frac{M(M-1)}{2}=2rM + M(2M-1)$$

Además, la búsqueda binaria no es necesaria. Puedes simplemente resolver la ecuación:

$$2x^2+(2r-1)x-T=0$$ y tomar el mayor número entero menor que la raíz mayor. Esa raíz mayor es:

$$\frac{1-2r+\sqrt{(2r-1)^2+8T}}{4}$$

Answer 2

Si el radio interior de un anillo es $r$ y el radio exterior es $r+1$ el área del anillo es $\pi(r+1)^2-\pi r^2=\pi (2r+1)$ , por lo que el anillo toma $2r+1$ mililitros de pintura. El siguiente anillo es $2$ cm más de radio (uno negro y otro blanco), por lo que se necesitan 2(r+2)+1 mililitros. Para pintar $x$ anillos a partir de $r$ toma $2r+1+2(r+2)+1+2(r+4)+1+\ldots 2(r+2x-2)+1=\sum_{i=0}^{x-1}(2r+4i+1)=2rx+2x(x-1)+x=2rx+2x^2-x$

Entonces no es necesario hacer una búsqueda binaria. Puedes simplemente resolver la cuadrática para $x$ y redondear hacia abajo.