Gửi bài giải
Điểm:
9,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Để phát hiện mức độ trùng lặp giữa các văn bản, người ta thường kiểm tra mức độ tương tự của các đoạn văn bản được biểu diễn theo dạng các xâu ký tự. Cho hai xâu ký tự st1
và st2
có thể chứa các chữ cái thường (~a, b, ..., z~), các chữ cái hoa (~A, B, ..., Z~) và dấu cách trắng. Để tính mức độ tương tự của hai xâu st1
và st2
, ta chuyển các xâu về dạng chữ cái thường hoặc chữ cái hoa sau đó tính độ tương tự theo công thức ~k = \frac{x}{y}~, trong đó:
- ~x~: số lượng chữ cái khác nhau có xuất hiện đồng thời trong cả 2 xâu
st1
vàst2
nhưng không tính dấu cách.
- ~y~: số lượng chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
nhưng không tính dấu cách.
Yêu cầu: Viết chương trình tính độ tương tự ~k~ của hai xâu st1
và st2
.
INPUT
Gồm hai dòng, mỗi dòng chứa một xâu không quá ~20000~ ký tự.
OUTPUT
In ra một dòng chứa phần nguyên của giá trị ~100 \times k~.
SAMPLE INPUT 1
The eyes
They see
SAMPLE OUTPUT 1
100
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1
vàst2
làt
,h
,e
,y
,s
, vì vậy ~x = 5~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
làt
,h
,e
,y
,s
, vì vậy ~y = 5~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{5}{5} = 1~, vì vậy phần nguyên của giá trị ~100 \times k = 100~.
SAMPLE INPUT 2
Form
Formal
SAMPLE OUTPUT 2
66
Giải thích:
- Chữ cái khác nhau có xuất hiện đồng thời cả hai xâu
st1
vàst2
làf
,o
,r
,m
, vì vậy ~x = 4~. - Chữ cái khác nhau có xuất hiện ở một trong hai xâu
st1
vàst2
làf
,o
,r
,m
,a
,l
, vì vậy ~y = 6~. - Độ tương tự của 2 xâu là ~k = \frac{x}{y} = \frac{4}{6} = 0.6666~, vì vậy phần nguyên của giá trị ~100 \times k = 66~.
SUBTASKS
Subtask | Điểm | Ràng buộc |
---|---|---|
1 | ~50\%~ | Chiều dài các xâu bé hơn ~1000~ ký tự |
2 | ~30\%~ | Chiều dài các xâu từ ~1000~ đến ~10000~ ký tự |
3 | ~20\%~ | Chiều dài các xâu từ ~10001~ đến ~20000~ ký tự |
Bình luận