PYTHON3

Captain Pi-rate has hidden his treasures among an archipelago of n islands. Instead of drawing a map to his treasure islands though, he has left a series of clues for himself on several islands, only some of which actually contain any treasure. Each clue contains a number and up to two references to other islands. He has a secret number, s , which serves as the key to finding the treasures in the islands. Starting with the first clue, whenever the sequence of numbers on a chain of clues sums to a multiple of s, then that island contains treasure.

For example, the diagram shows where the treasures would be located if s = 7 and the clues made references as shown. The first clue on island A has the number 2 and references islands B and C as follow-up islands. Since the clue on island B has the value 5 and 2+5 is divisible by 7, that means that there is treasure on island B. Given the starting island and the secret s, find the sequence of islands that has the maximum number of treasures and report the number of treasures on that path. In this problem, a tree will be constructed from the input for you, but in order for that given code to work, you must first complete the findMaxTreasure function that was started, but left incomplete using the functions of the ADT provided for you.

Input Format

The first line contains two integers n and s, separated by a space. The next n lines contains 4 integers: i, v, j, k to indicate that the clue on island i has the number v and makes reference to islands numbered j and k. If either j or k is 0, then no reference in that position was made by that clue.

Constraints 1 n 5 2 s 4 1 v 4

Output Format A single integer denoting the maximum number of treasures on any path.

Sample Input 0

10 7 3 3 0 0 6 6 0 0 7 1 0 0 5 2 6 7 9 7 0 0 8 3 0 9 4 4 5 8 2 5 3 4 10 8 0 0 1 2 2 10 

Sample Output 0

3

Explanation 0

This tree is the one shown in the diagram of the problem description. The secret is 7, so we are looking for sub-sequences whose sum is a multiple of 7. Starting at island A, our sequence begins with 2. Going to C yields a sequence of 2, 8 and since 2+8=10 is not a multiple of 7, it yields no treasures. Going to B, however, yields 2, 5; and since 2+5=7 is a multiple of 7, there is treasure at B. Sequence ABD is 2, 5, 3 which sums to 10, so no treasure is at D. Proceeding in this way, we see that only the shaded islands will have treasure on them. For example, the sequence ABEFI produces sequence 2,5,4,2,1 whose sum is 14, so there is treasure at island I. The sequence ABEGJ has treasure at islands B, G and J; that is 3 treasure chests in total. All the possible sequences with the number of treasure chests are:

Path	Treasure count
ABD	1
ABEFH	1
ABEFI	2
ABEGJ	3
AC	0

Since we want the maximum number of treasures on any path, we return 3 as the answer.

PYTHON3 Code:

import sys

def cons(x, y): return [x, y]

def car(p): return p[0]

def cdr(p): return p[1]

nil = []

def makeBinTree(root, left, right): return cons(left, cons(root, right))

emptyTree = nil

# Enter your code here. Return your answer do not print it

def isEmpty(tree): return tree is emptyTree

def root(tree): return car(cdr(tree))

def left(tree): return car(tree)

def right(tree): return cdr(tree)

def findMaxTreasure(tree, secret, ptotal): # Complete this function

if __name__=="__main__": n, s = input().strip().split(' ') n, s = int(n), int(s) nodes = [None] * (n+1) nodes[0] = emptyTree for i in range(n): i, v, j, k = list(map(int, input().strip().split(' '))) nodes[i] = makeBinTree(v, nodes[j], nodes[k]) r = findMaxTreasure(nodes[1], s, 0) print(r)

A 2 B 5 8 D 3 E 4 F 2 3 H 6 1 1 7