Արդյո՞ք բինար ծառը լրիվ է
Ձեզ խնդրում են պարզել, թե արդյոք տրված բինար ծառը լրիվ է:
Լրիվ բინար ծառ (complete binary tree) ենք համարում այն ծառը, որի բոլոր մակարդակները ամբողջովին լցված են, բացառությամբ ամենացածր մակարդակի, որտեղ հանգույցները լցված են հնարավորինս ձախից սկսած:
Վերևում示ված երկու ծառերն էլ լցված են այս սկզբունքով և համարվում են լրիվ բինար ծառեր:
Մուտք
Մուտքը պարունակում է բացատով բաժանված ամբողջ թվեր, որոնք ներկայացնում են բինար ծառի հանգույցների արժեքները: Արժեքը տրվում է այնպես, ինչպես նկարագրված էր նախորդ հայտարարությունում (յուրաքանչյուր անգամ նախաճյուղում ձախ և ապա աջ ենթառառները դիտարկելու սկզբունքով): 0 արժեքը նշանակում է, որ տվյալ հանգույցը գոյություն չունի: Ենթադրվում է, որ մուտքագրված բինար ծառը վավեր է:
Ելք
Ծրագիրը ելքում պետք է տպի Yes, եթե բինար ծառը լրիվ է, իսկ հակառակ դեպքում՝ No:
Օրինակներ
Մուտք | Ելք |
|---|---|
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | No |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Բացատրություն
Օրինակ 1-ը լրիվ բինար ծառ է, քանի որ վերջին մակարդակը լցված է ձախից սկսած
Օրինակ 2-ը նույնպես լրիվ բինար ծառ է, քանի որ վերջին մակարդակի հանգույցները նույնպես լցված են ձախից սկսած
Օրինակ 3-ը լրիվ բինար ծառ չէ, քանի որ վերջին մակարդակը լցված չէ ձախից սկսած
Օրինակ 4-ը ևս լրիվ բինար ծառ չէ նույն պատճառով
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB