Skip to content

Latest commit

 

History

History
346 lines (300 loc) · 9.83 KB

README_EN.md

File metadata and controls

346 lines (300 loc) · 9.83 KB
comments difficulty edit_url rating source tags
true
Medium
1793
Biweekly Contest 145 Q2
Bit Manipulation
Depth-First Search
Array
Dynamic Programming
Backtracking
Bitmask

3376. Minimum Time to Break Locks I

中文文档

Description

Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the ith lock.

To break a lock, Bob uses a sword with the following characteristics:

  • The initial energy of the sword is 0.
  • The initial factor x by which the energy of the sword increases is 1.
  • Every minute, the energy of the sword increases by the current factor x.
  • To break the ith lock, the energy of the sword must reach at least strength[i].
  • After breaking a lock, the energy of the sword resets to 0, and the factor x increases by a given value k.

Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.

Return the minimum time required for Bob to break all n locks.

 

Example 1:

Input: strength = [3,4,1], k = 1

Output: 4

Explanation:

Time Energy x Action Updated x
0 0 1 Nothing 1
1 1 1 Break 3rd Lock 2
2 2 2 Nothing 2
3 4 2 Break 2nd Lock 3
4 3 3 Break 1st Lock 3

The locks cannot be broken in less than 4 minutes; thus, the answer is 4.

Example 2:

Input: strength = [2,5,4], k = 2

Output: 5

Explanation:

Time Energy x Action Updated x
0 0 1 Nothing 1
1 1 1 Nothing 1
2 2 1 Break 1st Lock 3
3 3 3 Nothing 3
4 6 3 Break 2nd Lock 5
5 5 5 Break 3rd Lock 7

The locks cannot be broken in less than 5 minutes; thus, the answer is 5.

 

Constraints:

  • n == strength.length
  • 1 <= n <= 8
  • 1 <= K <= 10
  • 1 <= strength[i] <= 106

Solutions

Solution 1

Python3

class Solution:
    def findMinimumTime(self, strength: List[int], K: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == (1 << len(strength)) - 1:
                return 0
            cnt = i.bit_count()
            x = 1 + cnt * K
            ans = inf
            for j, s in enumerate(strength):
                if i >> j & 1 ^ 1:
                    ans = min(ans, dfs(i | 1 << j) + (s + x - 1) // x)
            return ans

        return dfs(0)

Java

class Solution {
    private List<Integer> strength;
    private Integer[] f;
    private int k;
    private int n;

    public int findMinimumTime(List<Integer> strength, int K) {
        n = strength.size();
        f = new Integer[1 << n];
        k = K;
        this.strength = strength;
        return dfs(0);
    }

    private int dfs(int i) {
        if (i == (1 << n) - 1) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        int cnt = Integer.bitCount(i);
        int x = 1 + cnt * k;
        f[i] = 1 << 30;
        for (int j = 0; j < n; ++j) {
            if ((i >> j & 1) == 0) {
                f[i] = Math.min(f[i], dfs(i | 1 << j) + (strength.get(j) + x - 1) / x);
            }
        }
        return f[i];
    }
}

C++

class Solution {
public:
    int findMinimumTime(vector<int>& strength, int K) {
        int n = strength.size();
        int f[1 << n];
        memset(f, -1, sizeof(f));
        int k = K;
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i == (1 << n) - 1) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            int cnt = __builtin_popcount(i);
            int x = 1 + k * cnt;
            f[i] = INT_MAX;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1 ^ 1) {
                    f[i] = min(f[i], dfs(i | 1 << j) + (strength[j] + x - 1) / x);
                }
            }
            return f[i];
        };
        return dfs(0);
    }
};

Go

func findMinimumTime(strength []int, K int) int {
	n := len(strength)
	f := make([]int, 1<<n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i == 1<<n-1 {
			return 0
		}
		if f[i] != -1 {
			return f[i]
		}
		x := 1 + K*bits.OnesCount(uint(i))
		f[i] = 1 << 30
		for j, s := range strength {
			if i>>j&1 == 0 {
				f[i] = min(f[i], dfs(i|1<<j)+(s+x-1)/x)
			}
		}
		return f[i]
	}
	return dfs(0)
}

TypeScript

function findMinimumTime(strength: number[], K: number): number {
    const n = strength.length;
    const f: number[] = Array(1 << n).fill(-1);
    const dfs = (i: number): number => {
        if (i === (1 << n) - 1) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        f[i] = Infinity;
        const x = 1 + K * bitCount(i);
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) == 0) {
                f[i] = Math.min(f[i], dfs(i | (1 << j)) + Math.ceil(strength[j] / x));
            }
        }
        return f[i];
    };
    return dfs(0);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}