Quick write up of the Theme Park problem
Perhaps the best way is to link to the code. Run it by typing "java com.ladro.google.roller.Coaster < input.file"
In a nutshell: I start at the beginning and see how many people I can stuff into a ride. I then repeat until I come back to a user that I've seen at the head of the line. Then I stop and say that this is the "first repeatable unit" that can go in. Then I start again and do it over again. This is the repeatable unit that can go in from this time on.
I have to do the first run through as then 2nd run through starts from a different head. I'll show an example later.
This "repeatable unit" allows for you to easily compute how many rides you can do. For example if the first repeatable unit has 7 rides and gets you 100 euros while the normal repeatable unit is of size 6 and gets 101 euros you can easily see for a theme park that has 27 rides available you can do (7+6+6+6+2) rides. So that's 100 + 3*101 + f(2) = 404 + f(2) euros. Now just determine the remainder for those two extra rides you can do: you know where your repeatable unit stopped and then just add in two more.
Oh to get the 3 repeatable unit count just do this: (27-7) % 6 = 3. Your first ride through takes 7 off of the number you can give. Then do a mod 6 to find out that you can do 3 "whole" repeatable unit rides.
Here's the code it could do with a lot of trimming
package com.ladro.google.roller;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class Coaster {
private static class NaiveWay implements Iterator {
private final int[] m_groups;
private final int m_r;
private final int m_k;
private int m_pos, m_numberTrips;
private NaiveWay(int[] groups, int R, int k) {
m_groups = groups;
m_r = R;
m_k = k;
}
@Override
public boolean hasNext() {
return m_numberTrips < m_r;
}
@Override
public Long next() {
long numberPeople = 0;
int initial = m_pos;
while (numberPeople + m_groups[m_pos] <= m_k) {
numberPeople += m_groups[m_pos];
m_pos++;
if (m_pos >= m_groups.length) {
m_pos = 0;
}
if (m_pos == initial) {
break;
}
}
m_numberTrips++;
return numberPeople;
}
@Override
public void remove() {
throw new IllegalStateException();
}
}
private static class EurosAndPositionInGroup {
private final List m_euros;
private final int m_pos;
public EurosAndPositionInGroup(List p_euros, int p_pos) {
m_euros = p_euros;
m_pos = p_pos;
}
public long getTotalEuros() {
long ret = 0;
for (long e : m_euros) {
ret += e;
}
return ret;
}
}
private static class AddingValues {
private final List m_initialEuros, m_repeatingEuros;
private final long m_initialRingValue, m_repeatingRingValue;
private int initialRingSize() {
return m_initialEuros.size();
}
private long initialRingValue() {
return m_initialRingValue;
}
/**
* For use when the number of rides isn't an integer loop through
*
* @return
*/
private Iterator getAdditionalTrips() {
if (m_repeatingEuros.isEmpty()) {
// shouldn't hit this
return new ArrayList().iterator();
}
return new Iterator() {
private int myPos = 0;
@Override
public boolean hasNext() {
return true;
}
@Override
public Long next() {
long ret = m_repeatingEuros.get(myPos);
myPos++;
if (myPos >= m_repeatingEuros.size()) {
myPos = 0;
}
return ret;
}
@Override
public void remove() {
throw new IllegalStateException();
}
};
}
/**
* Find the list of euros taken for rides and also the position in the
* group that is next in line
*
* @param groups
* @param pos
* @param k
* @param R
* @return
*/
private EurosAndPositionInGroup loopIt(final int[] groups, int pos, final int k, int R) {
List euros = new ArrayList();
Set tripPos = new HashSet();
while (!tripPos.contains(pos)) {
int initial = pos;
long sum = 0;
while (sum + groups[pos] <= k) {
sum += groups[pos];
pos++;
if (pos >= groups.length) {
pos = 0;
}
if (pos == initial) {
break;
}
}
if (sum == 0) {
throw new IllegalStateException("Has value > k");
}
tripPos.add(initial);
euros.add(sum);
if (euros.size() >= R) {
pos = 0;
break;
}
}
return new EurosAndPositionInGroup(euros, pos);
}
private AddingValues(int[] groups, int R, int k) {
EurosAndPositionInGroup loopIt = loopIt(groups, 0, k, R);
boolean overLimit = loopIt.m_euros.size() >= R;
m_initialRingValue = loopIt.getTotalEuros();
final int repeatPos = loopIt.m_pos;
m_initialEuros = Collections.unmodifiableList(loopIt.m_euros);
// now go through again to find repeating loop
if (overLimit) {
m_repeatingRingValue = 0;
m_repeatingEuros = Collections.emptyList();
} else if (repeatPos == 0) {
m_repeatingRingValue = initialRingValue();
m_repeatingEuros = Collections.unmodifiableList(loopIt.m_euros);
} else {
EurosAndPositionInGroup secondRun = loopIt(groups, repeatPos, k, R);
m_repeatingRingValue = secondRun.getTotalEuros();
m_repeatingEuros = Collections.unmodifiableList(secondRun.m_euros);
}
log("Initial ring size: %d, initial value: %d, repeating ring size: %d, repeating value: %d, repeat pos: %d, k: %d, overlimit: %s",
initialRingSize(), initialRingValue(), ringSize(), ringValue(), repeatPos, k, overLimit);
}
private int ringSize() {
return m_repeatingEuros.size();
}
public long ringValue() {
return m_repeatingRingValue;
}
}
private static long solveNaive(int[] groups, int R, int k) {
Iterator naiveWay = new NaiveWay(groups, R, k);
long ret = 0;
long numberTrips = 0;
while (naiveWay.hasNext()) {
ret += naiveWay.next();
numberTrips++;
// log("NAIVE: Trip # %d : %d", numberTrips, ret);
}
log("For naive did %d trips getting %d euros", numberTrips, ret);
return ret;
}
private static long solve(int[] groups, int pR, int k) {
AddingValues av = new AddingValues(groups, pR, k);
int remainingTrips = pR;
long euros = 0;
if (remainingTrips >= av.initialRingSize()) {
remainingTrips -= av.initialRingSize();
euros += av.initialRingValue();
}
log("Start with euros %d remainging trips %d", euros, remainingTrips);
// initial pass through leaves some people in line with remaining rides
// to go
if (remainingTrips > 0) {
int loopCount = remainingTrips / av.ringSize();
long numberTrips = loopCount * av.ringSize();
euros += loopCount * av.ringValue();
Iterator eurosCounter = av.getAdditionalTrips();
remainingTrips -= numberTrips;
log("Before final move. Number loops: %d, trips: %d, euros: %d, remaining trips: %d", loopCount, numberTrips, euros, remainingTrips);
while (remainingTrips > 0) {
euros += eurosCounter.next();
remainingTrips--;
}
}
log("returning %d", euros);
return euros;
}
private static void log(String format, Object... args) {
System.err.println(String.format(format, args));
}
private static int[] getInts(Scanner scanner) {
String[] parts = scanner.nextLine().split("\\s+");
int[] ret = new int[parts.length];
for (int pos = 0; pos < ret.length; pos++) {
ret[pos] = Integer.parseInt(parts[pos]);
}
return ret;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int numberCases = Integer.parseInt(s.nextLine());
for (int caseNumber = 1; caseNumber <= numberCases; caseNumber++) {
StringBuffer output = new StringBuffer("Case #" + caseNumber + ": ");
int[] RkN = getInts(s);
int[] groups = getInts(s);
// long eurosNaive = solveNaive(groups, RkN[0], RkN[1]);
long euros = solve(groups, RkN[0], RkN[1]);
// output.append(eurosNaive + " " + euros);
output.append(euros);
// if (euros != eurosNaive)
System.out.println(output.toString());
}
}
}