The Rumbling is a hypothetical cataclysmic event involving Karl Fritz’s Wall Titans marching across the Earth, destroying all life upon it. Eren Yeager who possesses the Founding Titan has decided to begin The Rumbling to show the true power of the Eldians to the rest of the world.
- There are NN Titans standing in a line from west to east. Each of the Titans is facing one of the four directions i.e., North, South, East, or West, represented by uppercase English letters ‘N’, ‘S’, ‘E’, and ‘W’ respectively.
- A Titan can rotate on the spot where it is standing. It requires XX units of energy to rotate 9090 degrees clockwise, and YY units of energy to rotate 9090 degrees anti-clockwise.
- For the activation of The Rumbling, all the Titans must face Eren Yeager.
So, Eren wants to position himself on the West-East line (on which other Titans are standing). He can either stand to the left of all Titans, in between two consecutive Titans, or to the right of all Titans. He wants to choose a position that minimizes the units of energy required by all the Titans to rotate and face him. Find the minimum units of energy required by all the Titans for the Activation of the Rumbling in the optimal configuration.
#include <bits/stdc++.h> #define int long long int #define endl '\n' using namespace std; signed main() { int t;cin>>t; while(t--) { int n,x,y,i;cin>>n; string s; cin>>s; cin>>x>>y; int a[n+1],b[n+1]; a[0]=0;b[0]=0; for(i=0;i<n;i++) { if(s[i]=='E') { a[i+1]=a[i]+0; } else if(s[i]=='W') { a[i+1]=min(2ll*x,2ll*y)+a[i]; } else if(s[i]=='N') { a[i+1]=min(x,3ll*y)+a[i]; } else if(s[i]=='S') { a[i+1]=min(y,3ll*x)+a[i]; } } for(i=0;i<n;i++) { if(s[i]=='E') { b[i+1]=b[i]+min(2ll*x,2ll*y); } else if(s[i]=='W') { b[i+1]=0+b[i]; } else if(s[i]=='N') { b[i+1]=min(y,3ll*x)+b[i]; } else if(s[i]=='S') { b[i+1]=min(x,3ll*y)+b[i]; } } int ans=min(a[n],b[n]),z; for(i=1;i<n;i++) { z= a[i]+b[n]-b[i]; ans=min(ans,z); } cout<<ans<<endl; } return 0; }