## 10110 - Light, more light

Moderator: Board moderators

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

### Re: 10110 - Light, More Light

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

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;
}``````

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

### Re: 10110 - Light, More Light

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
Contact:

### Re: 10110 - Light, More Light

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
Contact:

### Re: 10110 - Light, More Light

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

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=2;
status=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

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

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

problem is not in problem. I need help to count complexity of algorithms brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Slow algorithm

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

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: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10110 - Light, More Light

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

thanks a lot, lighted! xrenon
New poster
Posts: 10
Joined: Tue Sep 23, 2014 4:11 am

### Re: 10110 - Light, more light

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

Try input:

Code: Select all

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