Japanese parking garages P33845


Statement
 

pdf   zip

html

In the cities of Japan you can see parking garages of every imaginable kind. Unfortunately, during his visit to Japan, the author of this problem was unable to fully understand how they work. So here we will use two simplified models: Q-garages and S-garages.

A Q-garage stores the cars into queues (containers that use the “first in, first out” principle). Only after all the incoming cars have been stored into the queues of a Q-garage, the cars can start leaving the queues. An S-garage is identical to a Q-garage, except that it uses stacks (containers with the “last in, first out” principle) instead of queues.

Suppose that n cars, numbered 1, …, n, arrive at a garage in the order i1, …, in, and must leave it in the order o1, …, on. Which is the minimum number of queues for a Q-garage? And the minimum number of stacks for an S-garage?

For example, assume n = 8, that the incoming order is 6 8 5 2 1 7 3 4, and that the outcoming order must be 2 5 4 7 1 6 8 3. In this case, a Q-garage needs 4 queues, while an S-garage only needs 3 stacks. These are possible (not unique) solutions:




Input

Input consists of several cases. Every case begins with n, where 1 ≤ n ≤ 106, followed by the permutation i1, …, in and the permutation o1, …, on. A single 0 ends the input.

Output

For every case, print its case number, followed by the minimum number of queues for a Q-garage and the minimum number of stacks for an S-garage.

Public test cases
  • Input

    8
    1 2 3 4 5 6 7 8
    4 3 8 6 5 1 2 7
    
    1
    1
    1
    
    9
    5 2 9 6 1 7 4 3 8
    2 6 7 3 5 9 1 4 8
    
    10
    1 2 3 4 5 6 7 8 9 10
    10 9 8 7 6 5 4 3 2 1
    
    0
    

    Output

    Case 1: 4 3
    Case 2: 1 1
    Case 3: 2 5
    Case 4: 10 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - Final
    Date
    2007-10-03