Tomato, Carrot,Beetroot

Abhinav Chandurkar 0
Viewed 37

Problem Statement

Your current stamina is 1 you have N days to increase the stamina, You are given 3 arrays Ti, Ci and Bi If you eat carrot on ith day your stamina will be multiplied by C[i], if you eat Tomato on ith day, your stamina will get multiplied by T[i] and if you eat Beetroot on ith day your stamina is multiplied by C[i] You need to eat exactly one of carrot, beetroot, and tomato each day. And you can not eat the same vegetable on consecutive days (i.e if you eat tomato on ith day you have to eat either beetroot or carrot on i+1th day) If you make poor choices and your stamina is minimum of what could have been obtained, what is your stamina

Input Format

The first line contains an integer X denoting the number of test cases

The first line of each test case contains an integer denoting N

The Next N lines contain 3 space-separated integers denoting T[i], C[i] and B[i] (1<=i<=N) respectively

Output Format

Print an integer denoting the minimum stamina you can obtain.

Constraints

1<=X<=1000

1<=N<=30

-4<=T[i],B[i],C[i]<=4

Sample Input

1

2

-1 4 -3

-1 1 2

Sample Output

-4

Explanation

Eat carrot on day 1 so your stamina becomes 1*4=4

Eat tomato on day 2 so your stamina becomes 4*-1 = -4

  • i is same for all the vegetable

pls help me solve this problem,This problem was given to me in my relevel exam ,I was not able to solve it.

algorithm
1 Answers

Seems fairly complicated (at least for me), a simple solution is brute force but it is not efficient.

this is a quick and dirty brute force solution, it could be polished a bit

food = { "T" : [...], "C" : [...], "B" : [...]}

def rec_solution(n):
   best_solution = float("-inf")
   def inner(n, stamina, prev_choice, i):
      nonlocal best_solution
      if n == 0:
         best_solution = max(best_solution, stamina)
         return
      match prev_choice:
         case "T":
            inner(n-1, stamina*food["C"][i], "C", i+1)
            inner(n-1, stamina*food["B"][i], "B", i+1)
         case "C":
            inner(n-1, stamina*food["T"][i], "T", i+1)
            inner(n-1, stamina*food["B"][i], "B", i+1)
         case "B":
            inner(n-1, stamina*food["C"][i], "C", i+1)
            inner(n-1, stamina*food["T"][i], "T", i+1)
         case "":
            inner(n-1, stamina*food["C"][i], "C", i+1)
            inner(n-1, stamina*food["T"][i], "T", i+1)
            inner(n-1, stamina*food["B"][i], "B", i+1) 
   inner(n, 1, "", 0)
   return best_solution

print(rec_solution(n))

if you confirm some details I'll try to find an efficient solution later

Axeltherabbit0
Related