پاسخ سوال باقر حال نداره ولی پول داره کوئرا

پاسخ سوال باقر حال نداره ولی پول داره کوئرا

در این نوشته تمرین “باقر حال نداره ولی پول داره” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال باقر حال نداره ولی پول داره کوئرا

باقر سرما خورده و مقادیر زیادی خسته‌ است. باقر $n$ کاشی مربعی دارد که طول ضلع iاُمین کاشی عددی صحیح و برابر ai​ است. باقر می‌خواهد مجموع مساحت این کاشی‌ها دقیقا برابر m شود. برای دستیابی به این هدف او می‌تواند در هر مرحله یک کاشی به ضلع $a$ را به یک کاشی به ضلع b تبدیل کند، که عدد $b$ عددی صحیح و نامنفی است و می‌تواند کمتر یا بیش‌تر از عدد $a$ شود، ولی چون خودش خسته است، این کار را به کاشی‌کار می‌سپارد و (a-b)^2 ریال برای انجام این کار به کاشی‌کار می‌پردازد (دقت کنید که طول و عرض هر کاشی همیشه یکسان خواهد بود). به دلیل اینکه تغییر متعدد طول ضلع یک کاشی مقاوت کاشی را کم می‌کند، طول ضلع هر کاشی را حداکثر یک بار می‌توان تغییر داد. شما برای باقر کم‌ترین میزان پولی که باید به کاشی‌کار بپردازد تا مجموع مساحت کاشی‌ها دقیقا برابر $m$ شود را به دست آورید.

ورودی سوال

در خط اول $n$ و $m$ داده شده است.

در خط دوم تا خط $n+1$ام در هر خط طول ضلع یکی از کاشی‌ها داده شده است.

$$1\le n\le 10$$1

$$1\le m\le 10$$

1 ≤ ai​ ≤ 100

تمامی اعداد ورودی عددی صحیح هستند.

خروجی سوال

در تنها خط خروجی کم‌ترین میزان پولی که باقر باید به کاشی‌کار بپردازد تا مجموع مساحت کاشی‌ها برابر $m$ شود را چاپ کنید. درصورتی که رسیدن به مجموع مساحت $m$ غیر ممکن بود، عدد -1 را در خروجی چاپ کنید.

حل سوال

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int A[] = new int[11];
        for (int i = 1; i <= n; i++) {
            A[i] = scanner.nextInt();
        }
        int memo[][] = new int[10001][11];
        int INF = 1000000000;
        for (int i = 1; i <= m; i++) {
            memo[i][0] = INF;
        }
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i <= m; i++) {
                memo[i][j] = INF;
                for (int k = 1; k*k <= i; k++) {
                    if (memo[i][j] > memo[i - k * k][j - 1] + (A[j] - k) * (A[j] - k)) {
                        memo[i][j] = memo[i - k * k][j - 1] + (A[j] - k) * (A[j] - k);
                    }
                }
            }
        }
        if (memo[m][n]==INF){
            System.out.println(-1);
        }else{
            System.out.println(memo[m][n]);
        }
    }
}

منبع سوال‌: وب‌سایت کوئرا

اگر روش حل بهتری برای “تمرین باقر حال نداره ولی پول داره” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم.

اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.