fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * We read t test‐cases, each with two integers p, s.  We must build (if possible)
  6.  * a connected shape of N unit‐cells (N <= 50,000) so that
  7.  *
  8.  *      (perimeter of shape) / (area of shape)  =  p / s.
  9.  *
  10.  * Equivalently, if gcd(p,s)=g, put p0 = p/g, s0 = s/g, then we look for k>0
  11.  * such that
  12.  *      N = k * s0,
  13.  *      M = k * p0
  14.  * and N <= 50,000, and there is a connected arrangement of N cells of
  15.  * perimeter exactly M.  We know any connected arrangement has
  16.  *      minimal‐possible‐perimeter(N)  =  min_{a*b=N} [ 2*(a+b) ],   (a,b in ℕ)
  17.  * and maximal‐possible‐perimeter(N) = 2*N + 2  (a “tree” chain of N cells).
  18.  * Hence we just search over k until
  19.  *      k*s0 <= 50000,
  20.  *      k*p0 <= 2*(k*s0)+2,
  21.  *      minimal‐possible‐perimeter(k*s0) <= k*p0,
  22.  *      and (k*p0) is even
  23.  * (since any grid‐perimeter must be even).  If none is found, print “-1”.
  24.  *
  25.  * Once (N,M) = (k*s0, k*p0) is chosen, define
  26.  *      T = (2*N + 2 - M)/2   (an integer >=0).
  27.  * Then factor T = x*y (with x <= y) so that the  rectangle of size (x+1) x (y+1)
  28.  * has area A_rect = (x+1)(y+1) <= N.  The remainder d = N - A_rect cells are hung
  29.  * off a corner in a one‐cell‐thick chain.  That guarantees the final perimeter is
  30.  *   Perimeter(rect) + 2*d  = 2*( (x+1)+(y+1) ) + 2*(N - (x+1)(y+1) )  = M.
  31.  *
  32.  * We then output N lines of coordinates.  Any valid shape is acceptable.
  33.  */
  34. public class Main {
  35.     public static void main(String[] args) throws IOException {
  36.         FastReader fr = new FastReader();
  37.         StringBuilder sb = new StringBuilder();
  38.  
  39.         int t = fr.nextInt();
  40.         for(int _case=0; _case<t; _case++) {
  41.             int p = fr.nextInt();
  42.             int s = fr.nextInt();
  43.  
  44.             // 1)  Reduce p,s by their gcd
  45.             int g = gcd(p, s);
  46.             int p0 = p / g;
  47.             int s0 = s / g;
  48.  
  49.             // 2)  If p0 > 2*s0 + 2, impossible.
  50.             if (p0 > 2*s0 + 2) {
  51.                 sb.append("-1\n");
  52.                 continue;
  53.             }
  54.  
  55.             // We will choose some integer k > 0 with N = k*s0, M = k*p0.
  56.             // There are special small‐cases if p0 = 2*s0+2 or p0=2*s0+1; otherwise
  57.             // we do a small search in k.
  58.             int bestK = -1, bestN=0, bestM=0;
  59.  
  60.             if (p0 == 2*s0 + 2) {
  61.                 // Must have k=1
  62.                 bestK = 1;
  63.                 bestN = s0;
  64.                 bestM = p0;
  65.             }
  66.             else if (p0 == 2*s0 + 1) {
  67.                 // Must have k=2
  68.                 bestK = 2;
  69.                 bestN = 2*s0;
  70.                 bestM = 2*p0;
  71.             }
  72.             else {
  73.                 // p0 <= 2*s0.  We try k = 1 (if p0 even) or k=2 (if p0 odd),
  74.                 // and keep raising k until N=k*s0 <= 50000 and
  75.                 //    M=k*p0 <= 2*N+2  AND  minPerimeter(N) <= M
  76.                 boolean found = false;
  77.                 int startK = (p0 % 2 == 0 ? 1 : 2);
  78.                 for(int k = startK; k * s0 <= 50000; ){
  79.                     int N = k * s0;
  80.                     int M = k * p0;
  81.                     // Check M <= 2N+2
  82.                     if (M <= 2*N + 2) {
  83.                         int minP = minimalPerimeter(N);
  84.                         if (minP <= M) {
  85.                             bestK = k;
  86.                             bestN = N;
  87.                             bestM = M;
  88.                             found = true;
  89.                             break;
  90.                         }
  91.                     }
  92.                     // Increase k (by 1 if p0 even, else by 2 if p0 odd)
  93.                     if (p0 % 2 == 0) {
  94.                         k++;
  95.                     } else {
  96.                         k += 2;
  97.                     }
  98.                 }
  99.                 if (!found) {
  100.                     sb.append("-1\n");
  101.                     continue;
  102.                 }
  103.             }
  104.  
  105.             // Now we have N = bestK*s0, M = bestK*p0, with  N <= 50000, minPer(N) <= M <= 2N+2
  106.             int N = bestN;
  107.             int M = bestM;
  108.  
  109.             // 3)  Build an explicit connected shape whose area = N, perimeter = M.
  110.             //     Let T = (2N + 2 - M)/2  >= 0.  We factor T = x*y with x<=y, then
  111.             //     rectangle is size (x+1)x(y+1), area = (x+1)(y+1).  The leftover
  112.             //     d = N - (x+1)(y+1) cells are hung off one corner as a straight chain.
  113.             //     That construction has exactly perimeter = M.
  114.             int T = (2*N + 2 - M)/2;  
  115.             int a,b;
  116.             if (T == 0) {
  117.                 // Then (x,y)=(0,0) so a=1,b=1
  118.                 a = 1;  
  119.                 b = 1;
  120.             } else {
  121.                 int x = (int)Math.floor(Math.sqrt(T));
  122.                 while (x > 0 && T % x != 0) {
  123.                     x--;
  124.                 }
  125.                 int y = T / x;
  126.                 a = x + 1;
  127.                 b = y + 1;
  128.             }
  129.             int A_rect = a * b;
  130.             int d = N - A_rect;   // number of “chain” cells
  131.  
  132.             // 4)  Emit the coordinates:
  133.             //  - All rectangle cells: 0 <= i < a, 0 <= j < b.
  134.             //  - Then d cells: (a,0), (a,-1), …, (a,-(d-1)).
  135.             ArrayList<int[]> cells = new ArrayList<>();
  136.             for(int i=0;i<a;i++){
  137.                 for(int j=0;j<b;j++){
  138.                     cells.add(new int[]{i,j});
  139.                 }
  140.             }
  141.             for(int t2=0;t2<d;t2++){
  142.                 // chain runs “downward” from (a,0)
  143.                 cells.add(new int[]{a, -t2});
  144.             }
  145.  
  146.             // 5)  Print them
  147.             sb.append(cells.size()).append("\n");
  148.             for(int[] C: cells) {
  149.                 sb.append(C[0]).append(" ").append(C[1]).append("\n");
  150.             }
  151.         }
  152.  
  153.         System.out.print(sb);
  154.     }
  155.  
  156.     // Fast GCD
  157.     static int gcd(int a, int b) {
  158.         return (b==0 ? a : gcd(b, a%b));
  159.     }
  160.  
  161.     /** 
  162.      * minimalPerimeter(N) = \min_{(r,c): r*c = N} 2*(r + c).
  163.      * We simply try all divisors up to sqrt(N).
  164.      */
  165.     static int minimalPerimeter(int N) {
  166.         int best = Integer.MAX_VALUE;
  167.         int lim = (int)Math.floor(Math.sqrt(N));
  168.         for(int r=1; r<=lim; r++) {
  169.             if (N % r == 0) {
  170.                 int c = N / r;
  171.                 int per = 2*(r + c);
  172.                 if (per < best) best = per;
  173.             }
  174.         }
  175.         return best;
  176.     }
  177.  
  178.  
  179.     /** Very fast reader **/
  180.     static class FastReader {
  181.         BufferedReader br;
  182.         StringTokenizer st;
  183.         public FastReader() {
  184.             br = new BufferedReader(new InputStreamReader(System.in));
  185.         }
  186.         String nextToken() throws IOException {
  187.             while(st==null || !st.hasMoreTokens()) {
  188.                 String line = br.readLine();
  189.                 if(line==null) return null;
  190.                 st = new StringTokenizer(line);
  191.             }
  192.             return st.nextToken();
  193.         }
  194.         int nextInt() throws IOException {
  195.             return Integer.parseInt(nextToken());
  196.         }
  197.     }
  198. }
  199.  
Success #stdin #stdout 0.08s 55016KB
comments (?)
stdin
copy 
2
1 1
31 4
stdout
copy 
16
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
-1
https://ideone.com/U1BnFx
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!