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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0