# A. Mister B and Book Reading

At first day Mister B read v0 pages, but after that he started to speed up. Every day, starting from the second, he read a pages more than on the previous day (at first day he read v0 pages, at second — v0 + a pages, at third — v0 + 2a pages, and so on). But Mister B is just a human, so he physically wasn’t able to read more than v1 pages per day.

Also, to refresh his memory, every day, starting from the second, Mister B had to reread last l pages he read on the previous day. Mister B finished the book when he read the last page for the first time.

Help Mister B to calculate how many days he needed to finish the book.

# B. Mister B and Angle in Polygon

On one quiet day all of sudden Mister B decided to draw angle a on his field. Aliens have already visited his field and left many different geometric figures on it. One of the figures is regular convex n-gon (regular convex polygon with n sides).

That’s why Mister B decided to use this polygon. Now Mister B must find three distinct vertices v1, v2, v3 such that the angle 角V1V2V3(where v2 is the vertex of the angle, and v1 and v3 lie on its sides) is as close as possible to a. In other words, the value |角V1V2V3 – a| should be minimum possible.

If there are many optimal solutions, Mister B should be satisfied with any of them.

# D. Mister B and PR Shifts

Some time ago Mister B detected a strange signal from the space, which he started to study.

After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that’s why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.

Let’s define the deviation of a permutation p as $$\sum_{i=1}^{n}|{p[i]-i}|$$.

Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.

Let’s denote id k (0 ≤ k < n) of a cyclic shift of permutation p as the number of right shifts needed to reach this shift, for example:

k = 0: shift p1, p2, … pn,
k = 1: shift pn, p1, … pn - 1,
…,
k = n - 1: shift p2, p3, … pn, p1.

n个数，从1-n乱序，可以将其向后移动p位，求秩序值最小到时候是第几次。

cur[i]记录距离目标位置为i的数字的个数。
L记录开始在左边的个数，R记录开始在右边的个数。

# A Okabe and Future Gadget Laboratory

Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by n square grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and ax, y ≠ 1, there should exist two indices s and t so that ax, y = ax, s + at, y, where ai, j denotes the integer in i-th row and j-th column.
Help Okabe determine whether a given lab is good!

n * n的网格里（n <= 50），考虑每个不等于1的位置，在该行与该列上是否分别存在一个数，使得它们的和等于该位置的值，如果都存在输出“Yes”， 否则输出“No”。暴力枚举即可。

# B Okabe and Banana Trees

Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tree in such a point, and it has x + y bananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation $$y=-\frac{x}{m}+b$$. Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe’s rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 1018. You can trust him.

# C Okabe and Boxes

Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.

Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n. Of course, this means that it might be impossible for Daru to perform some of Okabe’s remove commands, because the required box is not on the top of the stack.

That’s why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe’s commands, but he can’t add or remove boxes while he does it.

Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe’s commands. It is guaranteed that every box is added before it is required to be removed.

# D Okabe and City

Okabe likes to be able to walk through his city on a path lit by street lamps. That way, he doesn’t get beaten up by schoolchildren.

Okabe’s city is represented by a 2D grid of cells. Rows are numbered from 1 to n from top to bottom, and columns are numbered 1 to m from left to right. Exactly k cells in the city are lit by a street lamp. It’s guaranteed that the top-left cell is lit.

Okabe starts his walk from the top-left cell, and wants to reach the bottom-right cell. Of course, Okabe will only walk on lit cells, and he can only move to adjacent cells in the up, down, left, and right directions. However, Okabe can also temporarily light all the cells in any single row or column at a time if he pays 1 coin, allowing him to walk through some cells not lit initially.

Note that Okabe can only light a single row or column at a time, and has to pay a coin every time he lights a new row or column. To change the row or column that is temporarily lit, he must stand at a cell that is lit initially. Also, once he removes his temporary light from a row or column, all cells in that row/column not initially lit are now not lit.

Help Okabe find the minimum number of coins he needs to pay to complete his walk!

bfs搜索题，从左上角到右下角，必须走在有灯的格子里，如果要去的格子没有灯，可以暂时照亮任意一行或者一列，但必须之前站在原来就是有灯的格子里，同时花费为1，问是否能到达目的地，如果能输出最小花费，否则输出-1。

• 每次bfs都是在原始就是有灯的点之间移动（除了终点）
• 一行或者一列最多被照亮一次
• 当前点，与下一次可以到达的点的横坐标或纵坐标距离小于等于2

# E Okabe and El Psy Kongroo

Okabe likes to take walks but knows that spies from the Organization could be anywhere; that’s why he wants to know how many different walks he can take in his city safely. Okabe’s city can be represented as all points (x, y) such that x and y are non-negative. Okabe starts at the origin (point (0, 0)), and needs to reach the point (k, 0). If Okabe is currently at the point (x, y), in one step he can go to (x + 1, y + 1), (x + 1, y), or (x + 1, y - 1).

Additionally, there are n horizontal line segments, the i-th of which goes from x = ai to x = bi inclusive, and is at y = ci. It is guaranteed that a1 = 0, an ≤ k ≤ bn, and ai = bi - 1 for 2 ≤ i ≤ n. The i-th line segment forces Okabe to walk with y-value in the range 0 ≤ y ≤ ci when his x value satisfies ai ≤ x ≤ bi, or else he might be spied on. This also means he is required to be under two line segments when one segment ends and another begins.

Okabe now wants to know how many walks there are from the origin to the point (k, 0) satisfying these conditions, modulo 10^9 + 7.

dp，因为ci是一条与x轴平行的线段，所以从ai到ai+1的每一次的贡献都是一样的，可以用矩阵加速，c最多为15，所以不会超时

# C – Reconciled?

Snuke has N dogs and M monkeys. He wants them to line up in a row.

As a Japanese saying goes, these dogs and monkeys are on bad terms. (“ken’en no naka”, literally “the relationship of dogs and monkeys”, means a relationship of mutual hatred.) Snuke is trying to reconsile them, by arranging the animals so that there are neither two adjacent dogs nor two adjacent monkeys.

How many such arrangements there are? Find the count modulo 109+7 (since animals cannot understand numbers larger than that). Here, dogs and monkeys are both distinguishable. Also, two arrangements that result from reversing each other are distinguished.

n只狗和m只猫排列，同种动物不能相邻出现，问有多少种排列方式（模1e9+7）
n和m相等时答案2 × n！× m!
n和m相差1时n! × m!

# D – Built?

There are N towns on a plane. The i-th town is located at the coordinates (xi,yi). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a−c|,|b−d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

# E – Connected?

Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions R×C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (xi,1,yi,1) and (xi,2,yi,2).

The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N. Here, the curves may not go outside the board or cross each other.

Determine whether this is possible.

R × C的网格里有N 种数，每种数出现两次，给出它们在网格里的坐标，问是否能够使得所有相同的数相互连通，并且不会有交叉或者穿过其他边

# F – Exhausted?

There are M chairs arranged in a line. The coordinate of the i-th chair (1≤i≤M) is i.

N people of the Takahashi clan played too much games, and they are all suffering from backaches. They need to sit in chairs and rest, but they are particular about which chairs they sit in. Specifically, the i-th person wishes to sit in a chair whose coordinate is not greater than Li, or not less than Ri. Naturally, only one person can sit in the same chair.

It may not be possible for all of them to sit in their favorite chairs, if nothing is done. Aoki, who cares for the health of the people of the Takahashi clan, decides to provide additional chairs so that all of them can sit in chairs at their favorite positions.

Additional chairs can be placed at arbitrary real coordinates. Find the minimum required number of additional chairs.

N 个人，M把椅子，每个人都要有椅子坐，第i个人不能坐[Li+1,Ri-1]里的椅子，最少要添多少椅子

1.调出控制台

2.生成执行文件

3.进入gdb

4.设置断点

5.运行

6.其他命令

# 基础排序算法分析与总结

## 插入类排序

### 直接插入排序

(1)将第i个记录插入到前面i-1个已经排序好的记录中
(2)插入过程为依次比较后移，直到找到比第i个记录小的数为止，插入。

A）｛48｝ 62 35 77 55 14 35 98
B）｛48 62｝ 35 77 55 14 35 98
C）｛35 48 62｝ 77 55 14 35 98
D）｛35 48 62 77｝ 55 14 35 98
E）｛35 48 55 62 77｝ 14 35 98
F）｛14 35 48 55 62 77｝ 35 98
G）｛14 35 35 48 55 62 77｝ 98
H）｛14 35 35 48 55 62 77 98｝

1.空间复杂度：O（1）
2.平均时间复杂度：O（n²）

3.稳定的排序算法
4.该排序与选择排序的区别是：选中已经排好序列的后一个数来进行插入操作，没有从未排序数中选择的过程
5.该排序与折半插入排序的区别：减少比较次数，直接插入排序为挨个比较，折半插入排序为二分比较，效率更高

### 折半插入排序

A）｛48｝ 62 35 77 55 14 35 98
B）｛48 62｝ 35 77 55 14 35 98
C）｛35 48 62｝ 77 55 14 35 98
D）｛35 48 62 77｝ 55 14 35 98
E）｛35 48 55 62 77｝ 14 35 98
F）｛14 35 48 55 62 77｝ 35 98
G）｛14 35 35 48 55 62 77｝ 98
H）｛14 35 35 48 55 62 77 98｝

1.空间复杂度：O（1）
2.平均时间复杂度：O（n²）
3.折半插入排序是一种稳定的排序算法
4.折半插入排序并没有改变时间复杂度，而是把比较次数的数量级降到了O（nlogn）
5.当n较大时 折半插入排序的比较次数要比直接插入排序的最差情况要好很多 但比其最好情况要差

### 希尔排序

(1)插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
(2)但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

1.空间复杂度：O（1）
2.时间复杂度：平均 O(n^1.5)或O(n^1.3)
最好 O(n)
最坏 O(n^2)
3.希尔排序是一种不稳定的排序算法
4.希尔排序对于中等规模（n≤1000）的序列具有较高的效率，而且希尔排序算法简单，容易执行，因此很多排序应用程序都选用了希尔排序
5.关于增量d的取法，最初Shell提出取d=n[n/2]–下取整，再取d=d=n[n/2]，直到d=1为止。

## 交换类排序

### 冒泡排序

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.空间复杂度：O（1）
2.时间复杂度： 平均O (n²)

3.冒泡排序是一种稳定的排序算法
4.冒泡两层for循环外层表示进行n-1趟排序 内层表示每趟要进行n-i次比较
5.冒泡排序的改进：

### 快速排序

1.从数列中挑出一个元素，称为”基准”（pivot）
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列

3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

1.平均空间复杂度：O（logn）
2.平均时间复杂度：O（nlogn）

3.快排是一种不稳定的排序算法
4.当数据趋近于无序时 快排的时间复杂度最优

5.快排使用了递推 因此需要栈的辅助 空间复杂度较别的算法略高
6.优化（一）

7.优化二（二）

（1）确定枢轴
（2）从最高位开始找到第一个小于枢轴的数 与枢轴交换
（3）从最低位开始找到第一个大于枢轴的数 与枢轴交换
（4）直到high=low停止 实现枢轴的坐标均小于它 右边均大于它

## 选择类排序

### 简单选择排序

A）1462 35 77 55 48 35 98
B）14 3562 77 55 48 35 98
C）14 35 3577 55 48 62 98
D）14 35 35 4855 77 62 98
E）14 35 35 48 5577 62 98
F）14 35 35 48 55 6277 98
G）14 35 35 48 55 62 7798
H）14 35 35 48 55 62 77 98

1.空间复杂度：O（1）
2.时间复杂度：O(n²)
3.简单选择排序是不稳定的排序算法

### 树形选择排序

1.时间复杂度为：O（n*logn）

### 堆排序

（1）从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大根堆。

（2）将当前无序序列中第一个元素，在树中是根节点（a）与无序序列中最后一个元素（b）交换。a进入有序序列，到达最终位置，

1.空间复杂度：O（1）
2.时间复杂度为：O（nlogn）

3.堆排序是一种不稳定的排序算法
4.由于堆排序的最差时间复杂度依然为O（nlogn） 这是堆排序最大的优点
5.它并不适用于n个数较小的情况 对于n较大的文件非常有效 如从1000000个记录中选出前10个最小的 这种情况用堆排序最好
6.堆中定义的三种操作
（1）创建大根堆（Build_Max_Heap）：将堆所有数据重新排序
（2）大根堆调整（Max_Heapify）：将堆的节点作调整，使得子节点永远小于父节点
（3）堆排序（HeapSort）：移除位在第一个数据的根节点，并做大根堆调整的递归运算
7.由于堆排序运用了子节点与父节点的关系 所以数组最好从a[1]开始存储数据 方便运算
8.堆的存储：

## 归并排序

1.空间复杂度：O（n）
2.时间复杂度为：O（nlogn）
3.归并排序是一种稳定的排序算法
4.归并排序运用了二分递归的方法实现两两排序 把两个子表合成一个总表的方法类似于单链表的合并操作
5.参加网上测试样例：对于5万个随机数 归并排序几乎不需要时间 对于20万个随机数 仅耗时62ms 而快排需要78ms

## 三大线性时间排序算法

### 计数排序

1.统计数组A中每个值A[i]出现的次数，存入C[A[i]]
2.从前向后，使数组C中的每个值等于其与前一项相加，这样数组C[A[i]]就代表了数组A中小于等于A[i]的元素个数
3.反向填充目标数组B：将数组元素A[i]放在数组B的第C[A[i]]项（即B[C[A[i]] – 1]），每放一个元素就将C[A[i]]递减

1.空间复杂度:O(n+k)
2.时间复杂度：O(n+k)–k为数据的范围

3.计数排序是一种稳定的排序算法
4.如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。

5.计数排序的时间复杂度和空间复杂度取决于数组A的数据范围(等于A中元素的最大值与最小值的差加上1)，因此对于数据范围很大的数组，计数排序需要大量时间

6.计数排序经常用作基数排序算法的一个子过程，其稳定性对于基数排序的正确性来说非常关键
7.计数排序不是比较排序，排序的速度快于任何比较排序算法

### 桶排序

1.在数组中查找数值的最大值和最小值；
2.初始化一个数组当作空桶，长度为 (MaxValue – MinValue + 1)。
3.遍历被排序数组，并把数值逐个放入对应的桶中。
4.对每个不是空的桶进行排序。
5.从不是空的桶里把数值再放回原来的数组中。

1.空间复杂度：O(k×n)
2.时间复杂度：O(n+k) （k=N(logN-logM)–N为待排数据 M为桶的数量）

3.桶排序是一种稳定的排序算法
4.当要被排序的数组中的数值是均匀分布时 桶排序的运行时间为线性时间O(n)。桶排序不是比较排序，它不受O(nlogn)下界的影响
5.在桶排序中找到正确的映射函数f(k)是关键 他可以把N个数据尽可能平均的分配到M个桶中

6.每个桶中可以根据情况使用各种排序函数 本文使用的是快排 也可以使用计数排序 堆排等等
7.桶排序算是计数排序的一种改进和推广 但是网上有许多资料把计数排序和桶排序混为一谈 其实桶排序要比计数排序复杂许多
8.代码中的结构体模拟了vector的作用 算出最大值-最小值后使用指针p动态分配空间 使得空间消耗最优

### 基数排序

1.获得值的最右侧的最小的位。
2.根据该位的值将数组内的元素值进行分组，但仍然保持元素的顺序。(以此来保持算法稳定性)
3.重复上述分组过程，直到所有的位都已被处理。

LSD 的排序方式由值的最低位也就是最右边开始,而 MSD 则相反 由值的最高位也就是最左边开始

170, 45, 75, 90, 802, 2, 24, 66

170, 90, 802, 2, 24, 45, 75, 66

802, 2, 24, 45, 66, 170, 75, 90

2, 24, 45, 66, 75, 90, 170, 802

1.空间复杂度:O(d×n)
2.时间复杂度:O(d×n)
3.基数排序是一种稳定的排序算法
4.基数排序的时间复杂度是O(ndn)，其中n是排序元素个数，dn是数字位数。这个时间复杂度不一定优于O(nlogn)，dn的大小取决于数字位的选择(比如比特位数)

5.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数，所以基数排序并不是只能用于整数排序
如果考虑和比较排序进行对照 基数排序的形式复杂度虽然不一定更小 但由于不进行比较 因此其基本操作的代价较小 而且如果适当的选择基数
dn一般不大于logn 所以基数排序一般要快过基于比较的排序 比如快速排序
6.基数排序类似于桶排序的思想 把数字按照位数放到10个桶中 每个桶中可以使用计数排序 因为在数据量较小时计数排序具有较高的效率
7.由于分块(桶)的数量是确定 所以可以使用vector来动态在每个桶中存放数字 即较少了内存消耗也减少了书写难度

## 总结

1.稳定性

2.在是三种排序算法中

3.经过一趟排序能够保证一个元素到达最终位置的是冒泡排序快速排序简单选择排序堆排序
4.元素比较次数和原始序列无关的是简单选择排序折半插入排序
5.排序趟数和原始序列有关的是交换类排序冒泡排序 快速排序）。
6.快速排序归并排序堆排序的平均时间为O(nlogn) 希尔排序复杂度为O(n^1.3)或O(n^1.5)。
7.对于选择排序 给定含n个元素的输入序列 任何比较排序在最坏情况下都需要Ω(nlogn)次比较来进行排序。

8.三种线性时间排序算法是非比较排序 在特定条件下速度快过所有比较排序
9.没有最优的排序算法 根据数据的特性以及大小选择合适的排序算法才是关键
10.最后总结下几种较优排序算法的实用情况：

希尔排序： 在中等数据量规模(n < 1000)具有较高的效率 但不稳定
快排排序: 在数据量较大且数据趋于无序时具有较高效率 但不稳定且过多递归容易爆内存
堆排序： 适用于数据量非常大的情况 最差时间复杂度依然为O(n×logn) 这是堆排序最大的优点 但不稳定
归并排序：和前三种排序算法不同的是归并排序是一种稳定的排序算法 且综合性能很强 在要求稳定性时优先使用归并排序

计数排序: 适用于数据范围较小的情况 线性时间O(n)运行 稳定 但耗空间较大
桶排序： 适用于数据是均匀分布的情况 线性时间O(n)运行 稳定 但映射函数的选择对性能的影响巨大
基数排序：线性时间O(n)运行 稳定 但数据的位数过大时不宜使用

# A Karen and Morning

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

# B Karen and Coffee

Karen, a coffee aficionado, wants to know the optimal temperature for brewing the perfect cup of coffee. Indeed, she has spent some time reading several recipe books, including the universally acclaimed “The Art of the Covfefe”.

She knows n coffee recipes. The i-th recipe suggests that coffee should be brewed between li and ri degrees, inclusive, to achieve the optimal taste.

Karen thinks that a temperature is admissible if at least k recipes recommend it.

Karen has a rather fickle mind, and so she asks q questions. In each question, given that she only wants to prepare coffee with a temperature between a and b, inclusive, can you tell her how many admissible integer temperatures fall within the range?

n个菜单，每个菜单在[l,r]区间是好的。

presum[l]++
presum[r+1]–

# C Karen and Game

The game is played as follows. In each level, you have a grid with n rows and m columns. Each cell originally contains the number 0.

One move consists of choosing one row or column, and adding 1 to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the i-th row and j-th column should be equal to gi, j.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this

# D Karen and Test

There are n integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.

Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.

The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.

Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?

Since this number can be quite large, output only the non-negative remainder after dividing it by 1e9 + 7.

# E Karen and Supermarket

On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.

The supermarket sells n goods. The i-th good can be bought for ci dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by di. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all i ≥ 2, in order to use the i-th coupon, Karen must also use the xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?