TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

18.4% (44/239)

Tags

Description

你聽說過<周強.h>的作者嗎?沒錯,就是周強。

這一切都得從周強#include <周強.h>的那天說起。自從那天,他開始吸收周圍的暗能量,變得愈來愈周強。在少年時便發明了自動AC機,把所有的題目全部秒完,得到了特級摳德(coder)的稱號,導致找不到可以寫的題目。他又用O(n)把宇宙持久化,於是算出了生命、宇宙以及任何事情的終極答案。隨著他的周強度增長到凡人不可理解的境界,有些能力漸漸變得無法掌控。他開始不小心把一些東西周異,例如各大Judge、天空,甚至他自己的大腦。

雖說周強是傳說中擁有六萬五千顆大腦的人,但是日子一天天的過去,大腦不斷地被周異又自動重生,令這些大腦之間的連結變得十分雜亂,使周強變得更不穩定。要知道,就算有大量的大腦,也要有妥善的連結才能發揮作用。於是乎,周強決定重新規劃自己的大腦。

周強現在擁有N顆大腦,大腦和大腦之間要有一條神經鍊才能互相溝通,而神經鍊會經過一些持久化同步器(定義在<周強.h>裡,可以經過很多個,但是至少要經過一個)。持久化同步器負責匯集來自一些大腦或另一個同步器的訊息。由於不能讓兩個大腦之間的訊息產生干涉,所以任兩個大腦之間只能有一條神經鍊。神經鍊被持久化同步器分隔的每一段稱為一條神經,每條神經都有一個訊息傳遞時間T,所以如果一個訊息要從一個大腦傳到另一個大腦,所需要的時間就是每一段訊息傳遞時間的總和。每一個持久化同步器都會連結三條或以上的神經。

下圖就是一個大腦連結的例子。

(在上圖中,標示英文字母的方格的是持久化同步器,標示數字的圓圈是大腦,而之間的線代表神經,旁邊的數字是訊息傳遞時間。綠色線代表大腦0到大腦 7的神經鍊,傳遞時間為6+1+1+5+3=16。)

每一個持久化同步器都會有一個穩定度,穩定度愈大則它愈穩定。如果從某個持久化同步器傳訊息到任意一個大腦最多需要耗費的時間為R,那麼這個同步器的穩定度就是–R(他是周強,所以穩定度當然是負的)。一個大腦規劃的穩定度就是最穩定(R愈小愈好)的持久化同步器的穩定度。

但是周強在尋找不可視境界線的旅程中遇到了重量之神CBD正在吃魔法晚餐,領悟到了胖的神力,因此他還可以藉由召喚CBD來改變大腦的穩定度。要知道,身為重量之神,CBD是可以任意操控周圍的重力的。然而CBD實在是太胖了,所以要挪出足夠的空間才能召喚他。因此,周強可以移除最穩定的持久化同步器,並且滿足移除後任何一組可以互相溝通的大腦數量都不超過$ [n/2] $($ [x] $ 代表不大於$ x $ 的最大整數)。如此一來,CBD感應到重力場(與電場)的變化,就會降臨在被移除的持久化同步器上,重新連結所有神經,並且瞬間反轉整個空間的重力場,使原本–R的穩定度變成R。
(注意,周強只有在完成整個大腦規劃之後才可以召喚CBD。如果有超過一個最穩定的持久化同步器,那麼周強只要移除其中一個滿足條件的就可以了。)

簡單來說,如果符合條件就可以召喚CBD使穩定度變成正數,否則穩定度就是負數。

現在周強已經按照<周強.h>的計算結果擬定好任意兩個大腦之間的訊息傳遞時間,希望你幫他算出這樣的大腦配置可以有多大的穩定度。然而他是O(n)的周強,而且持久化同步器是<周強.h>裡的最高機密,所以他只會讓你問Q次,每次告訴你某兩個大腦之間的訊息傳遞時間,避免浪費他自己寶貴的時間。

Input Format

這題不需要輸入,如果你輸入了任何東西,你會將得到一個WA

你有以下幾個與周強溝通的函數,請#include "lib1889.h"之後,依照規定呼叫這些函數。

int Init();:請在一開始或者傳出答案之後呼叫,將回傳一個整數N,代表周強告訴你他共有N個需要規劃的大腦。如果周強所有需要規劃的大腦都規劃完成了,周強會自動幫你結束程式。
void answer(int);:在呼叫上面的函數後,請在計算完成後呼叫這個函數,並傳入一個整數R(或-R),代表周強規劃的大腦最好的穩定度。

int getDistance(int, int);:你可以在限制的次數內呼叫這個函數,並傳入兩個數字a, b,代表你想知道第a和第b個大腦之間的訊息傳遞時間。如果你呼叫這個函數的次數超過Q次,你的code會被周強電爛而得到一個WA

對於所有的測資,$ 6 \le N \le 110 $。
對於13%的測資, $ Q = \frac{N(N-1)}{2} $ ,且你不需要考慮CBD有沒有降臨,所以答案正負不論。
對於12%的測資, $ Q = \left \lceil \frac{7N}{2} \right \rceil $ ,且你不需要考慮CBD有沒有降臨,所以答案正負不論。
對於13%的測資, $ Q = \frac{N(N-1)}{2} $ 。
對於10%的測資, $ Q = \left \lceil \frac{7N}{2} \right \rceil $ ,且保證每個持久化同步器都恰好連接3條神經。
對於13%的測資, $ Q = 5N $ 。
對於39%的測資, $ Q = \left \lceil \frac{7N}{2} \right \rceil $ 。

($ \lceil x \rceil $ 代表不小於 $ x $ 的最小整數)

Output Format

這題不需要輸出,如果你輸出了任何東西,你將得到一個WA

Sample Input

這題沒有輸入。

Sample Output

這題沒有輸出。

Hints

周強曰:「我的大腦數量哪有剩那麼少!」

Problem Source

IOI 2015 Day 2
Problem set / Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 13
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 13
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 13
For Testdata: 5 ~ 5, Score: 39
No. Time Limit (ms) Memory Limit (KiB)
0 2000 262144
1 2000 262144
2 2000 262144
3 1000 262144
4 2000 262144
5 2000 262144