Блог пользователя kingofnumbers

Автор kingofnumbers, 11 лет назад, По-английски

there is two countries A and B, the distance between them is 1200 km.

there is a company in country A wants to transport some goods to country B, so the company decided to hire a number of planes, each plane has a tank with Capacity 60 Liters initially all tanks are full of fuel, one liter of fuel can transport a plane only 10km.

unfortunately, a plane with full tank can fly 600km which is not enough to travel to country B.

a plane can be used to help another plane with fuel , if two planes are in the same point one plane can transfer any number of liters of fuel from its tank to the other plane's tank while they are in air ,take care that all planes must back safety to airport in country A before their tanks is empty, expect one plane should travel to country B.

help the company to find a strategy that transport goods to country B using minimum number of planes since hiring a plane is too expensive.

notes:

1- a plane cannot be used more that once so when a plane back to airport in country A cannot be used again.

2- one plane is enough to hold all goods so only one plane should arrive to country B.

3- if plane2 wants to transfer fuel to plane1 , both plane1 and plane2 need to be in the same distance from country A .

4- tank of a plane cannot hold more than 60 liter at any time

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Answer is 3 .

try to divide whole circle at r/6 if r is radius.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    impossible to do it using 3 planes, maybe my english is very bad.

    the plane that transport good don't need to back to country A but the other planes that help with fuel should back to country A .

    if you are sure ,can you tell the details of your solution?

»
11 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

If a plane transfer fuels to another plane at distance x from country A, then the maximum fuel it can transfer is 60 - (2 / 10) * x, and the plane that gets to country B needs an additional 60 liters of fuel. So, if the planes must leave country A before transferring fuel to another plane, then the answer is 3. Otherwise, the answer is just 2.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if plane2 wants to transfer fuel to plane1 , both plane1 and plane2 need to be in the same distance from country A

    in addition, tank of a plane cannot hold more than 60 liter at any time ,so tank of plane that will travel to B will overflow

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Ahhhhhhh, you're right. I hadn't considered that the fuel of a plane can't exceed 60 liters at any time...

      For the sake of simplicity, let's change the problem statement so that the planes can hold up to 600 liters and each liter allows a plane to travel 1 km.

      Now, let's consider the following plan:

      • N planes start at position 0, and at each step, they travel x kms, then half of them transfer fuel to another plane so that after all transfers are done, half of the remaining planes have a full tank, and the other ones return to country A.

      At any step, the planes are at distance d from country A, and they travel x kms before transferring T units of fuel to another plane. Furthermore, we want half of the remaining planes to have a full tank after the transfers, so T = x, and the other planes must return to country A, so 2d + x + T <  = 600, then the maximum value x can take is obtained by the following equation: 2x + d + T = 3x + d = 600 => x = (600 - d) / 3.

      Now, let's simulate the process and see what that yields for each step...

      • Step 1: N planes at distance 0.
      • Step 2: N / 2 planes at position 200.
      • Step 3: N / 4 planes at position 333,33.
      • Step 4: N / 8 planes at position 422,22.
      • Step 5: N / 16 planes at position 481,48.
      • Step 6: N / 32 planes at position 520,98. ... ... ...
      • Step 16: N / (215) planes at position 598,63.
      • Step 17: N / (216) planes at position 599,08. ... ... ...
      • Step 50: N / (249) planes at position 599,999998588. ... ... ...

      As we can see, the position of the planes with full tanks will tend to 600, but never reach it, so from this analysis, we could assume that it's impossible to reach country B, but... with a little more careful analysis and this procedure in mind, we can arrive to the following solution...

      • 8 planes start at position 0.
      • At position 200, 4 of them recharge the others and return to Country A.
      • The remaining 4 advance to position 400 and 2 of them (planes p and q) recharge the other 2 to full capacity and return to position 200.
      • Two extra planes travel from 0 to 200 and give 200 units of fuel to planes p and q, then they all return. So far we have used 10 planes.
      • The two planes at 400 travel to 600 and one of them (plane r) recharges the other one (plane k) and then returns to position 400. Plane k can now reach Country B.
      • Two extra planes start at position 0, travel to 200, one of them gives 200 units of fuel to the other one (plane s) and returns. 12 planes have been used so far.
      • Plane s, now at 200, travels to 400 to meet with plane r, it gives 200 units of fuel to it and they both return to 200.
      • Two extra planes start at position 0, travel to 200, give 200 units of fuel to planes r and s, and they all return.

      14 planes have been used in this solution. Maybe there's a better one, I'd like to know.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        that exactly my solution , I also wanted if there is a better solution.

        the main idea that the best partition of the way from A to B is to divide it to 6 parts

        thank you anyway :)

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Well it's not possible to do with any ammount of planes. Unless you can put a plane inside in a plane. If it is possible, would you explain how to do it with 100 planes?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    statment of problem didn't mention that you can put a plane inside another plane, however there exist a solution.

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

If I understood the problem correctly, I can do it using 16 planes (our plane with goodies and 15 additional planes).

Using this sequence we can transport one plane to the distance of 400 km with 60 liters of fuel, using 4 additional planes, which will return to country A at the end. Fuel transfers are colored.

Then we can transport 3 planes using this sequence and finish like this:

PS Sorry for my bad English.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You can improve your solution to become using only 14 planes , you don't need 3 planes to arrive to x=400 with full tanks it's enough for the third plane to hold 40 liters when arriving to x=400.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

As I said in a reply earlier, I arrived to this solution, which might not be optimal.

  • 8 planes leave from Country A and advance to position 200.
  • At position 200, 4 of them recharge the others to full capacity and return to Country A.
  • The remaining 4 advance to position 400 and 2 of them (planes p and q) recharge the other two to full capacity and return to position 200.
  • Two extra planes travel from Country A to position 200 and give 20 units of fuel to planes p and q, then they all return. So far we have used 10 planes.
  • The two planes at 400 travel to 600 and one of them (plane r) recharges the other one (plane k) to full capacity, and then returns to position 400. Plane k can now reach Country B.
  • Two extra planes leave Country A, travel to 200, one of them gives 20 units of fuel to the other one (plane s) and returns to Country A. 12 planes have been used so far.
  • Plane s, now at 200, travels to 400 to meet with plane r, it gives 20 units of fuel to it and they both return to 200.
  • Two extra planes leave Country A, travel to 200, give 20 units of fuel to planes r and s, and they all return.

14 planes have been used in this solution. Maybe there's a better one, I'd like to know.