11258 - String Partition

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

11258 - String Partition

Post by pvncad » Sat Aug 04, 2007 1:18 pm

I tried to solve this using DP. But was getting WA.

Can someone give me tricky i/o ?

Thanks

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Aug 04, 2007 1:58 pm

I have also used DP, but didn't find anything tricky.

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Sat Aug 04, 2007 2:07 pm

I too felt the same but got so many WAs.

Can you anything wrong with this code ?

Code: Select all

=======    Removed ============

Last edited by pvncad on Sat Aug 04, 2007 4:07 pm, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Aug 04, 2007 2:11 pm

why you didnt post your full code?
are all variables long long?

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Sat Aug 04, 2007 2:12 pm

yup all r long long

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Aug 04, 2007 2:15 pm

If i didnt misunderstand your code

Code: Select all

long long last = num[j]; 
It should be

Code: Select all

long long last = num[i+j];
isnt it?[/code]


another less important thing:
you dont need another variable max..
sum[0] is the result :)

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Sat Aug 04, 2007 2:19 pm

i don't think that is a problem. num[j] represents the j-length digit starting from i + 1th position.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Aug 04, 2007 3:01 pm

probably the best thing to do is to recode it in a much shorter way. My code is only 1/3 as long of yours.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Aug 04, 2007 3:20 pm

sclo wrote:probably the best thing to do is to recode it in a much shorter way. My code is only 1/3 as long of yours.
Yes this code is not readable for me.

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Sat Aug 04, 2007 4:07 pm

Will try to recode and see how it goes. Thanks for ur help

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Wed Aug 15, 2007 8:51 am

isnt there anyway without DP. I tryed but it is WA. is there any tricky input? or ......?

Code: Select all

#include <stdio.h>
#include <string.h>

#define MAX 4294967295L

int main()
{
	char str[200];
	long long num,sum,i;
	int test;

	scanf("%d%*c",&test);

	while(test--)
	{
		gets(str);

		sum = 0;
		num = 0;
		for(i=0;str[i];i++)
		{
			if((long long)(num*10 + str[i]-48) > MAX)
			{
				sum += num;
				num = 0;
				i--;
			}
			else
				num = num*10 + str[i]-48;
		}
		sum += num;

		printf("%lld\n",sum);
	}
	return 0;
}
please help

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Aug 15, 2007 8:58 am

Non-negative 32-bit signed integer must be in range 0..2147483647, i.e. the answer for string "4294967295" should be "429496734"
Last edited by mf on Wed Aug 15, 2007 12:20 pm, edited 2 times in total.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Wed Aug 15, 2007 12:12 pm

are you talking about signed or unsigned int???
sorry i cant undstnd. may u clarify again.
what abt 2147483648
Last edited by newton on Wed Aug 15, 2007 12:21 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Aug 15, 2007 12:18 pm

Sorry, I've made a typo in range.
I was talking about the data type from the problem statement.

S.M.ferdous
New poster
Posts: 13
Joined: Fri Nov 03, 2006 2:53 pm
Location: bangladesh
Contact:

11258 wa

Post by S.M.ferdous » Sun Aug 26, 2007 9:19 pm

hi

i m getting wrong ans with 11258 i cant find why ?
can any one help me i am giving the code here.

Code: Select all


//string partition 11258

#include<stdio.h>
#define LIMIT 2147483647L

int main(void)
{
	long long N,num,Tnum,prevnum,i,j;
	char a[250];

	scanf("%lld",&N);

	for(i=0; i<N; i++)
	{
		scanf("%s",a);
		num=0;Tnum=0;
		for(j=0; a[j]; j++)
		{
			prevnum=num;
			num = num*10 + (a[j]-'0');
			if(num>LIMIT)
			{
				Tnum=Tnum+prevnum;
				num=0;
				j--;
			}
		}
		Tnum = Tnum + num;
		printf("%lld\n",Tnum);
	
	}
	return 0;
}

Post Reply

Return to “Volume 112 (11200-11299)”