Codejam 2018 qualification round question number 1 and solutions in c++(CPP)
Problem:
An alien robot is threatening the universe, using a beam that will destroy all algorithms knowledge. We have to stop it!
Fortunately, we understand how the robot works. It starts off with a beam with a strength of 1, and it will run a program that is a series of instructions, which will be executed one at a time, in left to right order. Each instruction is of one of the following two types:
C(for "charge"): Double the beam's strength.S(for "shoot"): Shoot the beam, doing damage equal to the beam's current strength.
For example, if the robot's program is
SCCSSC, the robot will do the following when the program runs:- Shoot the beam, doing 1 damage.
- Charge the beam, doubling the beam's strength to 2.
- Charge the beam, doubling the beam's strength to 4.
- Shoot the beam, doing 4 damage.
- Shoot the beam, doing 4 damage.
- Charge the beam, increasing the beam's strength to 8.
In that case, the program would do a total of 9 damage.
The universe's top algorithmists have developed a shield that can withstand a maximum total of D damage. But the robot's current program might do more damage than that when it runs.
The President of the Universe has volunteered to fly into space to hack the robot's program before the robot runs it. The only way the President can hack (without the robot noticing) is by swapping two adjacent instructions. For example, the President could hack the above program once by swapping the third and fourth instructions to make it
SCSCSC. This would reduce the total damage to 7. Then, for example, the president could hack the program again to make it SCSSCC, reducing the damage to 5, and so on.
To prevent the robot from getting too suspicious, the President does not want to hack too many times. What is this smallest possible number of hacks which will ensure that the program does no more than D total damage, if it is possible to do so?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing an integer D and a string P: the maximum total damage our shield can withstand, and the robot's program.
Output
For each test case, output one line containing
Case #x: y, where x is the test case number (starting from 1) and y is either the minimum number of hacks needed to accomplish the goal, or IMPOSSIBLE if it is not possible.Limits
1 ≤ T ≤ 100.
1 ≤ D ≤ 109.
2 ≤ length of P ≤ 30.
Every character in P is either
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ D ≤ 109.
2 ≤ length of P ≤ 30.
Every character in P is either
C or S.Time limit: 20 seconds per test set.
Memory limit: 1GB.
Test set 1 (Visible)
The robot's program contains either zero or one
C characters.Test set 2 (Hidden)
No additional restrictions to the Limits section.
Sample
Input | Output |
6 1 CS 2 CS 1 SS 6 SCCSSC 2 CC 3 CSCSS | Case #1: 1 Case #2: 0 Case #3: IMPOSSIBLE Case #4: 2 Case #5: 0 Case #6: 5 |
Note that the last three sample cases would not appear in test set 1.
In Sample Case #1, the President can swap the two instructions to reduce the total damage to 1, which the shield can withstand.
In Sample Case #2, the President does not need to hack the program at all, since the shield can already withstand the 2 total damage it will cause.
In Sample Case #3, the program will do more damage than the shield can withstand, and hacking will do nothing to change this. The universe is doomed.
Sample Case #4 uses the program described in the problem statement. The statement demonstrates one way to reduce the total damage to 5 using two hacks. It is not possible to reduce the damage to 6 or less by using only one hack; remember that the President can only swap adjacent instructions.
In Sample Case #5, the robot will never shoot, and so it will never do any damage. No hacking is required.
In Sample Case #6, five hacks are required. Notice that even if two hacks swap the instructions at the same two positions, they still count as separate hacks.
Solution: C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
template<class T,class U>
ostream &operator<<(ostream &os,const pair<T,U> &x) {
return os<<"("<<x.first<<","<<x.second<<")";
}
namespace dbg_ns {
template<typename C>
struct is_iterable {
template<class T> static long check(...);
template<class T> static char check(int,
typename T::const_iterator = C().end());
enum {
value = sizeof(check<C>(0)) == sizeof(char),
neg_value = sizeof(check<C>(0)) != sizeof(char)
};
};
template<class T> ostream &_out_str(ostream &os,const T &x) {
return os<<'"'<<x<<'"';
}
template<class T> ostream &_dbg2_5(ostream &,const T &);
template<bool B,typename T=void> using eit=typename enable_if<B,T>::type;
template<class T>
inline ostream &_dbg3(ostream &os,eit<is_iterable<T>::neg_value,const T> &x) {
return os<<x;
}
template<class T>
inline ostream &_dbg3(ostream &os,eit<is_iterable<T>::value,const T> &V) {
os<<"{";
bool ff=0;
for(const auto &E:V) _dbg2_5(ff?os<<",":os,E), ff=1;
return os<<"}";
}
template<>
inline ostream &_dbg3<string>(ostream &os,const string &x) {
return _out_str(os,x);
}
template<>
inline ostream &_dbg3<const char *>(ostream &os,const char *const &x) {
return _out_str(os,x);
}
template<class T> inline ostream &_dbg2_5(ostream &os,const T &x) {
return _dbg3<T>(os,x);
}
template<class T,typename... Args> ostream &_dbg2(ostream &os,vector<string>::iterator nm,const T &x,Args&&... args);
inline ostream &_dbg2(ostream &os,vector<string>::iterator) { return os; }
template<typename... Args>
inline ostream &_dbg2(ostream &os,vector<string>::iterator nm,const char *x,Args&&... args) {
return _dbg2(_dbg3<const char *>(os<<" ",x),nm+1,args...);
}
template<class T,typename... Args>
inline ostream &_dbg2(ostream &os,vector<string>::iterator nm,const T &x,Args&&... args) {
return _dbg2(_dbg3<T>(os<<" "<<*nm<<"=",x),nm+1,args...);
}
vector<string> split(string s) {
vector<string> Z;
string z="";
s+=',';
int dep=0;
for(char c:s) {
if(c==',' && !dep) Z.push_back(z),z="";
else z+=c;
if(c=='(') ++dep;
if(c==')') --dep;
}
return Z;
}
template<typename... Args> inline ostream &_dbg1(int ln,const string &nm,Args&&... args) {
auto nms=split(nm);
return _dbg2(cerr<<"L"<<ln<<":",nms.begin(),args...)<<endl;
}
}
#define dbg(...) dbg_ns::_dbg1(__LINE__,#__VA_ARGS__,__VA_ARGS__)
#define sz(x) (int(x.size()))
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
// END SUBLIME HAX
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld; //CARE
typedef complex<ld> pt;
const ld eps=(ld)1e-8;
const ld tau=2*(ld)acosl(-1);
const int inf=1e9+99;
const ll linf=1e18+99;
const int P=1e9+7;
void go(int tn) {
printf("Case #%d: ",tn);
int D; string S;
cin>>D>>S;
int cc=0;
for(char c:S) if(c=='S') ++cc;
if(cc>D) {
printf("IMPOSSIBLE\n");
return;
}
int str=1;
int W=0;
for(char c:S) {
if(c=='S') W+=str;
else str*=2;
}
int Z=0;
for(;W>D;) {
for(int i=sz(S);--i>=0;) {
if(i>0 && S[i]=='S' && S[i-1]=='C') {
int w=1;
for(int j=0;j<i-1;j++) if(S[j]=='C') w*=2;
W-=w;
swap(S[i],S[i-1]);
++Z;
goto next;
}
}
next:;
}
printf("%d\n",Z);
}
int32_t main() {
int T; cin>>T; for(int t=1;t<=T;t++) go(t);
}
Comments