## 11730 - Number Transformation

Moderator: Board moderators

neilor
New poster
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

### 11730 - Number Transformation

Please, somebody can help me with my test cases? I can´t find my error.

11730.in

Code: Select all

``````6 12
6 13
10 24
10 25
94 141
39 52
39 65
39 78
20 26
20 35
20 25
6 6
10 25
22 66
21 30
33 470
12 260
100 1000
90 1000
94 141
9 12
12 9
4 6
4 12
0 0``````
11730.out

Code: Select all

``````Case 1: 2
Case 2: -1
Case 3: 7
Case 4: 3
Case 5: 1
Case 6: 1
Case 7: 2
Case 8: 3
Case 9: 3
Case 10: 3
Case 11: 1
Case 12: 0
Case 13: 3
Case 14: 4
Case 15: 3
Case 16: -1
Case 17: 124
Case 18: 180
Case 19: 182
Case 20: 1
Case 21: 1
Case 22: -1
Case 23: 1
Case 24: 4``````
Thanks
Last edited by neilor on Mon Dec 21, 2009 5:57 pm, edited 1 time in total.

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

### Re: 11730 - Number Transformation

my ac program gives:

Code: Select all

``````Case 1: 2
Case 2: -1
Case 3: 4
Case 4: 3
Case 5: 1
Case 6: 1
Case 7: 2
Case 8: 3
Case 9: 3
Case 10: 3
Case 11: 1
Case 12: 0
Case 13: 3
Case 14: 4
Case 15: 2
Case 16: 13
Case 17: 15
Case 18: 16
Case 19: 16
Case 20: 1
Case 21: 1
Case 22: -1
Case 23: 1
Case 24: 3
``````
what is the method you used???

neilor
New poster
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

### Re: 11730 - Number Transformation

Thanks Asif. I was wrong in my interpretation:
from 4 to 12 I was doing:
4 -> 6 -> 8 -> 10 -> 12 = 4 operations.
And the correct is
4 -> 6 -> 9 ->12 = 3 operations
because after the number are transformed to 6 I can use the prime factor 3 to add.

To solve, I used 2 approach:
path before founded with less steps (for example
12(with 2) and 12(with 3). I try always the right side with
bigger jumps and less steps

Code: Select all

``````               6
(2)/     \ (3)
8       9
(2)|        \ (3)
10         12
/       \
14          15
(2)/ |(7)     /(3)  \(5)
/   |       /       \
16   21      18        20
[18]discard (3)/ \(7)   \(3)   /(2) \(5)
24   28    21    22     25
5 steps+++    \(7)   \(2)  X
28      24
6 steps +++  (2)/ \(3)
26     27
\(2)   x
28
+++ 8 steps
``````
My time with this aproach was 0.088.
2: Using a array[100][1000] and pre-calculating each value.
The time with this aproach was 0.012.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 11730 - Number Transformation

Input:

Code: Select all

``````7 14
11 33
2 2
3 4
4 3
0 0
``````
AC output:

Code: Select all

``````Case 1: -1
Case 2: -1
Case 3: 0
Case 4: -1
Case 5: -1
``````
Mak
Help me PLZ!!

FelixP
New poster
Posts: 3
Joined: Sat Aug 20, 2011 5:48 pm

### Re: 11730 - Number Transformation

hi, i can't understand why 11 to 33 is -1?

can't you just do this ? 11 -> 22 ->> 33

drubo
New poster
Posts: 4
Joined: Thu Jul 21, 2011 12:26 pm

### Problem with 11730 - Number Transformation >> PLZ help

my answer for big number like (90 1000) is not working .....
what is the fault......
here is my code............
//////////////////////////////////////

Code: Select all

``````#include<stdio.h>
#include<math.h>
#include<set>
using namespace std;
set<int>s;
int prime[500]={0};
int a[1005];
int p,q;
int factor(int x,int count)
{
if(a[x]==0)
return 0;
a[x]=0;
count++;
if(x==q)
{
s.insert(count);
return 0;
}
else if(x>q)
return 0;
int fact[50];
int i,j,y,t=0;
j=x/2;
y=x;
for(i=0;prime[i]<=j;i++)
{
if(y%prime[i]==0)
fact[t++]=prime[i];
}
for(i=t-1;i>=0;i--)
factor(x+fact[i],count);
return 0;
}
int main()
{
//freopen("E:/Input.txt","r",stdin);
int i,j,k=1,l,x=0,y,t,count;
int fact[50];
prime[x++]=2;
for(i=3;i<510;i+=2)
{
j=sqrt(i);
for(k=2;k<=j;k++)
{
if(i%k==0)
break;
}
if(k>j)
prime[x++]=i;
}
k=1;
while(scanf("%d %d",&p,&q)&&(p+q))
{
if(p==q)
{
printf("Case %d: 0\n",k);
k++;
continue;
}
for(i=1;i<=q;i++)
a[i]=i;
count=0;
t=0;
j=p/2;
for(i=0;prime[i]<=j;i++)
{
if(p%prime[i]==0)
fact[t++]=prime[i];
}
for(i=t-1;i>=0;i--)
factor(p+fact[i],0);
set<int>::iterator it;
it=s.begin();
if(s.size()==0)
printf("Case %d: -1\n",k);
else
printf("Case %d: %d\n",k,*it);
k++;
s.clear();
}
return 0;
}``````

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

### Re: 11730 - Number Transformation

FelixP wrote:hi, i can't understand why 11 to 33 is -1?

can't you just do this ? 11 -> 22 ->> 33
Read the problem statement. You can't add 1 or A, only the other prime factors of A. So since 11 is prime it can't be transformed.
Check input and AC output for thousands of problems on uDebug!

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

### Re: Problem with 11730 - Number Transformation >> PLZ help

drubo wrote:my answer for big number like (90 1000) is not working .....
what is the fault......
A Transformation_number
90 0
93 1
94 2
141 3
188 4
235 5
282 6
329 7
376 8
378 9
385 10
396 11
398 12
597 13
796 14
995 15
1000 16

For input "90 1000", output is "Case 1: 16".
Check input and AC output for thousands of problems on uDebug!