超重剪枝的调用数

难度：T2

【知识点：搜索与状态】

前置知识：DFS、BFS、数组队列、已学剪枝。

题目描述

按输入顺序对n件正重量物品执行选/不选递归。状态(i,s,c)表示前i件已决定、已选重量s、件数c；初始(0,0,0)。每次进入函数先将calls加1，然后若s>W立即返回。若i==n也返回；否则先调用(i+1,s,c)，再调用(i+1,s+w[i],c+1)，这里重量下标从0开始。除此之外不加其他剪枝。输出不剪枝完整二选一树的调用数，以及按上述超重剪枝的调用数。进入后立即返回的调用也计数；本题不是输出方案数。

输入格式

第一行n W。第二行n个正重量；n=0时可省略第二行。

输出格式

一行完整调用数和剪枝调用数。

样例输入

2 1
2 3

样例输出

7 5

样例解释

完整树有7次。剪枝后根1次，不选第一件的分支3次，选第一件立刻超重的分支1次，合计5。

数据范围

0≤n≤18，0≤W≤100，1≤w[i]≤100。