On Tuesday, 14 August 2018 04:01:48 UTC+10, SHUBHAM KUMAR SHUKLA wrote:
> can please share code
Sure
This is problem A
//package kickstart.Y18.RoundD.A;
import java.util.Scanner;
public class QuestionA {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int t = keyboard.nextInt();
keyboard.nextLine();
int count = 1;
while(t-- > 0) {
String[] temp = keyboard.nextLine().split(" ");
int n = Integer.parseInt(temp[0]);
int o = Integer.parseInt(temp[1]);
double d = Double.parseDouble(temp[2]);
temp = keyboard.nextLine().split(" ");
int x1 = Integer.parseInt(temp[0]);
int x2 = Integer.parseInt(temp[1]);
int a = Integer.parseInt(temp[2]);
int b = Integer.parseInt(temp[3]);
int c = Integer.parseInt(temp[4]);
int m = Integer.parseInt(temp[5]);
int l = Integer.parseInt(temp[6]);
double[] candies = new double[n];
double[] xArray = new double[n];
double[] ss = new double[n];
int[] oddCount = new int[n];
xArray[0] = x1;
candies[0] = x1 + l;
oddCount[0] = !(candies[0] % 2 == 0) ? 1 : 0;
ss[0] = candies[0];
xArray[1] = x2;
candies[1] = x2 + l;
oddCount[1] = !(candies[1] % 2 == 0) ? oddCount[0] + 1 :
oddCount[0];
ss[1] = ss[0] + candies[1];
for(int i = 2; i < n; i++) {
xArray[i] = (a * xArray[i - 1] + b * xArray[i - 2] + c) % m;
candies[i] = ((a * xArray[i - 1] + b * xArray[i - 2] + c) % m)
+ l;
oddCount[i] = !(candies[i] % 2 == 0) ? oddCount[i - 1] + 1 :
oddCount[i - 1];
ss[i] = ss[i - 1] + candies[i];
}
double max = -1 * Double.MAX_VALUE;
double lastMax = max;
int cursor = 0;
int flag = 0;
for(int i = 0; i < n; i++) {
double localMax = lastMax;
double curMax = lastMax;
cursor = flag;
int so = (i == 0) ? oddCount[cursor] : oddCount[cursor] -
oddCount[i - 1];
if(localMax > d) {
localMax = -1 * Double.MAX_VALUE;
cursor = i;
so = (candies[i] % 2 == 0) ? 0 : 1;
}
if(localMax > max && so <= o) {
max = localMax;
curMax = localMax;
if(cursor == i) {
lastMax = -1 * Double.MAX_VALUE;
} else {
lastMax = curMax - candies[i];
}
}
while(so <= o){
localMax = (i == 0) ? ss[cursor] : ss[cursor] - ss[i - 1];
if(localMax > d) {
if(cursor == i) {
lastMax = -1 * Double.MAX_VALUE;
} else {
lastMax = curMax - candies[i];
}
break;
}
if(localMax > max) {
max = localMax;
curMax = localMax;
if(cursor == i) {
lastMax = -1 * Double.MAX_VALUE;
} else {
lastMax = curMax - candies[i];
}
}
if(cursor == n - 1) {
break;
} else {
cursor++;
}
so = (i == 0) ? oddCount[cursor] : oddCount[cursor] -
oddCount[i - 1];
}
if(cursor == i) {cursor++;}
flag = cursor;
}
if(max == -1 * Double.MAX_VALUE) {
System.out.printf("Case #%d: IMPOSSIBLE\n", count);
} else {
System.out.printf("Case #%d: %.0f\n", count, max);
}
count++;
}
}
}
This is problem B
//package kickstart.Y18.RoundD.B;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Set;
import java.util.Map;
import java.util.TreeMap;
import java.util.HashMap;
import javafx.util.Pair;
public class QuestionB {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
int count = 1;
while(t-- > 0) {
int n = in.nextInt();
int k = in.nextInt();
int p1 = in.nextInt();
int p2 = in.nextInt();
int a1 = in.nextInt();
int b1 = in.nextInt();
int c1 = in.nextInt();
int m1 = in.nextInt();
int h1 = in.nextInt();
int h2 = in.nextInt();
int a2 = in.nextInt();
int b2 = in.nextInt();
int c2 = in.nextInt();
int m2 = in.nextInt();
int x1 = in.nextInt();
int x2 = in.nextInt();
int a3 = in.nextInt();
int b3 = in.nextInt();
int c3 = in.nextInt();
int m3 = in.nextInt();
int y1 = in.nextInt();
int y2 = in.nextInt();
int a4 = in.nextInt();
int b4 = in.nextInt();
int c4 = in.nextInt();
int m4 = in.nextInt();
int[] pn = new int[n];
int[] hn = new int[n];
int[] xn = new int[k];
int[] yn = new int[k];
TreeMap<Integer, Integer> towers = new TreeMap<>();
HashMap<Pair<Integer, Integer>, Integer> balloons = new HashMap<>();
pn[0] = p1;
pn[1] = p2;
hn[0] = h1;
hn[1] = h2;
xn[0] = x1;
xn[1] = x2;
yn[0] = y1;
yn[1] = y2;
towers.put(pn[0], hn[0]);
towers.put(pn[1], hn[1]);
balloons.put(new Pair<Integer, Integer>(xn[0], yn[0]), 1);
Pair<Integer, Integer> balloon = new Pair<>(xn[1], yn[1]);
if(balloons.containsKey(balloon)) {
balloons.put(balloon, balloons.get(balloon) + 1);
} else {
balloons.put(balloon, 1);
}
for(int i = 2; i < n; i++) {
pn[i] = ((a1 * pn[i-1] + b1 * pn[i-2] + c1) % m1) + 1;
hn[i] = ((a2 * hn[i-1] + b2 * hn[i-2] + c2) % m2) + 1;
towers.put(pn[i], hn[i]);
}
for(int i = 2; i < k; i++) {
xn[i] = ((a3 * xn[i-1] + b3 * xn[i-2] + c3) % m3) + 1;
yn[i] = ((a4 * yn[i-1] + b4 * yn[i-2] + c4) % m4) + 1;
balloon = new Pair<>(xn[i], yn[i]);
if(balloons.containsKey(balloon)) {
balloons.put(balloon, balloons.get(balloon) + 1);
} else {
balloons.put(balloon, 1);
}
}
ArrayList<Map.Entry<Integer, Integer>> relevantTower = new
ArrayList<>();
for(Map.Entry<Integer, Integer> entry : towers.entrySet()) {
int x = entry.getKey();
int y = entry.getValue();
while(true) {
if(relevantTower.isEmpty()) {
relevantTower.add(entry);
break;
}
Map.Entry<Integer, Integer> flag =
relevantTower.get(relevantTower.size() - 1);
int xDistance = x - flag.getKey();
int yDistance = Math.abs(y - flag.getValue());
if(yDistance < xDistance) {
// relevant
relevantTower.add(entry);
break;
} else {
// irrelevant
if(flag.getValue() > y) {
break;
} else {
relevantTower.remove(relevantTower.size() - 1);
}
}
}
}
int sumOfBalloon = 0;
for(Map.Entry<Pair<Integer, Integer>, Integer> entry :
balloons.entrySet()) {
Pair<Integer, Integer> balloonCo = entry.getKey();
int num = entry.getValue();
int balloonX = balloonCo.getKey();
int balloonY = balloonCo.getValue();
if(balloonX < relevantTower.get(0).getKey()) {
if(relevantTower.get(0).getKey() - balloonX <=
relevantTower.get(0).getValue() - balloonY) {
sumOfBalloon += num;
}
} else if(balloonX == relevantTower.get(0).getKey()) {
if(balloonY <= relevantTower.get(0).getValue()) {
sumOfBalloon += num;
}
} else if(balloonX >
relevantTower.get(relevantTower.size()-1).getKey()) {
if(relevantTower.get(relevantTower.size()-1).getKey() -
balloonX <= relevantTower.get(relevantTower.size()-1).getValue() - balloonY) {
sumOfBalloon += num;
}
} else if(balloonX ==
relevantTower.get(relevantTower.size()-1).getKey()) {
if(balloonY <=
relevantTower.get(relevantTower.size()-1).getValue()) {
sumOfBalloon += num;
}
} else {
int index = binarySearch(balloonX, relevantTower);
if(index == -1) {
System.out.println("something wrong with binary
search");
System.exit(1);
}
int leftX = relevantTower.get(index).getKey();
int rightX = relevantTower.get(index + 1).getKey();
int leftY = relevantTower.get(index).getValue();
int rightY = relevantTower.get(index + 1).getValue();
if(balloonX == leftX) {
if(balloonY <= leftY) {
sumOfBalloon += num;
}
} else if(balloonX == rightX) {
if(balloonY <= rightY) {
sumOfBalloon += num;
}
} else if(balloonX - leftX <= leftY - balloonY) {
sumOfBalloon += num;
} else if(rightX - balloonX <= rightY - balloonY) {
sumOfBalloon += num;
}
}
}
System.out.printf("Case #%d: %d\n", count, sumOfBalloon);
count++;
}
}
private static int binarySearch(int balloonX, ArrayList<Map.Entry<Integer,
Integer>> relevantTower) {
int low = 0;
int high = relevantTower.size() - 1;
while(high >= low) {
int mid = (high + low) / 2;
if(mid == relevantTower.size() - 1) {
return mid - 1;
} else if(relevantTower.get(mid).getKey() > balloonX) {
high = mid - 1;
} else if(relevantTower.get(mid).getKey() < balloonX &&
relevantTower.get(mid+1).getKey() < balloonX) {
low = mid + 1;
} else if(relevantTower.get(mid).getKey() < balloonX &&
relevantTower.get(mid+1).getKey() >= balloonX) {
return mid;
} else if(relevantTower.get(mid).getKey() == balloonX) {
return mid;
}
}
return -1;
}
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/21e54484-2f49-42ee-b89f-5588210e983d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
