Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class t1 {
- public static void print_path(int n, int [] hod) {
- if(hod[n] == 0)
- return;
- else {
- print_path(hod[n], hod);
- if(n % hod[n] == 0)
- System.out.print(n / hod[n]);
- else
- System.out.print(1);
- }
- }
- public static void main(String[] args){
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int [] calculate = new int [n + 1];
- calculate[1] = 0;
- int [] hod = new int [n+1];
- if(n == 1)
- System.out.println("");
- else {
- for (int i = 2; i < n+1; i++) {
- if(i % 2 == 0 && i % 3 == 0) {
- calculate[i] = Math.min(Math.min(calculate[i-1],calculate[i/2]),calculate[i/3]);
- if(calculate[i-1] <= calculate[i/2]) {
- hod[i] = i-1;
- if(hod[i] > calculate[i/3])
- hod[i] = i/3;
- }else {
- hod[i] = i/2;
- if(hod[i] > calculate[i/3])
- hod[i] = i/3;
- }
- }else {
- if(i % 2 == 0 && i % 3 != 0) {
- calculate[i] = Math.min(calculate[i-1],calculate[i/2]);
- if(calculate[i-1] <= calculate[i/2])
- hod[i] = i-1;
- else
- hod[i] = i/2;
- }else {
- if(i % 2 != 0 && i % 3 == 0) {
- calculate[i] = Math.min(calculate[i-1],calculate[i/3]);
- if(calculate[i-1] <= calculate[i/3])
- hod[i] = i-1;
- else
- hod[i] = i/3;
- }else {
- calculate[i] = calculate[i-1];
- hod[i] = i-1;
- }
- }
- }
- calculate[i]++;
- }
- print_path(n, hod);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement