10110 - Light, more light

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

Moderator: Board moderators

Md. Mijanur Rahman
New poster
Posts: 9
Joined: Thu Nov 13, 2008 2:08 pm

Re: 10110 - Light, More Light

Post by Md. Mijanur Rahman » Sun Dec 19, 2010 10:59 am

why TLE???
#include<stdio.h>

int main()
{
long long int n,j,count;

while(scanf("%lld",&n)==1)
{ count=0;
if(n==0)break;
if(n%2==0)
for(j=1;j<=n;j++)
{
if(n%j==0) count++;
}
else for(j=1;j<=n;j+=2)
{
if(n%j==0) count++;
}

if(count%2!=0)printf("yes\n");
else printf("no\n");
}
return 0;
}

Md. Mijanur Rahman
New poster
Posts: 9
Joined: Thu Nov 13, 2008 2:08 pm

Re: 10110 - Light, More Light

Post by Md. Mijanur Rahman » Sun Dec 19, 2010 11:14 am

why WA plz help

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double n;
     
	while(scanf("%f",&n)==1)
	{ 
           if(floor(sqrt(n))==ceil(sqrt(n)))
	                                  printf("yes\n");
	  else printf("no\n");
	}
return 0;
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10110 - Light, More Light

Post by sohel » Mon Dec 20, 2010 2:41 am

Code: Select all

if(floor(sqrt(n))==ceil(sqrt(n)))
This condition will not always give you the correct result, since sqrt() of a square number will not give you the exact digits.
I mean, sqrt(25) != 5.00000000000000000000000.

shahedcsenu
New poster
Posts: 1
Joined: Tue Jul 12, 2011 11:29 pm
Location: bangladesh
Contact:

Re: 10110 - Light, More Light

Post by shahedcsenu » Wed Jul 13, 2011 12:47 am

i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??

sauro
New poster
Posts: 4
Joined: Mon Aug 30, 2010 11:26 pm
Location: BUET, bangladesh
Contact:

Re: 10110 - Light, More Light

Post by sauro » Wed Nov 09, 2011 9:53 pm

shahedcsenu wrote:i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??
check my earlier post.
all that we see or seem is but a dream within a dream

shuvrothpol1
New poster
Posts: 17
Joined: Wed Aug 15, 2012 12:37 pm

Re: 10110 - Light, More Light

Post by shuvrothpol1 » Thu Nov 15, 2012 2:50 am

runtime error...why??? (also tried with long long ) :(

#include <stdio.h>
#include <math.h>
#define N 70000

unsigned int status[N+1]={0},prime[N+1];
void list_prime();
unsigned int primefactor(unsigned int n);

int main ()
{
unsigned int n;
list_prime();
scanf ("%u",&n);
while (n!=0){
if (n%2==0)
printf ("yes\n");
else if (status[n]==0)
printf ("no\n");
else
{
n=primefactor(n)+1;
if (n%2==0)
printf ("no\n");
else
printf ("yes\n");
}
scanf ("%u",&n);
}
return 0;
}

void list_prime() {
unsigned int i, j, sqrtN;

sqrtN = sqrt( N );
for( i = 3; i <= sqrtN; i += 2 ) {
if( status == 0 ) {
for( j = i * i; j <= N; j += i + i )
status[j] = 1;
}
}
prime[0]=2;
status[1]=1;
j=1;
for( i = 3; i <= N; i += 2 ) {
if( status == 0 ){
prime[j++]=i;
}
}
}

unsigned int primefactor(unsigned int n)
{
unsigned int listSize=0,i,j;
unsigned int sqrtN =sqrt(n);
for(i = 0; prime <= sqrtN; i++ ) {
if( n % prime == 0 ) {
while( n % prime == 0 ) {
n /= prime;
listSize++;
}
}
}
if( n > 1 ) {
listSize++;
}
return listSize;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10110 - Light, More Light

Post by brianfry713 » Thu Nov 15, 2012 10:25 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Slow algorithm

Post by aybek » Sun Jan 26, 2014 2:30 pm

Hi!
Yesterday I have been solving 10110 problem and had wrote this algorithm,
the math model of the problem is very simple, solution is:
if the number of dividers of number is even then we have to print "no",
if odd we have to print "yes":
Here is solution of problem, how did I solve it

1. Get the number of dividers of number
|_1. Factorize number
|_2. Determine the number of dividers
2. If (number of dividers odd) print "yes"
else print "no"

Complexity of factorize algorithm is O(sqrt(n))
Complexity of div_num_of is not even O(n)
If input contains m number, the total complexity will be
O(mn)

Is it slow?

Code:

Code: Select all


#include <iostream>
#include <vector>
#include <cmath>
#include <map>

namespace nums {
	/* function will add factors of the numbers to the end of vector */
	/* TODO: optimizate for loop */
	template <class T>
	bool factorize(T n, std::vector<T> & v) {
		T i, c;
		for (c = n; (c%2) == 0; c /= 2) {
			v.push_back(2);
		}
		for (i = 3; i <= static_cast<T>(sqrt(c)+1.0); ) {
			if ((c % i) == 0) {
				v.push_back(i);
				c /= i;
			} else { i += 2; }
		}
		if (c > 1 && (c != n)) { v.push_back(c); }
		return true;
	}

	/* Returns number of dividers of n */
	template <class T>
	size_t div_num_of(T n) {
		if (n == 0) { return 0; }
		if (n == 1) { return 1; }

		std::vector<T> v, el;
		std::map<T, size_t> d;

		factorize(n, v);
		for (const T & e : v) {
			if (d.find(e) != d.end()) {
				++d[e];
			} else {
				d[e] = 1;
				el.push_back(e);
			}
		}

		size_t dn = 0;
		for (const T & e : el) {
			if (dn == 0) dn = 1;
				dn *= (d[e]+1);
		}
		return dn;
	}
}

int main() {
	using namespace std;
	using namespace nums;

	uint32_t n;
	for (;;) {
		cin >> n;
		if (n == 0) break;

		if (div_num_of(n)%2) {
			cout << "yes\n";
		} else {
			cout << "no\n";
		}
	}

	return 0;
}


aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: Slow algorithm

Post by aybek » Tue Jan 28, 2014 7:13 pm

problem is not in problem. I need help to count complexity of algorithms :D

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Slow algorithm

Post by brianfry713 » Tue Jan 28, 2014 9:13 pm

You can solve for each input value in constant time using sqrt().
Check input and AC output for thousands of problems on uDebug!

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

Re: 10110 - Light, More Light

Post by rafid059 » Fri Jul 18, 2014 11:59 am

Can some help me?? im getting a runtime error everytime.

Code: Select all

Accepted   :D
Last edited by rafid059 on Mon Jul 21, 2014 11:40 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10110 - Light, More Light

Post by lighted » Fri Jul 18, 2014 12:26 pm

Change line

Code: Select all

int num = s.nextInt();
It must be

Code: Select all

long num = s.nextLong();
Don't forget to remove your code after getting accepted. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

rafid059
New poster
Posts: 13
Joined: Thu Feb 27, 2014 6:35 pm

Re: 10110 - Light, More Light

Post by rafid059 » Mon Jul 21, 2014 11:41 pm

thanks a lot, lighted! :D

xrenon
New poster
Posts: 10
Joined: Tue Sep 23, 2014 4:11 am

Re: 10110 - Light, more light

Post by xrenon » Thu Oct 30, 2014 12:45 pm

deleted....thnx
Last edited by xrenon on Sun Nov 02, 2014 4:57 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10110 - Light, more light

Post by brianfry713 » Thu Oct 30, 2014 9:23 pm

Try input:

Code: Select all

4294967295
0
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest