Old Book
Time limit1sMemory limit512 MB
Given that the first k pages are illustrations and the page numbers on text pages sum to s, find the minimum possible number of illustrations in the book.
- Level
Hard8 of 10
- Topics
- Math, Number theory, Greedy, Binary search
- Solved
- No attempts yet
Problem
A group of young archaeologists is working at the excavation of an ancient library building. In the summer they found the remains of an old book and, after studying them, reached the following conclusions.
The book has several pages, and each page contains either text or an illustration. The first pages of the book definitely contain illustrations. All pages of the book are numbered, but the page number is written only on pages that contain text. The sum of the numbers of the pages with text is .
Unfortunately, neither the total number of pages in the book nor the number of illustrations could be determined. Still, the young archaeologists became interested in the smallest possible number of illustrations the book could have contained.
For example, if and , the pages of the book could have the following contents ('T' denotes a page containing text, and 'I' denotes a page containing an illustration):
- I T I I I T, pages 2 and 6 are numbered, 4 illustrations;
- I I T I T, pages 3 and 5 are numbered, 3 illustrations;
- I I I I I I I T, page 8 is numbered, 7 illustrations.
The minimum number of illustrations is 3.
Write a program that, given integers and , determines the smallest possible number of illustrations in the book.
Input
The first line of the input contains the integer ().
The second line of the input contains the integer ().
Output
Output a single integer: the minimum number of illustrations in the book.