WallHero

TP01 Punto uno

Sep 16th, 2020
592
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.AbstractMap.SimpleEntry;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  5.  
  6. public class PuntoUno {
  7.    
  8.    
  9.     static int maxN = (int) 1e7;
  10.     static boolean cribe[] = new boolean[maxN+1];
  11.     static Scanner scanner = new Scanner(System.in);
  12.     static Float actualAvg = 0.0f;
  13.     static long fastExp(long b, long e)
  14.     {
  15.         int s = 63;
  16.         long r = b;
  17.        
  18.         while(((e >> s--) & 1) == 0);
  19.         while(s >= 0)
  20.         {
  21.             r *=r;
  22.             if(((e >> s--)&1) == 1) r = r*b;
  23.         }
  24.         return r;
  25.     }
  26.    
  27.     static long fastExp(long b, long e, long m) {
  28.         int s =63;
  29.         long r = b;
  30.        
  31.         while(((e >> s--) & 1) == 0);
  32.         while(s >= 0)
  33.         {
  34.             r = (r*r)% m;
  35.             if(((e >> s--)&1) == 1) r = (r*b)%m;
  36.         }
  37.         return r;
  38.     }
  39.    
  40.     static boolean isPrimeProb(long n, int a)
  41.     {
  42.         if(n == a) return true;
  43.         long s = 0, d = n-1;
  44.         while((d%2) == 0)
  45.         {
  46.             s++;
  47.             d/=2;
  48.         }
  49.         long x = fastExp(a, d, n);
  50.         if((x== 1) || (x+1 == n)) return true;
  51.         for(int i = 0; i < s-1; i++)
  52.         {
  53.             x = fastExp(x, 2, n);
  54.             if(x == 1) return false;
  55.             if(x+1 == n) return true;
  56.         }
  57.         return false;
  58.     }
  59.    
  60.     static boolean rabin(long n)
  61.     {
  62.         if(n == 1) return false;
  63.         int tests[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
  64.         for(int t : tests)
  65.         {
  66.             if ( t == n ) return true;
  67.             if(!isPrimeProb(n, t)) return false;
  68.         }
  69.         return true;
  70.     }
  71.    
  72.     static long forceReadPositiveLong(String message, int op)
  73.     {
  74.         long n = 0;
  75.         while(true)
  76.         {
  77.             try
  78.             {
  79.                 System.out.println(message);
  80.                 n = Long.parseLong(scanner.next());
  81.                 if(op == 0) // Se carga el array de múltiplos de mil
  82.                 {
  83.                     if(n!= 0 && n%1000 == 0) return n;
  84.                     System.out.println("N debe ser múltiplo de 1000");
  85.                     continue;
  86.                 }
  87.                 else if(op == 1) // Se carga el array de  primos.
  88.                 {
  89.                     if(n > 1 &&  ((n<= maxN && cribe[(int) n]) || (n> maxN && rabin(n)))) return n;
  90.                     System.out.println("El número debe ser un número primo.");
  91.                     continue;
  92.                 }
  93.                 else
  94.                 {
  95.                     if(n > 0 ) return n;
  96.                     System.out.println("El tamaño de los arreglos a cargar debe ser positivo.");
  97.                     continue;
  98.                 }
  99.             }
  100.             catch(Exception ex)
  101.             {
  102.                 System.out.println("Se introdujo un número inválido, reintente.");
  103.             }  
  104.         }
  105.     }  
  106.    
  107.     /* Para números menores a maxN = 10^7 O(n log n)*/
  108.     static void initCribe()
  109.     {
  110.         Arrays.fill(cribe, true);
  111.         cribe[0] = (cribe[1] = false);
  112.         for(int i = 2; i*i <= maxN; i++)
  113.         {
  114.             if(cribe[i])
  115.             {
  116.                 for(int j = i*i; j < maxN; j+=i)
  117.                 {
  118.                     cribe[j] = false;
  119.                 }
  120.             }
  121.         }
  122.     }
  123.    
  124.     static ArrayList<Long> sumArrays(ArrayList<Long> a, ArrayList<Long> b)
  125.     {
  126.         ArrayList<Long> ret = new ArrayList<Long>();
  127.         int n = a.size();
  128.         for(int i = 0; i < n ; i++)
  129.         {
  130.             ret.add(a.get(i)+b.get(i));
  131.         }
  132.         return ret;
  133.     }
  134.    
  135.     static ArrayList<Long> chargeArray(int op, int max)
  136.     {  
  137.         ArrayList<Long> retArray = new ArrayList<Long>();
  138.         String msg = (op == 0) ? "Introduzca un número múltiplo de 1000:" : "Introduzca un numero primo:";
  139.         Float sum = (float) 0;
  140.         while(max-- > 0 )
  141.         {
  142.             retArray.add(forceReadPositiveLong(msg, op));
  143.             sum+=retArray.get(retArray.size()-1);
  144.         }
  145.         sum/= retArray.size();
  146.         actualAvg = sum;
  147.         return retArray;
  148.     }
  149.    
  150.     static void showArrayList(ArrayList<Long> a, float avg, float avgPrime)
  151.     {
  152.         ArrayList<Long> arraySumLess = new ArrayList<Long>();
  153.         ArrayList<Long> arraySumHigher = new ArrayList<Long>();
  154.        
  155.         for(int i = 0; i < a.size(); i++)
  156.         {
  157.             System.out.println(a.get(i));
  158.             if(a.get(i) < avg) arraySumLess.add(a.get(i));
  159.             if(a.get(i) > avgPrime) arraySumHigher.add(a.get(i));
  160.         }
  161.         System.out.println("Media del primer arreglo: " + avg);
  162.         System.out.println("Media del segundo arreglo: " + avgPrime);
  163.        
  164.        
  165.         System.out.print("Elementos menores de la media del primer arreglo: [");
  166.         for(int i = 0; i < arraySumLess.size(); i++)
  167.         {
  168.             System.out.print(arraySumLess.get(i) + ((i == arraySumLess.size()-1) ? "]":", "));
  169.         }
  170.        
  171.        
  172.         System.out.print("\nElementos mayores de la media del segundo arreglo: [");
  173.         for(int i = 0; i < arraySumHigher.size(); i++)
  174.         {
  175.             System.out.print(arraySumHigher.get(i) + ((i == arraySumHigher.size()-1) ? "]":", "));
  176.         }
  177.  
  178.     }
  179.    
  180.     public static void main(String[] args) {
  181.         initCribe();
  182.         int max = (int) forceReadPositiveLong("Introduzca el tamaño del arreglo:",2);
  183.         ArrayList<Long> divs1000Array = chargeArray(0, max);
  184.         Float avg1000 = actualAvg;
  185.         ArrayList<Long> primeArray = chargeArray(1, max);
  186.         Float avgPrime = actualAvg;
  187.         showArrayList(sumArrays(divs1000Array, primeArray), avg1000, avgPrime);
  188.     }
  189.  
  190. }
  191.  
RAW Paste Data