EXPRESSION - Ngôn ngữ lập trình mới

View as PDF

Submit solution

Points: 100.00
Time limit: 1.0s
Memory limit: 1000M
Input: stdin
Output: stdout

Author:
Problem types
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

An đang học một ngôn ngữ lập trình mới. Ngôn ngữ này chỉ sử dụng các mảng số. Mảng số gồm ~n~ phần tử trong ngôn ngữ này được ký hiệu là ~[x_1,x_2...,x_n]~. Ngoài ra ngôn ngữ lập trình này còn cung cấp các hàm sau:

  • ~link(expression\_1, expression\_2)~: hàm này giúp trả về mảng được ghép bởi mảng được tính toán trong ~expression\_1~, theo sau là mảng được tính toán trong ~expression\_2~. Ví dụ như ~link([1,2],[3,4]) = [1,2,3,4]~.
  • ~mix(expression)~: hàm này giúp xáo trộn ngẫu nhiên lại mảng được tính toán trong ~expression~ với xác suất như nhau. Ví dụ như ~mix([1,2]) = [1,2]~ với xác suất ~1/2~ và ~mix([1,2]) = [2,1]~ với xác suất ~1/2~.
  • ~sort(expression)~: hàm này giúp sắp xếp lại mảng được tính toán trong ~expression~ theo thứ tự không giảm. Ví dụ như ~sort([3,1,3,4]) = [1,3,3,4]~.

Bình gửi cho An hai dãy lệnh của ngôn ngữ nói trên và nhờ An kiểm tra xem, hai dãy lệnh đó có tương đương với nhau hay không. Hai dãy lệnh được gọi là tương đương với nhau khi với mỗi kết quả, xác suất để đạt được kết quả đó của cả hai dãy lệnh là bằng nhau.

Dữ liệu
  • Dòng đầu tiên chứa xâu ~S_1~ tương ứng với dãy lệnh thứ nhất.
  • Dòng thứ hai chứa xâu ~S_2~ tương ứng với dãy lệnh thứ hai.
Kết quả
  • Nếu hai dãy lệnh tương đương với nhau, in ra equivalent, ngược lại in ra not equivalent.
Ví dụ
Sample Input 1
link([1,2],sort([4,3]))
link([1,2,3],[4])
Sample Output 1
equivalent
Sample Input 2
mix([1,2,3,4])
mix([1,2,3,4])
Sample Output 2
equivalent
Sample Input 3
mix([1,2,3,4]) 
sort([4,3,2,1])
Sample Output 3
not equivalent
Sample Input 4
link(mix([1]),sort([3,2,1])) 
link(sort([1,2,1]),mix([3]))
Sample Output 4
equivalent
Giải thích
  • Trong ví dụ thứ nhất, cả hai dãy lệnh đều trả về kết quả là ~[1,2,3,4]~.
  • Trong ví dụ thứ hai, với mọi kết quả trả về thì xác suất để trả về kết quả đó của cả hai dãy lệnh đều là ~1/24~.
  • Trong ví dụ thứ ba, có thể dễ nhận thấy hai lệnh không tương đương.
  • Trong ví dụ thứ tư, cả hai dãy lệnh đều trả về kết quả là ~[1,1,2,3]~.
Giới hạn
  • Độ dài xâu ~S_1~, ~S_2~ không vượt quá ~2 × 10^6~.

Nguồn: Free Contest


Comments

Please read the guidelines before commenting.


There are no comments at the moment.