Problem Name: beecrowd | 3258

Problem Link:

Boiling Vegetables


By Andreas Björklund & Lukáš Poláček FI Finland

Timelimit: 1

The trick to boiling vegetables is to make sure all pieces are about the same size. If they are not, the small ones get too soft or the large ones get undercooked (or both). Fortunately, you have heard of the kitchen knife, but your parents’ warnings of using sharp instruments still echoes in your head. Therefore you better use it as little as possible. You can take a piece of a vegetable of weight and cut it arbitrarily in two pieces of weight Wleft and Wright, where Wleft + Wright = W. This operation constitutes a “cut”. Given a set of pieces of vegetables, determine the minimum number of cuts needed to make the ratio between the smallest and the largest resulting piece go above a given threshold.




The input starts with a floating point number T with 2 decimal digits, 0.5 < T < 1, and a positive integer N ≤ 1 000. Next follow N positive integer weights W₁, W₂, ..., WN. All weights are less than 10⁶ .




Output the minimum number of cuts needed to make the ratio between the resulting minimum weight piece and the resulting maximum weight piece be above T. You may assume that the number of cuts needed is less than 500.

To avoid issues with floating point numbers, you can assume that the optimal answer for ratio T is the same as for ratio T + 0.0001.




Input Samples Output Samples

0.99 3

2000 3000 4000





0.80 2

1000 1400



Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAXSIZE 1234

int n;
double ratio;
int values[MAXSIZE];

int solve(int, double, double, int);
int compare(const void *, const void *);

static inline double max(double a, double b)

    return a > b ? a : b;

static inline double min(double a, double b)

    return a  <  b ? a : b;

int main()

    scanf("%lf %d", &ratio, &n);

    for (int i = 0; i  <  n; ++i)
        scanf("%d", &values[i]);

    qsort(values, n, sizeof(int), compare);
    printf("%d\n", solve(0, values[0], values[0], 0));

    return 0;

int solve(int k, double curMin, double curMax, int curCuts)

    if (k == n)
        return curCuts;

    double absMax = curMin / ratio;
    double absMin = curMax * ratio;
    int low = (int)ceil(values[k] / absMax);
    int high = (int)(values[k] / absMin);

    if (k == 0)
        low = 1, high = values[0];

    for (int i = low; i  < = high; ++i)

        double newL = values[k] / i;

        if (k == 0)
            curMin = curMax = newL;

        int ans = solve(k + 1, min(curMin, newL), max(curMax, newL), curCuts + i - 1);
        if (ans != -1)
            return ans;

    return -1;

int compare(const void *a, const void *b)

    return *(int *)a - *(int *)b;

Copy The Code & Try With Live Editor


0.99 3 2000 3000 4000




#3250 Beecrowd Online Judge Solution 3250 Elevator Trouble Solution in C, C++, Java, Js and Python
#3299 Beecrowd Online Judge Solution 3299 Small Unlucky Numbers Solution in C, C++, Java, Js and Python