254. Strange Random
time limit per test: 0.25
sec.
memory limit per test: 9216
KB
input: standard
output: standard
Integer numbers from 1 to N are written in the increasing order, clockwise along the circle. You are moving from integer to integer sequentally. You start moving clockwise from 1.
Moving operation consists of the following steps:
1) You must count Qth integer in your current moving direction and erase that integer.
2) Then you must move to the next integer clockwise.
3) If that integer is odd then your moving direction becomes clockwise (or nothing happens if you are already moving clockwise).
4) If that integer is even then your moving direction becomes counterclockwise (or nothing happens if you are already moving counterclockwise).
If there are no integers left you stop the moving process. Your goal is to find the last erased integer.
Let us consider the following example where N=5 and Q=3. The numbers will be deleted in the following order  3, 1, 4, 5, 2. The last erased number is 2.
Input
The first line of input contains N and Q (1<=N<=2000000; 1<=Q<=10).
Output
Output the last erased integer.
Sample test(s)
Input
Test #1
5 2
Test #2
5 3
Output
Test #1
3
Test #2
2
Note
See picture:
Author:  Sergey Simonchik

Resource:  Petrozavodsk Summer Training Sessions 2004

Date:  August 25, 2004

Server time: 20170920 16:51:01  Online Contester Team © 2002  2016. All rights reserved. 

