Bedao Mini Contest 22 - Đếm đi các bạn ơiiii

Điểm: 0,10 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Hãy đếm số cặp (~i~, ~j~) thỏa mãn:

~1 \le i < j \le n~.
~j - i > 5~.
~|a_i - a_j|~ chia hết cho ~23~.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~).

Dòng thứ hai gồm ~n~ số nguyên dương mô tả dãy số ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~, ~1 \le i \le n~).

Output

In ra một số nguyên duy nhất là số cặp (~i~, ~j~) thỏa mãn yêu cầu đề bài.

Scoring

Subtask	Điểm	Giới hạn
1	~40~	~n \le 1000~
2	~60~	Không có ràng buộc gì thêm

Sample Input 1

10
1 24 25 4 30 15 3 1 24 2

Sample Output 1

Notes

Trong ví dụ, các cặp số (~i~, ~j~) thỏa mãn là:

(~1~, ~8~)
(~1~, ~9~)
(~2~, ~8~)
(~2~, ~9~)
(~3~, ~10~)

Bình luận

Hãy đọc nội quy trước khi bình luận.

-2

dphuc02040608 đã bình luận lúc 24, Tháng 9, 2025, 3:51

include<bits/stdc++.h>

define ll long long

define N 1000000

define buff iosbase::syncwith_stdio(false); cin.tie(0); cout.tie(0);

using namespace std; ll n; ll a[N]; ll c[25]; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; ll kq=0; for(int i=7; i<=n; i++) { c[a[i-6]%23]++; ll x=a[i]%23; kq+=c[x]; } cout<<kq; return 0; }

*

1

ngoccaidu2008 đã bình luận lúc 19, Tháng 9, 2025, 17:05

các số |ai-aj| chia hết cho 23 khi ai%23=aj%23

dùng mảng đếm lưu giá trị vị trí + binary search

bài này có thể có nhiều cách

0
vominhmanh10 đã bình luận lúc 28, Tháng 11, 2025, 13:19 ← sửa 3 →
mẫu cách giải hướng trên:
lưu vào từ điển của dư k list các chỉ số mà a[i] % 23 = k
duyệt list trong từ điển: với mỗi giá trị idx trong list đã sắp tăng dần, tìm kiếm nhị phân idx2 mà idx2 >= idx - 5
cộng vào kết quả cnt += (idx2 - 1)
thực hiện trong tối đa là O(23n log n)

import sys import bisect as bs from collections import defaultdict input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) cnt = defaultdict(list) res = 0 for i in range(n): cnt[a[i] % 23].append(i) for b in cnt.values(): for x in b: j = bs.bisect_left(b, x - 5) res += j print(res)

0

quyennguyen121 đã bình luận lúc 18, Tháng 10, 2025, 13:42 ← chỉnh sửa →

.

-5

dtnguyenthehung đã bình luận lúc 24, Tháng 4, 2025, 11:40

code nè

include<bits/stdc++.h>

define ll long long

using namespace std; map<ll, ll> mp; ll n, a[200005], ans; int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for (int i = 1; i <= n; i++) { cin>>a[i]; a[i] %= 23; } for (int i = 1; i <= n; i++) { ans += mp[a[i]]; if (i > 5) mp[a[i-5]]++; } cout<<ans; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-4

nongquan đã bình luận lúc 27, Tháng 3, 2025, 8:27

https://ideone.com/PQw1gp co the sd mang danh dau, fenwick tree, segment tree thay the map

-4

keelythuytrang đã bình luận lúc 11, Tháng 11, 2024, 12:38

tại sao 1,8 lại thỏa v mn

-1

NG_Bao đã bình luận lúc 24, Tháng 11, 2024, 11:51

1 - 1 = 0 chia hết cho 23

-12

nguyenttuca đã bình luận lúc 13, Tháng 6, 2024, 15:10

include<bits/stdc++.h>

define ll long long

using namespace std;

const int N = (int)1e6 + 3; int n, a[N], ans = 0, c[25];

int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); memset(c, 0, sizeof(c)); cin>>n; for(int i = 0; i < n; i++) cin>>a[i]; for(int i = 6; i < n; i++){ c[a[i - 6] % 23]++; ans += c[a[i] % 23]; } cout<<ans; return 0; }

sao em vẫn bị 4 test nhỉ mọi người có cao nhân nào tìm giúp em xem em sai ở đâu được không ạ:>

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-7

anhtuanng04050405 đã bình luận lúc 2, Tháng 4, 2024, 2:28

các bạn đếm pp đi, bài này khi duyệt đến i ta quét hết được các trường hợp trước đó

include <bits/stdc++.h>

define ll long long

using namespace std;

ll n; ll result; ll a[2 * 100000 + 1]; ll mp[23];

int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i){ cin >> a[i]; if (i >= 7){ ++mp[a[i - 6] % 23]; result += mp[a[i] % 23]; } } cout << result; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-2

ngan_2604 đã bình luận lúc 7, Tháng 2, 2024, 5:08

help!!!!!! ai giải thích giúp tui cái ví dụ được không? tui đọc không có hiểu

0

nccuongtq2023 đã bình luận lúc 14, Tháng 3, 2024, 13:23

cái ví dụ là trường hợp 1 là vị trí thứ 1 với vị trí thứ 8 có hiệu là |1-24|=23 chia hết cho 3 tương tự với trường hợp 2 3 4 5 cũng vậy

6

ithero đã bình luận lúc 4, Tháng 12, 2023, 16:30

bài này có special tests ko z? mình làm đc có 36/40 tests :<

-4

BackOnTrack đã bình luận lúc 7, Tháng 12, 2023, 15:03

https://ideone.com/uHxq9o

code tk

-161

tomioka_giyu_long đã bình luận lúc 1, Tháng 12, 2023, 3:25

chim tôi to đùng

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-10

van353735 đã bình luận lúc 18, Tháng 8, 2024, 3:22

=))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.