Решение задачи "Троичная строка" с Codeforces

Без пояснения   Просмотров: 43


Вам дана строка s, каждый символ которой — 1, 2 или 3. Вы должны выбрать кратчайшую непрерывную подстроку s, в которой каждый из трех символов встречается хотя бы один раз.

Непрерывная подстрока s — строка, которую можно получить из s удалением какого-то количества (возможно, ни одного) символов из начала строки s и какого-то количества (возможно, ни одного) символов из конца строки s.

Код

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int j;
    bool b1 = 0, b2 = 0, b3 = 0;
    string s, t = "";
    cin >> s;
    s += "0";
    vector<int> ed, bg, res;
    for(int i = 0; i < s.size() - 1; ++i){
        if(s[i] != s[i + 1]){
            t+=s[i];
            ed.push_back(i);
        }
    }

    s.insert(s.begin(), 1, '0');
    for(int i = 0; i < s.size() - 1; ++i){
        if(s[i] != s[i + 1])
            bg.push_back(i);
    }
    if(t.size() < 3){
        cout << 0 << endl;
        return;
    }
    for(int i = 0; i < t.size() - 2; ++i){
        if(int(t[i]) +int(t[i + 1]) + int(t[i + 2]) == 150)
            res.push_back(i);
    }
    if(res.size() == 0){
        cout << 0 << endl;
        return;
    }
    int mn = INFINITY;
    for(int i = 0; i < res.size(); ++i){
        mn = min(bg[res[i] + 2] - ed[res[i]] + 1, mn);
    }
    cout << mn << endl;
}
int main() {
	int t;
	cin >> t;
	while(t--){
        solve();
	}
	return 0;
}

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться