Challenge: Làm bánh cho lễ tạ ơn

anon10709737 · April 15, 2018, 3:09pm

Hôm nay mình lại có hứng làm tiếp 1 challenge nữa cho xôm nhỉ?

##DESCRIPTION

Mình không thể quên được lần đầu mình join DNH vào tháng 11 và lúc đấy mình đã thưởng thức xong lễ Tạ ơn(Nhà mình theo Thiên Chúa Giáo). Năm nay 2018 mình muốn làm 1 món bánh cho lễ tạ ơn. Nhưng vì mải xem meme, lướt DNH, xem hentai,… làm mình quên béng mất là mình phải đi mua đồ về chế biến. Thế là mình phải tìm loạn cả cái nhà này lên chỉ thấy vài thứ có sẵn để làm món bánh. Mà mình thích làm hai loại bánh: Bánh bí ngô và Bánh táo theo công thức sau(Chưa ăn bao giờ thì search google để biết hình dạng như nào nhé ):

####Bánh bí ngô

1 muỗng gia vị bí ngô
3 quả trứng
4 cốc sữa
3 cốc đường

####Bánh táo

1 quả táo
4 quả trứng
3 cốc sữa
2 cốc đường(táo đã ngọt rồi )

Lúc làm chợt nhận ra ba mình không hợp với khẩu vị làm bánh của mình và bạn muốn làm hết tất cả các kiểu, các vị của từng loại bánh một với những gì mình có. Mình khổng thể sử dụng nguyên liệu theo phân số vì mình mất cái ca đong rồi (Tức là không có chuyện 1/2 cốc sữa hoặc bất cứ cái gì)

##INPUT FORMAT

Bạn sẽ có 1 mảng gồm 5 số tự nhiên, e.g. 10,14,10,42,24. Nó bao gồm chỉ số theo thứ tự các thành phần sau:

10 muỗng gia vị bí ngô
14 quả táo
10 quả trứng
42 cốc sữa
24 cốc đường

##OUTPUT FORMAT

Hiển thị ra màn hình số bánh mình cần nướng. Với input như trên, output sẽ ra kết quả là:

3 chiếc bánh bí ngô và 0 chiếc bánh táo(bạn nào xài console thì không dấu hoặc tiếng anh đều được)

##CHALLENGE INPUTS

10,14,10,42,24
12,4,40,30,40
12,14,20,42,24

##CHALLENGE OUTPUTS

3 chiếc bánh bí ngô và 0 chiếc bánh táo
5 chiếc bánh bí ngô và 3 chiếc bánh táo
5 chiếc bánh bí ngô và 1 bánh táo

##HINT

Áp dụng quy hoạch tuyến tính(Linear programming)

##BONUS

Mình nấu dở lắm nên là thỉnh thoảng ăn vào dễ bị tiêu chảy(nếu như thế). Nên là bonus sẽ được thêm vào như sau:
####Pumpkin pie

1 lọ berberin(thuốc tiêu chảy, cần 1 lọ vì gia vị hết hạn)

####Apple pie

10 lọ berberin(cũng thuốc tiêu chảy, 10 lọ vì táo nhà mình có thuốc trừ sâu)

Vậy thì input format theo bonus sẽ thay đổi như sau:
e.g. 10,14,10,42,24,15

thì nó sẽ bao gồm như sau:

10 muỗng gia vị bí ngô
14 quả táo
10 quả trứng
42 cốc sữa
24 cốc đường
15 lọ berberin

còn output thì tự hiểu nhé, thằng chủ topic lười lắm!

P/s: input khuyến khích tự nghĩ ra và giải
Chúc các bạn “làm bánh” vui vẻ!

noname00 · April 15, 2018, 2:57pm

Ăn bánh thôi.

spice, apples, eggs, milk, sugar = list(map(int, input().split()))
first_term = min(spice, eggs // 7, milk // 7, sugar // 5, apples)

pumpkin_pies = first_term
apple_pies = first_term

spice -= first_term * 1
apples -= first_term * 1
eggs -= first_term * 7
milk -= first_term * 7
sugar -= first_term * 5

if min(spice, eggs // 3, milk // 4, sugar // 4) > 0:
	pumpkin_pies += min(spice, eggs // 3, milk // 4, sugar // 4)
else:
	apple_pies += min(apples, eggs // 4, milk // 3, sugar // 2)

print("{0} pumpkin pie(s) and {1} apple pie(s)".format(pumpkin_pies, apple_pies))

P/s: Bác nào đi mua sẵn berberin đi.

anon10709737 · April 15, 2018, 2:59pm

Nói đến berberin mới nhớ. Mình thêm berberin vào bonus 1 đây

MeigyokuThmn · April 15, 2018, 3:06pm

Mình cho ra 0 chiếc bánh bí ngô và 2 chiếc bánh táo thì có được không?

Thật sự rằng mình vẫn chưa hiểu được ràng buộc ở đây là gì cả.

anon10709737 · April 15, 2018, 3:09pm

tức là thành phần với số lượng chỉ là số chẵn. Còn số hữu tỉ hay vô tỉ thì không được.

MeigyokuThmn · April 15, 2018, 3:31pm

Vậy phải ưu tiên làm loại đồ ăn nào, hay ưu tiên cái nào cũng được?

yuh · April 15, 2018, 9:56pm

tntxtnt · April 16, 2018, 2:29am

giải bằng vẽ hình

nếu có thêm nhiều loại bánh nữa thì nó lên thành 3D 4D 5D v.v… rồi vẽ ko nổi nữa

giải bằng code, xài C++ xài thư viện glpk (GNU Linear Programming Kit)

/* [2018-03-28] Challenge #355 [Intermediate] Possible Number of Pies
 *
 * Original link: https://redd.it/87rz8c
 * Vietnamese link: https://daynhauhoc.com/t/challenge-lam-banh-cho-le-ta-on/66409
 */
#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>
#include <glpk.h>
#include <fmt/printf.h>

/* Solve linear programming problem
 *   Maximize cᵀx
 *   subject to: Ax ≤ b, x ≥ 0,
 *   such that the matrix A and the vectors b and c are non-negative.
 */
std::vector<int> packingLP(
    const std::vector<std::vector<double>>& A,
    const std::vector<double>& b,
    const std::vector<double>& c);

int main()
{
    std::vector<std::string> pieNames = {
        "pumpkin pie",
        "apple pie",
    };
    std::vector<std::vector<double>> pieRecipes = {
    //pumpkin pie    apple pie
        {  1      ,      0  },  //scoop of synthetic pumpkin flavouring
        {  0      ,      1  },  //apple
        {  3      ,      4  },  //eggs
        {  4      ,      3  },  //cups of milk
        {  3      ,      2  },  //cups of sugar
    };
    std::vector<double> pieBias = {1, 1}; //1-1: no bias


    std::vector<std::vector<double>> ingredients = {
    //  pump appl eggs milk sugr
        {10,  14,  10,  42,  24},
        {12,   4,  40,  30,  40},
        {12,  14,  20,  42,  24},
    };
    for (auto const& ing : ingredients)
    {
        auto result = packingLP(pieRecipes, ing, pieBias);
        fmt::print("{} {}{} and {} {}{}\n",
            result[0], pieNames[0], result[0] == 1 ? "" : "s",
            result[1], pieNames[1], result[1] == 1 ? "" : "s");
    }
}


std::vector<int> packingLP(
    const std::vector<std::vector<double>>& A,
    const std::vector<double>& b,
    const std::vector<double>& c)
{
    int rows = A.size();
    int cols = A[0].size();
    // init packing LP
    glp_prob* lp = glp_create_prob();
    glp_set_obj_dir(lp, GLP_MAX);
    glp_add_rows(lp, rows);
    glp_add_cols(lp, cols);
    // load b
    for (int i = 0; i < rows; ++i)
        glp_set_row_bnds(lp, i + 1, GLP_UP, 0.0, b[i]);
    // load c
    for (int j = 0; j < cols; ++j)
    {
        glp_set_col_bnds(lp, j + 1, GLP_LO, 0.0, 0.0);
        glp_set_obj_coef(lp, j + 1, c[j]);
    }
    // load A
    int aSize = rows * cols;
    std::vector<int> ia(aSize + 1);
    std::vector<int> ja(aSize + 1);
    std::vector<double> va(aSize + 1);
    for (int i = 0, id = 1; i < rows; ++i)
    {
        for (int j = 0; j < cols; ++j)
        {
            ia[id] = i + 1;
            ja[id] = j + 1;
            va[id] = A[i][j];
            id++;
        }
    }
    glp_load_matrix(lp, aSize, &ia[0], &ja[0], &va[0]);
    // set MIP columns
    for (int j = 0; j < cols; ++j)
        glp_set_col_kind(lp, j + 1, GLP_IV);
    // solve MIP
    glp_iocp iocp;
    glp_init_iocp(&iocp);
    iocp.msg_lev = GLP_MSG_OFF;
    iocp.presolve = GLP_ON;
    int err = glp_intopt(lp, &iocp);
    if (err) throw std::runtime_error("Error during `glp_intopt()`");
    // get x
    std::vector<int> x(cols);
    for (int j = 0; j < cols; ++j)
        x[j] = glp_mip_col_val(lp, j + 1);
    glp_delete_prob(lp);
    return x;
}

anon10709737 · April 16, 2018, 6:08am

chỉ được phép 2 cái bánh trên thôi bạn nhé

MeigyokuThmn · April 16, 2018, 9:20am

Nếu là input 10,14,10,42,24
Mình thấy có 2 đáp án khả dĩ:
3 chiếc bánh bí ngô và 0 chiếc bánh táo
0 chiếc bánh bí ngô và 2 chiếc bánh táo
Vậy đáp án nào mới là hợp lệ đây?

anon10709737 · April 16, 2018, 9:34am

Lấy cả 2!!!
20 char

noname00 · April 16, 2018, 11:51am

Bonus

spice, apples, eggs, milk, sugar, berberin = list(map(int, input().split()))
first_term = min(spice, eggs // 7, milk // 7, sugar // 5, apples, berberin // 11)

pumpkin_pies = first_term
apple_pies = first_term

spice -= first_term * 1
apples -= first_term * 1
eggs -= first_term * 7
milk -= first_term * 7
sugar -= first_term * 5
berberin -= first_term * 11

if min(spice, eggs // 3, milk // 4, sugar // 4, berberin) > 0:
	pumpkin_pies += min(spice, eggs // 3, milk // 4, sugar // 4, berberin)
else:
	apple_pies += min(apples, eggs // 4, milk // 3, sugar // 2, berberin // 10)

print("{0} pumpkin pie(s) and {1} apple pie(s)".format(pumpkin_pies, apple_pies))

noname00 · April 16, 2018, 12:13pm

It’s Thanksgiving, Joe.

trankhoa001 · April 17, 2018, 1:49pm

#include <iostream>
using namespace std;


int nhonhat(int a, int b, int c, int d, int e){
    int re = a;
    if (re > b) re = b;
    if (re > c) re = c;
    if (re > d) re = d;
    if (re > e) re = e;
    return re;
};

int main()
{
    int bi_ngo, tao, trung, sua, duong, berberin;
    cin >> bi_ngo >> tao >> trung >> sua >> duong >> berberin;
    int banh_tao = nhonhat(tao, trung/4, sua/3, duong/2, berberin/10);
    tao -= banh_tao * 1;
    trung -= banh_tao * 4;
    sua -= banh_tao * 3;
    duong -= banh_tao * 2;
    berberin -= banh_tao * 10;
    int banh_bi_ngo = nhonhat(bi_ngo, sua/4, trung/3, duong/3, berberin/1);
    cout << banh_tao << " cai banh tao va " << banh_bi_ngo << " cai banh bi ngo " << endl;
    return 0;
}

Em thích ăn táo và uống thuốc tiêu chảy hơn bí ngô nên ưu tiên bánh táo thôi.

anon12276517 · April 17, 2018, 3:47pm

package dnh_challenge;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DNH_Challenge 
{
// Var
    public static int Pumpkin_spiced;
    public static int Apple;
    public static int Egg;
    public static int Milk;
    public static int Sugar;
    
    public static int Min_Pumpkin;
    public static int [][] Result; // [Pumpkin Pie] [Apple Pie]
//----------------------------------------------------------------------------//            
    public static void main(String[] args) throws IOException
    {
        Input();
        Cooking();
        Output();
    }
    
    public static void Input() throws IOException
    {               
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Input Pumpkin_spiced: ");
        Pumpkin_spiced = Integer.parseInt(in.readLine());
        System.out.print("Input Apple:  ");
        Apple = Integer.parseInt(in.readLine());          
        System.out.print("Input Egg:  ");
        Egg = Integer.parseInt(in.readLine());
        System.out.print("Input Milk: ");
        Milk = Integer.parseInt(in.readLine());
        System.out.print("Input Sugar: ");
        Sugar = Integer.parseInt(in.readLine());                                       
    }
    
    public static void Cooking()
    {
         Min_Pumpkin = Math.min(Pumpkin_spiced, Math.min(Egg / 3, Math.min(Milk / 4, Sugar / 3)));
         Result = Get_Result(new int[Min_Pumpkin + 1][2], Min_Pumpkin, 1);
    }
    
    public static int[][] Get_Result(int[][] input, int check, int size)
    {        
        if(check == 0)        
        {
            return input;
        }
        else
        {
            // Get 
            int Extra_Egg = Egg - check * 3;
            int Extra_Milk = Milk - check * 4;
            int Extra_Sugar = Sugar - check * 3;
            
            // Find Min_Apple_Pie
            int Apple_Pie = Math.min(Apple, Math.min(Extra_Egg / 4, Math.min(Extra_Milk / 3, Extra_Sugar / 2)));
            
            // Add to list
            if(size == 1) 
            {
                input[size - 1][0] = check;
                input[size - 1][1] = Apple_Pie;
                return Get_Result(input, check - 1, size + 1);                    
            }     
            else
            {
                if(Apple_Pie != input[size - 1][1]) // Sorf for Duplicate Min_Apple_Pie
                {
                    input[size][0] = check;
                    input[size][1] = Apple_Pie;
                    return Get_Result(input, check - 1, size + 1);                        
                }
                else
                {
                    return Get_Result(input, check - 1, size);
                }
            }            
        }
    }
    
public static void Output()
{
    int number = 1;
    System.out.println("--------------------------------------");
    for(int i = 0; i < Result.length; i++)
    {

        int Pumpkin_Pie = Result[i][0];            
        int Apple_Pie = Result[i][1];
                  
        if(Pumpkin_Pie == 0 && Apple_Pie == 0) {}
        else
        {
            System.out.println("Case " + number + ":" + Pumpkin_Pie + " Pumpkin Pie and " + Apple_Pie + " Apple_Pie");
            number ++;
        }
    }
}
    
}

Đây là giải bằng java Nhưng mình nghĩ cách của mình hơi dài vì không dùng Linear programming

anon12276517 · April 18, 2018, 12:03pm

Đây là cho phần Bonus

package dnh_challenge;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DNH_Challenge 
{
// Var
    public static int Pumpkin_spiced;
    public static int Apple;
    public static int Egg;
    public static int Milk;
    public static int Sugar;
    public static int Berberin;
    
    public static int [][] Result; // [Pumpkin Pie] [Apple Pie]
//----------------------------------------------------------------------------//            
    public static void main(String[] args) throws IOException
    {
        Input();
        Cooking();
        Output();
    }
    
    public static void Input() throws IOException
    {               
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Input Pumpkin_spiced: ");
        Pumpkin_spiced = Integer.parseInt(in.readLine());
        System.out.print("Input Apple:  ");
        Apple = Integer.parseInt(in.readLine());          
        System.out.print("Input Egg:  ");
        Egg = Integer.parseInt(in.readLine());
        System.out.print("Input Milk: ");
        Milk = Integer.parseInt(in.readLine());
        System.out.print("Input Sugar: ");
        Sugar = Integer.parseInt(in.readLine());     
        System.out.print("Input Berberin: ");
        Berberin = Integer.parseInt(in.readLine());            
    }
    
    public static void Cooking()
    {
         int Max_Pumpkin = Math.min(Pumpkin_spiced, Math.min(Egg / 3, Math.min(Milk / 4, Math.min(Sugar / 3, Berberin))));
         Result = Get_Result(new int[Max_Pumpkin + 1][2], Max_Pumpkin, 1);
    }
    
    public static int[][] Get_Result(int[][] input, int check, int size)
    {        
        if(check == 0)        
        {
            return input;
        }
        else
        {
            // Get 
            int Extra_Egg = Egg - check * 3;
            int Extra_Milk = Milk - check * 4;
            int Extra_Sugar = Sugar - check * 3;
            int Extra_Berberin = Berberin - check;
            
            // Find Min_Apple_Pie
            int Apple_Pie = Math.min(Apple, Math.min(Extra_Egg / 4, Math.min(Extra_Milk / 3, Math.min(Sugar / 2, Berberin / 10))));
            
            // Add to list
            if(size == 1) 
            {
                input[size - 1][0] = check;
                input[size - 1][1] = Apple_Pie;
                return Get_Result(input, check - 1, size + 1);                    
            }     
            else
            {
                if(Apple_Pie != input[size - 1][1]) // Sorf for Duplicate Min_Apple_Pie
                {
                    input[size][0] = check;
                    input[size][1] = Apple_Pie;
                    return Get_Result(input, check - 1, size + 1);                        
                }
                else
                {
                    return Get_Result(input, check - 1, size);
                }
            }            
        }
    }
    
    public static void Output()
    {
        int number = 1;
        System.out.println("--------------------------------------");
        for(int i = 0; i < Result.length; i++)
        {

            int Pumpkin_Pie = Result[i][0];            
            int Apple_Pie = Result[i][1];
                      
            if(Pumpkin_Pie == 0 && Apple_Pie == 0) {}
            else
            {
                System.out.println("Case " + number + ":" + Pumpkin_Pie + " Pumpkin Pie and " + Apple_Pie + " Apple_Pie");
                number ++;
            }
        }
    }
    
}