Problema.-
A. Pythagorean Theorem II LINk
Como todos saben la formula del Teorema de Pitagoras que equivale a
a 2 + b 2 = c 2
Dado n , su tarea es contar cuántos triángulos rectángulos con los laterales del largo de a, b y c que satisface una desigualdad 1 ≤ a ≤ b ≤ c ≤ n.
(1 ≤ n ≤ 10 4 )
Solución.-
Ni mas vi el ejercicio dije Fuerza bruta pues era 10 4 y rotar por cada variable tanto a,b y c entonces me daba un O(n3) pero al hacer correr cuando n=10 4 tardo mas de 2 s, entonces intente buscar alguna idea para poder solucionar eso, y lo que vino a mi cabeza fue rotar entre a y b y ver si la suma de cuadrados es un numero cuadrado perfecto, así llegue a eliminar mi tercer for, así es como llegue a hacer mis hack muchos usaron 3 for y para el caso mencionado les daba tiempo limite Excedido jejeje.
Código.-
int main() { int n; int c; cin>>n; c=0; int t=0,q=0; for(int i=1;i<=n && q<=n;i++) { for(int j=i;j<=n && q<=n;j++) { t=i*i+j*j; int q=sqrt(t); if(q*q==t && q<=n) c++; } } cout<<c<<endl; return 0; }Si tienen una mejor idea por favor me gustaría leerla o una forma de mejorar el código como siempre, toda critica es bien aceptada.
No hay comentarios:
Publicar un comentario