Page 2 of 2
Posted: Tue Aug 28, 2007 2:14 pm
You are using some sort of greedy. Greedy will not work I think. Try the cases.

Input:

Code: Select all

``````2
12147483647
92000000000``````
Output:

Code: Select all

``````2147483648
2000000009``````
Hope these help.

### Re: 11258 wa

Posted: Fri Oct 31, 2008 4:33 pm
S.M.ferdous wrote:hi

i m getting wrong ans with 11258 i cant find why ?
can any one help me i am giving the code here.
Ferfous ,
this is not a greedy problem.
You have to think in dp.
Suppose....

long long split(int i){

for(int k=1;k<=10;k++) MAXIMIZE num[k]+split(i+k);
}
i means from i'th position to end of input string .
k means we take k digit number which is maximum 10 digit.
I first implement 2D dp . BUT TLE. so 1D dp is essential.

### Runtime error.

Posted: Sat Nov 14, 2009 9:50 pm
Hi ,
I am getting runtime error in this question.
http://uva.onlinejudge.org/index.php?o ... ID+7557502

I am not able to figure it out.

here is the code.

Code: Select all

``````#include<iostream>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
#include<stdio.h>
//#include<climits>
using namespace std;
long long sum[501];
long long int tonum(string s){
long long int ans=0;
int i;
for(i=0;i<s.size();i++){
ans=10*ans+s[i]-48;
}
return ans;
}
int main(){
string s;
int t;
long long int prev,next;
cin>>t;
getline(cin,s);
long long int num;
int i;
while(t--){
getline(cin,s);
int sz=s.size();
for(i=0;i<sz;i++){
if(i>=9){
num=tonum(s.substr(i-9,10));
if(num <= 2147493647LL){

if(i-10<0){
sum[i]=num;
}
else{
int j=1;
prev=sum[i-j]+tonum(s.substr(i-j+1,j));
next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
while(next>prev){
prev=next;
j++;
next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
}
//	cout<<"kk"<<i<<" "<<prev<<"\n";

sum[i]=max(num+sum[i-10],prev);
}
}
else{
num=tonum(s.substr(i-9,9));
if(i-9<0){
sum[i]=num;
}
else{
int j=1;
prev=sum[i-j]+tonum(s.substr(i-j+1,j));
next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
//		cout<<"pp"<<prev<<" "<<next<<"\n";
while(next>prev){
prev=next;
j++;
next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
}

sum[i]=max(num+sum[i-9],prev);
}
//	}
}
}
else
sum[i]=tonum(s.substr(0,i+1));
}
if(sz>0)
cout<<sum[i-1]<<"\n";
}
return 0;
}

``````
One more question related to c++

when i use INT_MAX present in climits
if(num <= INT_MAX); // in this case it is not entering if condition when num=2147493647.why?? here num is long long
if(num <= 2147493647LL)//here it is OK

### 11258 Runtime error.

Posted: Sun Nov 11, 2012 7:40 am
I am getting a run-time error for StringPartiotion Problem. I have followed all the submission conventions like
no class is public the class having main method is named Main, and classes are not inside any package and I
removed spaces from each line before processing it.
Also I have tested it on random input and also on the sample input given and it works correctly.
Here is the code...Can somebody please give a hind what I am missing here.

Code: Select all

``````
import java.util.Scanner;
class Main {
long maxValue = Long.MIN_VALUE;

Main(int logLength, int[] marks) {
long comp[][] = new long[marks.length][marks.length];
for (int k = 0, l = 0; l < marks.length; ++l) {
for (int i = k, j = l; i < marks.length && j < marks.length; ++i, ++j) {
if (i == j) {
comp[i][j] = marks[i];
continue;
}
if (i == j - 1) {
comp[i][j] = 10 * marks[i] + marks[j];
continue;
}
if (marks[i] == 0) {
comp[i][j] = comp[i + 1][j];
continue;
}
long max = this.arrayToNumber(marks, i, j);
for (int m = i + 1; m <= j; ++m) {
long current = comp[i][m - 1] + comp[m][j];
if (max < current) {
max = current;
}
}
comp[i][j] = max;
}
}
this.maxValue = comp[0][marks.length - 1];
}

private long arrayToNumber(int[] marks, int low, int high) {
long sum = 0;
for (int i = low; i <= high; ++i) {
sum = 10 * sum + marks[i];
if (sum > Integer.MAX_VALUE || sum < Integer.MIN_VALUE) {
return -1;
}
}
return sum;
}

public long getMinCost() {
return this.maxValue;
}

public static void main(String args[]) {

Scanner scan = new Scanner(System.in);
scan.useDelimiter("\n");
String s = scan.next();
s = s.replaceAll("\\s", "");
int l = Integer.parseInt(s);
while (l-- > 0) {
s = scan.next().replaceAll("\\s", "");
int digits[] = new int[s.length()];
for (int i = 0; i < digits.length; ++i) {
digits[i] = Character.digit(s.charAt(i), 10);
}
Main m = new Main(digits.length, digits);
System.out.println(m.getMinCost());
}
System.exit(0);
}
}

``````