In this HackerRank Almost Integer Rock Garden problem solution you have given the values of x and y for the first stone Victor placed in the garden, place the remaining 11 stones according to the requirements above. For each stone, you place, print two space-separated integers on a new line describing the respective x and y coordinates of the stone's location.
Problem solution in Java.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStream;
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyReader in = new MyReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
AlmostIntegerRockGarden solver = new AlmostIntegerRockGarden();
solver.solve(1, in, out);
out.close();
}
static class AlmostIntegerRockGarden {
Map<Integer, Integer> m = new TreeMap<>();
Map<Integer, LinkedList<Integer[]>> m2 = new TreeMap<>();
public void solve(int testNumber, MyReader in, PrintWriter out) {
int x = in.nextInt();
int y = in.nextInt();
for (int i = -12; i <= 12; i++) {
for (int j = -12; j <= 12; j++) {
int d2 = i * i + j * j;
if (isZero(Math.sqrt(d2) - (int) (Math.sqrt(d2)))) {
// System.err.printf("zero %s \n", d2);
} else {
if (!m.containsKey(d2)) {
m.put(d2, 0);
m2.put(d2, new LinkedList<>());
}
m.put(d2, m.get(d2) + 1);
m2.get(d2).add(new Integer[]{i, j});
}
}
}
int targetD2 = x * x + y * y;
int targetidx = -1;
int n = m.size();
Integer[] vs = new Integer[n];
int[] vsSize = new int[n];
int idx = 0;
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
vs[idx] = entry.getKey();
vsSize[idx] = entry.getValue();
if (targetD2 == entry.getKey()) {
targetidx = idx;
}
idx++;
}
int[][] groups = new int[][]{
{3, 14, 14, 16, 31, 31, 31, 45, 46, 50, 52, 52},
{3, 4, 13, 19, 32, 33, 41, 43, 47, 59, 59, 59},
{21, 24, 36, 41, 41, 44, 47, 54, 56, 58, 58, 62},
{0, 9, 31, 31, 33, 34, 34, 37, 53, 56, 56, 63},
{9, 15, 15, 31, 31, 33, 34, 34, 37, 56, 60, 63},
{2, 3, 6, 8, 8, 8, 20, 25, 39, 43, 56, 62},
{0, 24, 27, 29, 40, 40, 48, 49, 49, 54, 55, 55},
{0, 2, 2, 3, 8, 20, 25, 34, 39, 43, 56, 62},
{21, 24, 26, 36, 44, 47, 54, 56, 56, 58, 58, 62},
{9, 26, 26, 26, 31, 31, 33, 34, 34, 37, 60, 63},
{11, 12, 29, 31, 35, 37, 43, 44, 44, 57, 60, 64},
{11, 12, 29, 31, 35, 37, 43, 44, 44, 53, 57, 67},
{9, 10, 21, 21, 24, 25, 30, 38, 41, 44, 48, 62},
{2, 4, 16, 19, 30, 33, 41, 43, 47, 59, 59, 59},
{4, 8, 13, 25, 27, 28, 37, 43, 45, 49, 51, 65},
{7, 9, 31, 31, 33, 34, 34, 37, 41, 41, 60, 63},
{18, 18, 28, 30, 31, 40, 42, 44, 48, 49, 61, 66},
{1, 23, 27, 28, 30, 31, 33, 46, 54, 61, 66, 66},
{3, 5, 16, 22, 31, 31, 31, 45, 46, 52, 52, 54},
{0, 10, 13, 30, 31, 31, 31, 45, 46, 50, 52, 54},
{3, 4, 4, 4, 8, 16, 20, 25, 34, 43, 56, 62},
{3, 4, 4, 8, 16, 17, 20, 25, 34, 39, 43, 56}
};
int[] g = new int[0];
for (int i = 0; i < groups.length; i++) {
for (int j = 0; j < groups[i].length; j++) {
if (groups[i][j] == targetidx) {
g = groups[i];
}
}
}
double sum = Math.sqrt(x * x + y * y);
boolean first = true;
for (int i = 0; i < g.length; i++) {
if (targetidx == g[i]) {
if (first) {
first = false;
continue;
}
}
Integer[] point = m2.get(vs[g[i]]).removeFirst();
if (point[0] == x && point[1] == y) {
point = m2.get(vs[g[i]]).removeFirst();
}
out.println(point[0] + " " + point[1]);
sum += Math.sqrt(point[0] * point[0] + point[1] * point[1]);
}
}
boolean isZero(double v) {
return Math.abs(v) < 1E-12;
}
}
static class MyReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public MyReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
inline int pack(int x,int y){
return (x+25)*64 + (y+25);
}
inline void unpack(int p,int &x,int &y){
x = (p/64)-25;
y = (p%64)-25;
}
map<double,vi> mp;
vector<double> V;
int n;
map<double,int> rev;
vector<vi> answers;
vi ids;
void appen(int a,int b,int c,int d,int e,int f,int g,int h,int i,int j,int k,int l){
vi v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
v.push_back(d);
v.push_back(e);
v.push_back(f);
v.push_back(g);
v.push_back(h);
v.push_back(i);
v.push_back(j);
v.push_back(k);
v.push_back(l);
int demi = answers.size();
answers.push_back(v);
double sum = 0.0;
REP(z,v.size()){
ids[v[z]] = demi;
sum += V[v[z]];
}
// printf("%.15f\n",sum);
}
int main(){
FOR(x,-12,13)FOR(y,-12,13){
int dst = x*x + y*y;
double sq = sqrt(dst);
int sqi = sq;
if(sqi!=sq)mp[sq].push_back(pack(x,y));
}
{
map<double,vi>::iterator iter = mp.begin();
while(iter != mp.end()){
double d = iter->first;
V.push_back(d);
iter++;
}
}
n = V.size();
REP(i,n)rev[V[i]] = i;
// go
ids.assign(n,-1);
appen(0,1,3,25,41,43,62,8,10,20,34,39);
appen(2,1,3,25,41,43,62,6,8,20,34,39);
appen(4,13,27,65,8,45,49,25,28,37,43,51);
appen(5,30,31,45,22,31,46,13,16,31,52,54);
appen(7,1,3,25,8,15,34,16,20,39,43,62);
appen(9,10,41,48,21,24,62,21,25,30,38,44);
appen(11,37,43,67,12,35,44,29,31,44,53,57);
appen(14,21,44,66,21,36,37,3,36,37,54,62);
appen(17,1,3,25,41,43,62,4,8,16,20,34);
appen(18,8,27,31,7,12,57,25,29,31,50,57);
appen(19,15,43,59,33,47,59,4,7,30,32,59);
appen(23,1,30,66,46,54,61,27,28,31,33,66);
appen(26,1,3,25,34,43,62,1,8,16,20,39);
appen(40,11,38,43,26,36,65,0,3,27,59,62);
appen(42,44,48,49,18,30,66,18,28,31,40,61);
appen(55,0,24,40,49,54,55,27,29,40,48,49);
appen(56,3,6,25,0,34,43,0,8,20,39,62);
appen(58,45,53,65,26,51,65,18,21,22,46,65);
appen(60,26,34,63,31,33,41,9,15,31,34,37);
appen(64,12,35,37,43,44,60,11,29,31,44,57);
int xx,yy;
scanf("%d%d",&xx,&yy);
double vv = sqrt(xx*xx+yy*yy);
int id = ids[rev[vv]];
vi vec = answers[id];
vi head(n,0);
bool poyo = false;
REP(i,vec.size()){
double ww = V[vec[i]];
if(!poyo && ww==vv){
poyo = true;
continue;
}
while(true){
int po = mp[ww][head[vec[i]]++];
int xxx,yyy;
unpack(po,xxx,yyy);
if(xx==xxx && yy==yyy)continue;
printf("%d %d\n",xxx,yyy);
break;
}
}
return 0;
}
0 Comments