#include #include #include #include #include #include typedef struct { int key; void* value; } data; typedef struct FibNode FibNode; typedef struct FibNode FibNode; struct FibNode { FibNode* left; FibNode* right; FibNode* parent; FibNode* child; int key; void* value; bool mark; int degree; }; typedef FibNode FibHeap; typedef FibNode FibElem; FibNode* fib_node_init(int key, void* value) { FibNode* new_node = (FibNode *)malloc(sizeof(FibNode)); new_node->left = new_node->right = new_node; new_node->key = key; new_node->value = value; new_node->parent = NULL; new_node->child = NULL; new_node->mark = false; new_node->degree = 0; return new_node; } void fib_node_free(FibNode* to_free) { to_free->degree = -1; free(to_free); } void fib_node_kill(FibNode* to_kill) { FibNode* kid = to_kill->child; if (kid) { kid->left->right = NULL; while (kid->right != NULL) { kid = kid->right; fib_node_kill(kid->left); } fib_node_kill(kid); } fib_node_free(to_kill); } void fib_node_add(FibNode* old, FibNode* new_right) { FibNode* oldRight = old->right; assert(old != new_right); assert(oldRight != new_right); old->right = new_right; oldRight->left = new_right; new_right->left = old; new_right->right = oldRight; } FibHeap* fib_heap_init(void) { return NULL; } FibElem* fib_heap_add_with_comp(FibHeap** H, FibNode* new_node, bool (*comp)(int, int)) { assert(H); assert(new_node); FibNode* old_node = *H; new_node->parent = NULL; new_node->mark = false; if (old_node) { fib_node_add(old_node, new_node); if (comp(old_node->key, new_node->key)) *H = new_node; } else { new_node->left = new_node; new_node->right = new_node; *H = new_node; } return new_node; } FibElem* fib_heap_insert_with_comp(FibHeap** H, int key, void* value, bool (*comp)(int, int)) { FibNode* new_node = fib_node_init(key, value); return fib_heap_add_with_comp(H, new_node, comp); } bool is_empty_fib_heap(FibHeap* H) { return H == NULL; } data fib_heap_min(FibHeap* H) { assert(H); data d; FibNode* head = H; d.key = head->key; d.value = head->value; return d; } data fib_heap_elem_data(FibElem* x) { assert(x); data d; d.key = x->key; d.value = x->value; return d; } void fib_heap_remove_from_with_comp(FibHeap** H, FibNode* x, bool (*comp)(int, int)) { assert(!x->parent); if (x->right == x) *H = NULL; else { x->left->right = x->right; x->right->left = x->left; *H = x->right; } x->left = x; x->right = x; x->parent = NULL; } FibHeap* fib_heap_union_with_comp(FibHeap* H1, FibHeap* H2, bool (*comp)(int, int)) { if (!H1) return H2; if (!H2) return H1; if (comp(fib_heap_min(H2).key, fib_heap_min(H1).key)) return fib_heap_union_with_comp(H2, H1, comp); FibNode* H1first = H1; FibNode* H1last = H1first->left; FibNode* H2first = H2; FibNode* H2last = H2first->left; H1last->right = H2first; H2first->left = H1last; H2last->right = H1first; H1first->left = H2last; return H1first; } FibNode* fib_heap_link_with_comp(FibHeap** H, FibNode* x, FibNode* y, bool (*comp)(int, int)) { assert(x); assert(y); assert(x->degree == y->degree); if (comp(x->key, y->key)) return fib_heap_link_with_comp(H, y, x, comp); fib_heap_remove_from_with_comp(H, y, comp); if (x->child) { FibNode* z = x->child; y->right = z; y->left = z->left; z->left->right = y; z->left = y; } y->parent = x; x->child = y; x->degree++; y->mark = false; return x; } void fib_heap_match_degrees_with_comp(FibHeap** H, FibNode** A, FibNode* x, bool (*comp)(int, int)) { int d = x->degree; while (A[d]) { if (d > 99) exit(1); FibNode* y = A[d]; if (y != x) { x = fib_heap_link_with_comp(H, x, y, comp); A[d] = NULL; d++; } else break; } A[d] = x; } void fib_heap_consolidate_with_comp(FibHeap** H, bool (*comp)(int, int)) { FibNode* x = *H; if (!x) return; FibNode** A = (FibNode**)calloc(100, sizeof(FibNode)); memset(A, '\0', 100); assert(x->degree >= 0); FibNode* last = x->left; while(x != last) { FibNode* next = x->right; fib_heap_match_degrees_with_comp(H, A, x, comp); x = next; } fib_heap_match_degrees_with_comp(H, A, last, comp); *H = fib_heap_init(); for (int i = 0; i < 100; i++) if (A[i]) fib_heap_add_with_comp(H, A[i], comp); free(A); } data fib_heap_extract_min_with_comp(FibHeap** H, bool (*comp)(int, int)) { assert(H && *H); FibNode* z = *H; data d = fib_heap_elem_data(z); FibNode* first = z->child; fib_heap_remove_from_with_comp(H, z, comp); fib_node_free(z); if (first) { FibNode* current = first->right; while (current != first) { current->parent = NULL; current = current->right; } first->parent = NULL; *H = fib_heap_union_with_comp(*H, first, comp); } fib_heap_consolidate_with_comp(H, comp); return d; } void fib_heap_decrease_key_with_comp(FibHeap** H, FibElem* x, int new_key, bool (*comp)(int, int)) { assert(H && *H); assert(x && (comp(x->key, new_key) || x->key == new_key)); x->key = new_key; if (x->parent && comp(x->parent->key, new_key)) { if (x->left == x) { assert(x->parent->degree == 2); x->parent->child = NULL; } else { assert(x->parent->degree > 2); x->left->right = x->right; x->right->left = x->left; x->parent->child = x->left; } x->parent->degree--; fib_heap_add_with_comp(H, x, comp); if (! x->parent->mark) { x->parent->mark = true; } else fib_heap_decrease_key_with_comp(H, x->parent, x->parent->key, comp); } else { if (!comp(new_key, (*H)->key) && new_key != (*H)->key) { assert(!x->parent); *H = x; } } } void fib_heap_delete_with_comp(FibHeap** H, FibElem* x, bool (*comp)(int, int)) { fib_heap_decrease_key_with_comp(H, x, INT_MIN, comp); fib_heap_extract_min_with_comp(H, comp); } void fib_heap_free(FibHeap** H) { FibNode* header = *H; FibNode* first = header; if (header) { while(header != first) { FibNode* next = header->right; fib_node_kill(header); header = next; } } *H = NULL; } bool min(int x, int y) { return x < y; } bool max(int x, int y) { return x > y; } int main(void) { int N; scanf("%d", &N); int* A = (int *)calloc(N, sizeof(int)); int* B = (int *)calloc(2 * N, sizeof(int)); if (A == NULL || B == NULL) exit(EXIT_FAILURE); 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 = 1073741824; for (int i = 0; i < N; i++) { FibHeap* pq = fib_heap_init(); for (int j = 0; j < N; j++) fib_heap_insert_with_comp(&pq, A[j], 0, min); for (int j = 0; j < N; j++) { data xy = fib_heap_extract_min_with_comp(&pq, min); fib_heap_insert_with_comp(&pq, xy.key + B[i + j] / 2, xy.value + 1, min); } int tmp = 0; while (!is_empty_fib_heap(pq)) { data xy = fib_heap_extract_min_with_comp(&pq, min); tmp = tmp > xy.value ? tmp : xy.value; } m = m < tmp ? m : tmp; fib_heap_free(&pq); } printf("%d\n", m); free(A); free(B); return 0; }