11730 - Number Transformation

[neilor]

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

[asif_khan_ak_07]

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]

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:
1) recursive backtracking discarding
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
  [12]discard  (2)/     \ (3)
                 /       \
               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)]

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

[FelixP]

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

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

[drubo]

my answer for big number like (90 1000) is not working .....
what is the fault......
please someone explain answer for case >> 90 1000
my answer is >> 44
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]

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.

[brianfry713]

my answer for big number like (90 1000) is not working .....
what is the fault......
please someone explain answer for case >> 90 1000
my answer is >> 44

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