|
Let us consider, 100n + 5 = O(n). For this function there are multiple n_0 and c possible.
Solution1: 100n+5 ≤100n+n=101n≤101n,for all n ≥5,n_0=5 and c=101 is a solution.
Solution2:100n+5≤100n+5n=105n≤105n,for all n≥1,n_0=1 and c=105 is also a solution
|
|
|
|
|
Thank you for that bit of enlightenment.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
|
The difficulty of understanding when and how it began.
|
|
|
|
|
Thanks for replying!
|
|
|
|
|
But how could time "begin"? Surely that implies a transition from one state to another, which requires the concept of "time" to already exist.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
The scientists tell us it started with an enormous bang.
|
|
|
|
|
But again, "started" requires the concept of time to already exist.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Hey, I didn't invent big bang. I'm only repeating what they say happened: space and time did not exist, then they did. Go figure (as the scientists probably don't say).
|
|
|
|
|
Setting the date on my watch.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Can you please elaborate?
|
|
|
|
|
|
Time to rehash Stroustrup's computer/phone comment?
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Hello everyone,
I have been struggling since previous month about some question that I found on some university,
and I just cant think about a good way to solve it.
Please, help me to think about a way to solve this question.
The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
The question :
Quote: Vik the puffin is planning a long road trip around the circle road in Iceland, during which he wants to visit
all the landmarks along a path of length L. The tank of Vik's car can take up to F units of fuel and for every
unit of distance covered, his car consumes a unit of fuel. Using Google maps, Vik knows how far each of
the N gas stations are from the beginning of the path and the price per fuel unit each station offers. At the
starting point he has T units of fuel in his car.
1. Task
Write a program that will accept the above information and will calculate the minimum amount of money
Vik needs to spend on gas. If the journey is impossible to make, it should print -1.
2. Input
The first line contains four space separated integers:
N (0 < N < 50001): The total number of gas stations
F (0 < F < 1000001): The units of fuel Vik's car can take
T (0 <= T <= F): The units of fuel Vik's car has at the beginning of the trip
L (0 < L < 1000000001): The path length of the landmarks he plans to visit
Each of the following N lines will contain two integers: the first one, D_i (0 <= D_i <= L) corresponds
to the distance of the station from the starting point, and the second one, C_i (1 <= C_i <= 1,000,000)
represents the cost per fuel unit for that station.
Note: You may assume that the trip will be on a straight line where all gas stations are
spread on this line at the positions specified by their D_i values.
3. Output
The minimum amount of money to be spent or with -1 in case the trip is not feasible.
Note: There is a newline character at the end of the last line of the output.
4. Sample input
4 20 6 34
4 40
18 15
10 7
20 12
2
5. Sample output
348
6. Explanation
The rst line of the input is 4 20 6 34 which means that:
a. There are in total N=4 gas stations on the route
b. The (max) fuel capacity of Vik's car is F=20 liters
c. The tank currently has T=6 liters of gas
d. Vik wants to travel L=34 kms in total
Then the details for the 4 gas stations are provided in the form Di Ci, where Di is the distance of this
gas station from the starting point and Ci is the cost per liter of gas:
4 40
18 15
10 7
20 12
For simplicity assume that the whole trip is done in a straight line as depicted below:
link to show the trip from the example -> Vik The Puffin — imgbb.com[^]
Obviously Vik does not have enough fuel for all 34 kms, so he needs to refuel. The cheapest gas station is
the one labeled (B) above, however Vik does not (initially) have enough fuel in his tank to reach (B), since
B-S = 10 and he has T=6. So he needs to add an extra 4 liters from gas station A, so that he can the make
it until gas station B to get as much (cheap) as he can in order to make his 34 km journey. Thus he pays
(i) 4lt * 40$/lt = 160¿ and now he can make it until (B). Since until this moment he has only traveled
10 kms, he needs gas for another 34-10=24kms. Normally he would want to refuel his car with 24 liters
(since B is the cheapest gas station) but since his (max) fuel capacity is F=20 liters he will only take 20
liters and thus pay (ii) 20 lt * 7 $/lt = 140$. He knows however that up to point (B) he has only traveled
10kms and he needs to travel another 24kms to reach his goal, whereas he has gas for 20kms. So he would
have to stop at a later gas station (after he has traveled at least 4kms) to refuel another 4 liters of gas so
that he could complete the whole 34 kms journey. Since he now has quite some gas, he may decide whether
he wants to refuel at (C) or at (D) and since (D) is cheaper, it is more than 4kms away from (B) and is
within reach (based on his gas in the tank) he will choose to refuel another 4 liters at (D) and thus pay (iii)
4lt*12$/lt=48$). After that he can successfully reach the end point of his trip.
PLEASE HELP ME WITH THIS!
Thanks in advance!
|
|
|
|
|
Quote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
I think the most important thing is that the solution "works"; worry about performance later.
Try a flow chart.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Member 13870192 wrote: I have been struggling since previous month about some question that I found on some university, ..but mysteriously cannot link to..
It's a straightforward problem. Create a class called Vic, and have him go on each possible route, calculating the costs on the way. Select the cheapest, and done. It is a naive brute-force solution that I called "travelling Orca's". Since it resembles having an Orca in a Taxi take the actual route and phone back the results. Is as quick and efficient as the name suggests, but it works, and is a very good starting point to explain possible optimizations.
Member 13870192 wrote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible. The TSP thingy has been done to death. If you skipped class, that's your problem. You are fishing for free labor.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Member 13870192 wrote: The most important thing is that the solution has to work as fast as it can with the lowest complexity
that possible.
This question comes from a challenge site, the challenge is that you find a solution, your solution.
Your solution always start with a sheet of paper and a pencil, then you solve the problem by hand.
As you solve the problem by hand, write down how you make decisions to get to solution.
Then try the example and another order of stations in increasing order, then in decreasing order, solve by hand, compare with your procedure, improve the procedure if not optimum.
that procedure will be your program.
If you are unable to solve the problem, you will need to study data structures and algorithms.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
In particular I need tutorials on heuristic algorithms concerning graphs like pagoda function, bidirectional search etc. Also heuristic algorithms not concerning graphs. Introduction, pseudocode minimal amount of mathematics. In pdf or web page free of charge.
|
|
|
|
|
I usually only have time for one tutorial.
You will need to prioritize your requested items.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Create a block diagram or a pseudocode of an algorithm checking the balance of html tags. Include self-closing tags and tags with attributes.
I need suggestions on how to begin this task.
|
|
|
|
|
You begin by defining what you have to look for. That are - Opening tags <name[ attributes]>
- Closing tags </name>
- Self-closing tags <name[ attributes] />
Then think about how you can detect the above and what you have to do with them. For self-closing tags it is obvious that these can be simply skipped. For opening tags you have to find the corresponding closing tag and check if they are on the same level. Such can be done by pushing an open sequence onto a stack and popping upon a closing sequence after checking for identical names.
|
|
|
|
|
Read forward for an opening tag.
Locate the first closing tag that matches; if there is another "same" opening tag before the target closing, then error.
If closing found, locate next opening after previous opening and repeat; else error.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Gerry Schmitz wrote: if there is another "same" opening tag before the target closing, then error.
That's not how HTML works.
<div>
<div>
<div>
This is perfectly valid HTML.
</div>
</div>
</div>
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
<!-- You forgot a <div>! -->
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
And also:
<script>
var closingTag = "</div>";
var openingTag = "<div>";
</script> which is still perfectly balanced HTML.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|