Find ID of Soldier
There are N soldiers standing in a line, with IDs from 1 to N, in ascending order. They are participating in an exercise consisting of Q actions. During the ith action, the Major calls S numbers rowi and coli. The soldiers at the rowith and colith positions swap places; then the soldiers at (rowi+1)th and (coli-1)th positions swap places, and so on until (rowi+m) < (coli-m). Each of the soldier's IDs will be covered in the range [rowi, coli] for at most one action.
Write an algorithm to find the ID of the soldier at Kth position in the line after all the actions are completed.
Input
- The first line of the input consists of an integer-
num, representing the number of soldiers (N). - The second line consists of two space-separated integers-
actionsandnumSoldiers, representing the number of actions (Q) and number of soldiers called by the Major (S), respectively. - The next
Qlines consist ofSspace-separated integers -rowiandcoli, representing the positions of the soldiers initially called for theith action. - The last line consists of an integer-
posSoldier, representing the position of the soldier whose ID is requested to be found afterQactions (K).
Output
Print an integer representing the ID of the Kth position soldier in the line after Q actions.
num = 10 actions = 2 numSoldiers = 2 swaps = [[1, 5], [6, 10]] posSoldier = 1 return = 5
Step1: After the 1st action, the position of soldiers is in the order: 5 4 3 2 1 6 7 8 9 10.
Step2: After the 2nd action, the position of soldiers is in the order: 5 4 3 2 1 10 9 8 7 6.
Step3: The ID of the soldier at position 1 is 5.
So, the output is 5.
1 <= posSoldier <= num <= 10^91 <= actions <= 10^51 <= rowi <= coli <= num1 <= i <= actions
public int findIdOfSoldier(int num, int actions, int numSoldiers, int[][] swaps, int posSoldier) {
// write your code here
}