Xâu con chẵn - LQDOJ: Le Quy Don Online Judge

Xâu con chẵn

All submissions

Best submissions

Author:

Problem types

Points: 100 (p) Time limit: 1.0s Memory limit: 1023M Input: stdin Output: stdout

Bạn được một xâu \(s = s_1 s_2 ... s_n\) có độ dài n, chỉ chứa các ký tự số \(1,2,3,...,9\) (không chứa số \(0\))

Một xâu con \(s[l...r]\) của xâu \(s\) là \(s_l s_{l+1} ... s_r\) được gọi là xâu con chẵn nếu nó biểu diễn số chẵn.

Hãy tìm số xâu con chẵn của xâu \(s\).

Input

Dòng đầu tiên chứa số nguyên dương \(n(n \leq 10^5)\) - là độ dài xâu \(s\)
\(n\) ký tự của xâu \(s\), chỉ gồm các ký tự từ \(1\) đến \(9\)

Output

Số xâu con chẵn của xâu \(s\).

Example

Test 1

Input

4
1234

Output

Test 2

Input

4
2244

Output

Comments

-16

todonghai2k7 7:29 a.m. 20 jul, 2020 ← edit 23 →

HINT

Để một số chẵn, chuỗi con phải kết thúc với một chữ số chẵn. Ta tìm thấy tất cả các chữ số chẵn trong chuỗi và với mỗi chữ số chẵn, hãy đếm số lượng chuỗi con kết thúc với nó. Bây giờ, hãy quan sát rằng số lượng chuỗi con sẽ là chỉ số của chữ số chẵn đó cộng với một.

VD :
Đầu vào:
n = 4,
str = "1234".

Đầu ra: 6

Giải thích :
"2", "4", "12", "34", "234", "1234"
là 6 chuỗi con chẵn.

Độ phức tạp thời gian: O (n).

This comment is hidden due to too much negative feedback. Click here to view it.

2 replies

-1

N7hoatt 9:42 p.m. 18 jul, 2020 ← edited →

HINT

tổng số xâu chẵn trong s là tổng các xâu có phần tử chẵn ở cuối vậy chỉ cần chạy-xét s[i] có chẵn không rồi cộng vào kết quả i+1

p/s:upvote đê

1 reply