The casino has introduced a new game in which there are M vertical chutes each containing N single digit (possibly zero) numbers. You can choose any chute and draw the bottom number and when you do this all the other numbers in the chute descend by one slot. You need to build the largest integer using this process drawing all the numbers from the chutes. For example, in the following example, we have three chutes of four numbers each and the largest number that can be drawn is 469534692781. Given the number of chutes and the numbers in each chute, write a program to find the largest integer that could be formed using the above process. To find the largest integer that could be formed using the above process.
Input Format:
First line contains M,N two comma separated integers giving the number of chutes and the number of digits in each chute The next M lines each contain N comma separated digits, giving the digits from top to bottom in each of the chutes.
Output Format:
One line containing the largest integer that could be formed.
Constraints:
1 <= M <= 20, 1 <= N <= 50
Example 1
Input:
2,3
1,2,3
2,4,6
Output:
643221
Explanation:
M is 2 and N is 3 (there are 2 chutes with 3 digits in each). The chutes
look like this, The largest integer that can be formed is 643221.
Example 2
Input:
4,4
7,5,5,2
3,6,1,7
8,7,0,4
8,7,3,9
Output:
9743782557163078
Explanation:
M is 4 and N is 4. The chutes look like this
The largest integer that can be formed is 9743782557163078, and this is the output.
Solution: In C
#include<stdio.h>
int main()
{
int a[20][20],i,j,m,n,f=0,c=0,r,p,k;
char ch;
scanf("%d%c%d",&m,&ch,&n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
if(j<n-1)
scanf("%c",&ch);
}
}
while(f!=1)
{
j=n-1;c=-1;
for(k=m-1;k>=0;k--)
{
if(a[k][j]>c)
{
c=a[k][j];
r=k;
}
}
for(p=j;p>0;p--)
{
a[r][p]=a[r][p-1];
}
a[r][p]=-1;
if(c!=-1)
printf("%d",c);
else
break;
}
}Solution: In Java
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] a=new int[100][100];
int i,j,m,n,f=0,c=0,r=0,p,k;
char ch;
m=sc.nextInt();
ch=sc.next().charAt(0);
n=sc.nextInt();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=sc.nextInt();
if(j<n-1)
ch=sc.next().charAt(0);
}
}
while(f!=1)
{
j=n-1;c=-1;
for(k=m-1;k>=0;k--)
{
if(a[k][j]>c)
{
c=a[k][j];
r=k;
}
}
for(p=j;p>0;p--)
{
a[r][p]=a[r][p-1];
}
a[r][p]=-1;
if(c!=-1)
System.out.printf("%d",c);
else
break;
}
}
}Solution: In Python 3
m, n = map(int, input().strip().split(","))
a = []
for i in range(m):
a.append(list(map(int, input().strip().split(","))))
high = [0]*m
for i in range(m):
high[i] = a[i][-1]
ans = []
for i in range(m*n):
h = max(high)
ans.append(str(h))
if len(a[high.index(h)]) != 0:
a[high.index(h)].pop()
if len(a[high.index(h)]) == 0:
high[high.index(h)] = -1
else:
high[high.index(h)] = a[high.index(h)][-1]
print("".join(ans))Also Checkout