Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

BCTEST17 - Xếp hàng 2

Lại nhắc đến Chí Phèo khi xếp hàng đi mua Iphone 4S, trong lúc chờ đợi, anh lại nghĩ ra một bài toán để thử tài các bạn sinh viên PTIT.

Có tất cả N người xếp hàng.  Hai người A và B sẽ nhìn thấy nhau nếu giữa 2 người không có người nào cao hơn người A hoặc B. Bạn hãy xác định số cặp người có thể nhìn thấy nhau.

Dữ liệu:

Dòng 1: Một số nguyên duy nhất N (1≤N≤500 000) là số người đứng xếp hàng.

Dòng 2..N+1: Mỗi dòng là chiều cao của một người đứng xếp hàng theo thứ tự từ đầu hàng tới cuối hàng. Chiều cao một người không quá 231.

Kết quả:

Một số nguyên duy nhất là số cặp người xếp hàng có thể nhìn thấy nhau.

Ví dụ:

INPUT

OUTPUT

7

2

4

1

2

2

5

1

10

Giải thích:

-          Người ở vị trí thứ 1 có thể nhìn thấy người ở vị trí thứ 2

-          Người ở vị trí thứ 2 có thể nhìn thấy người ở vị trí thứ 1,3,4,5,6

-          Người ở vị trí thứ 3 có thể nhìn thấy người ở vị trí thứ 2,4

-          Người ở vị trí thứ 4 có thể nhìn thấy người ở vị trí thứ 2,3,5,6

-          Người ở vị trí thứ 5 có thể nhìn thấy người ở vị trí thứ 2,4,6.

-          Người ở vị trí thứ 6 có thể nhìn thấy người ở vị trí thứ 2,4,5,7.

-          Người ở vị trí thứ 7 có thể nhìn thấy người ở vị trí thứ 6

=>  Có tất cả 10 cặp người có thể nhìn thấy nhau.

 


ID RESULT TIME
code...


Submit solution!
Được gửi lên bởi:adm
Ngày:2011-11-17
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
hide comments
< Xem lại 1  2 Xem tiếp
2012-11-03 14:15:34 Tobi
Ai có ý tưởng cho bài này không ạ em chỉ làm được O(n^2) thôi
2012-04-05 18:28:25 1970
người 1 có độ cao là 2 thì bị người 2 có độ cao là 4 che khuất rồi. làm sao nhìn thấy người 6 được.
2012-02-28 15:13:00 Nguyễn Vãn Linh D10CN4
giữa 2 người không có người nào cao hơn A hoặc B thì đáp án thế kia hình như sai thì phải..như người 1 có thể nhìn người thứ 6 chứ nhỉ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.