Problem Description
The pebble extraction problem is about extracting a given number of pebbles according to specific rules.
Each pebble has a specific weight, and we can extract them according to two rules:
- A pebble can be extracted if its weight is less than or equal to
X. - When a pebble is extracted, its weight becomes 0 and affects the surrounding pebbles.
Problem Input
The first line contains the number of pebbles N (1 ≤ N ≤ 100,000) and the weight limit X (1 ≤ X ≤ 10,000).
The second line lists the weight of each pebble separated by spaces. (1 ≤ weight ≤ 10,000)
Example
Input:
5 5
4 5 3 2 1
Output:
5
Problem Solving Process
To solve this problem, the following steps are needed:
Step 1: Problem Analysis
It is a problem of comparing the weights of the given pebbles.
We can select pebbles that are less than or equal to X, and we need to calculate how many pebbles we can extract.
In the given example, the pebble weights are [4, 5, 3, 2, 1] and X is 5.
Thus, there are 5 pebbles with weights less than or equal to X (i.e., 5).
As a result, we can extract 5 pebbles.
Step 2: Algorithm Design
The algorithms that can be used to solve the problem are as follows:
- Count the number of input pebbles and check the weight of each pebble.
- Count the pebbles with weights less than or equal to
X. - Finally, output the counted number.
Step 3: Kotlin Code Implementation
Below is the code implemented in Kotlin based on the above algorithm:
fun main() {
val input = readLine()!!.split(" ").map { it.toInt() }
val n = input[0]
val x = input[1]
val weights = readLine()!!.split(" ").map { it.toInt() }
val count = weights.count { it <= x }
println(count)
}
Step 4: Time Complexity Analysis
The time complexity of this algorithm is O(N).
The time complexity is determined by the number of pebbles input since we need to check each pebble’s weight.
Conclusion
The pebble extraction problem is a basic algorithm problem that involves filtering data based on conditions.
Using Kotlin allows for a concise solution to such problems and serves as good study material for practicing fundamental data processing skills.