I am stuck on the cyclic shift problem of code monks .
the problem cyclic shift on this page.
Am preparing for INOI .
My approach is that first I store all the indexes of most 1s together then check the values of the number formed by starting from those indexes and rule out the numbers which are smaller.
than simply .
solution = k/myVector.size()*n + myVector.at(k%myVector.size());
but am getting a wrong answer on this,
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int findTheBiggestPossibleNumber(string basicString, int n);
int main() {
int t;
std::cin >> t;
while (t > 0) {
int n,k;
string s;
cin >> n >> k >> s;
int ans = findTheBiggestPossibleNumber(s, k);
cout << ans << endl;
t--;
}
return 0;
}
int findTheBiggestPossibleNumber(string s, int k) {
int last1=-1;
int last1Real1 = -1;
int currMostContinous1s=0;
//make sure that first letter of the binary representation is 0;
int n = s.size();
int i =0;
for (; i < n && s.at(i)!='0'; ++i);
if(i==n){
return k-1;
}
for (; i < n && s.at(i)!='1'; ++i);
vector<int> maxS;
for (int j = 0; j < n; ++j) {
int currentI = (j+i)%n;
char currentChar = s.at(currentI);
if(currentChar == '1'){
if(last1 == -1) {
last1 = j;
last1Real1 = currentI;
}
}
else{
if(j-last1 > currMostContinous1s){
maxS.clear();
maxS.push_back(last1Real1);
currMostContinous1s = j- last1;
}
else if(j-last1 == currMostContinous1s) {
if(last1Real1 < i) {
maxS.insert(maxS.begin(), last1Real1);
}
else
maxS.push_back(last1Real1);
}
last1=-1;
}
}
for (int j = currMostContinous1s; j < n; ++j) {
bool thereIsA1AtJthValue = false;
for(vector<int>::iterator it = maxS.begin(); it != maxS.end(); ++it){
int currI = (*it + j)%n;
if(s.at(currI) == '1')
{
thereIsA1AtJthValue = true;
break;
}
}
if(thereIsA1AtJthValue){
for(vector<int>::iterator it = maxS.begin(); it != maxS.end(); ++it){
int currI = (*it + j)%n;
if(s.at(currI) == '0')
{
maxS.erase(it);
--it;
}
}
}
}
int ans = 0;
ans += ((k-1)/maxS.size())*n;
// for (int j = maxS.size()-1; j > 0; --j) {
// maxS[j] = maxS[j] - maxS[j-1];
// }
// for (int j = 0; j < maxS.size(); ++j) {
// cout << maxS[j] << " " ;
// }
// for (int j = 0; j < k; ++j) {
// ans+= maxS[j%maxS.size()];
// }
i=-1;
for (int j = ((k-1)/maxS.size())* maxS.size() ; j < k; ++j, i++);
if(i!=-1)
ans += maxS[i];
return ans;
}