Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT121J - Du hành không gian

Hãy tưởng tượng một thời điểm nào đó trong tương lai con người có trạm không gian ở tất cả các hành tinh. Mỗi hành tinh mã hóa bằng một dãy nhị phân có N phần tử. Luôn luôn có một đường bay giữa hai hành tinh khác nhau mà dãy nhị phân biểu diễn hai hành tinh đó khác nhau duy nhất một bít. Khi bay từ một hành tinh này đến hành tinh khác, các tàu không gian phải trả một khoản thuế cho mỗi điểm dừng. Khoản thuế này được tính trên các bít 1 trong biểu diễn của hành tinh điểm dừng đó. Sẽ có một mảng N số nguyên trong đó phần tử thứ I cho biết thuế phải trả nếu bít i bằng 1.

Ví dụ: Nếu hành tinh xuất phát là 110 và hành tinh đích là 011, dãy thuế là 3 1 2 thì cách đi tốn ít chi phí nhất là: 110 -> 010 -> 011 với tổng chi phí là 1+(1+2)=4.

Hãy viết chương trình tính chi phí thuế thấp nhấp có thể để đi từ hành tinh xuất phát đến hành tinh đích cho trước. 

Input

  • Mỗi bộ test gồm 2 dòng:
    • Dòng thứ nhất gồm số N (số bít mô tả hành tinh). Tiếp theo sẽ là hai dãy nhị phân có N phần tử mô tả hành tinh nguồn và hành tinh đích (1<=N<=1000).
    • Dòng thứ 2 ghi N số nguyên dương mô tả mảng thuế tương ứng với mỗi vị trí có bít 1. Các giá trị thuế không quá 106.
  • Dòng cuối cùng của input ghi số 0

Output

Với mỗi bộ test ghi trên một dòng giá trị thuế tối thiểu tìm được theo khuôn dạng như trong bộ test ví dụ.

Example

Input:

3 110 011

3 1 2

5 00000 11111

1 2 3 4 5

4 1111 1000

100 1 1 1

30 000000000000000000000000000000 111111111111111111111111111111

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

0 Output:

Case 1: 4

Case 2: 35

Case 3: 106

Case 4: 4960

ID RESULT TIME
code...



Được gửi lên bởi:adm
Ngày:2012-02-18
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2013-05-13 02:56:24 an IM3 Ex-Member of Bit
Bài A đề 2011 East Central Regional Contest
2013-01-15 13:58:00 Trần Vãn Dương D10CN2
Hiện tại mình vẫn chưa có đội ACM các bạn ai có nhã hứng vào đội mình xin nt vào 01644321263 Với minh nha tks
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.