OJ Board

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

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

yes its kinda funny..this code got AC
[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]

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.

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.

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

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]

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

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 and yor ouput is all right

Hope it Helps
Keep posting !!

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

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

I got AC before with this code... But now it cause WA ...!!!!
Can anybody tell me ... Why ???
[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]

See This Post:

http://online-judge.uva.es/board/viewtopic.php?t=6864

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

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