Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_18_05 - k-objętość hiperprostokąta

Bitriusz wziął udział w corocznej konferencji dot. matematyki zaawansowanej. Poruszanym tematem była wielowymiarowość w praktyce. Po zakończeniu wszystkich wykładów Bitriusz nie mógł przestać myśleć o wymiarach. Wszystko co widział, kojarzył z przestrzenią wielowymiarową. Gdy rozwiązał mu się but, zamiast go zawiązać zaczął się zastanawiać jakie hiperprostokąty udałoby mu się zbudować z długości powstałych po pocięciu owej sznurówki. Skacząc od jednej myśli do drugiej, zorientował się, że nie wie jak podzielić ową sznurówkę na kawałki o długościach będących liczbami naturalnymi, by zmaksymalizować objętość k-wymiarowego prostokątu powstałego z nich. Np. sznurówki o długości 10 cm można nie ciąć i otrzymać k-objętość równą 10 cm. Można ją też podzielić na 2 części po 5 cm. Mamy wtedy 2-wymiarowy prostokąt o k-objętości wynoszącej 25 cm2 (jednostki nas nie interesują, liczy się wyłącznie wartość). Wydaje się, że jest to maksimum, które możemy osiągnąć. A może w 3 wymiarach otrzymalibyśmy więcej? Owszem! 3*3*4 daje nam 36 cm3 i jest to maksymalna wartość k-objętości. Bitriusz myślał i myślał, i nie udało mu się stworzyć algorytmu, który by optymalnie dzielił jego sznurówki. Może Tobie się uda.

Wejście

W pierwszej linii znajduje się liczba testów t (0 < t ≤ 100). Każdy test składa się z jednej linii zawierającej liczbę n (1 ≤ n ≤ 109) oznaczającej długość sznurówki Bitriusza.

Wyjście

Dla każdego testu należy wypisać maksymalną k-objętość hiperprostokątu jaką da się uzyskać poprzez pocięcie sznurówki na dowolną ilość kawałków. Wynik należy podać modulo 1010101.

Przykład

Wejście:
2
10
7

Wyjście:
36
12

Dodane przez:Piotr Kąkol
Data dodania:2014-08-29
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-08-30 21:13:33 Piotr KÄ…kol
Tak. "z długości powstałych po pocięciu owej sznurówki". Tak więc masz długości np. 4 i 5 i budujesz z nich prostokąt łącząc na przemian linie o tych długościach.
2014-08-30 21:11:07 Tomasz Homoncik
Prostokąt z 2 odcinków?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.