return what you build from it — or, for search problems, CHOOSE → EXPLORE → UNDO. Before coding, say out loud: what is my state, what is my smallest state, and how does it shrink?★ Start Simple — Five Tiny Questions, One Per Page
The CCC problems below have long stories. These five do not — short words, small numbers, same Recipe. Each one now has its own page (use the Next button or the chips above): the question, a step-by-step walkthrough with the code and the call tree moving together, the code, and a predict-first check. Do them in order — the first four are chains (each call has exactly one child), and the fifth is your first real tree.
factorial(5) → 120. The chain in its purest form: calls pile up, answers multiply back.
bunny_ears(3) → 6. Same chain, gentler combine step: + 2 per bunny.
triangle(4) → 10. Each call adds its own row and trusts the smaller triangle for the rest.
count_x("xxhixx") → 4. The state is a string; the smaller problem drops its first letter.
fib(6) → 8. Two calls per call — the chain becomes a tree, and you can count the waste yourself.
Factorial — multiply on the way up
factorial(n) means n × (n−1) × … × 1.
BASE factorial(0) = 1
SMALLER factorial(n − 1)
COMBINE n × that answer
The code
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
✏️ Predict: factorial(4)?
24 — 4 × factorial(3) = 4 × 6.
Bunny Ears — add the same thing
Every bunny has 2 ears. How many ears on b bunnies — counted one bunny at a time?
BASE bunny_ears(0) = 0
SMALLER one fewer bunny
COMBINE 2 + that answer
The code
def bunny_ears(b):
if b == 0:
return 0
return 2 + bunny_ears(b - 1)
print(bunny_ears(3)) # 6
✏️ Predict: bunny_ears(10)?
20 — ten bunnies, two ears each, built two at a time.
Triangle — rows of blocks
Row 1 has 1 block, row 2 has 2, row 3 has 3… How many blocks in a triangle of r rows?
BASE triangle(0) = 0
SMALLER one fewer row
COMBINE r + that answer
The code
def triangle(r):
if r == 0:
return 0
return r + triangle(r - 1)
print(triangle(4)) # 10
✏️ Predict: triangle(5)?
15 — 5 + triangle(4) = 5 + 10.
Count the x's — a string that shrinks
Count the letter x in a string. The “smaller problem” is the string with its first letter removed.
BASE empty string → 0
SMALLER s[1:] — drop the first letter
COMBINE (1 if the first letter is x) + the rest
The code
def count_x(s):
if s == "":
return 0
first = 1 if s[0] == "x" else 0
return first + count_x(s[1:])
print(count_x("xxhixx")) # 4
✏️ Predict: count_x("xhix")?
2 — an x at the start and an x at the end.
Fibonacci — your first tree
Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… This one branches — it is the routes tree from §2 with different base cases.
BASE fib(0) = 0 · fib(1) = 1
SMALLER fib(n − 1) and fib(n − 2)
COMBINE add the two answers
The code
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
print(fib(6)) # 8
✏️ Predict: fib(7)?
13 — fib(6) + fib(5) = 8 + 5. Draw its tree the §2 way and count how many times fib(2) gets built!
CCC Word Hunt 🔤
How many times is the word hidden in the letter grid?
Input: the word W (distinct uppercase letters), then R and C, then the grid — letters separated by spaces. The word may lie on one straight segment (horizontal, vertical, or diagonal, in either direction) or on two perpendicular segments — bending once, at a right angle, at any letter after the first.
Sample input
MENU 5 7 F T R U B L K P M N A X C U A E R C N E O M N E U A R M M U N E M N S
Sample output
3
Output: one integer — the number of occurrences.
seg_ok — that checks whether a piece of the word can be read from a cell in a direction. Then a straight occurrence is one call, and a bent occurrence is two calls with perpendicular directions (their dot product is 0).The code
import sys
def main():
lines = sys.stdin.read().split("\n")
W = lines[0].strip()
R = int(lines[1])
C = int(lines[2])
grid = [lines[3 + r].split() for r in range(R)]
L = len(W)
DIRS = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
(0, 1), (1, -1), (1, 0), (1, 1)]
def seg_ok(r, c, dr, dc, i0, i1):
# can W[i0:i1] be read starting at (r, c), stepping (dr, dc)?
for i in range(i0, i1):
rr = r + dr * (i - i0)
cc = c + dc * (i - i0)
if not (0 <= rr < R and 0 <= cc < C):
return False
if grid[rr][cc] != W[i]:
return False
return True
count = 0
for r in range(R):
for c in range(C):
if grid[r][c] != W[0]:
continue
for dr, dc in DIRS:
if seg_ok(r, c, dr, dc, 0, L):
count += 1 # straight
for k in range(1, L - 1): # bend after letter k
br, bc = r + dr * k, c + dc * k
if not seg_ok(r, c, dr, dc, 0, k + 1):
break
for dr2, dc2 in DIRS:
if dr * dr2 + dc * dc2 != 0:
continue # second leg must be perpendicular
if seg_ok(br, bc, dr2, dc2, k, L):
count += 1
print(count)
main()
Key points & traps
✏️ Predict first: word CAT, grid below — how many occurrences? (Count the bend!)
C A . . T . . . .
Answer: 1. C(0,0) → A(0,1) heading east, then bend south (perpendicular) to T(1,1). No straight placement exists: the T is not in line with C and A in any single direction. If you answered 0, your search is missing bent words — the 9-mark part of the problem.
π Day 🥧
minimum parameter is the trick that kills duplicates, and memoization on the full state (left, people, minimum) makes n = 250 survivable.In how many ways can n pieces of pie be given to k people in line, if everyone gets at least one piece and nobody gets fewer than the person in front of them?
Input: n (pieces, up to 250), then k (people). Amounts must be non-decreasing along the line.
Sample input
8 4
Sample output
5
Output: one integer — the number of distributions.
left, people remaining, and the minimum the next person may take (= what the previous person took). The next amount can range from minimum up to left // people — beyond that, the people behind cannot all keep up. The official example lists the five ways for 8/4: [1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2].The code
from functools import lru_cache
n = int(input())
k = int(input())
@lru_cache(None)
def ways(left, people, minimum):
# ways to give `left` pieces to `people` people so that each
# person gets at least `minimum` and amounts never decrease
if people == 1:
return 1 # last person takes everything left
total = 0
for first in range(minimum, left // people + 1):
total += ways(left - first, people - 1, first)
return total
print(ways(n, k, 1))
Key points & traps
minimum from the state and the cache returns wrong answers — the §2 test again: cache only when the full state determines the answer.✏️ Predict first: 5 pieces, 2 people — how many ways?
Answer: 2 — [1, 4] and [2, 3]. ([3, 2] and [4, 1] break the non-decreasing rule.)
Rule of Three 🔀
A word-rewriting game: use exactly S moves to turn the START string into the TARGET string — then print the diary of the moves you used.
Input is four lines. The first three lines are the three rewriting rules, each written pattern replacement (strings of A's and B's). The fourth line holds three things at once — S I F: S = the exact number of moves you must make, I = the initial (start) string, F = the final (target) string. One move replaces one occurrence of a rule's pattern, at a position you choose. A solution is guaranteed to exist. If this still sounds tangled, the green Decode box right below this card walks the sample input and output line by line.
Sample input
AA AB AB BB B AA 4 AB AAAB
Sample output
2 1 BB 3 1 AAB 3 3 AAAA 1 3 AAAB
Output: S lines, each rule position resulting-string (positions are 1-based). Any valid sequence is accepted.
🔍 Decode the question — what is it actually asking?
In plain words: you are given a short string of A's and B's, like AB. You are also given three find-and-replace rules. One move = pick a rule, find its left-hand pattern somewhere in your current string, and replace that one occurrence with the rule's right-hand side. You must make exactly S moves — not “up to S” — and after the last move your string must be exactly the target. The question is not asking whether it can be done (it promises it can). It is asking you to find one winning sequence of moves — and print it.
📥 The INPUT, line by line (sample)
| Line | Sample | What it means |
|---|---|---|
| 1 | AA AB | Rule 1: wherever you find AA, you may replace it with AB |
| 2 | AB BB | Rule 2: wherever you find AB, you may replace it with BB |
| 3 | B AA | Rule 3: wherever you find B, you may replace it with AA |
| 4 | 4 AB AAAB | Three values in one line: 4 = S, make exactly 4 moves · AB = I, the start string · AAAB = F, the target string |
📤 The OUTPUT — it is a diary of your moves, not the final string
Print S lines (here, 4 lines) — one line per move. Every line has three parts: the rule number you used, the position where its pattern starts in the current string (1-based — the first character is position 1), and the whole string after that move. Here is the sample output, decoded move by move:
| Before | Output line | Read it as… | After |
|---|---|---|---|
AB | 2 1 BB | Rule 2 at position 1: AB → BB | BB |
BB | 3 1 AAB | Rule 3 at position 1: the first B → AA; the second B stays | AAB |
AAB | 3 3 AAAA | Rule 3 at position 3: that B → AA | AAAA |
AAAA | 1 3 AAAB | Rule 1 at position 3: the AA starting there → AB; the first AA is untouched | AAAB 🎯 |
After exactly 4 moves the string is AAAB — the target — so this diary wins. Any diary that reaches the target in exactly S moves is accepted: the animation and the code below find a different valid diary for this same input, and that is fine. Recipe check for this problem — base case: used == S and the string equals F; make it smaller: one move spent, S − used shrinks by 1 each call; self-call: choose a (rule, position), explore it, and on failure pop the recorded step and try the next choice.
The code
import sys
sys.setrecursionlimit(10000)
rules = []
for _ in range(3):
a, b = input().split()
rules.append((a, b))
S, I, F = input().split()
S = int(S)
steps = [] # the record: (rule number, position, resulting string)
def dfs(cur, used):
if used == S:
return cur == F
for ri in range(3):
a, b = rules[ri]
start = 0
while True:
p = cur.find(a, start)
if p == -1:
break
nxt = cur[:p] + b + cur[p + len(a):]
steps.append((ri + 1, p + 1, nxt)) # record the choice
if dfs(nxt, used + 1):
return True
steps.pop() # undo - try the next choice
start = p + 1
return False
dfs(I, 0)
for ri, p, w in steps:
print(ri, p, w)
Key points & traps
str.find. The +1 when recording is the easiest mark to lose in this problem.✏️ Predict first: in the official sample solution, after 2 1 BB and 3 1 AAB, rule 3 is played at position 3. What string results?
AAAA. AAB's B is at position 3; rule 3 (B→AA) replaces it: AA + AA = AAAA. One more step (rule 1 at position 3) turns AAAA into the target AAAB.
Fractals 🌀
Where does a vertical line cross the block fractal?
Every segment is split into thirds; the middle third becomes a square bump. Given a level, a width (a power of 3, at most 81), and an x-coordinate, output every y where the fractal's lines pass through the point (x, y), in increasing order. The fractal starts as the segment from (0, 1) to (width, 1).
Sample inputs
3 27 5 3 27 18 2 27 19 4 81 38
Sample outputs
4 5 6 1 2 3 4 7 8 9 10 1 4 7 37 38 39
See the code section below for the full program — and try the slider: at level 4 with x = 38 the picture reports exactly the fourth sample's answer, 37 38 39.
split() code, with the line running right now lit up. Middle: the call tree — one box per call: solid blue is running now, pale blue is a caller waiting, green is finished; finished branches fold up so the frontier stays visible. Below: the drawing itself, growing segment by segment in exactly the order the leaf calls draw them. It traces level 2, width 9 — the same code the playground above runs at bigger sizes.The code
level, width, xq = map(int, input().split())
points = set()
def split(x, y, dx, dy, nx, ny, length, lev):
# one segment: start (x, y), direction (dx, dy), bump side (nx, ny)
if lev == 0:
for i in range(length + 1):
points.add((x + dx * i, y + dy * i))
return
t = length // 3
x1, y1 = x + dx * t, y + dy * t # end of first third
x2, y2 = x1 + nx * t, y1 + ny * t # up the bump
x3, y3 = x2 + dx * t, y2 + dy * t # across the top
x4, y4 = x3 - nx * t, y3 - ny * t # down to the last third
split(x, y, dx, dy, nx, ny, t, lev - 1)
split(x1, y1, nx, ny, -dx, -dy, t, lev - 1)
split(x2, y2, dx, dy, nx, ny, t, lev - 1)
split(x3, y3, -nx, -ny, dx, dy, t, lev - 1)
split(x4, y4, dx, dy, nx, ny, t, lev - 1)
split(0, 1, 1, 0, 0, 1, width, level)
ys = sorted(y for (px, y) in points if px == xq)
print(*ys)
Key points & traps
✏️ Predict first: level 1, width 27, x = 13 — which y values?
Answer: 10. At level 1 the bump occupies the middle third (x from 9 to 18) and rises 9 units above y = 1, so its top edge is the segment y = 10 — and x = 13 crosses only that top edge.
Harvest Waterloo 🎃
What is the total value of every pumpkin the farmer can reach?
The patch is rows of S (small, $1), M (medium, $5), L (large, $10) and * (hay). The farmer starts at row A, column B and moves up/down/left/right — never through hay, never outside. Harvest everything reachable.
Sample input
6 6 **LMLS S*LMMS S*SMSM ****** LLM*MS SSL*SS 5 1
Sample output
37
Output: one integer — the total value.
The code
import sys
sys.setrecursionlimit(1000000)
R = int(input())
C = int(input())
grid = [input().strip() for _ in range(R)]
A = int(input())
B = int(input())
VALUE = {'S': 1, 'M': 5, 'L': 10}
visited = [[False] * C for _ in range(R)]
def fill(r, c):
if not (0 <= r < R and 0 <= c < C):
return 0
if visited[r][c] or grid[r][c] == '*':
return 0
visited[r][c] = True # permanent: never unmarked
total = VALUE[grid[r][c]]
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
total += fill(r + dr, c + dc)
return total
print(fill(A, B))
Key points & traps
visited[r][c] = False. That one line is the difference between “count every path” and “visit every cell once” — and it changes the running time from exponential to O(R × C).✏️ Predict first: patch below, farmer starts at (1, 0). Total value?
S S M *
Answer: 7. From (1, 0) the M ($5) is harvested, then up to (0, 0) S ($1) and right to (0, 1) S ($1). The hay at (1, 1) blocks nothing else — everything reachable totals 5 + 1 + 1 = 7.
Escape Room 🚪
Can you escape from the top-left cell to the bottom-right cell?
An M×N room; every cell holds a positive integer. Standing on a cell with value x, you may jump to any cell (a, b) with a × b = x (rows and columns are 1-based). Start at (1, 1); the exit is (M, N).
Sample input
3 4 3 10 8 14 1 11 12 12 6 2 3 9
Sample output
yes
Output: yes or no.
The code
from collections import deque
M = int(input())
N = int(input())
grid = []
for _ in range(M):
grid.append(list(map(int, input().split())))
seen_cell = [[False] * N for _ in range(M)]
seen_value = set()
queue = deque()
queue.append((0, 0))
seen_cell[0][0] = True
while queue:
r, c = queue.popleft()
if (r, c) == (M - 1, N - 1):
break
x = grid[r][c]
if x in seen_value:
continue # this value's jumps were already explored
seen_value.add(x)
a = 1
while a * a <= x: # factor pairs of x
if x % a == 0:
b = x // a
for rr, cc in [(a - 1, b - 1), (b - 1, a - 1)]:
if 0 <= rr < M and 0 <= cc < N and not seen_cell[rr][cc]:
seen_cell[rr][cc] = True
queue.append((rr, cc))
a += 1
print("yes" if seen_cell[M - 1][N - 1] else "no")
Key points & traps
✏️ Predict first: room below — yes or no?
2 2 2 3 5 7
Answer: no. From (1, 1) = 2 you can jump to (1, 2) and (2, 1). Their values, 3 and 5, only point outside the 2×2 room (3 = 1×3, 5 = 1×5). The exit (2, 2) needs a jump from a cell holding 4 — there is none.