Page 5 of 6
Re: 10110 - Light, More Light
Posted: Sun Dec 19, 2010 10:59 am
by Md. Mijanur Rahman
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;
}
Re: 10110 - Light, More Light
Posted: Sun Dec 19, 2010 11:14 am
by Md. Mijanur Rahman
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;
}
Re: 10110 - Light, More Light
Posted: Mon Dec 20, 2010 2:41 am
by sohel
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.
Re: 10110 - Light, More Light
Posted: Wed Jul 13, 2011 12:47 am
by shahedcsenu
i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??
Re: 10110 - Light, More Light
Posted: Wed Nov 09, 2011 9:53 pm
by sauro
shahedcsenu wrote:i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??
check my earlier post.
Re: 10110 - Light, More Light
Posted: Thu Nov 15, 2012 2:50 am
by shuvrothpol1
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;
}
Re: 10110 - Light, More Light
Posted: Thu Nov 15, 2012 10:25 pm
by brianfry713
It looks like you figured it out.
Slow algorithm
Posted: Sun Jan 26, 2014 2:30 pm
by aybek
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;
}
Re: Slow algorithm
Posted: Tue Jan 28, 2014 7:13 pm
by aybek
problem is not in problem. I need help to count complexity of algorithms
Re: Slow algorithm
Posted: Tue Jan 28, 2014 9:13 pm
by brianfry713
You can solve for each input value in constant time using sqrt().
Re: 10110 - Light, More Light
Posted: Fri Jul 18, 2014 11:59 am
by rafid059
Can some help me?? im getting a runtime error everytime.
Re: 10110 - Light, More Light
Posted: Fri Jul 18, 2014 12:26 pm
by lighted
Change line
It must be
Don't forget to remove your code after getting accepted.
Re: 10110 - Light, More Light
Posted: Mon Jul 21, 2014 11:41 pm
by rafid059
thanks a lot, lighted!
Re: 10110 - Light, more light
Posted: Thu Oct 30, 2014 12:45 pm
by xrenon
deleted....thnx
Re: 10110 - Light, more light
Posted: Thu Oct 30, 2014 9:23 pm
by brianfry713