Problem A
Að Skera Rétthyrning
Languages
de
en
et
is
lt
sv
Irus átti rétthyrning. Irus skar rétthyrninginn niður og fékk tvo rétthyrninga úr því. Hann setti annan rétthyrninginn til hliðar og hélt áfram að skera hinn þar til hann átti $K$ rétthyrninga. Hann passar sig að skera aldrei rétthyrningana sem hann setur til hliðar. Hliðarlengdir rétthyrningana eru alltaf heiltölur.
Eftir að hafa skorið þá niður raðar hann rétthyrningunum eftir lengd lengri hliðarinnar. Irus áttaði sig þá á því að þessar hliðarlengdir væru allar mismunandi. Styttri hliðarlengdirnar þurfa hins vegar ekki að vera mismunandi.
Verkefni
Irus gleymdi hliðarlengdunum á upprunalega rétthyrningnum. Hjálpaðu Irus að muna þær.
Inntak
Fyrsta línan inniheldur fjölda rétthyrninga $K$.
Næstu $K$ línur innihalda tvær jákvæðar heiltölur hver, $a_ i$ og $b_ i$, sem eru hliðarlengdirnar á rétthyrning númer $i$. Tölurnar eru raðaðar þannig að $a_ i \ge b_ i$ og $a_1 < \cdots < a_ K$.
Úttak
Á fyrstu línunni skaltu skrifa út $P$ - fjölda möguleika fyrir hliðarlengdir upprunalega rétthyrningsins.
Á næstu $P$ línunum skaltu skrifa út möguleikana, einn möguleika á hverri línu, sem inniheldur þá einungis styttri hliðarlengdina á mögulega rétthyrningnum. Athugaðu að við skrifum styttri hliðarlengdina af tilteknum rétthyrning einu sinni þó það væru margar leiðir til að skera hann niður í gefnu $K$ rétthyrningana.
Takmarkanir
-
$2 \leq K \leq 100\, 000$
-
$1 \leq b\_ i \leq a\_ i < a\_ {i+1} \le 5\, 000\, 000$ (fyrir öll $1 \leq i \leq K$).
Hlutverkefni
Nr. |
Stig |
Frekari takmarkanir |
1 |
25 |
$K \leq 10$. |
2 |
20 |
Öll $b_ i = 1$. |
3 |
55 |
Engar frekar takmarkanir. |
Sýnidæmi
Upprunalegi rétthyrningurinn hefði getað verið $2 \times 8$ eða $4 \times 4$.
Sample Input 1 | Sample Output 1 |
---|---|
3 2 1 3 2 4 2 |
2 2 4 |