trang chủ / đề bài / icpcwf20_g

Chi phí cơ hội

Đề bài

Mô tả

Cũng như với hầu hết các loại sản phẩm, mua một chiếc điện thoại mới có thể khá khó khăn. Một trong những thách thức chính là có rất nhiều khía cạnh của chiếc điện thoại mà bạn có thể quan tâm, chẳng hạn như giá cả, hiệu năng và mức độ thân thiện với người dùng. Thông thường sẽ không có chiếc điện thoại nào đồng thời tốt nhất ở tất cả các mặt: chiếc rẻ nhất, chiếc mạnh nhất và chiếc thân thiện nhất có lẽ là ba chiếc khác nhau.

Vì vậy khi mua điện thoại, bạn buộc phải hy sinh một số thứ bằng cách cân nhắc các khía cạnh mình quan tâm với nhau và chọn chiếc điện thoại đạt được sự thỏa hiệp tốt nhất (tất nhiên "tốt nhất" phụ thuộc vào thứ tự ưu tiên của bạn). Một cách đo sự hy sinh này là chi phí cơ hội, được định nghĩa (trong bài này) như sau.

Giả sử bạn đã mua một chiếc điện thoại có giá x, hiệu năng y và độ thân thiện z. Để đơn giản, ta coi ba giá trị này được đo trên cùng một thang số, giá trị càng cao càng tốt. Nếu có n chiếc điện thoại, chiếc thứ i có bộ giá trị (giá, hiệu năng, độ thân thiện) là (xi,yi,zi), thì chi phí cơ hội của chiếc điện thoại của bạn là

max1≤i≤n(max(xi−x,0)+max(yi−y,0)+max(zi−z,0)).

Hãy viết chương trình, cho danh sách các điện thoại, tìm một chiếc điện thoại có chi phí cơ hội nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số điện thoại được xem xét. Tiếp theo là n dòng, dòng thứ i chứa ba số nguyên xi, yi, zi: lần lượt là giá, hiệu năng và độ thân thiện của chiếc điện thoại thứ i.

Dữ liệu ra

In ra một dòng gồm hai số nguyên: chi phí cơ hội nhỏ nhất có thể, và chỉ số (từ 1 tới n) của chiếc điện thoại đạt chi phí cơ hội đó. Nếu có nhiều chiếc như vậy, in chiếc có chỉ số nhỏ nhất.

Ràng buộc

  • 2≤n≤200000.
  • 1≤xi,yi,zi≤109.

Ví dụ

Input Output Giải thích
4
20 5 5
5 20 5
5 5 20
10 10 10
10 4 Ba điện thoại đầu có chi phí cơ hội 15 (ví dụ điện thoại 1 so với điện thoại 2: 0+15+0). Điện thoại 4 có chi phí 10, nhỏ nhất.
4
15 15 5
5 15 15
15 5 15
10 10 10
10 1 Điện thoại 1 có chi phí 10 (so với điện thoại 2 hay 3: 0+0+10), điện thoại 2, 3 cũng có chi phí 10, điện thoại 4 có chi phí 10 (so với điện thoại 1: 5+5+0). Cả bốn bằng nhau nên in chỉ số nhỏ nhất.

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.402 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.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0