Digits Forest CodeChef Solution

Problem -Digits Forest CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Digits Forest CodeChef Solution in C++14


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int t, n, m, ans, dis[maxn + 10][10000], a[maxn + 10];
vector<int> g[maxn + 10];

struct hnode {
	int x, y, d;
	bool operator < (const hnode &t) const {
		return d > t.d;
	}
};

priority_queue<hnode> hp;

int calc(int stat) {
	if (!(stat >> (a[1] - 1) & 1)) return 2e9;
	if (!(stat >> (a[n] - 1) & 1)) return 2e9;
	int mod = 1;
	for (int i = 0; i < 7; ++i)
		if (stat >> i & 1) mod = mod / __gcd(mod, i + 1) * (i + 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < mod; ++j) dis[i][j] = 2e9;
	dis[1][a[1] % mod] = a[1];
	while (!hp.empty()) hp.pop();
	hp.push((hnode){1, a[1] % mod, a[1]});
	while (!hp.empty()) {
		hnode p = hp.top(); hp.pop();
		if (p.d > dis[p.x][p.y]) continue;
		for (int i = 0; i < (int)g[p.x].size(); ++i) {
			int e = g[p.x][i];
			if (stat >> (a[e] - 1) & 1) {
				int w = (p.y * 10 + a[e]) % mod;
				if (p.d + a[e] < dis[e][w]) {
					dis[e][w] = p.d + a[e];
					if (e == n && w == 0) return dis[e][w];
					hp.push((hnode){e, w, dis[e][w]});
				}
			}
		}
	}
	return dis[n][0];
}

int main() {
	for (;;) {
		scanf("%d", &n);
		if (!n) break;
		for (int i = 1; i <= n; ++i) g[i].clear();
		ans = 2e9;
		for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)  {
				int x; scanf("%d", &x);
				if (x) g[i].push_back(j);
			}
		for (int i = 0; i < 1 << 7; ++i)
			if (i & 1) ans = min(ans, calc(i));
		printf("%d\n", ans <= 1e9 ? ans : -1);
	}
}

Digits Forest CodeChef Solution in JAVA

import static java.util.Arrays.*;
     
    import java.io.*;
    import java.util.*;
     
    class DigitsForest {
     
    final int MOD = 1000000007;
    final double eps = 1e-12;
    final int [] F = { 0, 0, 1, 2, 5, 8, 3, 16 };
    final int [] R = { -1, 21, 84, 21, 84, 105, 84, 21 };
    final int INF = (int)1e9;
    public DigitsForest () throws IOException {
    next: for (;;) {
    int N = sc.nextInt();
    if (N == 0) exit();
    final int [] D = sc.nextInts();
    int [][] G = new int [N][];
    for (int i = 0; i < N; ++i)
    G[i] = sc.nextInts();
    if (N == 1) {
    print (D[0]);
    continue next;
    }
     
    if (D[N-1] %2 != 0)
    for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
    if (D[i] % 2 == 0)
    G[i][j] = 0;
    if (D[N-1] != 5)
    for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
    if (D[i] == 5)
    G[i][j] = 0;
    int M = R[D[N-1]];
    int [][][] S = new int[N][32][M]; /* Distance */
    for (int [][] s2 : S) for (int [] s : s2) fill(s, INF);
    boolean [][][] V = new boolean [N][32][M];
    Queue<int []> Q = new PriorityQueue<int []>(10, new Comparator<int[]>() {
    public int compare(int[] A, int[] B) {
    return A[3] - B[3];
    }
    });
    int [] start = { 0, F[D[0]] | F[D[N-1]], D[0], D[0] };
    S[start[0]][start[1]][start[2]] = D[0]; Q.add(start);
    while (!Q.isEmpty()) {
    int [] Z = Q.poll();
    int n = Z[0], f = Z[1], r = Z[2], d = Z[3];
    if (V[n][f][r])
    continue;
    V[n][f][r] = true;
     
    if (n == N-1) {
    boolean good = true;
    for (int i = 2; i <= 7; ++i)
    if ((f & F[i]) == F[i] && r % i != 0)
    good = false;
    if (good) {
    print(S[n][f][r]);
    continue next;
    }
    }
    for (int p = 0; p < N; ++p)
    if (G[n][p] == 1) {
    int g = (f | F[D[p]]), s = (10 * r + D[p]) % M, e = d + D[p];
    if (!V[p][g][s]) {
    if (e < S[p][g][s]) {
    S[p][g][s] = e;
    Q.add(new int [] { p, g, s, e });
    }
    }
    }
    }
    print(-1);
    }
    }
     
    ////////////////////////////////////////////////////////////////////////////////////
    static MyScanner sc;
    static PrintWriter pw = new PrintWriter(System.out);
    static void print (Object... a) {
    StringBuffer b = new StringBuffer();
    for (Object o : a)
    b.append(" ").append(o);
    pw.println(b.toString().trim());
    }
     
    static void exit (Object... a) {
    print(a);
    exit();
    }
     
    static void exit () {
    pw.flush();
    System.err.println("------------------");
    System.err.println("Time: " + (millis() - t) / 1000.0);
    System.exit(0);
    }
    static class MyScanner {
    String next() throws IOException {
    newLine();
    return line[index++];
    }
    char [] nextChars() throws IOException {
    return next().toCharArray();
    }
    double nextDouble() throws IOException {
    return Double.parseDouble(next());
    }
    int nextInt() throws IOException {
    return Integer.parseInt(next());
    }
    long nextLong() throws IOException {
    return Long.parseLong(next());
    }
    String nextLine() throws IOException {
    line = null;
    return r.readLine();
    }
    String [] nextStrings() throws IOException {
    line = null;
    return r.readLine().split(" ");
    }
    int [] nextInts() throws IOException {
    String [] L = nextStrings();
    int [] res = new int [L.length];
    for (int i = 0; i < L.length; ++i)
    res[i] = Integer.parseInt(L[i]);
    return res;
    }
    long [] nextLongs() throws IOException {
    String [] L = nextStrings();
    long [] res = new long [L.length];
    for (int i = 0; i < L.length; ++i)
    res[i] = Long.parseLong(L[i]);
    return res;
    }
     
    boolean eol() {
    return index == line.length;
    }
     
    //////////////////////////////////////////////
    private final BufferedReader r;
     
    MyScanner () throws IOException {
    this(new BufferedReader(new InputStreamReader(System.in)));
    }
    MyScanner(BufferedReader r) throws IOException {
    this.r = r;
    }
    private String [] line;
    private int index;
     
    private void newLine() throws IOException {
    if (line == null || eol()) {
    line = r.readLine().split(" ");
    index = 0;
    }
    }
    }
    public static void main(String[] args) throws IOException {
    run();
    exit();
    }
     
    static void start() {
    t = millis();
    }
     
    static void run () throws IOException {
    sc = new MyScanner ();
    new DigitsForest();
    }
     
    static long t;
    static long millis() {
    return System.currentTimeMillis();
    }
    } 
Digits Forest CodeChef Solution Review:

In our experience, we suggest you solve this Digits Forest CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Digits Forest CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Digits Forest CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *