trang chủ / bài tập / shopping

Mua sắm

Đề bài

Mô tả

Cửa hàng có k món hàng được xếp thành một hàng duy nhất. Có n khách hàng đã đặt đơn online, mỗi đơn gồm m món hàng phân biệt.

Khi xử lý đơn hàng thứ i, thu ngân lần lượt lấy các món ai1,ai2,,aim. Gọi pos(x) là vị trí (đánh số từ 1) của món x trong hàng tại thời điểm lấy món đó. Thời gian xử lý đơn i bằng pos(ai1)+pos(ai2)++pos(aim).

Ngay sau khi lấy một món ra khỏi hàng, thu ngân đặt một món mới cùng loại lên đầu hàng (món vừa bị lấy được thay bằng bản sao mới ở vị trí 1, các món còn lại giữ nguyên thứ tự tương đối). Cửa hàng có nguồn cung vô hạn.

Hãy tính tổng thời gian xử lý toàn bộ n đơn hàng.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên n, m, k.
  • Dòng thứ hai chứa k số nguyên phân biệt p1,p2,,pk là vị trí ban đầu của các món hàng (món hàng được đánh số từ 1 đến k).
  • Mỗi dòng trong n dòng tiếp theo chứa m số nguyên phân biệt ai1,ai2,,aim — đơn hàng của khách thứ i.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng thời gian xử lý tất cả các đơn hàng.

Ràng buộc

  • 1n,k100
  • 1mk
  • 1plk, các pl phân biệt
  • 1aijk, các aij trong cùng một đơn phân biệt

Ví dụ

Input Output Giải thích
2 2 5
3 4 1 2 5
1 5
3 1
14 Khách 1 lấy món 1 (vị trí 3), hàng thành [1,3,4,2,5]; rồi lấy món 5 (vị trí 5), hàng thành [5,1,3,4,2]. Tốn 3+5=8. Khách 2 lấy món 3 (vị trí 3), hàng thành [3,5,1,4,2]; rồi lấy món 1 (vị trí 3), hàng thành [1,3,5,4,2]. Tốn 3+3=6. Tổng =14.
3 2 3
3 1 2
1 2
2 1
2 3
13 Ba khách lần lượt mua (1,2), (2,1), (2,3) trên cửa hàng có 3 món.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0