CLASS HOMEWORK

• Problem Description

  
  Ramesh and Suresh were in the same class and got home work from their mathematics teacher. The Homework consists of N strings and each string consists of only digits. The task which they need to perform is that they need to divide the string into 4 integers such that their sum is maximum.
  
  Note:
  Each integer should be <= 1012 and should not contain any leading zeroes.
  
  As we know that Suresh and Ramesh are weak in mathematics and also they dont want to be punished. So, they need your help for finding the answer.
  
  INPUT:
  
  First line contains an integer N denoting the number of strings. Next N lines contain N strings each consists of digits only.
  
  OUTPUT:
  
  For each test case, Print the required answer if exists. Print "unlucky" otherwise.
  
  CONSTRAINTS:
  
  1<=N<=104
  1<=size of each string <= 20
  Explanation:In test case 1: 4 integers are 4,2,5,1. So maximum sum is 12. In test case 2: 4 integers are 52,3,1,0. So maximum sum is 56. In test case 3: None of division (0 , 0 , 0 , 06) , (0 , 00 , 0 , 6 ) is valid.
  SUBTASKS:
  
  subtask 1 : 1<= N<=102 : ( 50 pts )
  subtask 2 : 1<=N<=104 : ( 50 pts )

• CODING ARENA

• #include <stdio.h>

  #include<string.h>

  #define max(a,b) (a)>(b)?(a):(b)

  long long int dp[5][21];

  char s[21];

  long long extract(char *s,int i,int l)

  {

    long long int num=0;

    for(;i<=l;i++)

    {

      num=num*10+s[i]-'0';

    }

    return num;

  }

  long long int fun(int n,int m)

  {

    int i=0;

    long long num=0;

    long long temp;

    if(n==0&&m==-1)

    {

      return 0;

    }

    if(n<=0||m<0)

      return-1000000000000000LL;

    if(dp[n][m]!=-100000000000000LL)

    {

      return dp[n][m];

    }

    for(i=m;i>=0;i--)

    {

      if(m-i>0&&s[i]=='0')

      {

        continue;

      }

      else

        num=extract(s,i,m);

      if(num>100000000000000LL)

        break;

      temp=fun(n-1,i-1);

      dp[n][m]=max(dp[n][m],num+temp);

    }

    return dp[n][m];

  }

  int main()

  {

    int t,i,j;

    long long int res;

    scanf("%d",&t);

    while(t--)

    {

      scanf("%s",s);

      for(i=0;i<5;i++)

        for(j=0;j<21;j++)

          dp[i][j]=-100000000000000LL;

      res=fun(4,strlen(s)-1);

      if(res<0)

        printf("unlucky\n");

      else

        printf("The output is:%lld\n",res);

    }

    return 0;

  }

  
  

  
  

• Test Case 1

  
  Input (stdin)

  2
  
  4251
  
  52310
  
  

  Expected Output

  The output is:12
  
  The output is:56

• Test Case 2

  
  Input (stdin)

  2
  
  4214
  
  5603
  
  

  Expected Output

  The output is:11
  
  The output is:14