coinswitch

Problem Statement

Problem A restaurant chain owns N restaurants, numbered with unique IDs from 0 to N-1 . The head office is restaurant 0 . The chain keeps the restaurants in a hierarchy held together by exactly N-1 connections: every restaurant is connected below at most two others, one on its left and one on its right . The hierarchy is therefore a binary tree rooted at restaurant 0 , and there is exactly one path between any two restaurants. For every restaurant the chain records restCust[i] , its number of permanent customers. To choose a host for the annual festival, the chain generates a number M and lays the restaurants out in a sequence using one rule, applied to every restaurant: for a restaurant with ID X , first the restaurant connected to the left of X is added, then X itself is added, and then the restaurant connected to the right of X is added. The rule applies recursively: the whole group hanging below the left connection is laid out before X , and the whole group hanging below the right