COCI 2016/2017 - Contest 7 - Poklon

View as PDF

Submit solution

Points: 0.90 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 7
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nhân vật chính trong bài này là Kile, còn được biết đến là chúa hề chuyên ngồi trên ghế dự bị ở đội bóng thất học El locos. Hôm nay là ngày sinh nhật của Kile.

Bạn thân của Kile là Ivan đã quyết định sẽ tặng Kile một cái cân đặc biệt. Điều đặc biệt nằm ở chỗ là chiếc cân có tính đệ quy, tức là ở cuối mỗi đòn cân, hoặc sẽ là một quả cân, hoặc sẽ là một cái cân mới, hoặc chẳng có gì cả. Tất nhiên, cái cân sẽ nghiêng về bên nào mà khối lượng ở bên đó nặng hơn. Nếu hai bên nặng bằng nhau thì cân thăng bằng.

Kile vô cùng thích thú với món quà này, và vốn là một nhà khoa học máy tính đại tài, anh lập tức cố gắng làm cho chiếc cân thăng bằng với những quả cân mới sao cho tổng khối lượng là nhỏ nhất có thể. Những quả cân cần phải có khối lượng là một số dương (có thể là số thực). Cái cân đệ quy sẽ cân bằng nếu như tất cả các "cân con" nằm trong cái cân đó đều thăng bằng và tổng khối lượng của hai bên đòn cân là bằng nhau.

Sau khi thành công làm chiếc cân thăng bằng, Kile quyết định xăm lên ngực mình tổng khối lượng của những quả cân được đặt trên chiếc cân ở dạng nhị phân, không có số ~0~ ở đầu. Hãy tìm số được xăm trên ngực Kile.

Input

Dòng đầu gồm số nguyên dương ~N~ ~(1 \le N \le 10^6)~ là số cân mà cái cân đệ quy của Kile chứa (cả chính nó).

Dòng thứ ~i~ trong ~N~ dòng tiếp theo gồm hai số nguyên miêu tả lần lượt đòn cân bên trái và bên phải của cân thứ ~i~. Nếu ở bên đòn cân đó là một cân khác, thì sẽ được miêu tả bằng số nguyên ~j~ là số hiệu của cái cân này. Còn nếu là một quả cân thì sẽ là một số nguyên âm, và khối lượng của quả cân này sẽ là trị tuyệt đối của số nguyên âm nói trên. Cái cân gốc chứa tất cả các cân khác có số hiệu là ~1~.

Tất cả các số trong input đều có giá trị tuyệt đối không quá ~10^9~.

Output

Dòng duy nhất in ra số mà Kile xăm trên ngực. Số này cần được viết dưới dạng nhị phân và không chứa chữ số ~0~ ở đầu.

Sample 1

Input
2
2 -10
-4 -3
Output
10100
Giải thích

Ví dụ trên chính là hình ảnh ở trên. Kile sẽ thêm một quả cân với khối lượng ~1~ vào bên có khối lượng ~4~ và một quả cân có khối lượng ~2~ vào bên có khối lượng ~3~. Như vậy, tổng khối lượng của các quả cân là ~20~ và có dạng nhị phân là ~10100~.

Sample 2

Input
4
2 3
-9 4
-2 -13
-1 -7
Output
111000

Comments

Please read the guidelines before commenting.


There are no comments at the moment.