EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All IOI entries
Competitive Programming

IOI 1995 - Shopping Offers

Problem Statement A shop sells b different products (b 5). Each product i has a unit price c_i, and we wish to buy exactly q_i units of product i (q_i 5). There are s special offers (s 99). Each offer specifies a bund...

Source sync Apr 19, 2026
Track IOI
Year 1995
Files TeX and C++
Folder competitive_programming/ioi/1995/shopping_offers
IOI1995TeXC++
Source of truth

Source-first archive entry

This page is built from the copied files in competitive_programming/ioi/1995/shopping_offers. Edit competitive_programming/ioi/1995/shopping_offers/solution.tex to update the written solution and competitive_programming/ioi/1995/shopping_offers/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++
Problem statement

Problem Statement

Rendered from the "Problem Statement" section inside solution.tex because this entry has no separate statement file.

Raw TeX

A shop sells $b$ different products ($b \le 5$). Each product $i$ has a unit price $c_i$, and we wish to buy exactly $q_i$ units of product $i$ ($q_i \le 5$).

There are $s$ special offers ($s \le 99$). Each offer specifies a bundle: for each product, how many units are included, along with a bundle price. An offer may be used as many times as desired, but we cannot buy more than the required quantity of any product.

Find the minimum total cost to buy exactly the required quantities.

Editorial

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

Solution Approach

State-Space DP

Since there are at most 5 products each with quantity at most 5, the state space is at most $6^5 = 7{,}776$ states. Define: \[ \mathrm{dp}[q_1][q_2][q_3][q_4][q_5] = \text{minimum cost to buy exactly } (q_1, q_2, \ldots, q_5) \text{ items.} \]

Base Case

$\mathrm{dp}[0][0][0][0][0] = 0$.

Transitions

For each state $(q_1, \ldots, q_b)$ with at least one $q_i > 0$:

  1. \textbf{Buy one unit of product $i$:} If $q_i > 0$, transition from $(q_1, \ldots, q_i - 1, \ldots, q_b)$ with cost increase $c_i$.

  2. \textbf{Use offer $j$:} If $q_i \ge o_{j,i}$ for all $i$, transition from $(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ with cost increase equal to the offer price.

  3. We compute the DP bottom-up, iterating through all quantity tuples in lexicographic order. Each state takes its value as the minimum over all valid predecessors.

C++ Solution

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int b; // number of products (1..5)
int price[6]; // unit price for each product (1-indexed)
int want[6];  // desired quantity for each product
int code[6];  // product code mapping

int s; // number of offers
struct Offer {
    int qty[6]; // quantity of each product in offer (1-indexed)
    int cost;
};
Offer offers[100];

int dp[6][6][6][6][6];

int main() {
    scanf("%d", &s);

    // Read offers (product codes used directly for now)
    for (int i = 0; i < s; i++) {
        int nk;
        scanf("%d", &nk);
        memset(offers[i].qty, 0, sizeof(offers[i].qty));
        for (int j = 0; j < nk; j++) {
            int c, q;
            scanf("%d %d", &c, &q);
            offers[i].qty[c] = q; // store by product code
        }
        scanf("%d", &offers[i].cost);
    }

    scanf("%d", &b);
    for (int i = 1; i <= b; i++)
        scanf("%d %d %d", &code[i], &want[i], &price[i]);

    // Remap offer quantities from product codes to indices 1..b
    Offer mapped[100];
    for (int i = 0; i < s; i++) {
        mapped[i].cost = offers[i].cost;
        memset(mapped[i].qty, 0, sizeof(mapped[i].qty));
        for (int j = 1; j <= b; j++)
            mapped[i].qty[j] = offers[i].qty[code[j]];
    }

    // Initialize DP to infinity
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0][0] = 0;

    // Set up quantity bounds
    int w[6];
    for (int i = 1; i <= 5; i++)
        w[i] = (i <= b) ? want[i] : 0;

    // Bottom-up DP over all quantity tuples
    for (int q1 = 0; q1 <= w[1]; q1++)
    for (int q2 = 0; q2 <= w[2]; q2++)
    for (int q3 = 0; q3 <= w[3]; q3++)
    for (int q4 = 0; q4 <= w[4]; q4++)
    for (int q5 = 0; q5 <= w[5]; q5++) {
        if (q1 == 0 && q2 == 0 && q3 == 0 && q4 == 0 && q5 == 0)
            continue; // base case already set

        int best = 0x3f3f3f3f;
        int qq[6] = {0, q1, q2, q3, q4, q5};

        // Option 1: buy a single unit of product j
        for (int j = 1; j <= b; j++) {
            if (qq[j] > 0) {
                int prev[6] = {0, q1, q2, q3, q4, q5};
                prev[j]--;
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + price[j]);
            }
        }

        // Option 2: use an offer
        for (int o = 0; o < s; o++) {
            bool ok = true;
            int prev[6] = {0, q1, q2, q3, q4, q5};
            for (int j = 1; j <= b; j++) {
                prev[j] -= mapped[o].qty[j];
                if (prev[j] < 0) { ok = false; break; }
            }
            if (ok) {
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + mapped[o].cost);
            }
        }

        dp[q1][q2][q3][q4][q5] = best;
    }

    printf("%d\n", dp[w[1]][w[2]][w[3]][w[4]][w[5]]);
    return 0;
}

Correctness

The DP processes states in non-decreasing order of the quantity tuple (lexicographically). Every predecessor state $(q_1, \ldots, q_i - 1, \ldots, q_b)$ or $(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ is componentwise $\le$ the current state, so it has already been computed when needed. The base case $\mathrm{dp}[\mathbf{0}] = 0$ is correct, and each transition adds exactly the cost of one purchase, so by induction the DP computes the minimum cost for every reachable state.

Complexity Analysis

  • Time complexity: $O(Q^b \cdot (b + s))$, where $Q = \max(q_i) + 1 \le 6$, $b \le 5$, and $s \le 99$. With these bounds: $6^5 \times 104 \approx 810{,}000$ operations.

  • Space complexity: $O(Q^5) = O(7{,}776)$ for the DP table.

Source code

Code

Exact copied C++ implementation from solution.cpp.

C++ competitive_programming/ioi/1995/shopping_offers/solution.cpp

Exact copied implementation source.

Raw file 
// IOI 1995 - Shopping Offers
// State-space DP over product quantities (at most 6^5 = 7776 states)
// Time: O(Q^b * (b + s)), Space: O(Q^b)
#include <bits/stdc++.h>
using namespace std;

int b; // number of products (1..5)
int price[6]; // unit price for each product (1-indexed)
int want[6];  // desired quantity for each product
int code[6];  // product code mapping

int s; // number of offers
struct Offer {
    int qty[6]; // quantity of each product in offer
    int cost;
};
Offer offers[100];

int dp[6][6][6][6][6];

int main() {
    scanf("%d", &s);

    // Read offers
    for (int i = 0; i < s; i++) {
        int nk;
        scanf("%d", &nk);
        memset(offers[i].qty, 0, sizeof(offers[i].qty));
        for (int j = 0; j < nk; j++) {
            int c, q;
            scanf("%d %d", &c, &q);
            offers[i].qty[c] = q;
        }
        scanf("%d", &offers[i].cost);
    }

    scanf("%d", &b);
    for (int i = 1; i <= b; i++)
        scanf("%d %d %d", &code[i], &want[i], &price[i]);

    // Remap offer quantities to product indices 1..b
    Offer mapped[100];
    for (int i = 0; i < s; i++) {
        mapped[i].cost = offers[i].cost;
        memset(mapped[i].qty, 0, sizeof(mapped[i].qty));
        for (int j = 1; j <= b; j++)
            mapped[i].qty[j] = offers[i].qty[code[j]];
    }

    // Initialize DP with large value
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0][0] = 0;

    int w[6] = {};
    for (int i = 1; i <= 5; i++)
        w[i] = (i <= b) ? want[i] : 0;

    for (int q1 = 0; q1 <= w[1]; q1++)
    for (int q2 = 0; q2 <= w[2]; q2++)
    for (int q3 = 0; q3 <= w[3]; q3++)
    for (int q4 = 0; q4 <= w[4]; q4++)
    for (int q5 = 0; q5 <= w[5]; q5++) {
        if (q1 == 0 && q2 == 0 && q3 == 0 && q4 == 0 && q5 == 0) continue;

        int best = 0x3f3f3f3f;
        int qq[6] = {0, q1, q2, q3, q4, q5};

        // Buy single items
        for (int j = 1; j <= b; j++) {
            if (qq[j] > 0) {
                int prev[6] = {0, q1, q2, q3, q4, q5};
                prev[j]--;
                best = min(best,
                    dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]] + price[j]);
            }
        }

        // Use offers
        for (int o = 0; o < s; o++) {
            bool ok = true;
            int prev[6] = {0, q1, q2, q3, q4, q5};
            for (int j = 1; j <= b; j++) {
                prev[j] -= mapped[o].qty[j];
                if (prev[j] < 0) { ok = false; break; }
            }
            if (ok) {
                best = min(best,
                    dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]] + mapped[o].cost);
            }
        }

        dp[q1][q2][q3][q4][q5] = best;
    }

    printf("%d\n", dp[w[1]][w[2]][w[3]][w[4]][w[5]]);
    return 0;
}
Source files

Source Files

Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.

TeX write-up competitive_programming/ioi/1995/shopping_offers/solution.tex

Exact copied write-up source.

Raw file 
\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{geometry}
\geometry{margin=2.5cm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!60!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  numbersep=8pt,
  frame=single,
  breaklines=true,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 1995 -- Shopping Offers}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}

A shop sells $b$ different products ($b \le 5$). Each product $i$ has a unit
price $c_i$, and we wish to buy exactly $q_i$ units of product $i$ ($q_i \le 5$).

There are $s$ special offers ($s \le 99$). Each offer specifies a bundle: for each product,
how many units are included, along with a bundle price. An offer may be used as many times
as desired, but we cannot buy more than the required quantity of any product.

Find the minimum total cost to buy exactly the required quantities.

\section{Solution Approach}

\subsection{State-Space DP}

Since there are at most 5 products each with quantity at most 5, the state space is
at most $6^5 = 7{,}776$ states. Define:
\[
  \mathrm{dp}[q_1][q_2][q_3][q_4][q_5] = \text{minimum cost to buy exactly } (q_1, q_2, \ldots, q_5) \text{ items.}
\]

\subsection{Base Case}
$\mathrm{dp}[0][0][0][0][0] = 0$.

\subsection{Transitions}
For each state $(q_1, \ldots, q_b)$ with at least one $q_i > 0$:
\begin{enumerate}
  \item \textbf{Buy one unit of product $i$:} If $q_i > 0$, transition from
    $(q_1, \ldots, q_i - 1, \ldots, q_b)$ with cost increase $c_i$.
  \item \textbf{Use offer $j$:} If $q_i \ge o_{j,i}$ for all $i$, transition from
    $(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ with cost increase equal to the offer price.
\end{enumerate}

We compute the DP bottom-up, iterating through all quantity tuples in lexicographic order.
Each state takes its value as the minimum over all valid predecessors.

\section{C++ Solution}

\begin{lstlisting}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int b; // number of products (1..5)
int price[6]; // unit price for each product (1-indexed)
int want[6];  // desired quantity for each product
int code[6];  // product code mapping

int s; // number of offers
struct Offer {
    int qty[6]; // quantity of each product in offer (1-indexed)
    int cost;
};
Offer offers[100];

int dp[6][6][6][6][6];

int main() {
    scanf("%d", &s);

    // Read offers (product codes used directly for now)
    for (int i = 0; i < s; i++) {
        int nk;
        scanf("%d", &nk);
        memset(offers[i].qty, 0, sizeof(offers[i].qty));
        for (int j = 0; j < nk; j++) {
            int c, q;
            scanf("%d %d", &c, &q);
            offers[i].qty[c] = q; // store by product code
        }
        scanf("%d", &offers[i].cost);
    }

    scanf("%d", &b);
    for (int i = 1; i <= b; i++)
        scanf("%d %d %d", &code[i], &want[i], &price[i]);

    // Remap offer quantities from product codes to indices 1..b
    Offer mapped[100];
    for (int i = 0; i < s; i++) {
        mapped[i].cost = offers[i].cost;
        memset(mapped[i].qty, 0, sizeof(mapped[i].qty));
        for (int j = 1; j <= b; j++)
            mapped[i].qty[j] = offers[i].qty[code[j]];
    }

    // Initialize DP to infinity
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0][0] = 0;

    // Set up quantity bounds
    int w[6];
    for (int i = 1; i <= 5; i++)
        w[i] = (i <= b) ? want[i] : 0;

    // Bottom-up DP over all quantity tuples
    for (int q1 = 0; q1 <= w[1]; q1++)
    for (int q2 = 0; q2 <= w[2]; q2++)
    for (int q3 = 0; q3 <= w[3]; q3++)
    for (int q4 = 0; q4 <= w[4]; q4++)
    for (int q5 = 0; q5 <= w[5]; q5++) {
        if (q1 == 0 && q2 == 0 && q3 == 0 && q4 == 0 && q5 == 0)
            continue; // base case already set

        int best = 0x3f3f3f3f;
        int qq[6] = {0, q1, q2, q3, q4, q5};

        // Option 1: buy a single unit of product j
        for (int j = 1; j <= b; j++) {
            if (qq[j] > 0) {
                int prev[6] = {0, q1, q2, q3, q4, q5};
                prev[j]--;
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + price[j]);
            }
        }

        // Option 2: use an offer
        for (int o = 0; o < s; o++) {
            bool ok = true;
            int prev[6] = {0, q1, q2, q3, q4, q5};
            for (int j = 1; j <= b; j++) {
                prev[j] -= mapped[o].qty[j];
                if (prev[j] < 0) { ok = false; break; }
            }
            if (ok) {
                int val = dp[prev[1]][prev[2]][prev[3]][prev[4]][prev[5]];
                if (val < 0x3f3f3f3f)
                    best = min(best, val + mapped[o].cost);
            }
        }

        dp[q1][q2][q3][q4][q5] = best;
    }

    printf("%d\n", dp[w[1]][w[2]][w[3]][w[4]][w[5]]);
    return 0;
}
\end{lstlisting}

\section{Correctness}

The DP processes states in non-decreasing order of the quantity tuple (lexicographically).
Every predecessor state $(q_1, \ldots, q_i - 1, \ldots, q_b)$ or
$(q_1 - o_{j,1}, \ldots, q_b - o_{j,b})$ is componentwise $\le$ the current state,
so it has already been computed when needed. The base case $\mathrm{dp}[\mathbf{0}] = 0$
is correct, and each transition adds exactly the cost of one purchase, so by induction
the DP computes the minimum cost for every reachable state.

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{Time complexity:} $O(Q^b \cdot (b + s))$, where $Q = \max(q_i) + 1 \le 6$,
        $b \le 5$, and $s \le 99$. With these bounds: $6^5 \times 104 \approx 810{,}000$ operations.
  \item \textbf{Space complexity:} $O(Q^5) = O(7{,}776)$ for the DP table.
\end{itemize}

\end{document}