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

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

Поймать Халка

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

요약
1차원부터 3차원까지의 상자와 그 안에 든 내부 상자가 주어질 때, 내부 상자 바깥의 얼음을 모두 잘라내는 데 필요한 최소 절단 횟수를 구한다.
난이도

보통10점 중 4점

유형
수학, 구현, 기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

Когда Локи ловил Халка, он немного не рассчитал своих сил, и случайно перенес его в параллельный nn-мерный мир. После этого Локи намертво вморозил Халка в глыбу льда. Для окончательной победы Локи необходимо только отпилить от глыбы лишний лед так, чтобы остался только сам замороженный Халк.

Пространство, в которое Локи перенес все происходящее, не более чем трехмерно. В одномерном пространстве глыба представляет из себя отрезок некоторой длины, а Халк внутри --- вложенный в него отрезок. В двумерном пространстве глыба и Халк --- прямоугольники со сторонами, параллельными оcям координат, причем Халк вложен в глыбу. Аналогично, в трехмерном пространстве глыба и Халк являются параллелепипедами со сторонами, параллельными осям координат.

Локи может отрезать от глыбы какие-то куски льда. В одномерном пространстве разрез --- точка, в двумерном --- прямая, в трехмерном --- плоскость. В любом пространстве разрез не должен проходить через Халка, но может его касаться. Локи хочет узнать, за какое минимальное количество разрезов он сможет оставить от глыбы льда только ту ее часть, в которой находится Халк.

입력

Первая строка входного файла содержит одно число nn (1≤n≤31 \le n \le 3) --- количество измерений в пространстве, в котором происходит действие.

Следующая строка содержит nn натуральных чисел a_ia\_i (1≤a_i≤100001 \le a\_i \le 10000) --- координаты одной из вершин глыбы. Будем считать, что вершина глыбы, противоположная данной, находится в начале координат.

В следующей строке сначала перечислены nn целых чисел b_ib\_i (0≤b_i≤a_i0 \le b\_i \le a\_i) --- координаты одной из вешин Халка, затем еще nn целых чисел c_ic\_i (0≤c_i≤a_i0 \le c\_i \le a\_i) --- координаты противоположной вершины Халка.

출력

Выведите единственное целое число --- минимальное количество разрезов, которые необходимо сделать Локи, чтобы выпилить Халка.

예제3

  1. 예제 1

    입력
    1
    5
    0 3
    
    예상 출력
    1
    
  2. 예제 2

    입력
    2
    3 4
    2 2 3 3
    
    예상 출력
    3
    
  3. 예제 3

    입력
    3
    2 2 2
    0 1 0 1 2 1
    
    예상 출력
    3