Editorial for Titania

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

English

To solve this problem we will use dynamic programming. The solution will include a 4D dp solution matrix of size \(N^3\times K\). A point in solution matrix res[X][Y][Z][K] will represent the cost of getting \(\mathbf{K}\ m^3\) of titanium from \(\mathbf{X\times Y\times Z}\) titanium block. To find a point's minimum total cut cost we have to cut the block into 2 pieces and solve the same problem twice again for the smaller problems of res[X1][Y][Z][K1] res[X-X1][Y][Z][K-K1] for every X1 and K1(This symbolizes the cutting operation)(we have to do this for all 3 dimensions).

Türkçe

Bu soruyu çözmek için dinamik programlama kullanacağız. Çözüm, \(N^3\times K\) boyutunda bir 4D dp çözüm matrisi içerecektir. Çözüm matrisindeki bir nokta res[X][Y][Z][K], \(\mathbf{X\times Y\times Z}\) titanyum bloğundan \(\mathbf{K}\ m^3\) titanyum almanın masrafını temsil edecek. Bir noktanın minimum toplam kesme maliyetini bulmak için bloğu 2 parçaya bölmeli ve aynı problemi daha küçük problemler olan, her bir X1 ve K1'e göre res[X1][Y][Z][K1] res[X-X1][Y][Z][K-K1] için iki kez daha çözmeliyiz (bu işlem X boyutundan kesmeyi sembolize ediyor)(bunu 3 boyut için de yapmalıyız).

Code-cpp

#include <bits/stdc++.h>
using namespace std;

#define min(a,b) (a<b?a:b)

long res[11][11][11][51];


long solve(int x,int y,int z,int k){
    if(res[x][y][z][k])return res[x][y][z][k];
    if(x*y*z==k||k==0)return 0;

    long curRes=LONG_MAX;
    for(int i=1;2*i<=x;i++){
        for(int j=0;j<=k;j++){
            if(i*y*z>=k-j && (x-i)*y*z>=j)
                curRes=min(curRes,y*y*z*z+solve(i,y,z,k-j)+solve(x-i,y,z,j));
        }
    }

    for(int i=1;2*i<=y;i++){
        for(int j=0;j<=k;j++){
            if(x*(y-i)*z>=k-j && x*i*z>=j)
                curRes=min(curRes,x*x*z*z+solve(x,y-i,z,k-j)+solve(x,i,z,j));
        }
    }

    for(int i=1;2*i<=z;i++){
        for(int j=0;j<=k;j++){
            if(x*y*(z-i)>=k-j && x*y*i>=j)
                curRes=min(curRes,x*x*y*y+solve(x,y,z-i,k-j)+solve(x,y,i,j));
        }
    }

    res[x][y][z][k]=curRes;
    return curRes;
}


int main(){
    int x,y,z,k,t;
    cin>>t;
    while(t--){
        cin>>x>>y>>z>>k;
        cout<<solve(x,y,z,k)<<endl;
    }

}

Code-python

arr = [[[[0 for _ in range(51)] for _ in range(11)] for _ in range(11)] for _ in range(11)]


def solve():

    for x in range (1,11):
        for y in range (1,11):
            for z in range (1,11):
                if x*y*z==1:
                    continue
                for k in range (1,51):
                    if x*y*z==k:
                        continue
                    curRes=999999999
                    for i in range(1,int(x/2)+1):
                        for j in range(k+1):
                            if i*y*z>=k-j and (x-i)*y*z>=j:
                                curRes=min(curRes,y*y*z*z+arr[i][y][z][k-j]+arr[x-i][y][z][j])
                    for i in range(1,int(y/2)+1):
                        for j in range(k+1):
                            if x*(y-i)*z>=k-j and x*i*z>=j:
                                curRes=min(curRes,x*x*z*z+arr[x][y-i][z][k-j]+arr[x][i][z][j])
                    for i in range(1,int(z/2)+1):
                        for j in range(k+1):
                            if x*y*(z-i)>=k-j and x*y*i>=j:
                                curRes=min(curRes,x*x*y*y+arr[x][y][z-i][k-j]+arr[x][y][i][j])
                    arr[x][y][z][k]=curRes


t=int(input())
solve()
for aaa in range(t):
    a,b,c,d=[int(i) for i in input().split()]
    print(arr[a][b][c][d])