Last active
August 19, 2017 23:54
-
-
Save vnnvanhuong/26e7b9e6f68677657cbe5010e1fface8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package vn.nvanhuong.coding.exercise; | |
import java.util.Scanner; | |
/** | |
* All squares (original & sub-squares) has these following characteristics: | |
* [1]. sorted entries | |
* + right entry - left entry = 1 | |
* + below entry - above entry = dimension | |
* [2]. if we know smallest entry (T), dimension (N) & orientation -> we can know the rest entries | |
*/ | |
public class Solution { | |
public static void main(String[] args) { | |
//Step 1. Find smallest entry of each input square. Time complexity: O(S) | |
//The value at cell (i,j) of a great square whose smallest entry is T is T + i*N + j | |
Scanner scanner = new Scanner(System.in); | |
int n = scanner.nextInt(); //N: size of original square | |
int s = scanner.nextInt(); //S: numbers of commands | |
long[] a = new long[s+1]; //entered rows | |
long[] b = new long[s+1]; //entered columns | |
long[] d = new long[s+1]; //entered dimension | |
long[] t = new long[s+1]; //T: found smallest entries | |
//init the original square (already known) | |
a[0] = 1; | |
b[0] = 1; | |
d[0] = n-1; | |
t[0] = 0; | |
//input and find smallest entries | |
int orientationNum = 4; | |
for (int i = 1; i <= s; i++) { | |
a[i] = scanner.nextInt(); | |
b[i] = scanner.nextInt(); | |
d[i] = scanner.nextInt(); | |
/* for example: T0 = 0, N = 7 | |
* 0 1 2 3 4 5 6 | |
* 7 8 9 10 11 12 13 | |
* 14 15 16 17 18 19 20 | |
* 21 22 23 24 25 26 27 | |
* 28 29 30 31 32 33 34 | |
* 35 36 37 38 39 40 41 | |
* 42 43 44 45 46 47 48 | |
* */ | |
//apply characteristic [2] and formula: V = T + i*N + j | |
if (i % orientationNum == 1) {//TOP | |
/* command (1,2,4) -> T1 = 0 + (1-1)*7 + (2-1) = 1 | |
/* % 29 22 15 8 1 % | |
* % 30 23 16 9 2 % | |
* % 31 24 17 10 3 % | |
* % 32 25 28 11 4 % | |
* % 33 26 19 12 5 % | |
* % % % % % % % | |
* % % % % % % % | |
* */ | |
t[i] = t[i-1] + (a[i]-a[i-1])*n + (b[i]-b[i-1]); | |
} else if (i % orientationNum == 2) {//RIGHT | |
/* command (2,3,3) -> T2 = 1 + ((2+4)-(3+3))*7 + (2-1) = 2 | |
/* % % % % % % % | |
* % % 26 25 24 23 % | |
* % % 19 18 17 16 % | |
* % % 12 11 10 9 % | |
* % % 5 4 3 2 % | |
* % % % % % % % | |
* % % % % % % % | |
* */ | |
t[i] = t[i-1]+((b[i-1]+d[i-1])-(b[i]+d[i]))*n+(a[i]-a[i-1]); | |
} else if (i % orientationNum == 3) {//BOTTOM | |
t[i] = t[i-1]+((a[i-1]+d[i-1])-(a[i]+d[i]))*n+((b[i-1]+d[i-1])-(b[i]+d[i])); | |
} else if (i % orientationNum == 0) {//LEFT | |
t[i] = t[i-1]+(b[i]-b[i-1])*n+((a[i-1]+d[i-1])-(a[i]+d[i])); | |
} | |
} | |
//Step 2. Determine some values | |
//Each square is contained in the previous one -> binary search. Time complexity: O(log S) | |
//The location of a value v in a great square whose smallest entry is T is ((v-T)/N, (v-T)%N) | |
int l = scanner.nextInt(); //L: number of queries | |
long[] w = new long[l]; | |
for (int i = 0; i < l; i++) { | |
w[i] = scanner.nextLong(); | |
int low = 0; | |
int high = s; | |
//find position of smallest entry | |
while (low != high) { | |
int mid = (low+high+1)/2; | |
if (w[i] >= t[mid] && w[i] < t[mid]+(d[mid]+1)*n && w[i]%n >= t[mid]%n && w[i]%n <= (t[mid]%n)+d[mid]){ | |
low = mid; | |
}else{ | |
high = mid-1; | |
} | |
} | |
//find position of input number with formula: (i, j) = ((v-T)/N, (v-T)%N) | |
long off1 = (w[i]-t[low])/n; | |
long off2 = (w[i]-t[low])%n; | |
if (low % orientationNum == 0) {//TOP | |
System.out.println((a[low]+off1)+" "+(b[low]+off2)); | |
} else if (low % orientationNum == 1) {//RIGHT | |
System.out.println((a[low]+off2)+" "+(b[low]+d[low]-off1)); | |
} else if (low % orientationNum == 2) {//BOTTOM | |
System.out.println((a[low]+d[low]-off1)+" "+(b[low]+d[low]-off2)); | |
} else if (low % orientationNum == 3) {//LEFT | |
System.out.println((a[low]+d[low]-off2)+" "+(b[low]+off1)); | |
} | |
} | |
scanner.close(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment