10494 - If We Were a Child Again

[Jan]

The first number can be too big to be stored in 'long long' or 'long double'.

[wallace]

Hi!
tested with all the entries that the forum suggested, and when I put the wrong
sorry if something is written wrong.
thank you!
My code:

#define MAXDIGITS 10000
#define PLUS 1
#define MINUS -1

#include<iostream>
#include<string>

using namespace std;

typedef struct {
char digits[MAXDIGITS];
int signbit;
int lastdigit;
} bignum;


void divide_bignum(bignum *a, bignum *b, bignum *c,bignum *r)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int asign, bsign; /* temporary signs */
int i,j; /* counters */
inicializa(c);
c->signbit = a->signbit;



a->signbit = PLUS;
b->signbit = PLUS;

inicializa(&row);
inicializa(&tmp);

row.signbit = 1;
tmp.signbit = 1;

c->lastdigit = a->lastdigit;
for (i=a->lastdigit; i>=0; i--) {

digit_shift(&row,1);
row.digits[0] = a->digits;
c->digits = 0;
while (compare_bignum(&row,b) != PLUS) {
c->digits ++;

*r = row;

subtract_bignum(&row,b,&tmp);

row = tmp;
}
}
zero_justify(c);

}
void ler_bignum(char *num,bignum *n)
{
bignum aux;
n->signbit = 1;

for( int j = 0; j < MAXDIGITS; j++) n->digits[j] =(char)0;

n->lastdigit = strlen(num)-1;

for(int i = 0; i < MAXDIGITS;i++) n->digits =(char) 0;

for(int i = 0; i < strlen(num); i++)
n->digits = num -'0';

inverte(n,&aux);
*n = aux;

}

int main()
{

char num[10000],num2[10000];
bignum a,b,c,r,aux;
char operacao;

while( scanf("%s %c %s",num,&operacao,num2)!= -1)
{

ler_bignum(num,&a);
ler_bignum(num2,&b);
divide_bignum(&a,&b,&c,&r);

if(operacao == '/')
{
print_bignum(&c);
}
else
{
if(c.digits[c.lastdigit] == '0'-'0')
{
print_bignum(&a);
}
else{

subtract_bignum(&r,&b,&aux);
print_bignum(&aux);
}
}
num[0] = '\0';
num2[0] = '\0';
}
return 0;
}

[sayem]

plz someone tell me why i got WA??
here is my code

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX 1000
/*******************************************************************/
int call_div(char *number,long div,char *result)
	{
	int len=strlen(number);
	int now;
	long extra;
	char Res[MAX];
	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;
	}
/*******************************************************************/
	int main()
		{
		char fir[MAX],res[MAX];
		long sec,remainder;
		char c;
		int j=0;
		while((c=getchar())!=EOF)
			{
			fir[j]=c; j++;
			while((c=getchar())!=' ')
				{
				fir[j]=c;
				j++;
				}
			fir[j]='\0';
			
			while(c=getchar())
				{
				if( c=='/' || c=='%') 
					break;
				}
			scanf("%ld",&sec);
			remainder=call_div(fir,sec,res);
			int len=strlen(res);
			if(c=='/')
				for(int i=0;i<len;i++) printf("%c",res[i]);
			else printf("%ld",remainder);
			printf("\n");
			j=0;
			fir[0]='\0';
			res[0]='\0';
			fflush(stdin);
			}
		return 0;
	}

[mathgirl]

I have tried with the sample inputs given previously. But I m getting TLE. Can anyone help me out?

Code: Select all

Got Ac. I optimised the algo.

[Enayet Kabir]

Error: Runtime Error
Please help anyone..
===========Here is my code =============
package pr;
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main
{
public static void main(String[] args)
{
BigInteger nm1,nm2;
String s;
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
nm1=sc.nextBigInteger();
s=sc.next();
nm2=new BigInteger(sc.next());
if(s.equals("/"))
System.out.println(nm1.divide(nm2).toString());
else if(s.equals("%"))
System.out.println(nm1.mod(nm2).toString());
}
}
}

[brianfry713]

Don't use a package.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

[Enayet Kabir]

Thanks for your tips. I have got Ac.

[sonjbond]

i ve checked so many critical input output . i am still getting WA ,,, plz anybody help me,,,, plz,,,, i am trying this for a long time ..... here's my code:

#include<stdio.h> /*10494*/
#include<string.h>
char num[100000000];
int ans[100000000];
int main()
{
unsigned long long n;
char sign;
while(scanf("%s %c %llu",num,&sign,&n)==3)
{
double len=strlen(num);

if(sign=='/')
{
long long m,i,j,a,dgt,p,c;
m=n;
dgt=0;
while(m!=0)
{
m=m/10;
dgt++;
}

c=0;
if(dgt<=len)
{
a=0;
for(i=0; i<dgt; i++)
a=a*10+(num-48);
}
if(len>dgt)c=1;
else if(len==dgt&&a>=n)c=1;
else if(len==dgt&&a<n)c==0;
else if(len<dgt)c=0;


if(c==1)
{
j=0;
i=dgt;
p=0;
for(;;)
{
if(p>1)
{
ans[j]=0;
j++;
}
if((a/n)>=1)
{
ans[j]=a/n;
j++;
a=a%n;
p=0;
}
else
{
a=a*10+(num-48);
i++;
p++;
}
if(i==len+1)break;
}
for(i=0; i<j; i++)
printf("%d",ans);
printf("\n");
}
else if(c==0)
printf("0\n");
}


else if(sign=='%')
{
unsigned long long rem,k;
k=0;
rem=0;
while(k<len)
{
rem=(rem*10+num[k]-48)%n;
k++;
}
printf("%llu\n",rem);
}

}

return 0;
}


plz help me

[brianfry713]

Why is len a double?

[i see]

It's WA all the time, I have checked over function div, function division and functon mod, I think they are all right, please help me, thanks in advance !

#include <iostream>
#include <string>
#include <fstream>
#include <deque>
//#define LOCAL
#define fin cin
#define fout cout
using namespace std;
#ifdef LOCAL
ifstream fin("in.cpp");
ofstream fout("out.cpp");
#endif
void division(const deque<int> &a, const unsigned &n, deque<int> &result)
{
deque<int>::size_type i = 0;
deque<int> s(a);
unsigned sum1 = 0, sum2 = 0, sum3 = 0;
if ( !s.empty()) {
sum1 = s.front();
sum2 = sum1 / n;
sum3 = sum1 % n;
while (!s.empty() && sum2 == 0 )
{
s.pop_front();
if(!s.empty())
result.push_back(0);
if (!s.empty()) {
s.front() = (sum1 * 10 + s.front());
sum1 = s.front();
sum2 = sum1 / n;
sum3 = sum1 % n; }
}
if (!s.empty())
s.pop_front();
if (!s.empty())
s.front() = sum3 * 10 + s.front();
result.push_back(sum2);
while (result.size() - 1 != 0 &&result.front() == 0)
result.pop_front();
division(s,n,result);
}
}
void div(const string &a, const unsigned &n, string &result)
{
deque<int> v,r;
result.clear();
string::const_iterator iter = a.begin();
while (iter != a.end())
{
v.push_back(*iter - '0');
++iter;
}
division( v, n, r);
deque<int>::const_iterator it = r.begin();
while (it != r.end())
{
result.push_back(*it + '0');
++it;
}
}
void mod(const string &a, const unsigned &n, unsigned &result)
{
string::size_type i = a.size();
string s(a);
result = 0;
unsigned sum1, sum2, sum3,d;
if (!s.empty()) {
sum1 = s.at(i - 1) - '0';
sum2 = sum1 % n;
sum3 = 10 % n;
s.erase(s.end() - 1);
mod( s, n, d);
result = (sum2 + sum3*d) % n;
}
}

int main()
{
string a, result_str;
char mark;
unsigned n, result_int;
while (fin >> a >> mark >> n)
{
if (mark == '/') {
div( a, n, result_str);
fout << result_str << endl;
result_str.clear();
}
else {
mod( a, n, result_int);
fout << result_int << endl;
}
}
return 0;
}

[brianfry713]

Some random input:

Code: Select all

875356291270936062618792023759228973612931947845036106320615547656937452547443078688 / 709393584
3492 % 1264095060
19266495048717272261061594909177115977673656394812939088509638561159848103044 / 1869470124
663175962178574 % 1626276121
89753883189643338604888977643030925405946922477548128936802 / 889023311
71108506462 % 1470503465
228472406 / 1238433452
7081311034039196933805664004626756987282996027613215991491075870480429610422205529028380409196254499 % 1682085273
75029435174314694226412889288868383338047689068790333732652658796041048708624 / 820697697
2928301789154925749945935708199782534902019621207311905677406474858260664628960701013772645202909945 % 826047641
778860467609759785338 / 1584710873
13787419098858437138097993243712202175 % 1388391521
8171117040851662196480810229756463797491706085394154155498 / 1215828993
1222703463633443972 % 1464415775
40247657133385108763508041135934150835659907637615065081226910427403280370034927425244386 / 1862875640
2223183422451757169813337986704848168521996064990893148967737122150904013741130 % 476152433
97565422172416578592736479722163021565003466025895060837821058550738230777691190898 / 989241888
67069217797 % 286448566
81588456568488387524505732721349419574122162022974356 / 386839851
93127798107601025197131206874924459128960640945466399521309913458 % 78374295
638955386033618705110300454249994981639334615617229281247863772372537681364035 / 827385948
399802 % 530406424
11200639083873100503 / 1105629391
217910359484692903033794991942065956114 % 67874133
9733924449938329543949557390727290504179362125391887052791963684667274100644373472179568 / 228217069
6215991621053219768206433690485129738092318741 % 1131352346
255012648562526913315269446074379002269035587170604130296093543643191094562591774119 / 1029621931
674931387938840086823850592685283678726629703723517894 % 33713861
4354873 / 1003463633
5145707899394645 % 1353668775
906269929655386736026930876524006854946832362247049654642516137712 / 1917305981
5901348582206361057420033904334245381131581339754496721013776 % 503458793
1041186434770745307299302799520835965630 / 992277052
847301675788907803103 % 729568616
92215338285808693374371396420295746491231813892451001330002224798547 / 278190158
2064375810930264386708198164850159706 % 1667250732
350272817797988980520243730015800047531 / 825791694
5130048220245840842542757522866009126948282 % 1268632557
77709454223965743944060228431119000257691987651148576691436769760907668776653769726407540 / 1369520631
301 % 2105210525
8716495351100708164149862252327390150697928 / 1983827549
9936360449664198049055016028849834491757624255052977681203287463804979751378095213273323861609191509 % 1409907854
9824653474714048334615546696756430025385056673408081535114011857851609 / 1994159651
4901443251326069680867544605539150496743096 % 1198911786
25828685340177808978397250248062656634171308290108167882138935412277914 / 272327630
487680861452593884350593462532000980967214484 % 193088109
74196809363895017198267593997973504194143642276185113064475 / 1469543483
27353748001645831229554631206519446810812988682024981564686 % 1718500113
842402720161949969420236892867353595 / 463079269
790521020636948408448242779939840805909182876848983707196301486666178296594378 % 1042080532
87604912224602398686972688988168048442964554705764353732830866971937123570260737184768963 / 1706740259
775605276632436043637494293824543224741616870496951602222736100723107480187347134424649 % 1893051878
35727440560040320869923548107249923667746960995173085439462386270 / 383174967
3431247558077377932078207146112887101079076933649846997801435943855 % 366420782
11827052611788677490027162048223327245416804883524747565769703238052515115893367862510008 / 1423977622
57015080715133948236090702000408119939912647932875604696896859870785878052857257917396998 % 1743131527
76528406 / 1045251304
96596288757022913813 % 1541787377
349201863420594491993412572601415357733207476818937270647 / 589306240
4163828592034771655468105189181097391262665054319877687325435756595833199 % 1268374276
11402580169705132999606430541458519967905976681892954627671718680786696185966175563025982386 / 661362461
113409682642305072802354307188742212172636088708998426878598364715944200008171990934731 % 1176924347
953121292 / 1255349946
4969940951072332871619121460736522439646746299678752674 % 1131491977
18066609058704660062652414201034040622727519006202499950370494 / 1513453188
2082256218130772141136386635237265680223248238572887735390816552212565889934701101875306618285439685 % 939288131
729076007 / 143154913
407133763969598175380773465558939 % 1920992956
715076681682537355181768247733377896464542097754465651495 / 983650352
4700610258632031926674131491110212573501586719023980315777 % 835022190
2031489051301992007397649338037151221327459649041790556610415243575627574538634713981742985522071563 / 2103540592
688564923272282621608928855489897645357695 % 1284263301
659066277675 / 571647241
1920 % 1198948480
47514504037787743130717861083002965437050 / 571876647
84257389119970966288165793745574919949051178286805841511095664255160097306245027523 % 347838179
9006784401918149179714428493983605404844038074983875449388879 / 1914635591
68092939997963066833572073872133953248359267563 % 1992434581
652892820541002536239751428282999198573549849324948933297325536476423700706638 / 1900257991
2148 % 1517735046
7519383942594184177940875409280031162666837546173899998638866882118386080736556 / 2000245409
804493771569380786558357913474944685985231191369134981 % 998126997
403265923784736369272084535542594040535023406232171499064511 / 1416732620
5676941456716541970011137618737194080147739585872896911894787499099 % 1877057460
48279066850976080994872481480636654772569676474463962301661854511119367244 / 123204721
8550166597673968532765813538969224251922610108263659330685692516043155336549385860795763324785309634 % 1733898061
6044994481650158601071703986514510900560645772732859131429091742755713778565741 / 439148632
3181525455729295796085054650774502957422196117806637132719706267674316758381164927652 % 682976441
7024742639063968796804208185490023699172091587358161503321983905266473604953 / 735937718
172888913344 % 2066212151
934892297192265177026825150701766365696527746473277079507589 / 1692359398
442110206675150894 % 307147498
258167866853476789747718219377234240148723261841917708732889505249456348865171284155050238311837093 / 584605206
84161434739816066216849697692411947292786887495236031000989133449480678459398013947 % 235104522
74594849200691569120730774813072523128068037106 / 1970996743
2503600283590964276075190030685636 % 648732992
643888989554 / 645202512
518738860466314532960772867300871744542890442897203402601453632707481862926327040580 % 637945550
7137490783643931443295011081 / 880210192
8491162351635940284513236355773515943178463077006 % 501797827

AC output:

Code: Select all

1233950110367696901271652921742845891897623855370301891989786515544433585612
3492
10305858757182937608186989624861807086933503942325070870461066839257
75348226
100957851249913219210164195169265843250702930642893
524340142
0
1580068370
91421525183486282192422052439204521537785781149560522932298003994570
794311842
491484270651
1054417477
6720613744116942765223900389219015603365946452137
442974522
21605122891287101034563982561892403529233925479649873504828755196671786620192707
363231291
98626456639103194336971383607810814380924664227213820567433410735977883275
40253353
210910164393813675428454584740674557787796692
49175643
772257962052817828506679514274268266445509678413379678582435596757968
399802
10130554754
2235752
42652043918495551022739484007339041341291444442273014437811238758251137212897837
156325525
247676006973599432115504779466841991994278516558330895047818813062161837889
28461014
0
16643270
472678820509759175484953998338362693996536571721595049174
145755047
1049290047242516807996586420624
239312839
331483108348530048911260895219361953456426067713189915690698
522344358
424166070381895825317230340192
522838378
56742083664138495146233564429683279636326988381928637547802498026703818802605369
301
4393776745107953011973150218778109
425148197
4926713600782833377374130160231804843284865296579045834437060
556312878
94844160102953229455260379742087340289970974631212293376690919
178350673
50489699843672483693541441126566177418884611715967
55120905
1819132871098036499276405510
405469874
51328789933115650895871138519952173017185829859635574303770417459835125135031303
1004305427
93240539275730715649604396278971751481215527827456132956
240803995
8305644996848607421463510926032886242517654454772567743181643368586950389514876
1368561933
0
1065532006
592564340436297589506964278201797689658279329977
156310463
17241045330066190435937715765604240982020261173990270711285076521430653418906664500
265866257
0
707073098
11937342497245881160780517118335899678138917770215500
522405324
5
901675663
726962258721925771426723636991468180214245577532
708049267
965747492122553728878862223561574713518748987869206070738099283408374357882909213658636631
821005423
1152
1920
83085232256017866612968829767589
214734062
4704176838796761498054920725634628299795372431778781
1853930442
343581147209080483345669787152074761922971884150307953262187090298321
2148
3759230696774059776352610245776112746306939553222541603963189939819222
697410098
284645047408265625501080461846494393935126168148914
874491499
391860526602516156786495880142747571925995242296469810614333962990
8134203
13765258596206121395982633930906816306695555806109989502208199393310904
298839035
9545295025990186844594107602852913837434394940684588615312666859760
1393304811
552419479158566516866309948368169469459540736673521
236539554
441610618933620631745996150737724084086796965406971946693354463985831061629600479738201712
163740701
37846256958878987412274366611204756885
327803076
997
602689830
8108848146175443789
465235324

Problems like these are very easy to solve with just a few lines of JAVA's BigInteger.

[shuvrothpol1]

first of all, in the problem there is given the limit( 0 < n < 2^31).so why should i use big int ? on the other hand, ANCI C doesn't support big int .In that case, how canI make the alternate of it in C ?

[brianfry713]

The first number may be arbitrarily long, the second number n will be in the range (0 < n < 2^31). In C you'll have to write your own bigint functions using an array, or you could use a C++ string or vector, but JAVA is much simpler for this problem.

[sonjbond]

my I/O is seems to correct ... but I m getting WA ... I cant find my wrong ......
plz help me ..... here's my Code :

Code: Select all

#include<stdio.h>         /*10494*/
#include<string.h>
char num[100000000];
int ans[100000000];
int main()
{
    unsigned long long n;
    char sign;
    while(scanf("%s %c %llu",&num,&sign,&n)==3)
    {
        long long len=strlen(num);

        if(sign=='/')
        {
            long long m,i,j,a,dgt,p,c,rem;
            m=n;
            rem=0;
            for(i=0; i<=len; i++)
            {
                ans[i]=(rem*10+num[i]-48)/n;
                rem=(rem*10+num[i]-48)%n;
            }

            for(i=0; i<len; i++)
                if(ans[i]!=0)break;
            for(; i<len; i++)
                printf("%d",ans[i]);
            printf("\n");
        }

        else if(sign=='%')
        {
            unsigned long long rem,k;
            k=0;
            rem=0;
            while(k<len)
            {
                rem=(rem*10+num[k]-48)%n;
                k++;
            }
            printf("%llu\n",rem);
        }

    }

    return 0;
}

help me plz ......

[brianfry713]

Try input:

Code: Select all

1 / 2