codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2219A.md (1546B)


      1 Source: https://codeforces.com/problemset/problem/2219/A
      2 
      3 A. Grid L
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Roger has $p$ unit-length segments and $q$ L-shaped pieces, each formed by joining two unit-length segments at a right angle.
     22 
     23  ![](https://espresso.codeforces.com/0cbf71a5c455440918b2789177b20f6f676173c2.png) 
     24 
     25 He wants to use all of these pieces, with no piece left unused, to form a grid of dimensions $n \times m$.
     26 
     27 Given $p$ and $q$, determine whether there exist positive integers $n$ and $m$ such that an $n \times m$ grid can be formed using exactly $p$ unit-length segments and $q$ L-shaped pieces, possibly rotating them, and provide any valid $n$ and $m$.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $p$ and $q$ ($1 \le p, q \le 10^8$).
     34 
     35 Output
     36 
     37 For each test case, print any valid $n$ and $m$ such that it's possible to construct $n \times m$ using all pieces. If there are no such $n$ and $m$, print $-1$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 7
     45 
     46 1 2
     47 
     48 1 3
     49 
     50 5 1
     51 
     52 2 5
     53 
     54 2 10
     55 
     56 100000000 100000000
     57 
     58 1 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 
     66 1 2
     67 
     68 1 2
     69 
     70 2 2
     71 
     72 2 4
     73 
     74 -1
     75 
     76 -1
     77 ```
     78 
     79 Note
     80 
     81 Here are the constructions for examples 2, 3, and 4. We use a different color for different L-shaped pieces, black for all unit-length segments.
     82 
     83  ![](https://espresso.codeforces.com/188cc89f1253f1c7fdb045e6a75db169eb725a05.png)