11260 - Odd Root Sum

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

Moderator: Board moderators

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

OK, I got it. But I don't think I have cases like this one.

I mean - I never get some negative value during my
calculations, at least if I am not doing something wrong.

In math (-1) % 3 = 2. In programming languages it equals -1.

In math the residues modulo N are always
considered members of the set {0, 1, ..., N-1}.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

I finally got accepted. I had a bug in my code which
was only showing up for numbers of the form
(2*N) ^ 2 i.e. for squares of even numbers.

For example for 64 my program was giving answer : 164
which is clearly wrong. The right answer is 156.

For 16 my answer was wrong - it was answering : 22,
the right answer is 18.

After fixing it I got ACC.

So it seems my long sequence of WA verdicts was not due to
some tricky calculations or number-related issues but due to
a very very stupid mistake in my code!

Thanks to Piklu_sust and Suhendry.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic »

to avoid negetive answer,u can add the modulo value(100000000) to the ans.
& also check the sqrt function. For larger input value(around 10^16 & above), sqrt doesnt work perfectly.
khobaib

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

prolem with 11260 (WA)

Post by deena sultana »

Hi,
my program works fine upto n=1000000000, but greater than this its getting overflow, my pc is not able to handle 64bit integer, so, i can not fix up where the overflow is occurring. i've used long long as my programs i/p.

After submission i got WA :(
now, what can i do? plzzz help :cry:

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Normal sqrt will not work for this problem (If you used it!!!). I had to use binary search to find the sqrt of a 64 bit int.

P.S. If you have problems with compiler then you should try other compilers like ms VC or gcc. I use VC, and I think its good. It would hardly take some time to switch from one to another.
Ami ekhono shopno dekhi...
HomePage

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana »

THANKS jan.
yes, the sqrt is doing something wrong :(
i will do binary search and also i will switch to VC :-)

thanks again.

mohammad
New poster
Posts: 2
Joined: Wed Jul 18, 2007 2:49 pm

Post by mohammad »

i got WA on this problem
here is my code :

Code: Select all

#include <iostream>
#include <math.h>

using namespace std;

#define m 100000000LL

int main()
{
	unsigned long long n, nn, s, ss, r;
	while (cin >> n, n)
	{
		n -= (n + 1) & 1;
		s = (unsigned long long) floor (sqrt ((long long double) n));
		nn = (s * s) + ((s + 1) & 1);
		r = ((((s * (s - 1)) >> 1) % m) * (2 * s - 1) / 3) % m;
		ss = s >> 1;
		r = (r + (ss * ss) % m) % m;
		r = (r + (s + s * (((n - nn) >> 1) % m)) % m) % m;
		printf("%llu\n", r);
	}
}
please help me :roll:

M Noaman Akram
New poster
Posts: 1
Joined: Sat Jul 16, 2011 5:11 pm

Re: 11260 - Odd Root Sum

Post by M Noaman Akram »

Code: Select all

[JAVA]
 import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
       int i=0;
         
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str;
Double a[]=new Double[30000];
int io=0;
while(!(str=br.readLine()).equals("0"))
   {   Double sum=0.0;
    Double go=Double.parseDouble(str);

    for(Double p=1.0;p<=go;p++)
    {
       if(p%2!=0)
       {
            sum=Math.floor(Math.sqrt(p))+sum;
       }
    
    } a[io]=sum%100000000;
 
     io++;
         }
for(int yu=0;yu<io;yu++)
{
    System.out.println(a[yu]);
}

    }}

i am getting TLE  :oops: 
plz help me.
what i should change in the code istead of using or loop which goes to exponational :(

Post Reply

Return to “Volume 112 (11200-11299)”