## 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:
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!!

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:
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
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

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

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

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

### Re: 10925 - Krakovia

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

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

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

### Re: 10925 - Krakovia

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

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

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:

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 After a while, I realized that you did not include "0 0" at the end of your test input
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

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

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

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