Charlie wants to divide a big piece of waffle which is made up of m*n square pieces. Each piece is of size 1*1. The shape of waffle is a rectangle of dimension m*n. However, Charlie can break the waffle either horizontally or vertically, along the lines such that the square pieces are not destroyed.
Each break along a line has a certain cost associated with it. The cost is only dependent on the line along which the waffle is being broken, and not on its length.
The total cost is obtained by summing up the costs of all the breaks.
Given the cost associated with each line, Charlie wants to know the minimum cost of breaking the waffle into single square pieces.
Input
First line contains two integers m and n denoting the number of rows and columns respectively.
This is followed by m-1, each line contains an integer denoting the cost of breaking a waffle along a horizontal line.
This is followed by n-1, each line contains an integer denoting the cost of breaking a waffle along a vertical line.
Output
Output should be a single line integer denoting the minimum cost to break the waffle into single square pieces.
Constraints
1<=n<=10^5
1<=m<=10^5
Sample Input
2 2
3
4
Sample Output
10
Explanation
Break the waffer along the column where the cost = 4, then break the two pieces along the row where the cost = 3*2 = 6. Otherwise, the cost would have been 3+(4*2) = 11.
def max_list(l1,l2):
m1=max(l1)
m2=max(l2)
if m1>=m2:
return l1.index(m1),1
else:
return l2.index(m2),2
s=0
m,n=list(map(int,input().split()))
if m<=0 or n<=0:
return 0
l1=list(map(int,input().split()))
m1=1
l2=list(map(int,input().split()))
m2=1
while max(l1)!=-1 or max(l2)!=-1:
index,i=max_list(l1,l2)
if i==1:
s=s+(l1[index]*m1)
m2=m2+1
l1[index]=-1
else:
s=s+(l2[index]*m2)
m1=m1+1
l2[index]=-1
print(s)
Can you give Solution in C++???
#include
using namespace std;
int main()
{
int hCost,vCost,hLines,vLines,m,n,sum1,sum2,cuts;
cin>>m;
cin>>n;
cin>>hCost;
cin>>VCost;
cuts=m*n-1;
sum1=0;
sum1+=hLines*hCost;
sum1+=cuts-hLines*vCost;
sum2+=vLines*vCost;
sum2+=cuts-vLines*hCost;
if(sum1<sum2)
{
cout<<sum1<<endl;
}
else
{
cout<<sum2<<endl;
}
return 0;
}
can u pls indent it
r,c=map(int,input().split())
rc=int(input())
cc=int(input())
if rc==cc:
print(((r*c)-1)*rc)
elif rc>cc:
res=(r-1)*rc+((c-1)*cc)*r
print(res)
else:
res=(c-1)*cc+((r-1)*rc)*c
print(res)
Wow @Shrutik Gumate such a simple and mid blowing solution! Big fan Sir!
CUTTING BOARDS in HACKERRANK
#include
using namespace std;
#define ll long long
int main(){
ll h,w,hc,wc;
cin>>h>>w>>hc>>wc;
ll mxs = hc>wc?h:w;
ll mn = hc<wc?h:w;
cout<<max(hc,wc)*(mxs-1) + mxs*(min(hc,wc)*(mn-1));
return 0;
}
r,c=map(int,input().split())
rcost=int(input())
ccost=int(input())
way1=((r-1)*rcost)+(r*(c-1)*ccost)
way2=((c-1)*ccost)+(c*(r-1)*rcost)
print(min(way1,way2))
is’nt it r*(c-2)*ccost
All other codes are wrong, go with this
r,c=map(int,input().split())
rcost=list(map(int,input().split()))
ccost=list(map(int,input().split()))
xa=[]
xb=[]
for i in range(max(r,c)-1):
xa.append(0)
xb.append(0)
way1=0
way2=0
for i in range(r-1):
xa[i]=xa[i]+rcost[i]
xb[i]=xb[i]+ccost[i]*r
way1=way1+xa[i]+xb[i]
xa=[]
xb=[]
for i in range(max(r,c)-1):
xa.append(0)
xb.append(0)
for i in range(c-1):
xa[i]=xa[i]+ccost[i]
xb[i]=xb[i]+rcost[i]*c
way2=way2+xa[i]+xb[i]
print(min(way1,way2))
bool comp1(int a,int b){
return a>b;
}
int main(){
int m,n;
cin>>m>>n;
int r[m-1],c[n-1];
for(int i=0;i>r[i];
}
for(int i=0;i>c[i];
}
sort(r,r+m-1,comp1);
sort(c,c+n-1,comp1);
int l1=0,l2=0,cnt=1,sum=0;
while(l1<m-1 && l2=c[l2]){
sum+=r[l1]*cnt;
cnt++;
sum+=c[l2]*cnt;
l1++;l2++;
}
else{
sum+=c[l2]*cnt;
cnt++;
sum+=r[l1]*cnt;
l1++;l2++;
}
}
while(l1<m-1){
sum+=r[l1]*cnt;
//cnt++;
l1++;
}
while(l2<n-1){
sum+=c[l2]*cnt;
//cnt++;
l2++;
}
cout<<sum;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println(“enter value”);
int r=sc.nextInt();
int c=sc.nextInt();
int Hc=sc.nextInt();
int Vc=sc.nextInt();
if(Hc>Vc) {
System.out.println(Hc*(r-1)+Vc*r*(c-1));
}
else
System.out.println(Vc*(c-1)+Hc*c*(r-1));
}
plz explain the logic