With the end of the semester, the admins of BITS Pilani are organising their very own Book Collection Drive (BCD). After some calculations and using previous data, they have estimated that $$$N$$$ books would be donated by the students in total.
To collect the books, they would need to keep some boxes in each bhawan. Each box can hold $$$K$$$ books at max. Now the admins want to know – what is the minimum number of boxes that would be required to collect all the books?
The first and only line of input consists of two space-separated integers, $$$N$$$ $$$(1 \leq N \leq 1000)$$$ and $$$K$$$ $$$(1 \leq K \leq 100)$$$.
Print the minimum number of boxes.
10 5
2
12 5
3
In the first case, a valid distribution of books is $$$5+5$$$, hence the minimum number of boxes would be $$$2$$$.
In the second case, a valid distribution of books is $$$5+5+2$$$, hence the minimum number of boxes would be $$$3$$$.
In both cases, it can be shown that it would be impossible to collect all books with lesser boxes.
After a gruelling semester, Poku returned to his hometown for the summer break. He wanted to spend his vacations productively, so he started applying around for internships. But alas! – he had very few options for internships in the small town of Jalna. So, he was accepted into a construction company as a brick-layer.
His first project was to construct a "staircase". A staircase consists of steps each having a height strictly greater than the previous step (the first step can be of any height). Poku has $$$N$$$ equally sized bricks, and he wants to construct a staircase with maximum number of steps to impress his mentor. He doesn't necessarily have to use all the bricks.
Help Poku calculate the maximum number of steps.
The first line of input consists of a single integer, $$$T$$$ $$$(1 \leq T \leq 10)$$$, which is the number of test cases.
The next $$$T$$$ lines of input, the $$$i^{th}$$$ of which consists of a single integer, $$$N$$$ $$$(1 \leq N \leq 10^6)$$$, which is the number of bricks that Poku would have in the $$$i^{th}$$$ case.
Print $$$T$$$ lines, the $$$i^{th}$$$ line consisting of a single integer – the maximum number of steps that Poku could construct in the $$$i^{th}$$$ case.
3 1 4 6
1 2 3
My dualite fiends, and Mithil, have been crying all semester long about their tiresome courses and no time to study. So I now help them draft a schedule that they will never follow :)
There are $$$N$$$ courses that they have this semester, and for each course, they require $$$a_i$$$ lectures to binge.
Each of my fiends has a compulsive need to watch the lectures of that course first which has the most unwatched lectures. Also, the dumdums that they are, they cannot watch two consecutive lectures of the same course!
Given the array containing the lectures of each course - your task is to find out whether my fiends would be able to watch all those lectures or not!
The first line of input consists of a single number $$$N$$$ $$$(2 \leq N \leq 100)$$$ - the number of courses. I know right! 100 courses!! They do make it sound like a 100 though ;)
The second line contains $$$N$$$ space separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 1000)$$$ - the elements of array $$$a$$$ - representing the lectures of the $$$i$$$th course. Again, 1000 lectures! RR hai ye bas.
Print NO if it is not possible to watch all the lectures, otherwise print YES.
5 1 2 3 4 5
YES
5 1 2 3 4 12
NO
Shiwom is playing Elder Ning (the pirated version of PC game Elden Ring). He came across a level in the game where he has to choose a single sword from $$$n$$$ different swords and he has to fight against $$$m$$$ mighty monsters using that sword!!! To kill the $$$i$$$-th monster he can use any of the following swords - $$$L_{i}$$$-th, $$$L_{i}+1$$$-th, ...., $$$R_{i}-1$$$-th, $$$R_{i}$$$-th.
Out of the $$$n$$$ swords, Shiwom would only choose that one for his battle which is capable of killing all of the monsters. So your task is to find the number of swords which are capable of killing all the monsters.
The first line of input contains integers $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 10^{5})$$$ – the number of swords and number of monsters respectively.
Each of the next $$$m$$$ lines of input contain integers $$$L_{i}$$$ and $$$R_{i}$$$ $$$(1 \leq L_{i} \leq R_{i} \leq n)$$$ – the left and right limit of the range of swords which can kill the $$$i$$$-th monster.
Print the number of swords which are capable of killing all the monsters.
4 2 1 2 1 4
2
10 3 1 7 5 10 3 4
0
For the first sample testcase —
- To kill the $$$1$$$-st Monster – $$$1$$$-st or $$$2$$$-nd sword can be used.
- To kill the $$$2$$$-nd Monster – Any of the $$$4$$$ swords can be used.
For the second testcase —
- To kill the $$$1$$$-st Monster – Any of $$$1$$$-st, $$$2$$$-nd, $$$3$$$-rd, $$$4$$$-th, $$$5$$$-th, $$$6$$$-th and $$$7$$$-th swords can be used.
- To kill the $$$2$$$-nd Monster – Any of $$$5$$$-th, $$$6$$$-th, $$$7$$$-th, $$$8$$$-th, $$$9$$$-th and $$$10$$$-th swords can be used.
- To kill the $$$3$$$-rd Monster – $$$3$$$-rd or $$$4$$$-th sword can be used.
All the rooms of Shankar Bhawan are dirty - as they have not been cleaned since the start of the semester! Help Utkarsh clean the bhavan.
There are $$$N$$$ rooms in Shankar Bhawan - numbered from $$$1$$$ to $$$N$$$. They are laid out in a circular format - such that room $$$1$$$ is adjacent to room $$$2$$$, room $$$2$$$ is adjacent to room $$$3$$$, ... , room $$$N-1$$$ is adjacent to room $$$N$$$ and room $$$N$$$ is adjacent to room $$$1$$$.
Utkarsh has somehow managed to get $$$N$$$ sweepers to clean the hostel. Each sweeper can sweep $$$K$$$ rooms in a row, and it is guaranteed that $$$K$$$ is a factor of $$$N$$$. The $$$i^{th}$$$ sweeper can clean $$$K$$$ rooms starting from room $$$i$$$. So, they can clean $$$i$$$, $$$i + 1$$$, $$$i + 2$$$, and so on. (Note than room $$$1$$$ comes after room $$$N$$$).
Moreover, the $$$i^{th}$$$ sweeper charges $$$A_i$$$ rupees for cleaning this set of $$$K$$$ rooms.
Utkarsh wants to hire the minimum number of sweepers for accomplishing the task of cleaning all the rooms. Moreover, he wants to hire these sweepers in such a way that the amount of money he spends is also minimized!
Help Utkarsh find the minimum cost for cleaning the hostel.
The first line of input contains two integers $$$N (1 \leq N \leq 2 \cdot 10^5)$$$ - the number of rooms, and $$$K (1 \leq K \leq N)$$$, the number of rooms in a row each sweeper can clean. It is guaranteed that $$$N$$$ is a multiple of $$$K$$$.
The next line contains $$$N$$$ space-separated integers representing the cost of cleaning the rooms for each sweeper. $$$(1 \leq A_{i} \leq 10^9)$$$.
Output a single integer - the minimum cost to clean the entire hostel.
Note : The answer may exceed 32-bit data types. Consider using 64-bit data types, such as long long in C++!
6 3 2 2 1 3 2 4
4
In this case, it is optimum to hire sweepers $$$2$$$ and $$$5$$$. Sweeper $$$2$$$ will clean the rooms $$$2,3,4$$$ and sweeper $$$5$$$ will clean the rooms $$$5, 6, 1$$$. The total cost is $$$2 + 2 = 4$$$ rupees.
In IPC, an update has to be installed on all the computers. But alas! There is no internet. The only remaining way is via patch cables - one cable connecting two computers at a time.
The are $$$N$$$ computers in the IPC, and $$$K$$$ patch cables are available. Each computer has exactly one port, so, only upto one patch cable can be connected to a given computer at a time. Initially, the update is installed on the first computer only.
You have to install the update on all the computers. For any two computers connected via patch cables, an update can be transferred and installed in exactly one hour.
You have to compute the minimum amount of time required to install the update in all $$$N$$$ computers.
The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ - the number of test cases.
Each of the next $$$T$$$ lines consists of two numbers $$$N (1 \leq N \leq 10^5)$$$ and $$$K (1 \leq K \leq 10^5)$$$.
For each test case, output a single integer on a new line - the minimum number of hours required to copy the files to all $$$N$$$ computers, assuming $$$K$$$ patch cables are available.
4 8 3 6 6 7 1 1 1
4 3 6 0
In the first example, there are $$$8$$$ computers and $$$3$$$ cables. First, only $$$1$$$ computer is connected. We connect a patch cable to this computer and after one hour, another computer has received the update, making the total computers done to $$$2$$$. Then, we connect two patch cables, one to each of these computers, installing the update in $$$2$$$ more computers by the end of the second hour. Now, $$$4$$$ computers are done. Now we only have $$$3$$$ patch cables, so we connect them to any of them, and get the updated installed on $$$7$$$ computers total by the end of the third hour. The last computer can be connected in the fourth hour, making our answer equal to $$$4$$$.
This is the same problem as the previous version (problem C). The only difference is in the output - now you have to output the sequence of lectures to be watched, too.
My dualite fiends, and Mithil, have been crying all semester long about their tiresome courses and no time to study. So I now help them draft a schedule that they will never follow :)
There are $$$N$$$ courses that they have this semester, and for each course, they require $$$a_i$$$ lectures to binge.
Each of my fiends has a compulsive need to watch the lectures of that course first which has the most unwatched lectures. Also, the dumdums that they are, they cannot watch two consecutive lectures of the same course!
Given the array containing the lectures of each course - your task is to find out whether my fiends would be able to watch all those lectures or not - and if they indeed can, print a suitable order of lectures that they can watch.
Note : In case there are multiple possible solutions, print the lexicographically least one. That is, if two lectures can be chosen at the same time, choose the lecture with the lower index first.
The first line of input consists of a single number $$$N$$$ $$$(2 \leq N \leq 100)$$$ - the number of courses. I know right! 100 courses!! They do make it sound like a 100 though ;)
The second line contains $$$N$$$ space separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 1000)$$$ - the elements of array $$$a$$$ - representing the lectures of the $$$i$$$th course. Again, 1000 lectures! RR hai ye bas.
Print $$$-1$$$ if it is not possible for them to watch all lectures.
Otherwise print $$$(\sum_{i=1}^{N}a_i$$$) numbers. This array of numbers represents the order in which the lectures should be binged. The $$$i$$$th number is the index $$$(1 \leq index \leq N)$$$ of the course whose lecture should be watched next.
If there are multiple courses with the same number of lectures to be watched - the lecture of the course with the lower index should be watched first.
5 1 2 3 4 5
5 4 5 3 4 5 2 3 4 5 1 2 3 4 5
5 1 2 3 4 12
-1
Abhinav is a scientist who works in the field of perfect arrays. What's a perfect array you ask, let me explain —
A perfect array of size $$$n$$$ is made by performing $$$n$$$ perfect operations on an empty array and –
- The $$$p$$$-th perfect operation involves choosing a random integer $$$q$$$ between $$$1$$$ and $$$p$$$ $$$(1\leq q \leq p)$$$, and inserting it in the $$$q$$$-th position. So, for instance if before the $$$p$$$-th operation array was like $$$A_{1},A_{2}...A_{q-1},A_{q},A_{q+1}....A_{p-1}$$$, then after the $$$p$$$-th operation array becomes $$$A_{1},A_{2}...A_{q-1},q,A_{q},A_{q+1},A_{q+2}....A_{p-1}$$$.
Harsh wants to become Abhinav's assistant and to check Harsh's intelligence, Abhinav gives him an array $$$Arr$$$ of size $$$n$$$ and asks him if it is a perfect array or not. And if $$$Arr$$$ is a perfect array, Harsh is required to give the sequence of $$$n$$$ operations that built up $$$Arr$$$.
Harsh is too dumb to solve this and asks for your help.
The first line of input contains an integer $$$n$$$ $$$(1 \leq n \leq 200)$$$ – the size of given array.
The next line of input contains $$$n$$$ integers, $$$Arr_{1}, Arr_{2},....Arr_{n}$$$ $$$(1 \leq Arr_{i} \leq N)$$$ – the elements of given array.
If the given array is not perfect then print "NO".
Else, in the first line print "YES" and in the next line print the sequence of $$$n$$$ operations that built up the array.
3 1 2 1
YES 1 1 2
2 2 2
NO
In the first sample testcase,
- $$$1$$$-st operation – Add $$$1$$$ at $$$1$$$-st index. Array becomes $$$[1]$$$
- $$$2$$$-nd operation – Add $$$1$$$ at $$$1$$$-st index. Array becomes $$$[1,1]$$$
- $$$3$$$-rd operation – Add $$$2$$$ at $$$2$$$-nd index. Array becomes $$$[1,2,1]$$$
In the second sample testcase, there is no possible sequence of operations that can form the array $$$[2,2]$$$.