Extraterrestrial Exploration

시간 제한1초메모리 제한1024 MB

요약
산화도가 비감소 순서로 놓인 연료 통에서 최대 50개만 확인할 수 있을 때, 세 통을 골라 세 쌍의 제곱근 거리 합이 최대가 되게 찾는다.
난이도

어려움10점 중 8점

유형
이분 탐색, 수학, 그리디, 완전 탐색
정답자
아직 제출이 없습니다

문제

After years of planning and construction, you finally succeeded in making your own spacecraft! Immediately hopping aboard, you take the spaceship on a maiden voyage to the Big Anthropomorphic Pig Constellation. After a couple of years, you reach the constellation and land on the nearest planet to take some pictures and hopefully score some souvenirs. While haggling with a local souvenir seller using the built-in translator of your spacecraft, you are suddenly notified that the craft is low on fuel! Your extensive use of the translator has drained more fuel than expected, and you cannot get back to Earth. Frantically, you look for a refuelling station. Luckily, a local points you to a shady store, strikingly similar to the petrol stations you know from home.

While the outside of the refuelling station may look similar to those on Earth, the inside is completely different. On a long shelf are a number of fuel canisters, with strange symbols on the side. From your research on rocket fuel, you deduce that these symbols probably denote the oxydilation level of the fuel in the canister. None of the rocket fuels burn on their own. Instead, combining two rocket fuels with oxydilation levels o_xo\_x and o_yo\_y yields a fuel with burn time ∣o_x−o_y∣\sqrt{|o\_x-o\_y|}. You can afford to buy three full canisters, and the burn time of rocket fuel is additive, so that combining rocket fuels with oxydilation levels o_xo\_x, o_yo\_y and o_zo\_z results in a total burn time of \[\sqrt{|o_x-o_y|} + \sqrt{|o_y-o_z|} + \sqrt{|o_z-o_x|}.\] You can only decode the symbols denoting the oxydilation levels with the translator of your spacecraft. Unfortunately, due to the low fuel levels of the spacecraft, you can only use your translator for 5050 items, before the fuel fully runs out. Luckily, you know that rocket fuel is always stored in non-decreasing order of oxydilation levels. Can you figure out which three canisters of rocket fuel to buy to maximize total burn time?

예제2

  1. 예제 1

    입력
    4
    
    1
    
    3
    
    3
    
    
    예상 출력
    
    ? 1
    
    ? 3
    
    ? 4
    
    ! 1 2 3
    
  2. 예제 2

    입력
    6
    
    -5
    
    5
    
    -3
    
    3
    
    -1
    
    1
    
    
    예상 출력
    
    ? 1
    
    ? 6
    
    ? 2
    
    ? 5
    
    ? 3
    
    ? 4
    
    ! 4 6 1