Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя fakehandle

Автор fakehandle, история, 3 года назад, По-английски

Hi everyone In contest This Question the solution i wrote . But now i am not able to find the logical mistake please help me to find logical mistake.

thanks in advance here is code

...
#include<iostream>
using namespace std;
#define ll long long int
int main(){
	ll t ;
	cin>>t;
	while(t--){
		ll n ,k;
		cin>>n>>k;
		string s;
		cin>>s;
		ll lastX=-1,lastS=-1;
		ll count=0;
		ll last=-1,i;
		for(i=0;i<n;i++){
			if(s[i]=='*'){
				s[i]='x';
				lastX=i;
				count++;
				break;
			}
		}
		for(i=n-1;i>=0;i--){
			if(s[i]=='*'){
				last=i;
				count++;
				s[i]='x';
				break;
			}
		}
		if(last==-1 || last &mdash; lastX<=k){
			cout<<count<<endl;
		}
		else{
			for(i=0;i<n;i++){
				if(s[i]=='*'){
					if(i-lastX<k){
						lastS=i;
					}
					else if((i-lastX==k))
					{
						s[i]='x';
						lastX=i;
						lastS=-1;
						count++;
					}
					else{
						s[lastS]='x';
						lastX=lastS;
						lastS=-1;
						count++;
					}
				}
			}
			if(last-lastX>k&&lastS!=-1){
				count++;
			}
			cout<<count<<endl;
		}
	}
}
...

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Pro tip: Please explain what you want your code to do, and your thought process for the solution, because it's hard to read code and understand it with no knowledge of what it's supposed to do.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

There are many things in your blog which makes it hard for anyone to debug

  1. No explanation of idea
  2. Bad formating (use spoilers or links for the code)
  3. Write sentences properly. I don't remember where I read this, but writing sentences properly using propper spelling, indentation, capitalization, etc. makes it more likely for people to take it seriously (and obviously easier to understand).

Anyway, the ideia is wrong from what I understood from the code, it is always taking the first character '*' possible, but that is not necessarily optimal. For a greedy solution, you should take the last '*' character possible which is in a distance of $$$k$$$ of the last character 'x'. You can also solve it with dp, it would be a good exercise.