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

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

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

در مورد سایت کوئرا بیشتر بخوانید…

تمرین باقر حال نداره ولی پول داره کوئرا + جاوا

باقر سرما خورده و مقادیر زیادی خسته‌ است.

باقر $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]);
        }
    }
}

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

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

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

موفق باشید.