From 3496b0ed08c51e37e135e686b1632fd86f930c2c Mon Sep 17 00:00:00 2001 From: Raghuram Subramani Date: Mon, 30 Sep 2024 16:08:27 +0530 Subject: (init): Initialize repository. --- problems/partitionnumbers.py | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 problems/partitionnumbers.py (limited to 'problems/partitionnumbers.py') diff --git a/problems/partitionnumbers.py b/problems/partitionnumbers.py new file mode 100644 index 0000000..9bb7cb6 --- /dev/null +++ b/problems/partitionnumbers.py @@ -0,0 +1,27 @@ +def compute_partitions(max_n): + partitions = [0] * (max_n + 1) + partitions[0] = 1 + + for i in range(1, max_n + 1): + for j in range(i, max_n + 1): + partitions[j] += partitions[j - i] + + return partitions + +def main(): + import sys + input = sys.stdin.read + data = input().split() + + T = int(data[0]) + queries = [int(data[i]) for i in range(1, T + 1)] + + max_n = 100 + partitions = compute_partitions(max_n) + + results = [str(partitions[n]) for n in queries] + + print("\n".join(results)) + +if __name__ == "__main__": + main() -- cgit v1.2.3