Soluție HackerRank pentru Making Candies. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Making Candies

Cerinta completa

Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies.

Karl just started a level in which he must accumulate [Expresie matematică indisponibilă în copia arhivată] candies starting with [Expresie matematică indisponibilă în copia arhivată] machines and [Expresie matematică indisponibilă în copia arhivată] workers. In a single pass, he can make [Expresie matematică indisponibilă în copia arhivată] candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers. Buying a machine or hiring a worker costs [Expresie matematică indisponibilă în copia arhivată] units, and there is no limit to the number of machines he can own or workers he can employ.

Karl wants to minimize the number of passes to obtain the required number of candies at the end of a day. Determine that number of passes.

For example, Karl starts with [Expresie matematică indisponibilă în copia arhivată] machine and [Expresie matematică indisponibilă în copia arhivată] workers. The cost to purchase or hire, [Expresie matematică indisponibilă în copia arhivată] and he needs to accumulate [Expresie matematică indisponibilă în copia arhivată] candies. He executes the following strategy:

  1. Make [Expresie matematică indisponibilă în copia arhivată] candies. Purchase two machines.
  2. Make [Expresie matematică indisponibilă în copia arhivată] candies. Purchase [Expresie matematică indisponibilă în copia arhivată] machines and hire [Expresie matematică indisponibilă în copia arhivată] workers.
  3. Make [Expresie matematică indisponibilă în copia arhivată] candies. Retain all [Expresie matematică indisponibilă în copia arhivată] candies.
  4. Make [Expresie matematică indisponibilă în copia arhivată] candies. With yesterday’s production, Karl has [Expresie matematică indisponibilă în copia arhivată] candies.

It took [Expresie matematică indisponibilă în copia arhivată] passes to make enough candies.

Function Description

Complete the minimumPasses function in the editor below. The function must return a long integer representing the minimum number of passes required.

minimumPasses has the following parameter(s):

  • m: long integer, the starting number of machines
  • w: long integer, the starting number of workers
  • p: long integer, the cost of a new hire or a new machine
  • n: long integer, the number of candies to produce

Input Format

A single line consisting of four space-separated integers describing the values of [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], the starting number of machines and workers, the cost of a new machine or a new hire, and the the number of candies Karl must accumulate to complete the level.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

Return a long integer denoting the minimum number of passes required to accumulate at least [Expresie matematică indisponibilă în copia arhivată] candies.

Sample Input

3 1 2 12

Sample Output

3

Explanation

Karl makes three passes:

  1. In the first pass, he makes [Expresie matematică indisponibilă în copia arhivată] candies. He then spends [Expresie matematică indisponibilă în copia arhivată] of them hiring another worker, so [Expresie matematică indisponibilă în copia arhivată] and he has one candy left over.
  2. In the second pass, he makes [Expresie matematică indisponibilă în copia arhivată] candies. He spends [Expresie matematică indisponibilă în copia arhivată] of them on another machine and another worker, so [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] and he has [Expresie matematică indisponibilă în copia arhivată] candies left over.
  3. In the third pass, Karl makes [Expresie matematică indisponibilă în copia arhivată] candies. Because this satisfies his goal of making at least [Expresie matematică indisponibilă în copia arhivată] candies, we print the number of passes (i.e., [Expresie matematică indisponibilă în copia arhivată]) as our answer.

Limbajul de programare folosit: java8

Cod:

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long m = sc.nextLong();
		long w = sc.nextLong();
		long p = sc.nextLong();
		long n = sc.nextLong();
		System.out.println(solve(m, w, p, n));

		sc.close();
	}

	static long solve(long m, long w, long p, long n) {
		if (BigInteger.valueOf(m).multiply(BigInteger.valueOf(w)).compareTo(BigInteger.valueOf(n)) > 0) {
			return 1;
		}

		long minPass = Long.MAX_VALUE;
		long currentPass = 0;
		long production = 0;
		while (true) {
			long remainPass = divideToCeil(n - production, m * w);
			minPass = Math.min(minPass, currentPass + remainPass);

			if (remainPass == 1) {
				break;
			}

			if (production < p) {
				long extraPass = divideToCeil(p - production, m * w);

				currentPass += extraPass;
				production += extraPass * m * w;

				if (production >= n) {
					minPass = Math.min(minPass, currentPass);

					break;
				}
			}

			production -= p;
			if (m <= w) {
				m++;
			} else {
				w++;
			}
		}
		return minPass;
	}

	static long divideToCeil(long x, long y) {
		return x / y + (x % y == 0 ? 0 : 1);
	}
}

Scor obtinut: 1.0

Submission ID: 464602889

Link challenge: https://www.hackerrank.com/challenges/making-candies/problem

Making Candies