10190 - Divide, But Not Quite Conquer!

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Aug 13, 2005 11:05 am

Code: Select all

127  0
12 7
127 1
1 1
22 0
0 0
   0 1
0 9
125 5
30    3
80  2
81 3
    64 4
64 2
64 1
60 1
60 2
60 3
60 4
60 5
       1000000000 500
1999999999 9
387420489 9
387420489 8
387420489 10
312500000 50
312500000 51
312500000 49
0 0
0 1
1 0
1 1
22 1
15 1
1 88
88 1
1 1
12 1
1 12
100 100
100 50
256 16
256 4
333333 333
4096 16
1024 16

this is my output

Code: Select all

Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
125 25 5 1
Boring!
Boring!
81 27 9 3 1
64 16 4 1
64 32 16 8 4 2 1
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
387420489 43046721 4782969 531441 59049 6561 729 81 9 1
Boring!
Boring!
312500000 6250000 125000 2500 50 1
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
Boring!
100 1
Boring!
256 16 1
256 64 16 4 1
Boring!
4096 256 16 1
Boring!
a lot different than yours..

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

Post by 59557RC » Sat Aug 13, 2005 1:13 pm

the difference is only 4 the imput "64 1" . i changed my code this way n it gives same output as u. so why WA.
#include<stdio.h>
#include<math.h>

int main()
{
long n,m,i,j,kk,kkk,p;
double k,l;

while(scanf("%ld %ld",&n,&m)!=EOF){p=1;
if(n==1 || m==1 || n==0 || m==0) {printf("Boring\n");continue;}


for(i=1;;i++) {
k=pow(m,i);
if(k==n) {
for(j=i;j>=0;j--) {kk=pow(m,j);printf("%ld ",kk);}
printf("\n");break;
}
else if(k>n) {printf("Boring!\n");break;}
}

}
return 0;
}
aaa

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

&#12641;.&#12641;a

Post by helloneo » Sat Aug 13, 2005 2:22 pm

You missed a lot of '!'s..
it's "Boring!" not "Boring"

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

Post by 59557RC » Sat Aug 20, 2005 3:07 pm

ya thanx- i got AC
aaa

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

10190(divide but not conquer) divides my heart by wa

Post by Shuvra(CSE-BUET) » Fri Jan 13, 2006 10:26 am

first of all run this code segment Mr.OBSERVER.
while(1)
printf("Thanks to Observer\n") ;
..........................................................................................................
Now I get ac .But I am not 100% satisfied .Situations may not be easy all times(in other problems). How can I solve this problem by using log ?(I am so much surprised when I ran my code in my pc and gave your inputs and got correct result.
Last edited by Shuvra(CSE-BUET) on Fri Jan 13, 2006 6:54 pm, edited 1 time in total.
Life is a challenge.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jan 13, 2006 11:13 am

Hi,

I think people avoid using log in their solution because it is easy to get precision errors. And using log here doesn't improve the runtime much. You can try.

Back to your code, in my machine your program gives incorrect result for the following cases: (Well, floating point errors are often machine dependent)

Code: Select all

64 2
64 4
64 8
Why does such error exist? One of the reasons may be the inaccuracy in floating point computation:

Code: Select all

z=log(n)/log(m); 
if(ceil(z)==floor(z)) ... 
Note that log, ceil and floor all gives floating point results. Suppose log(n)/log(m) = 2, but due to rounding/truncation errors, we may get something like z = 2.0000000001, and ceil(z) might give you 3 instead of 2. The case of using floor is similar. It might also be not safe comparing two floating point numbers directly without an epsilon, but I don't know since I'm not very experienced in C++...

Hope it helps. Happy programming~ :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

marif
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Location: BANGLADESH
Contact:

10190

Post by marif » Sat Jun 24, 2006 12:32 pm

I am gettting T.L. E. in this problem. I don't know why? Limit of the input to the problem up to '2000000000'. But my computer support this limit. So, I am not understanding the cause. Please help?
here is the code:

#include<stdio.h>
int main()
{
unsigned long n,j,m;
while(scanf("%lu%lu",&n,&m)==2)
{
j=1;
while(j<n)
{j=j*m;}
if(j<n || j>n)
{
printf("Boring!\n");
}
else
{
while(n>=1)
{
printf("%lu ",n);
n=n/m;
}
printf("\n");
}
}
return 0;
}
:( :( :(

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sun Jun 25, 2006 12:26 am

Search the topics about the problem before you post. There are already LOT of posts about this topic... You can get your answers from there.
http://acm.uva.es/board/viewtopic.php?t=2474
You have to think about cases where m = 1 or m = 0.
Istiaque Ahmed [the LA-Z-BOy]

marif
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Location: BANGLADESH
Contact:

Post by marif » Tue Jun 27, 2006 7:36 am

Thank's LA-Z-BOy. Plz, don't think I'm a miser. As I have to browse at cyber cafe, I am late to answer u.

marif
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Location: BANGLADESH
Contact:

Re: PROBLEM::10190,I'm boring with TLE

Post by marif » Fri Aug 18, 2006 5:35 pm

removed after AC
:( :( :([/quote]

Mois
New poster
Posts: 1
Joined: Fri Sep 15, 2006 2:32 pm
Location: Brazil
Contact:

Please anyone, WA in my code...

Post by Mois » Mon Sep 18, 2006 12:36 am

I don't understand because my code is Wrong

Inputs/Output
0 0
Boring!
0 1
Boring!
1 0
Boring!
1 1
Boring!
2 1
Boring!
2 2
2 1
8 16
Boring!
64 2
64 32 16 8 4 2 1
64 4
64 16 4 1
64 8
64 8 1
64 16
Boring!
2000000000 1999999999
Boring!
my code
int main() {
long int dividendo, divisor, k;
int i;
double temp;
while (scanf("%li %li", &dividendo, &divisor)==2) {
if ((dividendo<=1)||(divisor<=1)||(divisor>dividendo)) {
printf("Boring!\n");
continue;
}
else {
if (dividendo % divisor != 0) {
printf("Boring!\n");
continue;
}
temp = log(dividendo)/log(divisor);
k = round(temp);
if (((temp-k)< -0.0001)||((temp-k)>0.0001)) {
printf("Boring!\n");
continue;
}
}

for (i = 0; i<k; i++) {
printf("%li ", dividendo);
dividendo = dividendo/divisor;
}
printf("%li\n", dividendo);
}
}

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by albet_januar » Wed Dec 27, 2006 6:45 pm

i got RTE.. plz hlp..

Code: Select all

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

long array[100000001];
int ind;

int rec(n, m)
{
 if(n==1) return 1;
 else
 {
  if(n%m==0)
  {
   array[ind++] = n/m;
   return rec(n/m, m);          
  } 
  else return 0;   
 }    
}

int main()
{
 long n , m, i;
 long count;
 
 while(scanf("%ld %ld", &n, &m)!=EOF)
 {
  array[0] = n;
  ind = 1;
  count = rec(n, m);                 

  if(count) for(i=0;i<ind;i++) printf("%ld ", array[i]);
  else printf("Boring!");
  
  printf("\n");
 }
     
 return 0;    
}

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Wed Dec 27, 2006 8:40 pm

when m=0 then....??
form kisui na ... class tai asol....
iF U hv d class u get the form....

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Mon Feb 12, 2007 7:07 am

please help me, why I got CE here :( I compiled with GCC it's ok for all tests on the board

Code: Select all

Aced
Last edited by FAQ on Mon Feb 12, 2007 10:42 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Feb 12, 2007 7:42 am

You forgot "#include <cstdio>"

Post Reply

Return to “Volume 101 (10100-10199)”