genek
February 9, 2018, 3:06pm
#1
When solving this puzzle I get error:
Timeout: the program did not provide 1 input lines in due time…
I can’t figure out why.
Here is my java code
import javax.swing.event.AncestorEvent;
import java.util.*;
import java.io.*;
import java.math.*;
/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
class Player {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int boxCount = in.nextInt();
float [][] packages = new float [boxCount][3];
for (int i = 0; i < boxCount; i++) {
float weight = in.nextFloat();
float volume = in.nextFloat();
packages[i][0] = weight;
packages[i][1] = volume;
packages[i][2] = (float)i;
}
Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
int [] answer = new int [boxCount];
int truckNr = 0;
for (int i = 0; i < packages.length/2; i++)
{
answer[(int)packages[i][2]] = truckNr;
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckNr++;
if(truckNr == 100)
truckNr = 0;
}
// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");
for (int i = 0; i < answer.length; i++)
{
if(i != answer.length)
System.out.print(answer[i] + " ");
else
System.out.print(answer[i]);
}
}
}
You need a carriage return.
Either use : System.out.println(); after your loop
Or : System.out.print(answer[i]+"\n"); for the last item.
PS: You will need to fix your condition since your never enter your else statement.
1 Like
genek
February 9, 2018, 11:38pm
#3
Ok, now it works, but I exceeded max capacity of truck. I try to remedy it with code
class Player {
static int truckNr = 0;
static int functionCalls = 0;
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int boxCount = in.nextInt();
float [][] packages = new float [boxCount][3];
float [] truckLoad = new float [100];
for (int i = 0; i < boxCount; i++) {
float weight = in.nextFloat();
float volume = in.nextFloat();
packages[i][0] = weight;
packages[i][1] = volume;
packages[i][2] = (float)i;
}
Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
int [] answer = new int [boxCount];
for (int i = 0; i < packages.length/2; i++)
{
if(checkLoad(truckLoad))
{
answer[(int)packages[i][2]] = truckNr;
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
}
truckLoad[truckNr] += packages[i][1];
truckNr++;
if(truckNr == 100)
truckNr = 0;
}
// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");
for (int i = 0; i < answer.length; i++)
{
if(i < answer.length)
System.out.print(answer[i] + " ");
else
System.out.print(answer[i] + "\n");
}
}
static boolean checkLoad(float [] truckLoad)
{
if(functionCalls>100)
return false;
else
functionCalls++;
if(truckLoad[truckNr] <= 100)
return true;
else
{
truckNr++;
if(truckNr == 100)
truckNr = 0;
checkLoad(truckLoad);
}
return true;
}
}
but i still get timeout error.
if(i < answer.length - 1)
instead of if(i < answer.length)
genek
February 10, 2018, 3:26pm
#5
Ok I fixed that, but I exceeded lcapacity of truck 0, and didn’t know why, There is a lot of 0 in output. For example 0 0 50 0 0 95 0 0 50 0 0 4 14 0 0 0 26 0 0 0 70 0 0 93 0 0 0 0 0 0 0
genek
February 10, 2018, 7:07pm
#6
Fixed it. It was problem with checkLoad function. I didn’t reset variable that counts function calls if it returns true.
Now i exceedes capacity of truck 95
class Player {
static int truckNr = 0;
static int functionCalls = 0;
static float [] truckLoad = new float [100];
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int boxCount = in.nextInt();
float [][] packages = new float [boxCount][3];
Arrays.fill(truckLoad, 0);
for (int i = 0; i < boxCount; i++) {
float weight = in.nextFloat();
float volume = in.nextFloat();
packages[i][0] = weight;
packages[i][1] = volume;
packages[i][2] = (float)i;
}
Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
int [] answer = new int [boxCount];
for (int i = 0; i < packages.length/2; i++)
{
float v1 = packages[i][1];
float v2 = packages[packages.length - 1 - i][1];
if(checkLoad(v1, v2))
{
answer[(int)packages[i][2]] = truckNr;
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckLoad[truckNr] += v1;
truckLoad[truckNr] += v2;
}else if(checkLoad(v1, 0))
{
answer[(int)packages[i][2]] = truckNr;
truckLoad[truckNr] += v1;
if(checkLoad(0, v2))
{
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckLoad[truckNr] += v2;
}
}
truckNr++;
if(truckNr == 100)
truckNr = 0;
}
// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");
for (int i = 0; i < answer.length; i++)
{
if(i < answer.length - 1)
System.out.print(answer[i] + " ");
else
System.out.print(answer[i] + "\n");
}
}
static boolean checkLoad(float volume1, float volume2)
{
if(functionCalls>100)
return false;
else
functionCalls++;
if(truckLoad[truckNr] + volume1 + volume2 <= 100)
{
functionCalls = 0;
return true;
}else
{
truckNr++;
if(truckNr == 100)
truckNr = 0;
checkLoad(volume1, volume2);
}
functionCalls = 0;
return true;
}
}
genek
February 11, 2018, 4:56pm
#7
I fixed truck 95 overload, but now it;s truck 0 again.
class Player {
static int truckNr = 0;
static int functionCalls = 0;
static float [] truckLoad = new float [100];
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int boxCount = in.nextInt();
float [][] packages = new float [boxCount][3];
Arrays.fill(truckLoad, 0);
for (int i = 0; i < boxCount; i++) {
float weight = in.nextFloat();
float volume = in.nextFloat();
packages[i][0] = weight;
packages[i][1] = volume;
packages[i][2] = (float)i;
}
Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
int [] answer = new int [boxCount];
for (int i = 0; i < packages.length/2; i++)
{
float v1 = packages[i][1];
float v2 = packages[packages.length - 1 - i][1];
if(checkLoad(v1, v2))
{
answer[(int)packages[i][2]] = truckNr;
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckLoad[truckNr] += v1;
truckLoad[truckNr] += v2;
}else if(checkLoad(v1, 0))
{
answer[(int)packages[i][2]] = truckNr;
truckLoad[truckNr] += v1;
for(int j = 0; j < 100; j++)
{
truckNr++;
if(truckNr >= 100)
truckNr = 0;
if(checkLoad(0, v2))
{
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckLoad[truckNr] += v2;
break;
}
}
}else
{
for(int j = 0; j < 100; j++)
{
truckNr++;
if(truckNr >= 100)
truckNr = 0;
if(checkLoad(v1, v2))
{
answer[(int)packages[i][2]] = truckNr;
answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
truckLoad[truckNr] += v2;
truckLoad[truckNr] += v1;
break;
}
}
}
truckNr++;
if(truckNr >= 100)
truckNr = 0;
}
// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");
for (int i = 0; i < answer.length; i++)
{
if(i < answer.length - 1)
System.out.print(answer[i] + " ");
else
System.out.print(answer[i] + "\n");
}
}
static boolean checkLoad(float volume1, float volume2)
{
if(truckLoad[truckNr] + volume1 + volume2 <= 100)
return true;
else
return false;
}
}
genek
February 20, 2018, 10:13pm
#8
I change code a little bit. I flll trucks at first empty spot and it works, but when i try to swap some packages trucks get full.
class Player {
static int truckNr = 0;
static float [] truckLoad = new float [100]; // volume in each truck
static float [] truckWeight = new float [100]; // weight in each truck
static long startTime = System.nanoTime();
static float maxWeight = 0f;
static float minWeight = 0f;
static float delta = 0f;
static int minWeightTruckNr = 0, maxWeightTruckNr = 0;
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int boxCount = in.nextInt();
float [][] packages = new float [boxCount][3];
Arrays.fill(truckLoad, 0);
for (int i = 0; i < boxCount; i++) {
float weight = in.nextFloat();
float volume = in.nextFloat();
packages[i][0] = weight;
packages[i][1] = volume;
packages[i][2] = (float)i; //nr of package
}
Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
int [] answer = new int [boxCount]; //table with answers
//initial fill
for (int i = 0; i < packages.length; i++)
{
float v1 = packages[i][1];
for(int j = 0; j < 101; j++)
{
if(checkLoad(truckNr, v1))
{
answer[(int)packages[i][2]] = truckNr;
truckLoad[truckNr] += v1; //add volume to truck
truckWeight[truckNr] = packages[i][0]; //add weight to truck
truckNr++;
if(truckNr == 100)
truckNr = 0;
break;
}
truckNr++;
if(truckNr == 100)
truckNr = 0;
}
}
changeMaxMin();
delta = maxWeight - minWeight;
//loop responsible for packages swapping
while ((System.nanoTime() - startTime) < 49900000000L) //check if time for calculation passed
{
float tempMinWeightVolume = 0f, tempMaxWeightVolume = 0f; //volume of packages from min and max weight truck
float tempMaxWeightPackage = 0f, tempMinWeightPackage = 0f; //weight of packages from min and max weight truck
boolean maxVFound = false, minVFound = false;
int tempMinWeightTruckNr = minWeightTruckNr;
int tempMaxWeightTruckNr = maxWeightTruckNr;
int minAnswerNr = 0, maxAnswerNr = 0;
// find packages to swap
for(int i = 0; i < boxCount; i++)
{
//find package from max weight truck
if(!maxVFound && answer[i] == maxWeightTruckNr)
{
tempMaxWeightPackage = packages[i][0]; //get package weight
tempMaxWeightVolume = packages[i][1]; //get package volume
maxAnswerNr = (int)packages[i][2]; //get package nr
maxVFound = true;
}
//find package from min weight truck
if(!minVFound && answer[i] == minWeightTruckNr)
{
tempMinWeightPackage = packages[i][0]; //get package weight
tempMinWeightVolume = packages[i][1]; //get package volume
minAnswerNr = (int)packages[i][2]; //get package nr
minVFound = true;
}
//break loop if packages found
if(minVFound && maxVFound)
break;
}
if(checkLoad(tempMaxWeightTruckNr, tempMinWeightVolume, tempMaxWeightVolume) &&
checkLoad(tempMinWeightTruckNr, tempMaxWeightVolume, tempMinWeightVolume)) //check if packages can be swapped
{
//change load of trucks
truckLoad[tempMaxWeightTruckNr] = truckLoad[tempMaxWeightTruckNr] + tempMinWeightVolume - tempMaxWeightVolume;
truckLoad[tempMinWeightTruckNr] = truckLoad[tempMinWeightTruckNr] + tempMaxWeightVolume - tempMinWeightVolume;
//change answer
answer[minAnswerNr] = tempMaxWeightTruckNr;
answer[maxAnswerNr] = tempMinWeightTruckNr;
//change weight
truckWeight[tempMaxWeightTruckNr] = truckWeight[tempMaxWeightTruckNr] + tempMinWeightPackage - tempMaxWeightPackage;
truckWeight[tempMinWeightTruckNr] = truckWeight[tempMinWeightTruckNr] + tempMaxWeightPackage - tempMinWeightPackage;
}
changeMaxMin();
float newDelta = maxWeight - minWeight; //calculate new delta
if(newDelta < delta)
{
delta = newDelta;
}else
{
//reverse changes
truckLoad[tempMaxWeightTruckNr] = truckLoad[tempMaxWeightTruckNr] + tempMaxWeightVolume - tempMinWeightVolume;
truckLoad[tempMinWeightTruckNr] = truckLoad[tempMinWeightTruckNr] + tempMinWeightVolume - tempMaxWeightVolume;
answer[minAnswerNr] = tempMinWeightTruckNr;
answer[maxAnswerNr] = tempMaxWeightTruckNr;
truckWeight[tempMaxWeightTruckNr] = truckWeight[tempMaxWeightTruckNr] + tempMaxWeightPackage - tempMinWeightPackage;
truckWeight[tempMinWeightTruckNr] = truckWeight[tempMinWeightTruckNr] + tempMinWeightPackage - tempMaxWeightPackage;
changeMaxMin();
}
if(delta < 20f)
break;
}
// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");
for (int i = 0; i < answer.length; i++)
{
if(i < answer.length - 1)
System.out.print(answer[i] + " ");
else
System.out.print(answer[i] + "\n");
}
}
// check if added load exceed truck's limit
static boolean checkLoad(int truckNr, float volume1)
{
if(truckLoad[truckNr] + volume1 <= 100)
return true;
else
return false;
}
//check if swapped load exceed truck's limit
static boolean checkLoad(int truckNr, float volume1, float volume2)
{
if(truckLoad[truckNr] + volume1 - volume2 <= 100)
return true;
else
return false;
}
// find max and min weight and corresponding trucks
static void changeMaxMin()
{
minWeight = truckWeight[0];
maxWeight = truckWeight[0];
minWeightTruckNr = 0; //nr of truck that has min weight
maxWeightTruckNr = 0; //nr of truck that has max weight
for (int i = 0; i < 100; i+=2)
{
if(truckWeight[i] < truckWeight[i+1])
{
if(minWeight > truckWeight[i])
{
minWeight = truckWeight[i];
minWeightTruckNr = i;
}
if(maxWeight < truckWeight[i+1])
{
maxWeight = truckWeight[i+1];
maxWeightTruckNr = i + 1;
}
}else
{
if(minWeight > truckWeight[i+1])
{
minWeight = truckWeight[i+1];
minWeightTruckNr = i + 1;
}
if(maxWeight < truckWeight[i])
{
maxWeight = truckWeight[i];
maxWeightTruckNr = i;
}
}
}
}
}