10925 - Krakovia

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

Moderator: Board moderators

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Mon Dec 24, 2007 9:01 pm

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...
Amra korbo joy akhdin............................

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

10925,RTE,pleas help!!

Post by turcse143 » Tue Dec 25, 2007 3:19 pm

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++;
}
}
''I want to be most laziest person in the world''

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Tue Dec 25, 2007 8:12 pm

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
Amra korbo joy akhdin............................

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Thu Feb 28, 2008 8:33 am

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
''I want to be most laziest person in the world''

anton_indrawan
New poster
Posts: 6
Joined: Mon Dec 15, 2008 3:34 pm
Location: Surabaya, Indonesia

Re: 10925 - Krakovia

Post by anton_indrawan » Fri Dec 26, 2008 8:30 am

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



toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

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

Post by toru » Sun Jan 11, 2009 11:30 am

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:

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

Re: 10925 - Krakovia

Post by mf » Sun Jan 11, 2009 2:39 pm

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!

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

Re: 10925 - Krakovia

Post by toru » Mon Jan 19, 2009 4:28 pm

THANX mf, i fixed my code got accepted
ThaNX FOR HELP
:wink:

naheed
New poster
Posts: 8
Joined: Sun Oct 25, 2009 7:20 pm

Re: 10925 - Krakovia

Post by naheed » Fri Jul 16, 2010 1:51 am

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);
        }
    }

}

Pro.metal
New poster
Posts: 9
Joined: Fri Dec 17, 2010 8:13 pm

Re: 10925 - Krakovia

Post by Pro.metal » Fri Apr 08, 2011 11:36 am

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;    
}


shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 10925 - Krakovia

Post by shuvokr » Thu Dec 20, 2012 4:11 pm

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.
Last edited by shuvokr on Fri Feb 07, 2014 11:54 pm, edited 1 time in total.

Code: Select all

enjoying life ..... 

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » Sun Feb 24, 2013 10:18 am

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)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10925 - Krakovia

Post by DD » Sun Feb 24, 2013 10:22 am

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".
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

??????
New poster
Posts: 6
Joined: Thu Jun 13, 2013 5:40 am

Re: 10925 - Krakovia

Post by ?????? » Wed Aug 07, 2013 12:42 am

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10925 - Krakovia

Post by brianfry713 » Thu Aug 08, 2013 2:43 am

Add #include <stdlib.h>
Your code doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 109 (10900-10999)”