ჯაჭვი

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 8, ეტაპი 3


ბიტოტეტია ყოველთვის არ ყოფილა დემოკრატიული სახელმწიფო. მის ისტორიაში ასევე ყოფილა შავი ფურცლები. ერთხელ გენერალ ბაჟტელსკიმ, ბიტლანდიის მმართველმა, ძალაუფლების მოხვეჭის შემდეგ გადაწყვიტა დაესრულებინა საომარი მოქმედებები და გაათავისუფლა დაპატიმრებული  ოპოზიიციის აქტივისტები. თუმცა მას არ სურდა გაეთავისუფლებინა ბიტაზარის ოპოზიიციის ლიდერი და გადაწყვიტა ციხის კედლებზე დაება  ბიტური ჯაჭვით (Bytean chain). ბიტური ჯაჭვი შედგება ერთმანეთთან დაკავშირებული ბმულებისგან და კედელზე მიმაგრებული ღეროსგან. მიუხედავად იმისა, რომ თვითონ ბმულები არ არის დაკავშირებული კედელთან, ძალიან რთულია მათი მოხსნა. "გენერალო, რატომ დამატყვევეთ ნაცვლად იმისა, რომ გაგეთავისუფლებინეთ, როგორც ჩემი კომპანიონები!" - უთხრა ბიტაზარმა. "კი მაგრამ შენ არ ხარ დატყვევებული, შენ შეგიძლია მოხსნა ჯაჭვის ბმულები ღეროს, რაც გაკავებს ამ ციხის კედლებში" - უთხრა გენერალ ბაჟტელსკიმ, შემდეგ დაუმატა - "გაუმკლავდი ამას ციფრული საათის დაწყებამდე და არ ახმაურო ჯაჭვი ღამით, თორემ იძულებული ვიქნები დავუძახო სამოქალაქო ოფიცრებს". დაეხმარეთ ბიტაზარს.

ჯაჭვი შედგება n ცალი ბმულისგან. ბმულები გადანომრილია 1-დან n-ის ჩათვლით. ყოველი ბმული შეგვიძლია დავამაგროთ ან მოვხსნათ შემდეგი პრინციპების მიხედვით: ერთი მოქმედებით შეგვიძლია მხოლოდ ერთი ბმულის დამაგრება ან მოხსნა. ბმული No.1 ყოველთვის შეგვიძლია დავამაგროთ ან მოვხსნათ. თუ ბმულები 1,...,k-1 (1 <= k < n) არის მოხსნილი და ბმული No. k არის დამაგრებული მაშინ შეგვიძლია მოვხსნათ ან დავამაგროთ ბმული No. k+1.

 

დაწერეთ პროგრამა, რომელიც:

    წაიკითხავს ჯაჭვის აღწერას კონსოლიდან (stdin-დან),

    დაითვლის მოქმედებების მინიმალურ რაოდენობას ჯაჭვის ყველა ბმულის მოსახსნელად,

    გამოიტანს კონსოლში პასუხს (stdout-ში).

 

შემომავალი მონაცემები: 

პირველ ხაზზე შემოვა ერთი დადებითი რიცხვი n, 1 <= n <= 1000.

მეორე ხაზზე შემოვა n ცალი ერთი სფეისით დაშორებული რიცხვი, რომლებიც ეკუთვნის {0, 1} სიმრავლეს.

თუ მეორე ხაზზე შემოსული i-ური რიცხვი არის 1, მაშინ i-ური ბმული არის დამაგრებული.

თუ მეორე ხაზზე შემოსული i-ური რიცხვი არის 0, მაშინ i-ური ბმული არის მოხსნილი.

 

გამოტანა: კონსოლში უნდა გამოიტანოთ ერთი რიცხვი, რომელიც უდრის ჯაჭვის ყველა ბმულის მოსახსნელად მოქმედებების მინიმალურ რაოდენობას.




მაგალითები

შესატანი მონაცემები
4 1 0 1 0 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება

შენიშვნა

(ბმულები 1...k-1 ყველა უნდა იყოს 0 ანუ მოხსნილი, ბმული No. k უნდა იყოს 1 ანუ დამაგრებული და ამის შემდეგ შეგვიძლია ბმულ No. k+1ზე მოვახდინოთ ცვლილება, დავამაგროთ ან მოვხსნათ). ჩვენ გვსურს ყველა ბმული მოვხსნათ, ანუ ყოველი რიცხვი გახდეს 0. იმისათვის რომ მე-3 (თვლას 1დან ვიწყებთ) რიცხვი გავანულოთ, მე-2 რიცხვი უნდა უდრიდეს 1-ს და მანამდე სხვა ყველა 0-ს. ამისთვის ჯერ მე-2 რიცხვი (0) უნდა გავხადოთ 1, ხოლო მანამდე ყველა რიცხვი უნდა იყოს 0. ხოლო მე-2 რიცხვის შეცვლა შეგვიძლია როდესაც 1-ლი რიცხვი იქნება 1. 1-ლი რიცხვის შეცვლა ყოველთვის შეგვიძლია.

    1 0 1 0

    1 1 1 0

    0 1 1 0

    0 1 0 0

    1 1 0 0

    1 0 0 0

    0 0 0 0

ცვლილებები მოხდება შემდეგნაირად და ცვლილებების მინიმალური რაოდენობა იქნება 6.