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.|

TREEPATH - Đường đi trên cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/treepath


Cho một cây tam phân đầy đủ, mỗi nút có đúng 3 nút con: nút con trái, nút con giữa và nút con phải. Mỗi nút ghi một số nguyên theo quy tắc sau:

  • Nút gốc ghi số 1.
  • Nếu một nút ghi số X thì nút con trái của nó ghi số 3X, nút giữa ghi số 3X+1, nút phải ghi số 3X+2.

Để di chuyển trên cây từ một nút người ta dùng một trong 4 lệnh sau:

  • L: Di chuyển đến nút con trái,
  • C: Di chuyển đến nút con giữa,
  • R: Di chuyển đến nút con phải,
  • S: Đứng nguyên tại nút hiện thời.

Một khuôn mẫu đường đi từ nút gốc là một xâu gồm các ký tự : ‘L’, ‘C’, ‘R’, ‘S’ và ‘*’ trong đó dấu ‘*’ có thể được thay thế bởi 1 trong 4 ký tự: ‘L’, ‘C’, ‘R’ và ‘S’.

Với một cách thay thế dấu ‘*’ ta nhận được một đường đi từ nút gốc tới một nút lá nào đó và tổng các số ghi trên các nút đi qua gọi là trọng số của đường đi đó.

Yêu cầu

Cho một khuôn mẫu đường đi, hãy tính tổng T trọng số các đường đi phù hợp với khuôn mẫu.

Dữ liệu

Chứa một xâu không quá 2000 ký tự ‘L’, ‘C’, ‘R’, ‘S’ và ‘*’.

Kết quả

Ghi ra file văn bản số T tìm được.

Ví dụ

Dữ liệu
*LS		

Kết quả
55

Nguồn: 5-й этап Республиканской олимпиады по информатике, 10-11 класс Республика Казахстан, Апрель, 2009


Được gửi lên bởi:Jimmy
Ngày:2009-07-23
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2021-05-27 18:04:04
Tham khảo: https://vnspoj.github.io/problems/TREEPATH
2018-12-19 08:38:53
tổng các số trên các nút đã đi qua nhé, còn tổng các số trên các nút ở trạng thái cuối cùng chỉ ra 39 thôi.
cda.dev
2017-01-09 13:50:28
52
2016-05-06 09:57:01
QHD 1 tiếng phê :D
2014-01-03 16:15:44 anonymous
xu li so lon :3... được có 20 điểm.........

Last edit: 2014-01-05 10:38:55
2013-06-04 06:57:04 Silver sea
55
2013-06-04 06:56:18 Silver sea
56
2013-06-04 04:51:04 Silver sea
đáng lẽ ra 39 mới đúng chớ nhỉ?
sao ra 55 được ta?
có ai giúp mình không?
2012-11-17 06:17:14 Một Bạn Trai Giấu Tên
back tracking chăng ?
2012-10-24 14:50:07 Shinken Yellow
Ê everyone ! kqmax>> 3^2000 thì sao
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.