通信_美团笔试题

有N个信号塔，第i个塔的位置是i，信号强度X_i(X_i保证互不相同)。有N个人，第i个人的位置是i，一个人往左走一格要A秒，往右走一格要B秒。这些人之间要传递信息，具体地，如果i有信息，那么i会依次做以下操作：
- 选择一个j满足1 ≤ j ≤ i，并找到一个k使得j ≤ k ≤ i并且X_k最大来保证通信。
- i, j同时向k移动，先到的会等另一个人直到两个人都到达。
- 等到i,j都到达k时，信息的传递瞬间完成，并且i,j瞬间回到原来的位置。
- 之后i会失去信息，j会获得信息。
请对每个i计算，如果初始i有信息，那么最少多少时间以后信息可以传递到1，并输出最少时间的方案数，方案数对2^32取模。一个方案可以被描述成P_1=i,P_2,P_3,...,P_t=1，表示信息的传递是P_1->P_2->P_3-> ...->P_t。两个方案被认为是不同的当且仅当t不同或者存在一个1 ≤ i ≤ t使得P_i不同。特殊地，对于1，我们认为最少时间是0，方案数为1。

令f[i]表示从i出发的最小时间,g[i]表示最小时间的方案数。输出两行，第一行f[1] xor f[2] xor f[3] xor ... xor f[n] 第二行g[1] xor g[2] xor g[3] xor g[4] xor ... xor g[n]。 f[n]请转成64位有符号整形(c++ long long)计算xor。 g[n]请转成32位无符号整形(c++ unsigned int)计算xor。

通信

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题