SHARE
TWEET

Untitled

a guest Mar 25th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. public class Solution {
  4.    
  5.     private static int getSquareRoot(long a) {
  6.         long f = 0;
  7.         int ret = 0;
  8.         for(long i = 0; i < 16; i++) {
  9.             ret <<= 1;
  10.             long kari_f = (f + 1) << ((15 - i) * 2);
  11.             if(a >= kari_f) {
  12.                 f = f + 2;
  13.                 a -= kari_f;
  14.                 ret++;
  15.             }
  16.             f <<= 1;
  17.         }
  18.         return ret;
  19.     }
  20.    
  21.     public static void main(String[] args) {
  22.         int MAX_VALUE = 2 * 1000000;
  23.         int[] roots = new int[MAX_VALUE + 1];
  24.         for(int i = 1; i <= MAX_VALUE; i++) {
  25.             roots[i] = getSquareRoot(i);
  26.         }
  27.         try(Scanner sc = new Scanner(System.in)) {
  28.             int T = sc.nextInt();
  29.             while(T-- > 0) {
  30.                 int N = sc.nextInt();
  31.                 int root = roots[N];
  32.                 int bestRectangles = 0;
  33.                 int bestArea = 0;
  34.                 for(int x = 1; x <= root + 1; x++) {
  35.                     int y = x;
  36.                     int rectangles;
  37.                     do {
  38.                         int area = x * y;
  39.                         rectangles = x * (x + 1) * y * (y + 1) / 4;
  40.                         int abs1 = bestRectangles - N;
  41.                         int abs2 = rectangles - N;
  42.                         if(abs1 < 0) {
  43.                             abs1 *= -1;
  44.                         }
  45.                         if(abs2 < 0) {
  46.                             abs2 *= -1;
  47.                         }
  48.                         if(abs1 > abs2) {
  49.                             bestRectangles = rectangles;
  50.                             bestArea  = area;
  51.                         }
  52.                         if(abs1 == abs2 && bestArea < area) {
  53.                             bestArea = area;
  54.                         }
  55.                         y++;
  56.                     }  while(rectangles < N);
  57.                     if(y == x + 1) {
  58.                         break;
  59.                     }
  60.                 }
  61.                 System.out.println(bestArea);
  62.             }
  63.         }
  64.     }
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top