Page 3 of 4

Posted: Mon Dec 24, 2007 9:01 pm
by mohsincsedu
Some IO:

Input:

Code: Select all

2 1
1
0
2 2
1
0
3 3
5400000000
5400000000
5400000000
3 2
5400000000
5400000000
9000000001
6 3
1
2
3
4
5
6
11 3
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
11 3
10000000000
1000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
2 10
9999999999
2
2 10
2
999999999
0 0
Output:

Code: Select all

Bill #1 costs 1: each friend should pay 1

Bill #2 costs 1: each friend should pay 0

Bill #3 costs 16200000000: each friend should pay 5400000000

Bill #4 costs 19800000001: each friend should pay 9900000000

Bill #5 costs 21: each friend should pay 7

Bill #6 costs 11111111111: each friend should pay 3703703703

Bill #7 costs 11111111111: each friend should pay 3703703703

Bill #8 costs 10000000001: each friend should pay 1000000000

Bill #9 costs 1000000001: each friend should pay 100000000

Hope it helps...

10925,RTE,pleas help!!

Posted: Tue Dec 25, 2007 3:19 pm
by turcse143
here my code.Someone ples help whats my problem.
i get RTE.
#include<stdio.h>
#include<string.h>

char str1[29][29],str[29];
main()
{
int count,d,n,f,i,j,k,c,b,flag;
int e;
freopen("10925a.in","rt",stdin);
count=1;
while(scanf("%d %d",&n,&f)==2)
{
if(n==0&&f==0)
break;
for(i=0;i<35;i++)
memset(str1,'0',sizeof(str1));
c=0;
for(i=0;i<n;i++)
{
scanf("%s",str);
b=strlen(str);
if(c<b)
c=b;
k=0;
for(j=b-1;j>=0;j--)
{
str1[k]=str[j];
k++;
}

}

c=c+6;
for(j=n-1;j>0;j--)
{
d=0;
for(k=0;k<c;k++)
{
d=(str1[j-1][k]-48)+(str1[j][k]-48)+d;
if(d>9)
str1[j-1][k]=(d%10)+48;
else
str1[j-1][k]=(d+48);
d=d/10;
}
}
d=0;
for(i=0;i<2;i++)
{
d=str1[0]-48+(10*d);
if(d>f)
{
e=d%f;
break;
}
else
e=0;

}
for(i=c-1;i>=0;i--)
if(str1[0]>'0'&&str1[0]<='9')
break;
printf("Bill #%d costs ",count);
for(j=i;j>=0;j--)
printf("%c",str1[0][j]);
printf(": each friend should pay ");
str1[0][0]=str1[0][0]-(e%10);
str1[0][1]=str1[0][1]-(e/10);
flag=0;d=0;
for(j=i;j>=0;j--)
{
d=str1[0][j]-48+((d%f)*10);
e=d/f;
if(e==0&&j==0)
printf("%d",e);
else if(e==0&&flag==0)
{
flag=1;
continue;
}
else
{
printf("%d",e);
flag=1;
}
}
printf("\n\n");
count++;
}
}

Posted: Tue Dec 25, 2007 8:12 pm
by mohsincsedu
You use 2D for Big Integer Arithmatic....

I think it does not need...

You got RTE because problem description says 1 ≤ N ≤ 1000

but you used only 29


and another things ur algo may be worng becasue when i changed the array size then i got wa in ur code

Posted: Thu Feb 28, 2008 8:33 am
by turcse143
again i got WA,
i check all the input output of that given page
is there anyspecial input output?
pleas help me.
here my input output:
input:

Code: Select all

2 1
1
0
2 2
1
0
3 3
5400000000
5400000000
5400000000
3 2
5400000000
5400000000
9000000001
6 3
1
2
3
4
5
6
11 3
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
11 3
10000000000
1000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
2 10
9999999999
2
2 10
2
999999999
0 0
output:
Bill #1 costs 1: each friend should pay 1

Bill #2 costs 1: each friend should pay 0

Bill #3 costs 16200000000: each friend should pay 5400000000

Bill #4 costs 19800000001: each friend should pay 9900000000

Bill #5 costs 21: each friend should pay 7

Bill #6 costs 11111111111: each friend should pay 3703703703

Bill #7 costs 11111111111: each friend should pay 3703703703

Bill #8 costs 10000000001: each friend should pay 1000000000

Bill #9 costs 1000000001: each friend should pay 100000000

Press any key to continue

Re: 10925 - Krakovia

Posted: Fri Dec 26, 2008 8:30 am
by anton_indrawan
Try this case
Hope this help

Code: Select all

1 16
1743247980173
The output should be

Code: Select all

Bill #1 costs 1743247980173: each friend should pay 108952998760



10925 - TLE !!!!!!!!!!!!!!!!!!!!!!! Krakovia

Posted: Sun Jan 11, 2009 11:30 am
by toru
HI, It is really really bad and bit rusty for me to get TLE in this problem, well, anyone can suggest me what to modify my code inorder to get it with reasonable time.............

THANX IN ADVANCE
megh putra.....

Code: Select all

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

#define MAX 2000000

/*******************************************************************/

void reverse(char *from, char *to )
{
    long len=strlen(from);
    long l;

	for(l=0;l<len;l++)
      to[l]=from[len-l-1];
    
	to[len]='\0';
}

/******************************************************************/

void call_sum(char *first, char *sec, char *result)
{
    char F[MAX+100], S[MAX+100], Res[MAX+100];
    int f,s,sum,extra,now;

	f=strlen(first);
    s=strlen(sec);

	reverse(first,F);
    reverse(sec,S);

	for(now=0,extra=0;(now<f && now<s);now++)
	{
       sum=(F[now]-'0') + (S[now]-'0') + extra;
       Res[now]=sum%10 +'0';
       extra= sum/10;
	}
    
	for(;now<f;now++)
	{
       sum=F[now] + extra-'0';
       Res[now]=sum%10 +'0';
       extra=sum/10;
	}

	for(;now<s;now++)
	{
       sum=F[now] + extra-'0';
       Res[now]=sum%10 +'0';
       extra=sum/10;
	}
    
	if(extra!=0) 
		Res[now++]=extra+'0';

	Res[now]='\0';

	if(strlen(Res)==0) 
		strcpy(Res,"0");
    
	reverse(Res,result);
}

/*******************************************************************/

long call_div(char *number,long div,char *result)
{
  long len=strlen(number);
  long now;
  long extra;  
  char Res[MAX+100];
  
  for(now=0,extra=0;now<len;now++)
  {
    extra=extra*10 + (number[now]-'0');
    Res[now]=extra / div +'0';
    extra%=div;
  }
  Res[now]='\0';

  for(now=0;Res[now]=='0';now++)
	  ;
  strcpy(result, &Res[now]);
   
  if(strlen(result)==0)
     strcpy(result, "0");

  return extra;
}

/*******************************************************************/


char fir[MAX+100], sec[MAX+100], res[MAX+100], hold[MAX+100], xx[MAX+100], result[MAX+100];

int main()
{
     long len_f, len_s, j, test, len, i, remainder, second, len_d, lo;

	 second=0;
	 lo=0;
	 
	 while(1)
	 {
		 scanf("%ld", &second);

		 gets(xx);
	     sscanf(xx, "%ld", &test);

		 swap(second, test);
		 
		 if(test==0 && second==0)
			 break;

		 len_f=len_s=0;
	 
	 	 memset(result, '0', sizeof(result));
		 memset(sec, '0', sizeof(sec));
	     strcpy(sec, "0");
		 
		 for(j=0; j<test; j++)
		 {
	 	   memset(res, '0', sizeof(res));
		   memset(hold, '0', sizeof(hold));
         
		   gets(hold);
	   
		   strcpy(fir, hold);

		   len_s=strlen(sec);
		   len_f=strlen(fir);

		   if(len_f<len_s)		 
		      call_sum(sec, fir, res);
		   else
			  call_sum(fir, sec, res);
			 
		   memset(sec, '0', sizeof(sec));
		   memset(fir, '0', sizeof(fir));
		   strcpy(sec, res);
		
		 }
	
	     len=strlen(res);
        
	     for(i=0;i<len;i++) 
	         res[i];
         res[i]='\0';   

/////	 printf("%s", act_res);       ///////

	     len_d=remainder=0;
		 remainder=call_div(res,second,result);
	 
	     len_d=strlen(result);
 
	     for(i=0;i<len_d;i++) 
		    result[i];
	     result[i]='\0';
	 
		 printf("Bill #%ld costs %s: each friend should pay %s\n", ++lo, res, result);
		 printf("\n");
	 
	 }
     
	 return 0;
}
:oops: :oops: :oops: :oops: :oops:

Re: 10925 - Krakovia

Posted: Sun Jan 11, 2009 2:39 pm
by mf
Your memset's on lines 122-123, 128-129, 143-144 access almost 2Mb of memory each for every test case. That wastes a *lot* of precious memory bandwidth!

Re: 10925 - Krakovia

Posted: Mon Jan 19, 2009 4:28 pm
by toru
THANX mf, i fixed my code got accepted
ThaNX FOR HELP
:wink:

Re: 10925 - Krakovia

Posted: Fri Jul 16, 2010 1:51 am
by naheed
Getting WA!!!!!
I tried all test cases given by my previous posters.PLEASE HELP.

Code: Select all

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sn=new Scanner(System.in);
        BigInteger b[]=new BigInteger[1010];
        BigInteger zero=new BigInteger("0");
        BigInteger one=new BigInteger("1");
        BigInteger n=new BigInteger("1");
        BigInteger f=new BigInteger("1");
        int cas=1;
        try{
         while(true){
           n=sn.nextBigInteger();  // N
           f=sn.nextBigInteger();  //F
           if(n.equals(zero) && f.equals(zero))
              break;
           int i=0;
           BigInteger sum=zero;
           while(i!=n.intValue()){
               b[i]=sn.nextBigInteger(); //array of items
               sum=sum.add(b[i]); //sum
               i++;
           }
          
            System.out.print("Bill #"+cas+" costs "+sum+": ");
            System.out.print("each friend should pay ");
            System.out.println(sum.divide(f)); // (sum/F)
        cas++; //case
        }
        }catch(Exception e){
        System.exit(0);
        }
    }

}

Re: 10925 - Krakovia

Posted: Fri Apr 08, 2011 11:36 am
by Pro.metal
my code gives correct output sometimes also wrong output for the same test cases. i dunno what's wrong with it and why it is showing such a strange behavior.

please help. thanks

Code: Select all

#include <stdio.h>
#include <string.h>
char res[1000];
int main()
{
    int N,F,i,j,k,len,lim,high,sum,carry,p,m,n,v,quo,flag,r,a = 1;
    char in[1002][100],ch;
    while(scanf("%d%d",&N,&F))
    {
        getchar();
        if(!N && !F) break;
        high = 0;
        for(k=0; k<N; k++)
        {
            scanf("%s",in[k]);
            len = strlen(in[k]);
            if(len>high) high = len;     //saves the length of the max string
            lim = len/2;
            if(len%2==0)                             //reversing each string in the same string
            {
                for(i=0,j=len-1; i<lim,j>=lim; i++,j--)
                {
                    ch = in[k][i];
                    in[k][i] = in[k][j];
                    in[k][j] = ch;    
                }    
            }
            else
            {
                for(i=0,j=len-1; i<lim,j>lim; i++,j--)
                {
                    ch = in[k][i];
                    in[k][i] = in[k][j];
                    in[k][j] = ch;    
                }   
            }    
        }
        p = 0;
        carry = 0;
        for(m=0; m<high; m++)                          //adding the reversed string
        {
            sum = 0;
            for(n=0; n<N; n++) 
            {
                if(in[n][m]=='\0');
                else sum = sum + (in[n][m] - 48);
            }
            sum += carry;
            if(sum>9)
            {
                if(m==high-1)
                {
                    if(sum<=99)
                    {
                        res[p] = sum%10 + 48; 
                        sum = sum/10;
                        res[++p] = sum%10 + 48;  
                    }
                    else
                    {
                        res[p] = sum%10 + 48;
                        sum = sum/10;
                        res[++p] = sum%10 + 48;
                        sum = sum/10;
                        res[++p] = sum%10 + 48;         
                    }    
                }
                else
                {
                    carry = sum/10;
                    res[p] = sum%10 + 48;
                }   
            }  
            else 
            {
                res[p] = sum + 48;
                carry = 0;
            }
            ++p;    
        }
        printf("Bill #%d costs ",a);
        for(j=p-1; j>=0; j--) printf("%c",res[j]);
        printf(": each friend should pay ");
        r = 0;
        flag = 0;
        for(j=p-1; j>=0; j--)                                  //dividing the money among the friends
        {
            v = 10*r + (res[j]-48);
            quo = v/F;
            r = v%F;
            if(!flag)
            {
                if(quo)
                {
                    printf("%d",quo);
                    flag = 1;    
                }        
            }   
            else printf("%d",quo);
        }
        if(!flag) printf("0");
        printf("\n\n");
        a++;
    }
    return 0;    
}


Re: 10925 - Krakovia

Posted: Thu Dec 20, 2012 4:11 pm
by shuvokr
For bindas
Try it

Code: Select all

100 2
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
0 0
Important :: 1 ? N ? 1000 && 1 ? F ? 20 && 1 ? V ? 10^20
Hope that it's help you.

Re:

Posted: Sun Feb 24, 2013 10:18 am
by DD
Jemerson wrote:Hum.. i had accepted all sugestted inputs but I was still getting WA, so i found two inputs that showed me some extra cases. After correct this I got Accepted. Here they are:

Input:

Code: Select all

1 16
17432479801732498109834891047810
1 15
17432479801732498109834891047810
Output:

Code: Select all

Bill #1 costs 17432479801732498109834891047810: each friend should pay 1089529987608281131864680690488

Bill #2 costs 17432479801732498109834891047810: each friend should pay 1162165320115499873988992736520

Good Luck for everyone
My program prints lots junk result by using your test input :o After a while, I realized that you did not include "0 0" at the end of your test input 8)

Re: 10925 - Krakovia

Posted: Sun Feb 24, 2013 10:22 am
by DD
shuvokr wrote:For bindas
Try it

Code: Select all

100 2
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
999999999999999999
0 0
Important :: 1 ? N ? 1000 && 1 ? F ? 20 && 1 ? V ? 10^20
Hope that it's help you.
I think your test case misses one line. There should be one more line "999999999999999999".

Re: 10925 - Krakovia

Posted: Wed Aug 07, 2013 12:42 am
by ??????
WA!!!! :( Help pls!!!

Code: Select all

#include <string.h>
#include <iostream>

using namespace std;
char* stradd(char s[100000],char d[100000]);
char* strdiv(char s[100000],int x);


int main()
{
int n,x,t,i;
char s[100000],d[100000]="0";
for(t=1;;t++)
{
cin>>n>>x;if(n==0&&x==0)break;
for(i=0;i<n;i++)
{
  cin>>s;
   strcpy(d,stradd(d,s));
}
cout<<"Bill #"<<t<<" costs "<<d<<": each friend should pay "<<strdiv(d,x)<<endl<<endl;
d[0]='\0';
}
}


char* stradd(char s[100000],char d[100000])
{
    char h[100000];
    memset(h,'0',abs(strlen(s)-strlen(d))); h[abs(strlen(s)-strlen(d))]='\0';
    if(strlen(s)<strlen(d))
    {
        strcat(h,s);strcpy(s,h);
    }
    if(strlen(s)>strlen(d))
    {
        strcat(h,d);strcpy(d,h);
    }
    h[0]='\0';
    int i,hand;hand=0;
    char sum[100000];
    i=strlen(s)-1;
    while(i>=0)
    {
        sum[i]= (s[i] + d[i] + hand -96)%10  +48;
        hand= (s[i] + d[i] + hand -96)/10 ;
        i--;
    }sum[strlen(s)]='\0';
    if(hand!=0)
    {
        h[0]=hand+48;h[1]='\0';
        strcat(h,sum);strcpy(sum,h);
    }
    return sum;
}


char* strdiv(char s[100000],int x)
{
    char pro[100000];
    int i,n,j,c,hand;
    c=0;
    for(i=0,j=0,hand=0;i<strlen(s);i++)
    {
        n=(s[i]-48 + 10*hand)/x;
        hand=(s[i]-48 + 10*hand)%x;
        if(n>0)c=1;
        if(c==1)
        {
            pro[j]=n+48;j++;
        }
    }pro[j]='\0';
    return pro;
}

Re: 10925 - Krakovia

Posted: Thu Aug 08, 2013 2:43 am
by brianfry713
Add #include <stdlib.h>
Your code doesn't match the sample I/O.