Removal of vertices
Practice
3.6 (36 votes)
Data structures
Math basic
Basic math
Math
Problem
88% Success 7399 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

You are given an \(N-sided\) polygon where vertices are numbered from 1 to \(N\) in clockwise order, You are also given an integer \(K\). You create a vertex-explosion machine that explodes vertex in polygon thereby reducing the size of the polygon. You start with vertex 2.  At each step, one of the following operations on the polygon is performed:

  1. If \(K > 0\), then there is no effect of the vertex-explosion machine. Now, \(K\) is reduced by and you move to the next available vertex at distance in the clockwise direction.
  2. The vertex is exploded thus reducing the number of sides in the polygon by 1 and you move to the next available vertex at distance 2 in the clockwise direction from the exploded vertex. 

Note: Polygon with vertex 2 and 1 exists

For example, if \(N = 4\) and \(K = 2\), then the following diagram displays an explanation.

You are required to determine the remaining last vertex. 

Explanation of Test Case 1

Input format

  • The first line contains \(T\) denoting the number of test cases.
  • For each test case, the first line contains integers \(N\) and \(K\) denoting sides of the polygon and integer respectively.

Output format

Print an integer denoting the last-remaining vertex.

Constraints

\(1 \leq T \leq 10\)

\(3 \leq N \leq 10^{14}\)

\(1 \leq K \leq 10^{14}\)

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
Tags:
HiringOpenHiringOpenImplementationHiringMathematicsEasyBasic ProgrammingMathematicsMathematicsMathamatics
Points:50
12 votes
Tags:
Data StructuresGraph TheoryOpenDivide-and-conquer algorithmHardAlgorithms
Points:30
3 votes
Tags:
AlgorithmsOpenApprovedMediumMathamatics