codeforces-scrape

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

1744E1.md (1313B)


      1 Source: https://codeforces.com/problemset/problem/1744/E1
      2 
      3 E1. Divisible Numbers (easy version)
      4 
      5 time limit per test
      6 
      7 4 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 This is an easy version of the problem. The only difference between an easy and a hard version is the constraints on $a$, $b$, $c$ and $d$.
     22 
     23 You are given $4$ positive integers $a$, $b$, $c$, $d$ with $a \lt c$ and $b \lt d$. Find any pair of numbers $x$ and $y$ that satisfies the following conditions:
     24 
     25 * $a \lt x \leq c$, $b \lt y \leq d$,
     26 * $x \cdot y$ is divisible by $a \cdot b$.
     27 
     28 Note that required $x$ and $y$ may not exist.
     29 
     30 Input
     31 
     32 The first line of the input contains a single integer $t$ $(1 \leq t \leq 10$), the number of test cases.
     33 
     34 The descriptions of the test cases follow.
     35 
     36 The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($1 \leq a \lt c \leq 10^5$, $1 \leq b \lt d \leq 10^5$).
     37 
     38 Output
     39 
     40 For each test case print a pair of numbers $a \lt x \leq c$ and $b \lt y \leq d$ such that $x \cdot y$ is divisible by $a \cdot b$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 5
     48 
     49 1 1 2 2
     50 
     51 3 4 5 7
     52 
     53 8 9 15 18
     54 
     55 12 21 14 24
     56 
     57 36 60 48 66
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 2 2
     64 4 6
     65 12 12
     66 -1 -1
     67 -1 -1
     68 ```