아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

환율

면접 대비

시간 제한2초메모리 제한512 MB

요약
n개의 태블릿 값과 정수 환율 p가 주어질 때, c_i / c_j가 p에 가장 가까워지는 서로 다른 두 인덱스 i, j를 찾는다.
난이도

보통10점 중 6점

유형
배열, 이분 탐색, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

페옥티스트는 플랫란디아와 바이트란디아 국경의 환전소에서 일한다. 그는 매일 라디오로 플랫란디아 플라트와 바이트란디아 비트의 현재 환율을 듣고, 자기 환전소 문에 환율 정보를 붙인다.

페옥티스트에게는 nn개의 팻말이 있고, 그 위에는 c1,c2,…,cnc_1, c_2, \ldots, c_n이 적혀 있다. 오늘의 환율 pp를 알게 되면, 페옥티스트는 값 cic_i와 cjc_j가 적힌 팻말 두 개를 골라 ci/cjc_i/c_j가 pp에 최대한 가까워지도록 하고, 그 팻말 둘을 문에 걸어 <<cic_i 플라트를 cjc_j 비트로 바꿉니다>>라는 광고를 만든다. 쉬운 일이 아니라서 페옥티스트는 이 과정을 자동화하기로 했다.

주어진 환율 pp에 대해 페옥티스트가 알맞은 팻말 두 개를 찾도록 도와주자.

입력

첫째 줄에 정수 nn과 pp가 주어진다(2≤n≤100 0002 \le n \le 100\,000, 1≤p≤1091 \le p \le 10^9). nn은 팻말의 수이고 pp는 현재 환율이다. 둘째 줄에 nn개의 정수 cic_i가 주어진다(1≤ci≤1091 \le c_i \le 10^9). cic_i는 팻말에 적힌 수이다.

출력

값 ∣(ci/cj)−p∣\left|(c_i/c_j) - p \right|가 최소가 되는 두 팻말의 번호 ii와 jj를 출력한다(1≤i,j≤n1 \le i,j \le n, i≠ji \neq j). 그러한 쌍이 여러 개면 아무거나 출력해도 된다.

예제2

  1. 예제 1

    입력
    3 2
    1 6 3
    
    예상 출력
    2 3
    
  2. 예제 2

    입력
    4 3
    2 3 4 5
    
    예상 출력
    4 1