Advertisement
vov44k

Untitled

Sep 24th, 2022
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.40 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class t1 {
  4.    
  5.     public static void print_path(int n, int [] hod) {
  6.         if(hod[n] == 0)
  7.             return;
  8.         else {
  9.             print_path(hod[n], hod);
  10.             if(n % hod[n] == 0)
  11.                  System.out.print(n / hod[n]);
  12.             else
  13.                 System.out.print(1);
  14.         }
  15.     }
  16.    
  17.     public static void main(String[] args){
  18.     Scanner in = new Scanner(System.in);
  19.     int n = in.nextInt();
  20.     int [] calculate = new int [n + 1];
  21.     calculate[1] = 0;
  22.     int [] hod = new int [n+1];
  23.     if(n == 1)
  24.         System.out.println("");
  25.     else {
  26.     for (int i = 2; i < n+1; i++) {
  27.         if(i % 2 == 0 && i % 3 == 0) {
  28.             calculate[i] = Math.min(Math.min(calculate[i-1],calculate[i/2]),calculate[i/3]);
  29.             if(calculate[i-1] <= calculate[i/2]) {
  30.                 hod[i] = i-1;
  31.                 if(hod[i] > calculate[i/3])
  32.                     hod[i] = i/3;
  33.             }else {
  34.                 hod[i] = i/2;
  35.                 if(hod[i] > calculate[i/3])
  36.                     hod[i] = i/3;
  37.             }
  38.         }else {
  39.             if(i % 2 == 0 && i % 3 != 0) {
  40.                 calculate[i] = Math.min(calculate[i-1],calculate[i/2]);
  41.                 if(calculate[i-1] <= calculate[i/2])
  42.                     hod[i] = i-1;
  43.                 else
  44.                     hod[i] = i/2;
  45.             }else {
  46.                 if(i % 2 != 0 && i % 3 == 0) {
  47.                     calculate[i] = Math.min(calculate[i-1],calculate[i/3]);
  48.                     if(calculate[i-1] <= calculate[i/3])
  49.                         hod[i] = i-1;
  50.                     else
  51.                         hod[i] = i/3;
  52.                 }else {
  53.                     calculate[i] = calculate[i-1];
  54.                     hod[i] = i-1;
  55.                 }
  56.             }
  57.         }
  58.         calculate[i]++;
  59.     }
  60.    
  61.     print_path(n, hod);
  62.    
  63.     }
  64.    
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement