Problem MORSEDEC

Giải bài trực tuyến

• Giải bài trực tuyến
• sign in

• News
• Problems
• acm challenge main oi tutorial
• Status
• Ranking
• Forum
• info
• rules
• links

SPOJ time:

2024-12-03

01 : 22 : 32

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

Nộp bài

Các bài nộp

Làm tốt nhất

PDF

Về danh sách bài

MORSEDEC - Morse decoding

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/morsedec

Hiện nay, khi công nghệ thông tin phát triển, con người thường trao đổi với nhau bằng điện thoại, fax hay email. Hãy quay ngược thời gian lại 100 năm, khi đó con người không có điện thoại hay fax, lại càng chẳng có email, người ta phải liện lạc với nhau bằng mật mã MORSE. Đây là loại mật mã mà các kí tự chỉ được mã hóa bằng 2 kí hiệu “.” (tích) và “-“ (tè). Để chuyển đi một văn bản, người ta mã hóa từng chữ cái trong văn bản đó thành những dãy kí tự tích tè. Trên thế giới đã quy định một quy tắc mã hóa chuẩn như sau:

A	.-	B	-...	C	-.-.
D	-..	E	.	F	..-.
G	--.	H	....	I	..
J	.---	K	-.-	L	.-..
M	--	N	-.	O	---
P	.--.	Q	--.-	R	.-.
S	...	T	-	U	..-
V	...-	W	.--	X	-..-
Y	-.--	Z	--..

Hạn chế của cách mã hóa này là một dãy mã hóa có thể có nhiều cách giải mã. Ví dụ dãy -.-..-- có thể được hiểu là CAT hay NXT đều đúng. Rõ ràng là trong trường hợp bình thường, chúng ta sẽ phải hiểu là CAT vì NXT không có nghĩa. Tuy vậy một dãy mã hóa vẫn có thể có nhiều cách giải mã có nghĩa. Bạn có trong tay một dãy đã mã hóa và một danh sách các từ có nghĩa, bạn hãy tính xem có bao nhiêu cách giải mã có nghĩa.

(Một cách giải có nghĩa là một cách chia đoạn code ban đầu thành các đoạn con liên tiếp sao cho mỗi đoạn là một từ có nghĩa)

Input

Dòng thứ nhất ghi xâu đã mã hóa gồm không quá 10000 kí tự tích tè. Dòng thứ hai ghi số N là số các từ có nghĩa (N ≤ 1000). Trong N dòng tiếp theo, mỗi dòng ghi một từ có nghĩa. Các từ là các xâu không rỗng gồm không quá 10 kí tự trong khoảng “A” đến “Z”.

Output

Gồm một dòng duy nhất ghi số P là phần dư số cách giải mã có nghĩa khi chia cho 1 triệu (mod 1 000 000). 

Example

Input:

.---.--.-.-.-.---...-.---.

6

AT

TACK

TICK

ATTACK

DAWN

DUSK  Output: 2 Submit solution!

Được gửi lên bởi:	Nhung anh sao dem
Ngày:	2013-09-06
Thời gian chạy:	1s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:	ACM Central European Programming Contest, Warsaw 2001

hide comments

2019-05-15 13:20:34 easy 1 đấm Hash + QHĐ :((

2017-08-20 20:35:35 Ðặng Minh Tiến https://kienthuc24h.com/morsedec-spoj-morse-decoding/

2013-09-18 09:51:13 Think like Nguyễn Mai Lan PS tăng lên 1 triệu ký tự cho nhiệt nhỉ :))

2013-09-15 17:58:50 dhkhtn lan sau cac ban set time 1s di dung set kieu 0.699s cha de lam cai gi.

2013-09-07 14:29:35 Nhung anh sao dem Test có chút vấn đề. mình đã update lại và rejudge. Thành thật xin lỗi các bạn về sự cố này.

2013-09-07 01:40:35 Anh chỉ yêu mình em ....LTKC PS xem bai minh sai dau cai.Minh thu test BTC dung roi ma cham toan sai.

About SPOJ

RSS

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.