Shaass has n books. He wants to make a bookshelf for all his books. He wants the…
- User
Shaass has n books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the i-th book is ti and its pages' width is equal to wi. The thickness of each book is either 1 or 2. All books have the same page heights.
Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.
Help Shaass to find the minimum total thickness of the vertical books that we can achieve. Input
The first line of the input contains an integer n, (1 ≤ n ≤ 100). Each of the next n lines contains two integers ti and wi denoting the thickness and width of the i-th book correspondingly, (1 ≤ ti ≤ 2, 1 ≤ wi ≤ 100).
Output
On the only line of the output print the minimum total thickness of the vertical books that we can achieve.
Examples
Input
5 1 12 1 3 2 15 2 5 2 1
Output
5
Input
3 1 10 2 1 2 4
Output
3
Assistant
We need to parse the problem carefully. We have n books, each has thickness t_i (1 or 2) and width w_i. We choose a subset of books to place vertically (standing upright). The remaining books are placed horizontally on top of the vertical ones, i.e., lying flat. In the horizontal orientation, the books occupy space in terms of their width (the dimension that would be vertical if placed vertically). Actually we need to interpret dimensions.
We have a bookshelf: likely a rectangular space. The vertical books are placed with their thickness contributing to the total width (or depth) of the shelf? Let's refer to the figure. Typically, when you place a book vertically (spine out), its thickness contributes to the horizontal width of the shelf that it occupies (like on a bookshelf, books are placed side by side, with their spines facing outward, so the total width needed is the sum of thicknesses of vertical books). When you place a book horizontally on top of the vertical ones, you lay it flat, so its width (the length of the book cover) is placed horizontally? Actually typical scenario: Consider a shelf of fixed depth and height. You have books that you can either stand upright (vertical) or stack horizontally on top of the upright ones, lying flat. The vertical books occupy the height of the shelf? Wait, let's think: In the given figure (which we cannot see), but likely it shows some books standing vertically side by side, and then some books placed horizontally on top of them, spanning across the vertical ones. The horizontal books' width (which is the larger dimension? Actually typical book: thickness is small (1-2), width (the length from left to right when standing) is larger (like the width of the pages). In the vertical orientation, the book stands on its bottom edge, so its thickness (the spine width) is the horizontal extent it occupies on the shelf, and its height (the page height) is vertical, which is the same for all books. In the horizontal orientation, the book is laid flat, so its thickness becomes vertical? Actually if you lay a book flat, you put it on its cover, so its width (the length from left to right when standing) becomes the horizontal extent? Let's imagine: Book dimensions: thickness (say depth of spine), width (the horizontal dimension when standing upright, i.e., the length of the cover from left to right), height (vertical). When placed vertically on a shelf, the height is vertical, the width is horizontal, and the thickness is depth (into the shelf). However, in the problem, it seems we only care about the horizontal space (the total thickness of vertical books) and the sum of widths of horizontal books must be no more than the total thickness of vertical books. That suggests that the horizontal books are placed on top of the vertical ones, and they extend horizontally across the vertical ones, and their total width (the sum of their widths) must fit within the total thickness (i.e., the horizontal space occupied by the vertical books). Actually think: We have a shelf with some depth. The vertical books are placed side by side; their total thickness (sum of t_i for vertical books) is the horizontal length they occupy (like the shelf width). Then we place horizontal books on top of them (stacked). These horizontal books are lying flat, so their width (which is the dimension that would be horizontal if they were standing) is now placed horizontally, but they need to be supported by the vertical books. Specifically, each horizontal book spans across the vertical books; the condition is that the sum of the widths of all horizontal books (i.e., total width if you lay them side by side? Actually they could be stacked? Wait, the figure might show multiple horizontal books stacked on top of each other? The text: "Then he puts the rest of the books horizontally above the vertical books." It says "above the vertical books", which suggests they are placed on top of the vertical books, maybe stacked? But the condition: "The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books." That suggests that the horizontal books are placed side by side? Or maybe they are stacked, but the total width of all horizontal books (i.e., if you put them side by side) cannot exceed the total thickness? But they are placed above the vertical ones, so they are not side by side; they are on top. I'm trying to interpret.
Typically, in such problems (like "Shaass and Bookshelf" from Codeforces), the condition is: The sum of widths of horizontal books must be ≤ sum of thicknesses of vertical books. The idea: When you place a book horizontally, you lay it flat so that its width rests on the vertical books. The vertical books provide a base of total thickness (width). If you put multiple horizontal books, they can be stacked, but the base's total thickness must support their total width? Actually if you stack them, each horizontal book rests on the ones below; the bottommost horizontal book rests on the vertical books. So the condition is that the total width of all horizontal books (i.e., sum of their widths) must be ≤ the total thickness of vertical books. That seems plausible: The vertical books form a foundation; the horizontal books are placed on top, and the total width (i.e., the sum of their widths) must be supported, meaning the foundation must be at least as wide as that total width. But why sum? Usually if you place books horizontally stacked, the pressure distributes; the bottom book's width is the one that needs support. However, if you stack them, each higher book rests on the one below, so the bottom horizontal book supports all above it. So the total width of all horizontal books doesn't need to be ≤ the foundation width; only the width of the bottom one matters. So maybe they are placed side by side on top of the vertical books, i.e., horizontally placed books are also placed next to each other horizontally (like in a row) on top of the vertical books. But then they would occupy additional horizontal space beyond the vertical books? That seems odd.
Let's search memory: This is Codeforces problem 294B (Shaass and Bookshelf). I recall that problem: There are n books, each with thickness t_i (1 or 2) and width w_i. Choose some to place vertically (standing) and the rest horizontally (lying). The horizontally placed books lie on top of the vertical ones. The condition: The total width of the horizontal books must be <= the total thickness of the vertical books. The goal: minimize the total thickness of the vertical books. So the interpretation: The vertical books stand side by side, their total thickness is the width of the shelf they occupy (which we want to minimize). The horizontal books are placed on top, they rest on the vertical books, so they don't occupy extra width, but their widths must be supported: the sum of widths of all horizontal books must not exceed the total thickness of the vertical books, because perhaps the horizontal books are placed side by side in a single layer on top? Or they could be stacked? The phrase "sum of the widths of the horizontal books must be no more than the total thickness of the vertical books" implies that if you place them horizontally, they occupy some of the width of the vertical base, and the total width they require (if placed side by side) must fit within the base width. However, they are placed above, so they could be arranged in multiple layers? But the sum condition would then be like the total area of the horizontal books' widths? Hmm.
I think typical solution: It's a knapsack-like DP. Because we want to minimize sum of thickness of vertical books subject to sum of widths of horizontal books <= sum thickness of vertical books. Since thicknesses are 1 or 2, we can do DP on total thickness of vertical books. Equivalent to: choose a subset V (vertical) such that sum_{i in V} t_i is at least sum_{i not in V} w_i (since sum of widths of horizontal books = total width sum of all books minus sum_{i in V} w_i? Actually careful: The horizontal books are the complement. Their total width = sum_{i not in V} w_i. The condition: sum_{i not in V} w_i <= sum_{i in V} t_i. We want to minimize sum_{i in V} t_i.
Yes! That is exactly the problem: We have books, each with t_i and w_i. Choose some to be vertical (V). Then the condition: total width of horizontal books (which are the rest) must be <= total thickness of vertical books. That is sum_{i in H} w_i <= sum_{i in V} t_i, where H = complement. And we want to minimize sum_{i in V} t_i. Equivalent to: minimize T = sum_{i in V} t_i subject to sum_{i not in V} w_i <= T.
Let total width of all books W_total = sum all w_i. Then sum_{i not in V} w_i = W_total - sum_{i in V} w_i. So condition becomes: W_total - sum_{i in V} w_i <= sum_{i in V} t_i => W_total <= sum_{i in V} (t_i + w_i). Actually careful: W_total - sum_{V} w_i <= sum_{V} t_i => W_total <= sum_{V} (t_i + w_i). But that seems weird because t_i + w_i might be large.
Alternatively, we can think: we need to select subset V such that sum_{V} t_i >= total_width - sum_{V} w_i. Rearranged: sum_{V} (t_i + w_i) >= total_width.
But the typical approach: Since n <= 100 and t_i <= 2, w_i <= 100, we can do DP on total thickness. We want smallest T such that there exists subset V with sum t_i = T and sum w_i for that subset is at least something. Actually condition: sum_{i in V} t_i >= sum_{i not in V} w_i = W_total - sum_{i in V} w_i. So sum_{i in V} (t_i + w_i) >= W_total. Equivalent to: sum_{i in V} (t_i + w_i) >= W_total. But note t_i + w_i can be up to 102. So we can also do DP on sum of (t_i + w_i). But the typical solution: Because t_i is small, we can treat it as a knapsack to maximize total width of vertical books for a given total thickness? Let's derive.
We want to minimize T (sum t_i for vertical) subject to T >= W_total - sum_{V} w_i => sum_{V} w_i >= W_total - T. So for a given T, we need to check if there exists subset V with sum t_i = T (or possibly <= T? Actually we are picking exactly V, but we can also have vertical books with total thickness T, but condition is T >= W_total - sum_V w_i. If we have T larger than needed, it's okay as long as condition holds. But we want to minimize T, so we can consider possible V and compute T. But perhaps we can treat as DP: For each possible total thickness T (from 0 to maybe 2n), we compute the maximum possible total width sum_{V} w_i that can be achieved with a subset of books having total thickness exactly T (or at most T). Then condition for T being feasible is: max width sum for thickness exactly T (or <= T) is >= W_total - T. Actually careful: If we choose V with thickness exactly T, then the condition is sum_V w_i >= W_total - T. If we choose V with thickness less than T, we could add extra books as vertical? But we wouldn't add extra because we want minimize T, so we consider exactly T. But we could also consider subsets with thickness less than T and then add dummy books? No, we must select some subset, thickness sum can be any integer within constraints, not necessarily every integer reachable. So we need to test if there exists subset V with sum t_i = T and sum w_i >= W_total - T. If we find minimal T for which such a subset exists, that's the answer.
Alternatively, we can treat it as: maximize sum_V w_i for a given sum t_i, and then check condition. Since t_i are 1 or 2, we can do DP of size up to 200. n=100, max total thickness = 200. We'll compute dp[t] = maximum total width achievable from a subset with total thickness exactly t. Initialize dp as -inf, dp[0]=0. For each book (t_i, w_i), we update dp in reverse for t from max down to t_i: dp[t] = max(dp[t], dp[t - t_i] + w_i). After processing all books, for each t from 0..200, we have the max width for thickness exactly t. Then we need smallest t such that dp[t] >= W_total - t. But is it necessary that the subset used for dp[t] is the vertical set? Yes. But careful: The condition is sum_V w_i >= W_total - t. However, we must also ensure that the subset we consider doesn't overlap? No, dp[t] gives max sum of w_i for any subset with thickness exactly t. That subset could be any books. Then the remaining books are horizontal with total width = W_total - sum_V w_i. Condition: W_total - sum_V w_i <= t. So sum_V w_i >= W_total - t. So if dp[t] >= W_total - t, then there exists a subset V with thickness t that satisfies condition. But note: dp[t] is the maximum width we can get for that thickness; if the max is enough, then there is some subset that meets the condition. Conversely, if the max is not enough, no subset with that thickness can meet it (because all subsets with that thickness have width <= dp[t] which is less than needed). So this works.
But is it possible that a subset with thickness less than t could satisfy condition but we consider t larger? We are looking for minimal t, so we iterate t from 0 upward and check. However, we must also consider that we might not be able to achieve certain t values exactly. But minimal t could be 0? Only if we choose no vertical books, but then condition: sum of widths of horizontal books (all books) <= 0, which impossible unless all w_i=0 (but w_i>=1), so not. So answer at least 1.
So DP is straightforward.
But wait: there is a nuance: The condition is "The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books." That's exactly as used. But is there any consideration about the vertical books' heights? No, all books have same page height. So they can all stand vertically, that's fine.
Edge cases: DP size: max thickness = sum of all t_i <= 200. But we also need to consider that some t might be unreachable; dp[t] = -infinity initially. We'll set dp[0]=0, and others = -1 (or -large). We'll update using typical unbounded? Actually each book once. So it's 0-1 knapsack.
We can also incorporate that we might allow vertical books with total thickness > required? The DP is exactly for a given thickness, we consider subsets. The condition uses t itself, so if we get a subset with thickness t that yields width sum w, then condition is w >= W_total - t. So if we have a subset with thickness t that meets condition, then that t is feasible. The minimal t over all feasible t is answer.
But what about subsets where thickness is less than some t but we could add extra vertical books that increase thickness and also width? But that would increase t, so if we want minimal t, we wouldn't add extra if not needed. So fine.
So algorithm:
- Read n.
- Collect books: arrays t[i], w[i].
- Compute total_width = sum w[i].
- Let max_thickness = sum t[i] (max possible vertical thickness if we put all books vertical).
- Initialize dp array of size max_thickness+1 with -inf (maybe -1e9). dp[0] = 0.
- For each book i from 1 to n: for thickness from max_thickness down to t[i]: if dp[thickness - t[i]] != -inf: dp[thickness] = max(dp[thickness], dp[thickness - t[i]] + w[i])
- Then iterate t from 1 to max_thickness: if dp[t] >= total_width - t: answer = t; break.
- Print answer.
But is there any scenario where we might need to consider t beyond max_thickness? No, because total vertical thickness can't exceed sum of all t_i. However, could answer be larger than max_thickness? That would imply that we need to put all books vertical and still condition not satisfied? Let's think: If we put all books vertical, then horizontal set is empty, sum of widths of horizontal books = 0, condition 0 <= total thickness (which is sum t_i). So condition holds. So answer always <= sum t_i. So answer is within range.
Thus solution is straightforward.
But wait: Is there any nuance about the sum of widths of horizontal books being no more than total thickness of vertical books? That condition we used is sum_{i in H} w_i <= sum_{i in V} t_i. But is that correct? Let's read problem statement: "He puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books." Yes.
Thus condition: sum_{i not in V} w_i <= sum_{i in V} t_i.
Now, is there any other constraint? For example, the horizontal books are placed above the vertical ones, so they must be placed in a way that the vertical books support them. Could it be that the sum of widths of horizontal books is not simply sum, but perhaps the maximum width? The phrase "sum of the widths" indicates it's sum.
Thus solution is correct.
Now, check examples:
Example 1: 5 1 12 1 3 2 15 2 5 2 1
Compute total_width = 12+3+15+5+1 = 36. t values: 1,1,2,2,2 sum = 8. DP: We need minimal t such that dp[t] >= 36 - t. Let's compute manually? They answer is 5. Let's test: t=5, we need dp[5] >= 31. Can we get dp[5] >=31? Possibly by selecting books with thickness 5 (maybe 2+2+1 or 2+1+1+1?) and maximizing width sum. Check: Books: (1,12), (1,3), (2,15), (2,5), (2,1). To achieve thickness 5, we can pick (2,15)+(2,5)+(1,12) => thickness=5, width=15+5+12=32 >=31. So t=5 works. t=4? Need dp[4]>=32. Can we get thickness 4 with width sum >=32? Options: (2,15)+(2,5)=4, width=20 <32. (2,15)+(1,12)+(1,3)=4? that's 2+1+1=4, width=15+12+3=30 <32. (2,15)+(1,12)+(? Actually two 2's? Already done. (2,5)+(1,12)+(1,3)=4? 2+1+1=4 width=5+12+3=20. (2,15)+(2,1)+(? ) width 16. So max perhaps 30. So t=4 fails. t=3? need dp[3]>=33. Max width for thickness 3: can be (2,15)+(1,12)=3 width=27 <33; (2,15)+(1,3)=18; (2,5)+(1,12)=17; (1,12)+(1,3)+(1?) only two ones? Actually we have three ones? There are two ones: 12 and 3. So can't do three ones. So max maybe 27 <33. So answer 5 correct.
Example 2: 3 1 10 2 1 2 4 total_width=15? 10+1+4=15. t sum=1+2+2=5. Check t=3? need dp[3]>=12. Can we get thickness 3 with width sum >=12? Options: (1,10)+(2,1)=3 width=11 (<12); (1,10)+(2,4)=3 width=14 >=12. So yes, t=3 works. t=2? need dp[2]>=13. Options: (2,1) width=1; (2,4) width=4; (1,10)+(1?) only one 1? Actually we have only one 1-thickness book, can't get thickness 2 from two ones. So max width for thickness 2 is 4 <13. t=1? need dp[1]>=14, not possible. So answer 3, matches.
Thus DP works.
Complexity: O(n * total_thickness) ≤ 100 * 200 = 20000, trivial.
Implementation details: We'll use -1 to indicate unreachable, but careful: width sums are non-negative, so -1 is fine as unreachable. Then dp[t] = max(...). For update: if dp[prev] != -1, then candidate = dp[prev] + w_i. Compare.
But note: It's 0-1 knapsack, so loop backward.
Edge: There might be multiple books with same t, w; fine.
Answer always exists because at t = total_thickness (all vertical) we have dp[total_thickness] = total_width? Actually if all books are vertical, then sum_V w_i = total_width, condition becomes total_width - total_thickness <= total_thickness => total_width <= 2total_thickness, which is always true? Not necessarily: total_width could be > 2total_thickness? But t_i are 1 or 2, so total_thickness is at least ceil(n) and at most 2n. w_i can be up to 100, so total_width could be up to 100*n. So it's possible that for all books vertical, the condition is total_width <= total_thickness? Wait condition: horizontal books sum width <= vertical thickness. If all are vertical, horizontal sum = 0, so condition 0 <= total_thickness is true. So always satisfied. So answer always ≤ total_thickness. So we can iterate t from 1 to total_thickness.
But careful: In the all-vertical case, the set of vertical books is all books, so horizontal set empty, condition holds. So answer is defined.
Thus we can compute DP, then find minimal t.
But there is also a possibility that we could have vertical books set empty? That would require total_width <= 0, impossible since w_i>=1. So t must be at least 1.
Thus solution is done.
Now the problem statement says: "Help Shaass to find the minimum total thickness of the vertical books that we can achieve." So answer is as computed.
Now check constraints: n up to 100, w up to 100, t up to 2.
We'll code accordingly.
Potential pitfalls: The DP array size should be up to 200, but we can also set to 201. Or we can compute sum_t = sum(t_i). But note that sum_t can be at most 200. So safe.
We'll implement.
However, there might be a nuance: The DP for exact thickness t might not consider subsets where thickness is not exactly t but condition holds with that thickness? Actually we need to consider subsets with thickness exactly t because t is the total thickness of vertical books. If a subset has thickness less than t, that would correspond to a different t (smaller). So we only need exact t.
But what if there exists a subset with thickness less than t but we consider t as vertical thickness because we could include extra vertical books that have thickness but also increase t, but they also increase w_i? Actually if we add an extra book as vertical, it increases both thickness and width sum. Condition: sum_V w_i >= total_width - t. If we start with a subset that works at thickness t0, and we add an extra vertical book (which was originally horizontal?), wait we cannot add a book that is not already vertical; the vertical set is exactly the set we choose. So the vertical thickness is exactly sum of t_i for that set. So if we add another book to the set, we increase thickness and also possibly add its w_i to sum_V, which changes the condition. So we need to check each possible vertical set. Our DP enumerates all subsets by thickness; for each thickness, we compute max sum_V w_i. That's enough to check feasibility.
Thus algorithm correct.
Now we can also approach using DP on total width sum, but we already have solution.
We'll code in C++ for the solution.
But there is a twist: The problem might be known as "Shaass and Bookshelf" and there is also a solution using DP on sum of widths or using two-dimensional DP due to t_i=1,2. But our DP is simple.
Now confirm that DP for exactly thickness is correct: We need to ensure that dp[t] is the maximum width sum for exactly thickness t. However, in the typical knapsack for exactly weight, we initialize dp[0]=0, others = -inf. Then for each item, we update dp[t] = max(dp[t], dp[t-t_i] + w_i) only if dp[t-t_i] is reachable. This yields the best width for exactly that weight.
Now find minimal t where dp[t] >= total_width - t.
We must also consider that dp[t] might be -1 (unreachable), so we skip.
Now we need to output answer.
Let's test with the examples.
Example 1: total_width=36, sum_t=8.
DP compute: We'll run loop.
We can manually confirm answer 5.
Now test with a possible edge case: n=1, t=1, w=5. total_width=5. Then only possible vertical set: either book vertical or horizontal. If vertical: thickness=1, condition: horizontal sum=0 <=1, ok. So answer=1. DP: dp[1] =5? Wait dp[1] = w=5 because that's the width of vertical book? Actually if we choose that book as vertical, then its w_i is included in dp[1]. Then condition: total_width - t = 5 - 1 =4, dp[1]=5 >=4, so t=1 works. So answer 1. That's correct.
If n=1, t=2, w=5: total_width=5, dp[2]=5, condition: total_width - t =5-2=3, dp[2]=5>=3, so answer=2? But could we choose no vertical? horizontal would be 5 <=0 false. So answer 2. That's correct.
Now another scenario: two books: (t=1,w=100) and (t=2,w=1). total_width=101. Options: vertical both: t=3, dp[3]=101? Actually vertical both includes both, sum w =101, condition: total_width - t =101-3=98, dp[3]=101>=98 -> t=3 works. But maybe vertical only the first: t=1, w=100, condition: 101-1=100, dp[1]=100>=100 works? 100 >=100 yes, so t=1 works. vertical only second: t=2, w=1, condition: 101-2=99, dp[2]=1 <99 fails. So answer=1. DP would find t=1 dp[1]=100, check 100>=100 -> answer 1. Good.
Edge: total_width - t could be negative? Possibly if t > total_width. But total_width can be up to 100100=10000, t max 200, so it's positive usually, but could be negative if t > total_width? Actually total_width is sum of w_i, w_i >=1, so total_width >= n >=1. t max 200, n max 100, total_width could be as low as n1=100, so t max 200 > total_width possible? For n=100, each w_i could be 1, total_width=100, t could be up to 200. So total_width - t could be negative. But condition dp[t] >= negative number is always true if dp[t] is reachable (since widths are non-negative). However, minimal t might be less than total_width, but we still need to check. But if t > total_width, condition automatically satisfied because sum_V w_i is at least 0, and total_width - t is negative. So any such t is feasible. But we seek minimal t. So we must consider that for large t, condition holds automatically. But our DP will only consider t where dp[t] is reachable. The smallest t that is reachable might be 1, but condition may not hold for small t; we must go up until condition holds. However, there might be gaps: some t unreachable, but a larger t reachable. That's fine. Since at t = sum_t (all books vertical) is always reachable (dp[sum_t] = total_width). And condition for t = sum_t: total_width - t <= t? Actually condition is total_width - t <= t => total_width <= 2t. For t = sum_t, is it always true? sum_t is sum of t_i, total_width could be large, but the condition is about the specific vertical set? Wait: For vertical set = all books, sum_V w_i = total_width, so condition: total_width - sum_t <= sum_t => total_width <= 2*sum_t. This is not automatically true. For all books vertical, horizontal set is empty, so sum of widths of horizontal books = 0. Condition is 0 <= sum_t, which is always true. Wait, I'm mixing: Condition is sum_{horizontal} w_i <= sum_{vertical} t_i. For vertical = all books, horizontal = empty, sum_{horizontal} w_i = 0, condition 0 <= sum_t is true. So it's always satisfied regardless of total_width. So t = sum_t is always feasible. Actually check: If vertical set = all books, then horizontal set is empty, so the sum of widths of horizontal books = 0, condition is 0 <= total thickness of vertical books, which is true because thickness sum >= 1. So indeed t = total thickness of all books always works. So answer always <= total_thickness. So we can iterate up to total_thickness.
Now condition for DP: For a given t, we have a particular vertical set, not necessarily all books. The condition uses t and the width sum for that set. For vertical set being all books, t = total_thickness, and width sum = total_width. Then condition becomes: total_width - total_thickness <= total_thickness? Actually careful: sum_{horizontal} w_i = total_width - sum_V w_i. If V = all books, sum_V w_i = total_width, so sum_{horizontal}=0, condition holds. So no need to check total_width <= 2*t. That's a different expression I mistakenly derived earlier. So condition always holds for all-vertical case.
Thus answer exists.
Now complexity fine.
Now we need to print answer.
We should also consider that dp[t] is maximum width sum for exactly t. But there might be cases where we can achieve a larger width sum with thickness less than t, but that doesn't help for that t. So fine.
Now let's implement.
Pseudo:
int main() { int n; cin >> n; vector t(n), w(n); int sum_t = 0, sum_w = 0; for (int i=0; i<n; ++i) { cin >> t[i] >> w[i]; sum_t += t[i]; sum_w += w[i]; } vector dp(sum_t+1, -1); dp[0] = 0; for (int i=0; i<n; ++i) { for (int j=sum_t; j>=t[i]; --j) { if (dp[j - t[i]] != -1) { dp[j] = max(dp[j], dp[j - t[i]] + w[i]); } } } int ans = sum_t; // maximum possible for (int j=0; j<=sum_t; ++j) { if (dp[j] != -1 && dp[j] >= sum_w - j) { ans = j; break; } } cout << ans << endl; return 0; }
But wait: We need to ensure that the subset we choose for dp[j] is indeed the vertical set. In the condition, we use sum_V w_i = dp[j] (max width). However, if dp[j] is not exactly the width sum of the vertical set, but the max possible width for that thickness. If the max width is >= sum_w - j, then there exists a subset with that thickness meeting the condition. If the max width is less, no subset can meet it because all subsets have width <= max width. So correct.
Now one nuance: The dp we computed yields maximum width sum for exactly thickness j. But what if the maximum width is achieved by a subset that is not necessarily the one we want? Actually any subset with width sum at least sum_w - j will work. If max width is enough, then at least one subset works. So we are good.
Now we must ensure we consider the vertical set exactly as the selected books. There's no requirement that the vertical books must be placed in some order, etc.
Thus solution is fine.
Let's test some custom cases.
Case: n=2; (t=1,w=5), (t=2,w=5). sum_w=10. sum_t=3. DP: init dp[0]=0. Process first book (1,5): dp[1]=5. Process second book (2,5): update from high: j=3: dp[3] = max(dp[3], dp[1]+5=10) => dp[3]=10. j=2: dp[2] = max(dp[2], dp[0]+5=5) => dp[2]=5. Now dp[1]=5, dp[2]=5, dp[3]=10. Check j=1: dp[1]=5 >= 10-1=9? 5>=9 false. j=2: 5 >= 8? false. j=3: 10 >= 7? true. So ans=3. But is there a better? Could j= ? maybe we could put both vertical: t=3 works. Could we put only first vertical: t=1, condition: horizontal sum = w2=5, need 5 <= 1? false. Only second vertical: t=2, horizontal sum = w1=5, need 5 <=2 false. So indeed t=3 minimal. So ans=3 correct.
Case: n=2; (1,1), (1,2). sum_w=3, sum_t=2. dp[0]=0. First (1,1): dp[1]=1. Second (1,2): j=2: dp[2]=dp[1]+2=3? Actually dp[2] from dp[1]+2 =1+2=3. Also j=1: update dp[1]=max(1, dp[0]+2=2) => dp[1]=2. Now dp[1]=2, dp[2]=3. Check j=1: dp[1]=2 >= 3-1=2? 2>=2 true => ans=1. So answer=1. Which vertical set gives t=1? We need a subset with thickness 1 and width >=2. The vertical book could be the second one (w=2) gives t=1, width=2, then horizontal book is first with w=1, condition: 1 <= 1, true. So answer 1 correct.
Thus solution works.
But what about case where we might need to consider not using all books? Already covered.
Now we need to output the answer.
Implementation note: Since we are using int, dp values can be up to total_width <= 10000. So fine.
Now confirm constraints: n up to 100, t up to 2, so sum_t up to 200. So dp array size 201.
Now we should consider that we need to break at the smallest j that satisfies condition. We start from j=0? j=0 is unreachable? Actually dp[0] = 0, but condition: sum_w - 0 = sum_w, dp[0]=0 >= sum_w? only if sum_w=0, but not. So ignore j=0.
Now code.
But I recall there is also a known solution using DP on sum of widths, but this is simpler.
Now double-check: The condition is sum of widths of horizontal books ≤ total thickness of vertical books. In our formulation, horizontal books are the complement. So we used that. However, we must be careful: The horizontal books are placed above the vertical books, and their widths are summed. The vertical books are standing. The condition is as we used.
Thus answer.
Now we can produce final solution.
But wait: The problem statement may have an alternative interpretation: The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. However, the horizontal books are placed above the vertical books, maybe they are stacked? If they are stacked, the condition might be that the sum of widths of all horizontal books (i.e., the total width if placed side by side) does not exceed the total thickness, which is the same as we used. So fine.
Thus final answer.
Now I'll produce final answer with explanation.
But the user asked: "We need to provide the final answer." Possibly the expected output is just code. Since it's a coding problem, we should provide the solution.
But the user said: "We need to parse the problem and provide solution." The assistant should respond with a solution in C++? Typically, the system expects a solution explanation and code. Since it's a coding problem, we can provide code.
But I'm ChatGPT, and I need to output final answer. The instruction: "We need to parse the problem and provide solution." So I'll write a thorough explanation and then provide C++ code.
Given the conversation, I'll produce final output with code.
But the instruction might be to just output the answer? Actually the user says: "We need to parse the problem and provide solution." It's ambiguous. In this context, the assistant likely should provide a solution description and code.
However, as per the meta-instruction: "You are ChatGPT ... provide the final answer." The final answer should be the solution code and explanation. I'll produce a complete solution.
Thus final. We need to minimize the total thickness of vertical books such that the sum of widths of horizontal books does not exceed that thickness.
Let (V) be the set of books placed vertically. Then the condition is[ \sum_{i \notin V} w_i \le \sum_{i \in V} t_i. ]
If total width (W = \sum w_i), this becomes
[ \sum_{i \in V} w_i \ge W - \sum_{i \in V} t_i. ]
For a fixed total thickness (T = \sum_{i \in V} t_i), we need a subset with that (T) whose total width is at least (W - T).
We can compute for each possible (T) the maximum total width achievable with exactly that thickness (0‑1 knapsack). Then the smallest (T) with (\text{dp}[T] \ge W - T) is the answer.Thickness values are only 1 or 2, so (T \le 200). Complexity is (O(n \cdot \text{sum } t_i) \le 20000), well within limits.
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> t(n), w(n); int sumT = 0, sumW = 0; for (int i = 0; i < n; ++i) { cin >> t[i] >> w[i]; sumT += t[i]; sumW += w[i]; } vector<int> dp(sumT + 1, -1); dp[0] = 0; for (int i = 0; i < n; ++i) { for (int j = sumT; j >= t[i]; --j) { if (dp[j - t[i]] != -1) dp[j] = max(dp[j], dp[j - t[i]] + w[i]); } } int ans = sumT; // worst case: all books vertical for (int T = 1; T <= sumT; ++T) { if (dp[T] != -1 && dp[T] >= sumW - T) { ans = T; break; } } cout << ans << endl; return 0; }