Runda 12 - Biedronki

21.12.2009 - Damian Rusak
TrudnośćTrudność

 

Zawody stałe, runda 12;

Limit czasowy: 3s; Limit pamięciowy: 128MB;


W pewnym sadzie rośnie krzak. Na owym krzaku mieszka rodzina biedronek. Każda biedronka umiłowała sobie jedno miejsce krzaka i tam ustanowiła swoją siedzibę. Krzak składa się z liści i gałęzi. Jest tak wielki, że nawet najstarsze biedronki nie wiedzą, jak jest wielki. Wiedzą za to, że każdy liść krzaka jest połączony za pomocą gałęzi z dokładnie dwoma liśćmi powyżej. Wiedzą też, że pierwszy liść rośnie tuż przy ziemi, oraz że z każdego liścia można dojść do każdego innego (przechodząc po gałązkach i innych liściach) na dokładnie jeden sposób. Aby ułatwić sobie życie, biedronki ponumerowały liście - ten najniższy ma numer 1 oraz każde dwa liście, z którymi jest połączony niżej położony liść o numerze $ x $ mają numery $ 2x $ i $ 2x+1 $. Rodzina biedronek wpadła na pomysł, aby poodwiedzać się nawzajem. Każdego dnia jedna z biedronek udaje się w odwiedziny do drugiej, idąc tylko po liściach i gałęziach, po czym wraca do swojego domku. Tak dla każdej pary biedronek - kiedyś pierwsza odwiedzi drugą, a innym razem druga pierwszą. Mówimy, że biedronka przeszła w podróży $ k $ gałęzi, jeśli po drodze do innej i z powrotem przeszła łącznie po $ k $ gałęziach. Rodzina zastanawia się, ile łącznie przyjdzie im przejść gałęzi, przy założeniu, że każda biedronka wyprawi się do każdej innej dokładnie raz.

Zadanie:

Mając zadaną ilość biedronek w rodzinie oraz numery siedzib biedronek na krzaku, oblicz, ile w sumie przejdą biedronki, jeśli każda z nich wyruszy do każdej innej. (po każdej podróży biedronka wraca do swojego liścia).

Wejście:


Pierwsza linia wejścia zawiera jedną liczbę naturalną $ n $ $ (1 \leq n \leq 100000) $-  oznaczającą ilość biedronek w rodzinie. W kolejnym wierszu znajduje się $ n $ liczb $ a_{i} $ oznaczających numer siedziby $ i $-tej biedronki $ (1 \leq a_{i} \leq 10^{9}) $. Może się zdarzyć, że kilka biedronek mieszka w tym samym miejscu - wtedy koszt odwiedzenia się tych par wynosi zero.

Wyjście:


Wyjście powinno się składać z jednej linii, zawierającej jedną liczbę - ilość gałązek, które w sumie przebędą biedronki, jeśli każda odwiedzi każdą inną. Możesz założyć, że odpowiedź nie przekroczy $ 2^{63}-1 $.

Przykład:

Wejście:

5

3 6 5 8 6

 

Wyjście:

120

 

Biedronka z 3 liścia: 2*(1 + 1 + 3 + 4)  -> 18

Biedronki z 6 liścia - każda po 2 * (1 + 4 + 5) -> 40

Biedronka z 8 liścia 2*(5 + 5 + 3 + 4) -> 34

Biedronka z 5 liścia 2*(3 + 3 + 4 + 4) -> 28

Łącznie 120

 

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska10184:20:32
2Przemysław Derengowski10302:22:23
3Michał Karpiński106730:20:48
4Kuba Skudlarski8151:56:41
5Krzysztof Kapusta8468:08:51
6Michal Zgliczynski8712:46:47
7Mateusz Wasilewski82077:14:42
8Franciszek Okrzesik5129:51:20
9Wojciech Kuprianowicz5150:30:07
10Darek Bukowski5153:03:31
11Michał Okrasa51090:28:40
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com