There are N farms in a row, at each farm you either i) collect apples or ii) drink milk(energy). Visiting each farm costs you one unit of energy. This means if energy becomes zero, you cannot visit anymore farms. Given initial energy (even before first farm is visited) as P, find the maximum number of apples which we can collect.
Input
T (the number of test cases)
N P (in each test case the first line has N-the number of farms and P-the initial energy)
m1 m2 m3 m4 … mN (the milk values at each farm)
a1 a2 a3 … aN (the apples available at each farm)
.
.
.
(t such cases)
Output
In each line, output the maximum number of apples which can be collected.
amax1
amax2
.
.
(t such lines)
Test case 0
2
5 1
5 4 3 2 1
5 4 3 2 1
5 1
3 0 0 1 2
4 5 1 10 20
Expected output for Test case 0
10
36
import java.util.ArrayList;
class FarmOutput {
public FarmOutput() {
this._collected = 0;
}
public FarmOutput(int collected) {
this._collected = collected;
}
int _collected;
}
@SuppressWarnings("unused")
public class HowManyApples {
private class Farm {
Farm(String[] data) {
this._currentEnergy = this._initialEnergy = Integer.parseInt(data[0].substring(2));
for(int index = 0; index < Integer.parseInt(data[0].substring(0, 1)); index++) {
this._energyAppleMap.add(new Pair(data[1].split(" ")[index], data[2].split(" ")[index]));
}
}
int _initialEnergy;
int _currentEnergy;
private int _farmPosition = -1;
private class Pair {
Pair(String milk, String apple) {
this._milk = Integer.parseInt(milk);
this._apple = Integer.parseInt(apple);
}
Pair(int milk, int apple) {
this._milk = milk;
this._apple = apple;
}
int _milk;
int _apple;
}
int getApple() {
return this._energyAppleMap.get(this._farmPosition)._apple;
}
int getMilk() {
return this._energyAppleMap.get(this._farmPosition)._milk;
}
int getRemainingApples(int farmToVisit) {
return this.getRemaining(this._farmPosition + 1, farmToVisit)._apple;
}
int getRemainingMilk(int farmToVisit) {
return this.getRemaining(this._farmPosition + 1, farmToVisit)._milk;
}
int getSize() {
return this._energyAppleMap.size();
}
boolean canMove() {
return this._currentEnergy > 0 && this._farmPosition < (this.getSize() - 1);
}
void move() {
if(this.canMove()) {
this._farmPosition++;
this._currentEnergy--;
}
}
int farmsToBeVisited() {
return this.getSize() - this._farmPosition - 1;
}
void consumeEnergy() {
this._currentEnergy += this._energyAppleMap.get(this._farmPosition)._milk;
}
private Pair getRemaining(int start, int end) {
final Pair pair = new Pair(0, 0);
int endPos = (end >= this._energyAppleMap.size() ? this._energyAppleMap.size() - 1 : end);
for(int index = start; index <= endPos; index++) {
pair._apple += this._energyAppleMap.get(index)._apple;
pair._milk += this._energyAppleMap.get(index)._milk;
}
return pair;
}
private ArrayList
_energyAppleMap = new ArrayList<>();
}
private Farm[] _farms;
public HowManyApples(String[] testCases, String splitter) {
this._farms = new Farm[testCases.length];
for(int index = 0; index < testCases.length; index++) {
this._farms[index] = new Farm(testCases[index].split(splitter));
}
}
public FarmOutput[] getMaxApplesCollected() {
FarmOutput[] outputs = new FarmOutput[this._farms.length];
for(int index = 0; index < this._farms.length; index++) {
if(!this._farms[index].canMove()) {
outputs[index] = new FarmOutput(0);
} else {
outputs[index] = new FarmOutput(this.getApplesCollected(this._farms[index]));
}
}
return outputs;
}
public void printParsedInput() {
for(int index = 0; index < this._farms.length; index++) {
System.out.println(this._farms[index].getSize() + " " + this._farms[index]._initialEnergy);
this._farms[index]._energyAppleMap.forEach((pair) -> {
System.out.print(pair._milk + " ");
});
System.out.println("");
this._farms[index]._energyAppleMap.forEach((pair) -> {
System.out.print(pair._apple + " ");
});
System.out.println("");
}
}
private int getApplesCollected(Farm farm) {
int collectedApples = 0;
while(farm.canMove()) {
farm.move();
if(farm._currentEnergy >= farm.farmsToBeVisited()) {
collectedApples += farm.getApple();
continue;
}
int consumableEnergy = farm.getMilk();
int applesToBeCollectedWithCurEnergy = farm.getRemainingApples(farm._currentEnergy);
int applesToBeCollectedWithAllEnergy = farm.getRemainingApples(farm._currentEnergy + consumableEnergy);
if(applesToBeCollectedWithAllEnergy > applesToBeCollectedWithCurEnergy) {
farm.consumeEnergy();
} else {
collectedApples += farm.getApple();
}
}
return collectedApples;
}
}
import java.util.Scanner;
public class HelloWorld {
public static void main(String[] args) {
demoApples();
}
static void demoApples() {
final String Splitter = ":";
Scanner scanner = new Scanner(System.in);
System.out.println("Paste the input as per right structure");
int noOfTestCases = Integer.parseInt(scanner.nextLine());
String[] testCases = new String[noOfTestCases];
for(int index = 0; index < noOfTestCases; index++) {
testCases[index] = scanner.nextLine() + Splitter + scanner.nextLine() + Splitter + scanner.nextLine();
}
scanner.close();
HowManyApples demo1 = new HowManyApples(testCases, Splitter);
FarmOutput[] output = demo1.getMaxApplesCollected();
for(int index = 0; index < output.length; index++) {
System.out.println(output[index]._collected);
}
}
}
