10023 - Square root

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

Moderator: Board moderators

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri May 28, 2004 2:14 pm

You should remove the fopen. Input is sent in via standard input.

rlatif119
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

Post by rlatif119 » Fri May 28, 2004 6:46 pm

You are right......This code seems to be wrong for some very big inputs. But i also used this sqrtl() function and got accepted.....parhaps judges don't use such bignumbers as the problem says....10^100.
But i am surprised how you got accepted using file fuctions?????? :o

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Mon Jun 14, 2004 5:50 am

yes its kinda funny..this code got AC :D
[c]int main(){
int cases,i;
long double n,res;
scanf("%d",&cases);
for(i=0;i<cases;i++){
scanf("%llf",&n);
res=sqrtl(n);
printf("%llu\n\n",(unsigned long long int)res);
}
}
[/c]
if u can think of it .. u can do it in software.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Jun 14, 2004 9:50 am

I submitted the above code in C++ and i got compile error,
but with C it got AC(P.E).

What is the mystery with the sqrtl() function. Is it part of ANSI C.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

very bad problem description

Post by helmet » Wed Jul 21, 2004 11:39 am

Thanks to this message thread I was able to realise to print floor(sqrt(number)).The problem description must be changed.

It is sad that such a nice problem should allow sqrtl() to solve it.
Just another brick in the wall...

User avatar
truckDriver
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:58 am

10023 - Square root Help input & test data ....

Post by truckDriver » Thu Oct 21, 2004 7:10 am

I tryed like this...

3

10
3

100
10

10000000
3162

is this right ?
or below right?

3

10
100
10000000
3

10

3162

is there any test data for this problem ?
I think my java logic is good and some test result always right...
(Even the max number in the problom)
but return message is always WA ...
plz help me ....

HYri
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:00 pm

10023 help me for compile online

Post by HYri » Fri Oct 22, 2004 4:47 am

hello.
first, sorry for there's many korean(my language) notes;;

i modify BigNum class for this problem..

i can compile it on VC++, and it works perfectly

but online-judge

it says compile error.. but i dont know why

plz help me

[cpp]
// Quiz4.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include <stdio.h>
#include <iostream>
#include <stdlib.h>

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// #include CBigNum.h Header
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// Header

/************************************************************************/
/* CBigNum */
/* */
/* 무한 크기의 Integer를 다루는 클래스 */
/* 정의된 연산은 + , - , * 의 세가지 산술 연산과 */
/* < , > 의 비교 연산과 */
/* int 와의 상호 캐스팅 연산이다. */
/* */
/* 참조 소스 : vnl_bignum of Texas Instruments Inc. */
/* */
/* 수정 : Seven.. ( hytgbn@hotmail.com ) */
/* // [10/21/2004] */
/************************************************************************/
class CBigNum;

int Magnitude_Cmp(const CBigNum&, const CBigNum&);
void Add(const CBigNum&, const CBigNum&, CBigNum&);
void Subtract(const CBigNum&, const CBigNum&, CBigNum&);
void Multiply_Aux(const CBigNum&, unsigned short d, CBigNum&, unsigned short i);

class CBigNum {
public:
CBigNum(); // 생성자
CBigNum(int); // int 생성자
CBigNum(CBigNum const&); // copy 생성자
~CBigNum(); // 소멸자

// 타입 캐스팅
operator int() const;
inline operator int() { return ((const CBigNum*)this)->operator int(); }

CBigNum operator-() const; // -X operator
inline CBigNum operator+() { return *this; } // +X operator
inline CBigNum operator+() const { return *this; } // +X operator

CBigNum& operator=(const CBigNum&); // Assign

// 산술 operator
CBigNum operator+(CBigNum const& r) const;
inline CBigNum& operator+=(CBigNum const& r) { return *this = operator+(r); }
inline CBigNum& operator-=(CBigNum const& r) { return *this = operator+(-r); }
CBigNum& operator*=(CBigNum const& r);

// 비교 operator
bool operator< (CBigNum const&) const;
inline bool operator> (CBigNum const& r) const { return r<(*this); }

// 계산 func
friend int Magnitude_Cmp(const CBigNum&, const CBigNum&);
friend void Add(const CBigNum&, const CBigNum&, CBigNum&);
friend void Subtract(const CBigNum&, const CBigNum&, CBigNum&);
friend void Multiply_Aux(const CBigNum&, unsigned short, CBigNum&, unsigned short);

private:
unsigned short count; // data 갯수
int sign; // 부호(+ , -)
unsigned short* data; // data ptr

void Resize(short); // alloc 된 크기 재정의
CBigNum& Trim(); // 정수에 크기에 맞는 포인터 재할당
};

// operator with BigNum or int
// plus
inline CBigNum operator+(CBigNum const& r1, int r2) { return r1+CBigNum(r2); }
inline CBigNum operator+(int r2, CBigNum const& r1) { return r1 + r2; }
// minus
inline CBigNum operator-(CBigNum const& r1, CBigNum const& r2) { return r1 + (-r2); }
inline CBigNum operator-(CBigNum const& r1, int r2) { return r1 + (-r2); }
inline CBigNum operator-(int r2, CBigNum const& r1) { return -(r1 + (-r2)); }
// multiply
inline CBigNum operator*(CBigNum const& r1, CBigNum const& r2) {
CBigNum result(r1); return result *= r2;
}

inline CBigNum operator*(CBigNum const& r1, int r2) {
CBigNum result(r1); return result *= CBigNum(r2);
}

inline CBigNum operator*(int r2, CBigNum const& r1) {
CBigNum result(r1); return result *= r2;
}


//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// Source
typedef unsigned short Counter;
typedef unsigned short Data;

//////////////////////////////////////////////////////////////////////////
// 기본 생성자 0으로 초기화 한다.
CBigNum::CBigNum ()
: count(0), sign(1), data(0) {
}

//////////////////////////////////////////////////////////////////////////
// int 생성자 : int값으로 초기화 한다.
CBigNum::CBigNum (int l) {
if (l >= 0) // 부호 설정
this->sign = 1;
else {
l = -l;
this->sign = -1;
}
Data buf[sizeof(l)];
Counter i = 0;
while (l) {
buf = Data(l);
l >>= 16;
i++;
}
// 데이터 포인터 할당.
this->data = ((this->count = i) > 0 ? new Data : 0);

i = 0;
while (i < this->count) { // data 입력
this->data = buf;
i++;
}
}

//////////////////////////////////////////////////////////////////////////
// copy 생성자 : b의 값으로 초기화 한다.
//////////////////////////////////////////////////////////////////////////
CBigNum::CBigNum (const CBigNum& b)
: count(b.count), sign(b.sign) {
this->data = // 메모리 할당
(b.count > 0 ? new Data[b.count] : 0);
for (Counter i = 0; i < this->count; i++) // 데이터 복사
this->data = b.data;
}

//////////////////////////////////////////////////////////////////////////
// 소멸자 : 자원 해제
//////////////////////////////////////////////////////////////////////////
CBigNum::~CBigNum () {
delete [] this->data; // 메모리 해제
}

//////////////////////////////////////////////////////////////////////////
// = : assign
//////////////////////////////////////////////////////////////////////////
CBigNum& CBigNum::operator= (const CBigNum& rhs) {
if (this != &rhs) { // a=a식의 assign 방지
delete [] this->data;
this->count = rhs.count; // 복사
this->data =
(this->count > 0 ? new Data[this->count] : 0);
for (Counter i = 0; i < this->count; i++)
this->data = rhs.data;
this->sign = rhs.sign;
}
return *this;
}

//////////////////////////////////////////////////////////////////////////
// - : negative
//////////////////////////////////////////////////////////////////////////
CBigNum CBigNum::operator- () const {
CBigNum neg(*this); // 참조 생성
if (neg.count) // 0 이면 하지 않는다.
neg.sign *= -1; // 부호 반전
return neg;
}

//////////////////////////////////////////////////////////////////////////
// + : add
//////////////////////////////////////////////////////////////////////////
CBigNum CBigNum::operator+(const CBigNum& b) const {
CBigNum sum; // 리턴값 생성
if (this->sign == b.sign) { // 부호가 같으면
Add(*this,b,sum); // 그냥 계산
sum.sign = this->sign;
}
else { // 부호가 다르면
int mag = Magnitude_Cmp(*this,b);
if (mag > 0) { // this가 크면
Subtract(*this,b,sum); // this-b
sum.sign = this->sign;
}
else if (mag < 0) { // b가 크면
Subtract(b,*this,sum); // b-this
sum.sign = b.sign;
}
}
return sum;
}


//////////////////////////////////////////////////////////////////////////
// *= : multiply
//////////////////////////////////////////////////////////////////////////
CBigNum& CBigNum::operator*= (const CBigNum& b) {
if (b.count == 0 || this->count == 0) // 0 체크
return (*this)=0L;
CBigNum prod;
// 메모리 할당
prod.data = new Data[prod.count = this->count + b.count];
for (Counter i = 0; i < b.count; i++) // 한 자리(Data)씩 계산을 해준다.
Multiply_Aux(*this, b.data, prod, i);// this * b.data를 prod에 계속 입력
prod.sign = this->sign * b.sign; // Multiply_Aux 주석 참조
prod.Trim();
return (*this)=prod;
}

//////////////////////////////////////////////////////////////////////////
// < : true for a < b
// : false for a > b
//////////////////////////////////////////////////////////////////////////
bool CBigNum::operator< (const CBigNum& rhs) const {
if (this->sign < rhs.sign) return true; // 부호 참조
if (this->sign > rhs.sign) return false; // 부호 계산이 저렴하다.
if (this->sign == 1)
return Magnitude_Cmp(*this,rhs) < 0;
else
return Magnitude_Cmp(*this,rhs) > 0;
}

//////////////////////////////////////////////////////////////////////////
// int : this의 상위 비트 부분을 int로 변환한다.
// : 프로그램에서는 int로 변환되는 부분은 int보다 크지 않은 경우만이다.
//////////////////////////////////////////////////////////////////////////
CBigNum::operator int () const {
int j = 0;
for (Counter i = this->count; i > 0; )
j = int(j*0x10000 + this->data[--i]);
return this->sign*j;
}

//////////////////////////////////////////////////////////////////////////
// Name : Resize
// Desc : new_count의 크기만큼 data의 메모리 크기를 할당한다.
//////////////////////////////////////////////////////////////////////////
void CBigNum::Resize (short new_count) {
if (new_count == this->count) return;
Data *new_data = (new_count > 0 ? new Data[new_count] : 0); // 메모리 할당

if (this->count <= new_count) { // 복사
short i = 0;
for (; i < this->count; i++)
new_data[i] = this->data[i];
for (; i < new_count; i++)
new_data[i] = 0;
}
else {
for (short i = 0; i < new_count; i++)
new_data[i] = this->data[i];
}

delete [] this->data;
this->data = new_data;
this->count = new_count;
}

// trim // trim CBigNum of excess data allotment
//////////////////////////////////////////////////////////////////////////
// Name : Trim
// Desc : 실제 데이터가 참조하는 부분만큼을 남기고 메모리를 삭제한다.
// : ex) 00134 -> 134
//////////////////////////////////////////////////////////////////////////
CBigNum& CBigNum::Trim () {
Counter i = this->count;
for (; i > 0; i--) // 상위 비트쪽에 0인 부분을
if (this->data[i - 1] != 0) break; // 스킵한다.
if (i < this->count) { // 사이즈 조정의 필요가 있으면
this->count = i;
Data *new_data = (i > 0 ? new Data[i] : 0);
for (; i > 0; i--)
new_data[i - 1] = this->data[i - 1];
delete [] this->data;
this->data = new_data;
}
return *this;
}


//////////////////////////////////////////////////////////////////////////
// Add : sum = b1 + b2
//////////////////////////////////////////////////////////////////////////
void Add (const CBigNum& b1, const CBigNum& b2, CBigNum& sum) {
const CBigNum *bmax, *bmin; // 자리수를 이용해 큰 자리수를 찾아서
if (b1.count >= b2.count) { // 계산에 활용한다.
bmax = &b1;
bmin = &b2;
}
else {
bmax = &b2;
bmin = &b1;
}
sum.data = ((sum.count = bmax->count) > 0 ? // 메모리 할당
new Data[sum.count] : 0);
unsigned long temp, carry = 0;
Counter i = 0;

// 각 자리수를 더하고 캐리를 위로 올려준다.
while (i < bmin->count) {
temp = (unsigned long)b1.data[i] + (unsigned long)b2.data[i] + carry;
carry = temp/0x10000L;
sum.data[i] = Data(temp);
i++;
}

// 자리수가 남은 경우 따로 계산을 해준다.(bmin은 alloc되어있지 않다!)
while (i < bmax->count) {
temp = bmax->data[i] + carry;
carry = temp/0x10000L;
sum.data[i] = Data(temp);
i++;
}

// 캐리가 남으면 데이터 크기를 더 잡아준다.
if (carry) {
sum.Resize(bmax->count + 1);
sum.data[bmax->count] = 1;
}
}
//////////////////////////////////////////////////////////////////////////
// Subtract : diff = bmax - bmin
//////////////////////////////////////////////////////////////////////////
void Subtract (const CBigNum& bmax, const CBigNum& bmin, CBigNum& diff) {
diff.data = new Data[diff.count = bmax.count]; // 메모리 할당.
unsigned long temp;
int borrow = 0;
Counter i = 0;
for (; i < bmin.count; i++) { // bmax - bmin을 실행한다.
temp = (unsigned long)bmax.data[i] + 0x10000L - borrow;
temp -= (unsigned long)bmin.data[i];
borrow = (temp/0x10000L == 0); // bmin[i]가 크면 앞에서 빌려온다.
diff.data[i] = (Data) temp;
}
for (; i < bmax.count; i++) { // bmax의 남은 자리수 : bmin은 alloc되지 않았다!
temp = (unsigned long)bmax.data[i] + 0x10000L - borrow;
borrow = (temp/0x10000L == 0);
diff.data[i] = (Data) temp;
}
diff.Trim(); // 데이터 크기 확인
}

//////////////////////////////////////////////////////////////////////////
// Name : Magnitude_Cmp
// Desc : 인자의 b1, b2의 절대 크기 비교
// Return : -1 : abs(b1) < abs(b2)
// 0 : abs(b1) = abs(b2)
// +1 : abs(b1) > abs(b2)
//////////////////////////////////////////////////////////////////////////
int Magnitude_Cmp (const CBigNum& b1, const CBigNum& b2) {
if (b1.count > b2.count) return 1; // 자리수 비교
if (b2.count > b1.count) return -1;
Counter i = b1.count;
while (i > 0) { // 상위 비트부터 크기 비교
if (b1.data[i - 1] > b2.data[i - 1])
return 1;
else if (b1.data[i - 1] < b2.data[i - 1])
return -1;
i--;
}
return 0; // 모두 같다.
}

//////////////////////////////////////////////////////////////////////////
// Name : Multiply_Aux
// Desc : BigNum * ungisnged short를 하고
// : prod의 i번째 자리 이후로 기록한다.
// : ex) Multiply_Aux(134, 2, prod, 1)
// : prod : 2680 <- 134*2 << 1
//////////////////////////////////////////////////////////////////////////
void Multiply_Aux (const CBigNum& b, Data d, CBigNum& prod, Counter i) {
if (i == 0) { // index 가 0이면,
Counter j = 0; // 첫 계산에 호출 되는 것이기 때문에
while (j < prod.count) // prod를 0 으로 초기화해준다.
prod.data[j++] = 0;
}
if (d != 0) { // d==0이면 점프
unsigned long temp;
Data carry = 0;

Counter j = 0;
for (; j < b.count; j++) {
temp = (unsigned long)b.data[j] * (unsigned long)d
+ (unsigned long)prod.data[i + j] + carry;
prod.data[i + j] = Data(temp % 0x10000L);
carry = Data(temp/0x10000L);
}
if (i+j < prod.count)
prod.data[i + j] = carry;
}
}


//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
int main(int, char*)
{
char szInput[1002] = {0,}; // 1 ~ 10^1000까지의 계산을 위한 공간
szInput[0] = '0';
char* pNum;
CBigNum nNum;
CBigNum nCarry = 0;
CBigNum nTmp = 0;
CBigNum nScale = 0;
int nCnt = 0;

#ifndef ONLINE_JUDGE
freopen( "10023.in", "r", stdin );
#endif
scanf("%d\n\n", &nCnt);

while(nCnt)
{
nCarry = 0;
nTmp = 0;
nScale = 0;

memset(szInput, 0, 1002);
gets(szInput+1);
scanf("\n");
szInput[0] = '0'; // 0자리를 '0'으로 채우고 자리수의 짝, 홀에 따라서
szInput[1001] = '\0'; // 포인터 할당 위치를 체크한다.
int len = (int)strlen(szInput+1);

pNum = szInput;

if(len & 1)
++len;
else
++pNum;

len >>= 1; // half length : 정답의 자리수



for(int i = 0; i<len; ++i)
{
// 위로 부터 두 자리를 끊는다.
nNum = nCarry + int( *pNum * 10 + *(pNum+1) - '0' * 11 );
pNum += 2;

//2 * Scale * n + n^2 =< nNum 인 최대 n을 찾는다.
// n^2 + 2 * Scale * n - nNum =<0
// 1000자리까지 갈 경우 double의 범위를 넘는다.
// double 범위 이내는 근의 공식을 이용할 수 있지만,
// 그 이상은 sqrt함수가 에러가 난다.
for(int j=0; j<10; ++j)
{
if( (j + 2 * nScale) * j > nNum )
break;
}
nTmp = j-1;
printf("%d", int(nTmp));

nCarry = (nNum - nTmp * (nTmp + 2 * nScale)) * 100;
nScale = nScale * 10 + nTmp*10;
}
printf("\n\n");


--nCnt;
}



return 0;
}


[/cpp]

HYri
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:00 pm

oops

Post by HYri » Fri Oct 22, 2004 5:38 am

Got it!

[cpp]for(int j; -> int j; for(j = 0; .... style)[/cpp]

and [cpp]gets -> scanf("%s\n\n", szInput+1);[/cpp]

but.. still.. compile error

so i include memory.h

then P.E :D

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Oct 22, 2004 7:21 am

Hi !! truckDriver, The first option is the good one, for each input that you get calculted the sqrt, this problem can be easy solved in C with long double :wink: and yor ouput is all right

Hope it Helps
Keep posting !!

User avatar
truckDriver
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:58 am

WA IS MINE ...

Post by truckDriver » Fri Oct 22, 2004 4:28 pm

thanx Ghust_omega...

but as yet, returned answer always WA...

Is there anyone who test my program's test data

and if my test is right ...

anyghing that you guess possible cause that I GET ALWAYS WA.. ?


5

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
100000000000000000000000000000000000000000000000000

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
316227766016837933199889354443271853371955513932521

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
10540925533894597773329645148109061779065183797750722756191682842641981462130794071147493694597667650624490947176133517161829520101512933382301731989000513011149738857264199802197167178247044464947080

15241578750190521
123456789

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
3162277660168379331998893544432718533719555139325216826857504852792594438639238221344248108379300295187347284152840055148548856030453880014690519596700153903344921657179259940659150153474113339484124085316929577090471576461044369257879062037808609941828371711548406328552999118596824564203326961604691314336128949791890266529543612676178781350061388186278580463683134952478031143769334671973819513185678403231241795402218308045872844614600253577579702828644029024407977896034543989163349222652612067792

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Fri Oct 22, 2004 4:34 pm

Well, it seems I can't quote the last post, so here is my reply:
For the last case it seems that your answer is incorrect.
I assume that the value is 10^1200 and obviously the correct answer is 10^600.
unless you lost some cypher while posting it seems likely that you don't get the entire input line and truncate it somewhere around 1000 chars...
although I don't think you need all that cyphers to get accepted

Ciao!!!

Claudio

User avatar
habibiamin
New poster
Posts: 8
Joined: Tue Oct 12, 2004 1:54 pm
Location: Iran-Tehran
Contact:

10023 Why WA??? but before AC

Post by habibiamin » Tue Nov 09, 2004 1:09 pm

I got AC before with this code... But now it cause WA ...!!!!
Can anybody tell me ... Why ??? :roll:
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>
int main(){
int j,i;
long double n,root;
cin>>j;
for(i=0;i<j;i++)
{
cin>>n;
root=sqrtl(n);
if(i<j-1)
cout<<(unsigned long long int)root<<"\n\n";
if(i==j-1)
cout<<(unsigned long long int)root<<"\n";
}
return 0;
}
[/cpp]

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Tue Nov 09, 2004 3:00 pm


ponny93
New poster
Posts: 1
Joined: Fri Nov 12, 2004 6:59 am

Post by ponny93 » Fri Nov 12, 2004 7:12 am

Try 10^1000... It must be 10^500.. :roll:

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sat Dec 04, 2004 10:24 am

Hello, I have passed the problem before rejudge.
But I got TLE all the time.
Could someone offer an proper algorithm to solve the problem?
Thx :D

Post Reply

Return to “Volume 100 (10000-10099)”