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

BCSORT - Sắp xếp đảo

Xem xét thuật toán sắp xếp sau đây.

Thuật toán sắp xếp đảo (dãy a):

While  (a không là dãy không giảm)

            Phân đoạn dãy a thành một số tối thiểu các ‘đoạn dốc’

            Với mỗi đoạn dốc có chiều dài lớn hơn 1

                        Đảo đoạn dốc.

Một đoạn dốc là một dãy con liên tiếp giảm của a. Thủ tục đảo đoạn dốc sẽ đảo ngược lại các phần tử của đoạn với nhau.

Cho một hoán vị của N số tự nhiên đầu tiên với các đoạn dốc ban đầu có độ dài chẵn. Xác định số lần đảo đoạn dốc để được một dãy sắp xếp tăng dần.

Dữ liệu:

Một dòng chứa số nguyên dương N ( 1≤N≤100 000)

Dòng thứ 2 chứa hoán vị của N số tự nhiên đầu tiên cần sắp xếp.

Kết quả:

Một dòng duy nhất chứa số lần đảo đoạn dốc.

Ví dụ:

INPUT

OUTPUT

2

2 1

1

 

INPUT

OUTPUT

4

4 3 2 1

1

 

INPUT

OUTPUT

4

3 1 4 2

3

ID RESULT TIME
code...


Submit solution!
Được gửi lên bởi:adm
Ngày:2011-10-24
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
Nguồn bài:COCI 2011-2012 Contest 1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.