countStepsTaken

[Problem E – Sasuke CodeWar #30]

Hải có một ma trận a được thiết lập như sau:

• a[i].size()=2. (0 ≤ i < a.size()).
• a[i][0] ≤ a[i][1].

Một lần biến đổi Hải thực hiện các việc như sau:

• Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1]
• Xóa tất cả các phần tử mà a[i][0] = a[i][1]

Hải muốn biết phải biến đổi bao nhiêu lần để a không còn phần tử nào.

Ví dụ:

• Với a = [[1,2],[3,5],[2,4],[5,6]] thì countStepsTaken(a) = 2.
  Giải thích:
  • Lần biến đổ thứ 1:
    • Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[2,2],[4,5],[3,4],[6,6]]
    • Xóa a[0] và a[3], a = [[4,5],[3,4]]
  • Lần biến đổi thứ 2:
    • Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[5,5],[4,4]
    • xóa a[0] và a[1], lúc đó a rỗng và kết thúc.
• Với a = [[1,2],[2,3],[3,4]]  thì countStepsTaken(a) = 1.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Matrix: Integer: a.
  0 ≤ a.size() ≤ 105.
a[i].size()=2; 
|a[i]| ≤ 109.

• [Đầu ra] Integer.
  Số bước biến đổi để matrix a rỗng.

Author: Phan Đức Hải

Fanpage: CodeLearn.io

Group: Codelearn – Tự học lập trình C#, C++, Java, Python,Basic algorithms.