Задача 49: Призы победителям сборов

Условие задачи:

Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.

Например, если размер холодильника должен быть 12, возможными вариантами являются:
Размеры баночек | Площадь поверхности
3 * 2 * 2 | 32
4 * 3 * 1 | 38
6 * 2 * 1 | 40
12 * 1 * 1 | 50
Лучшим вариантом является 3 × 2 × 2.

Помогите организаторам сборов выбрать оптимальную форму холодильника.

Входные данные:

Входной файл содержит одно число \(N (1 <= N <= 10^6)\).

Выходные данные:

Выведите три числа A, B и C — оптимальные длины сторон холодильника. Если решений несколько — выведите любое из них.

Решение:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <math.h>

using namespace std;

int n, p;
int L = 1000000000;
float t;
int rez[3];
int a = 0;
int b = 0;
int c = 0;

bool prime(int n){
    bool isPrime = true;
    if (n == 0 || n == 1){
        isPrime = false;
    } else {
        for (int i = 2; i <= n / 2; ++i){
            if (n % i == 0){
                isPrime = false;
                break;
            }
        }
    }
    return isPrime;
}

void checkAns(){
    int m = rez[2] + rez[0] + rez[1];
    if (m <= L){
        L = m;
        a = rez[0];
        b = rez[1];
        c = rez[2];
    }
}


void f(int i, int s, int l_e){
    if (i == 3){
        if (s == n){
            checkAns();
        }
        return;
    }
    for (int j = 1; j <= n / s + 1; j++){
        rez[i] = j;
        f(i + 1, s * j, j);
    }
}

int main()
{
    cin >> n;
    t = pow(n, 1./3.);
    if (prime(n)){
        cout << n << " 1 1" << endl;
    } else if ((float)((int)t) < t ){
        f(0, 1, n / 2 + 1);
        if (a == 0){
            cout << n << " 1 1" << endl;
        } else {
            cout << a << " " << b << " " << c << endl;
        }
    } else {
        cout << t << " " << t << " " << t << endl;
    }
    return 0;
}

Задача 49: Призы победителям сборов

Условие задачи:

Входные данные:

Выходные данные:

Решение:

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик

Пожалуйста, подождите загрузки решения