#include #include #include #include #include #include typedef struct heap_elem node; struct heap_elem { node *prev; node *next; node *child; }; typedef bool heap_less_func(const node *a, const node *b, void *aux); typedef struct pheap_t { size_t size; node *root; heap_less_func *less; } PairingHeap; void init_pheap(PairingHeap *h, heap_less_func *less) { h->size = 0; h->root = NULL; h->less = less; } node* merge_node(node *a, node *b, heap_less_func *less, void *aux) { if (less(a, b, aux)) { if (a->child != NULL) a->child->prev = b; if (b->next != NULL) b->next->prev = a; a->next = b->next; b->next = a->child; a->child = b; b->prev = a; return a; } if (b->child != NULL) b->child->prev = a; if (a->prev != NULL && a->prev->child != a) a->prev->next = b; b->prev = a->prev; a->prev = b; a->next = b->child; b->child = a; return b; } void push_pheap(PairingHeap *h, node *elem, void *aux) { h->size++; elem->prev = NULL; elem->next = NULL; elem->child = NULL; if (h->root == NULL) h->root = elem; else h->root = merge_node(elem, h->root, h->less, aux); } node* merge_right_node(node *a, heap_less_func *less, void *aux) { node *b; for (b = NULL; a != NULL; a = b->next) { if ((b = a->next) == NULL) return a; b = merge_node(a, b, less, aux); } return b; } node* merge_left_node(node *a, heap_less_func *less, void *aux) { node *b; for (b = a->prev; b != NULL; b = a->prev) a = merge_node(b, a, less, aux); return a; } node* merge_subheaps_node(node *a, heap_less_func *less, void *aux) { a->child->prev = NULL; node *e; e = merge_right_node(a->child, less, aux); e = merge_left_node(e, less, aux); return e; } void detach_subheap_node(node *elem) { if (elem->prev->child == elem) elem->prev->child = elem->next; else elem->prev->next = elem->next; if (elem->next != NULL) elem->next->prev = elem->prev; elem->prev = NULL; elem->next = NULL; } node* pop_pheap(PairingHeap *h, void *aux) { assert (h->size > 0); h->size--; node *root = h->root; if (root->child == NULL) { h->root = NULL; return root; } h->root = merge_subheaps_node(root, h->less, aux); return root; } void remove_pheap(PairingHeap *h, node *elem, void *aux) { if (elem == h->root) { pop_pheap(h, aux); return; } assert (h->size > 0); h->size--; detach_subheap_node(elem); elem = merge_subheaps_node(elem, h->less, aux); h->root = merge_node(h->root, elem, h->less, aux); } node* top_pheap(PairingHeap *h) { return h->root; } bool is_empty_pheap(PairingHeap *h) { return h->root == NULL; } size_t size_pheap(PairingHeap *h) { return h->size; } void increase_pheap(PairingHeap *h, node *elem, void *aux) { remove_pheap(h, elem, aux); push_pheap(h, elem, aux); } void decrease_pheap(PairingHeap *h, node *elem, void *aux) { if (elem->prev == NULL) return; detach_subheap_node(elem); h->root = merge_node(h->root, elem, h->less, aux); } #define heap_entry(HEAP_ELEM, STRUCT, MEMBER) ((STRUCT *) ((uint8_t *) &(HEAP_ELEM)->child - offsetof(STRUCT, MEMBER.child))) #define HEAP_INITIALIZER(NAME, LESS) { 0, NULL, (LESS) } struct pair_wrapper { int a, b; node elem; }; bool pair_less(const node * a, const node *b, void *aux) { struct pair_wrapper *x, *y; x = heap_entry(a, struct pair_wrapper, elem); y = heap_entry(b, struct pair_wrapper, elem); return x->a == y->a ? x->b < y->b : x->a < y->a; } int main(void) { int N; scanf("%d", &N); int A[3030], B[3030]; for (int i = 0; i < N; i++) scanf("%d", A + i); for (int i = 0; i < N; i++) { scanf("%d", B + i); B[i + N] = B[i]; } int m = INT32_MAX; for (int i = 0; i < N; i++) { PairingHeap pq; init_pheap(&pq, pair_less); for (int j = 0; j < N; j++) { struct pair_wrapper p; p.a = A[j], p.b = 0; push_pheap(&pq, &p.elem, NULL); } for (int j = 0; j < N; j++) { struct pair_wrapper* p = pop_pheap(&pq, NULL); p->a += B[i + j] / 2; p->b += 1; push_pheap(&pq, p, NULL); } int tmp = 0; while (!is_empty_pheap(&pq)) { struct pair_wrapper* p = pop_pheap(&pq, NULL); tmp = tmp > p->b ? tmp : p->b; } m = m < tmp ? m : tmp; } printf("%d\n", m); return 0; }