Решение задачи Сломанная гирлянда с Codeforces

С пояснением   Просмотров: 20


Ничто не вечно в этом мире, понял Костя утром 7-го января, увидев частично перегоревшую четырехцветную гирлянду. Он сразу задался целью заменить сломанные лампочки, однако он не знает сколько лампочек каждого цвета требуется. Гарантируется, что для каждого из четырех цветов хотя бы одна лампочка осталась рабочей.

Известно, что гирлянда состоит из лампочек четырёх цветов: красного, синего, жёлтого и зелёного. Гирлянда сделана следующим образом: если вы возьмёте четыре любые подряд идущие лампочки, то среди них нет лампочек одинакового цвета. Например, гирлянда может иметь вид «RYBGRYBGRY», «YBGRYBGRYBG», «BGRYB», но не может «BGRYG», «YBGRYBYGR» или «BGYBGY». Буквы обозначают цвета: 'R' — красный, 'B' — синий, 'Y' — жёлтый, 'G' — зелёный.

Используя то, что для каждого цвета хотя бы одна лампочка всё еще горит, посчитайте количество перегоревших лампочек каждого из четырёх цветов.

Код

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100008];
int main() 
{
    string s;
    cin>>s;
    
    char a[4]={'R','B','Y','G'};
    char b[4];
    map<char,ll> mp;
    ll i,m=s.length();
    for(i=0;i<m;i++)
    {
        if(s[i]!='!')
        {
            b[i%4]=s[i];
        }
    }
    ll c=0;
    for(i=0;i<m;i++)
    {
        if(s[i]=='!')
        {
            mp[b[i%4]]++;
        }
    }
    for(i=0;i<4;i++)
    {
        cout<<mp[a[i]]<<" ";
    }
}

         

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


Так как ни какие четыре подряд идущие лампочки не должны быть одного цвета, а всего возможных цветов тоже четыре, то цвет у пятой лампочки такой же как у первой, цвет шестой лампочки совпадает с цветом второй лампочки, то есть цвет n-й лампочки равен цвету n - 4 лампочки.

Таким образом, координаты всех лампочек одного цвета равны по модулю 4.

По условию задачи задана координата хотя бы одной лампочки каждого цвета, значит мы можем восстановить всю гирлянду и одним проходом посчитать количество перегоревших лампочек.

За один проход по гирлянде мы узнаём каким числам по модулю 4 соответствуют цвета. А вторым проходом, зная на каком месте какая лампочка, подсчитываем количество перегоревших лампочек каждого цвета.

Асимптотика такого решения — O(n).

Также существует другое решение:

Можно просто перебирать цвета первых четырёх лампочек (всего 4! = 24 варианта), проверяя соответствие каждого варианта заданной гирлянде. Найдя цвета первых четырёх лампочек, легко воссоздаём гирлянду с работающими лампочками и подсчитываем количество перегоревших.

Это решение в худшем случае будет работать за 24·n.


Комментарии

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