We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Geometry
  4. Circle City

Circle City

Problem
Submissions
Leaderboard
Discussions
Editorial

Roy lives in a city that is circular in shape on a plane that has radius . The city center is located at origin and it has suburbs lying on the lattice points (points with integer coordinates). The city Police Department Headquarters can only protect those suburbs which are located strictly inside the city. The suburbs located on the border of the city are still unprotected. So the police department decides to build at most additional police stations at some suburbs. Each of these police stations can protect the suburb it is located in.

Given the square of radius, , of the city, Roy has to determine if it is possible to protect all the suburbs.

Input Format
The first line of input contains integer ; test cases follow.
Each of the next lines contains two space-separated integers: , the square of the radius of the city, and , the maximum number of police stations the headquarters is willing to build.

Constraints


Output Format
For each test case, print in a new line possible if it is possible to protect all the suburbs;, otherwise, print impossible.

Sample Input

5
1 3
1 4
4 4
25 11
25 12

Sample Output

impossible
possible
possible
impossible
possible

Explanation

  • For , there are points on circumference - [(0,1), (0,-1), (1,0), (-1,0)].
  • For , there are points on circumference - [(0,2), (0,-2), (2,0),(-2,0)].
  • For , there are points on circumference - [(0,5), (0,-5), (3,4), (-3,4), (3,-4), (-3,-4), (4,3), (-4,3), (4,-3), (-4,-3), (5,0), (-5,0)].

Test Case #01: There are suburbs on the border, while we are allowed to construct max police stations.
Test Case #02: We can cover all the suburbs as exactly stations are allowed.
Test Case #03: We can cover all the suburbs as exactly stations are allowed.
Test Case #04: It is impossible to cover suburbs, on the border, with police stations.
Test Case #05: We can to cover all suburbs, on the border, with police stations.

Timelimits

Timelimits for this challenge are given here

Author

Bidhan

Difficulty

Medium

Max Score

30

Submitted By

4471

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature