[Home|Training|Problems|Contests|C Language] | [Login|Register] |

Problems Status Rank |
Problem 1042
ACM Hacker
Time Limit: 1000ms
Memory Limit: 65536kb Description
You are taking part in an ACM programming contest. You get stuck at a problem. Don't give up! It can be solved in an abnormal way. Suppose your problem has only one input file containing N input cases. The input for case i is Ai bits long. The output for case i is Bi bits long. The values of N and Ai,Bi(1<=i<=N) are given in the problem description. The following operation (called a "probe") gives you information about the input data: your program reads the input data and examines a particular bit. If it is 1, the program goes into an infinite loop, if it is 0, the program halts. Then you know this bit is 1 if the judge replies "Time limit exceeded" and 0 if the judge replies "Wrong answer". In this way, you get one bit per probe. Suppose that you have a correct program, but it is so inefficient that you will not use it in your submissions. You can get accepted by probing all the input cases, solve them with your inefficient program and submit another program printing all the answers. Another way to get accepted is to guess the output, but you may have to guess 2^m times if the output is m bits long. Since there are more than one input cases, it may be better to combine these two methods together. You can probe some input cases (so you know their answers for sure) and guess the answers to the other cases. Suppose that for each case you can choose to use probe or guess, but not both, and you do not use other methods to crack the problem. That means, if you choose to probe one input case, you must probe all bits of it. Now your task is to find out how many submissions (probes + guesses) are needed to guarantee that you get accepted. The number of guesses is computed according to the worst situation, i.e. 2^m, where m is the total length of output for the cases you guess. Note that when m=0, this formula still holds: after you have probed all the input data, you have to submit a program which prints the right answers. Input
There are at most 20 test cases. The first line of each case is an integer N (1<=N<=100). The next line contains N integers Ai (0<=Ai<=10000). The third line contains N integers Bi (1<=Bi<=20). A case with N=0 marks the end of input. This case should not be processed. Output
For each test case, print on a single line the minimum number of submissions to guarantee that you can get accepted.
Sample Input
1 8 6 2 5 6 1 2 3 100 100 100 2 4 3 0 Sample Output
9 8 132 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.7ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.7ms with 1 query(s).