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

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

공격 순서

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

요약
각 하수인의 공격력 a_i와 버프 값 b_i가 주어질 때, 버프 대상이 어떻게 정해지더라도 공격력이 증가하지 않도록 한 줄로 세울 수 있는지 판정합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 수학
정답자
아직 제출이 없습니다

문제

어떤 게임에서 당신은 11번부터 nn번까지 번호가 붙은 nn개의 하수인으로 이루어진 보드를 조종한다. 각 하수인 ii는 공격력이라 부르는 정수 a_ia\_i를 가진다.

다가오는 전투를 위해 당신은 하수인들을 왼쪽에서 오른쪽으로 일렬로 배치한다.

그 뒤 일부 하수인의 공격력이 강화된다. 각 하수인 ii의 능력은 "전투 전에 다른 무작위 하수인 하나의 공격력을 b_ib\_i만큼 증가시킨다"이다. 형식적으로, 각 ii에 대해 j≠ij \ne i인 임의의 하수인 jj가 선택되고 그 공격력 a_ja\_j가 b_ib\_i만큼 증가한다.

강화 대상은 서로 독립적으로 정해지며 동시에 일어난다. 따라서 어떤 하수인의 공격력은 여러 번 강화될 수 있다.

모든 강화가 끝난 뒤 하수인들의 공격력이 왼쪽에서 오른쪽으로 비오름차순이 되기를 바란다. 강화 대상이 어떻게 정해지더라도 그렇게 되도록 하수인을 배치하는 것이 가능한지 판별하라.

입력

각 입력은 여러 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 tt가 주어진다 (1≤t≤10001 \le t \le 1000). 테스트 케이스의 설명이 이어진다.

각 테스트 케이스의 첫 줄에는 정수 nn이 하나 주어진다 (2≤n≤1002 \le n \le 100).

다음 nn줄 중 ii번째 줄에는 두 정수 a_ia\_i와 b_ib\_i가 주어진다 (0≤a_i,b_i≤1060 \le a\_i, b\_i \le 10^6).

출력

각 테스트 케이스마다 강화 대상이 어떻게 정해지더라도 공격력이 비오름차순이 되도록 하수인을 배치하는 것이 가능하면 "Yes", 아니면 "No"를 출력한다.

힌트

첫 번째 예제에서 하수인들은 서로를 강화한다. 전투 중 하수인 11과 22의 공격력은 항상 각각 2020과 3535이다. 하수인을 ⟨2,1⟩\langle 2, 1 \rangle 순서로 배치하면 된다.

두 번째 예제에서는 하수인 22만 다른 하수인을 강화한다. 가능한 배치 중 하나는 ⟨3,1,2⟩\langle 3, 1, 2 \rangle이다. 하수인 22가 하수인 11을 강화하면 왼쪽에서 오른쪽으로 하수인들의 공격력은 ⟨10,10,7⟩\langle 10, 10, 7 \rangle이 된다. 하수인 22가 하수인 33을 강화하면 공격력은 ⟨13,7,7⟩\langle 13, 7, 7 \rangle이 된다. 두 수열 모두 비오름차순이다.

예제1

  1. 예제 1

    입력
    3
    2
    15 25
    10 5
    3
    7 0
    7 3
    10 0
    3
    10 10
    20 20
    30 30
    
    예상 출력
    Yes
    Yes
    No