题解 | #F. Energy Synergy Matrix#

题意

在一个2行n列的矩阵里，小小红沿着最短路径去n列的一个格子里，小红以最短路径最小为目的，放障碍，小紫以最短路径最大为目的，放障碍。障碍不能把路堵死，直到小小红到达n列截止，小红先手，输出最短路径。

关键词

构造，最短路径，规律

题解

小红的意图是让小红一直向右走，所以堵下面或上面，而小紫的意图是让小小红蛇皮S型走，即堵右面。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

 

小红放在（2，2）的活小小红最多向右走到3就要向下走了，如果放在（2，3），最多走在4就得向下，至于小紫为啥不能放在（1，2）阻挡，因为路不能被封死，其次如果放在（2，4）的话，小紫就可以放在（1，2）了，反而不是小红的立场了，因此第一回合小红会放在（2，3），小紫会放在（1，5）；

第二回合其实是一个道理，只不过小小红的起点变成（2，6），即小红与小紫的放置的行数2边1，1边2，与刚才一个道理，小红放在（1，8），小紫放在（2，10）。

然后会发现一个规律，小紫放在的列数一定是5的倍数，而小小红的路径数分为向右走和上下走的加起来，向右走一定是（n-1）与，障碍无关，而上下走的步数与小紫的障碍数有关，有几个障碍则转向几次，即有几步上下走，又因为列数是5的倍数，所以数量是n/5。

故最后的结果ans=(n-1)+n/5。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int n;
        cin>>n;
        cout<<n-1+n/5<<endl;
    }
}