2. Rage Quit - Грешно броене на уникалните символи

Joro_Paspalev 23 Точки

2. Rage Quit - Грешно броене на уникалните символи

Здравейте,

имам проблем с тази задача, който втори ден немога да реша.

Judge ми дава 50/100, но не само това е проблема.

В задачата се искат 2 неща:

1. Да се принтира броя на уникалните символи

2. Да се повторят всички нецифрови знаци или последователност от такива n на брой пъти, като n е число следващо всеки такъв знак или група от знаци.

При първото условие срещам следния проблем - при определен вход ми връща брой уникални символи 54 а Judge иска 53. Нямам никаква представа откъде се получава това разминаване.

Пробвах различни начини на Regex-ите, със StringBuilder, само със String, гледах решения с метода .Distrinct() (за който едва сега разбрах, че съществува, след доста ровене в нета, който уж премахва еднаквите символи в дадена колекция), но отново няма промяна на изхода.

С второто условие няма проблем - принтират се всички необходими групи последователно, толкова пъти колкото се иска. Дори в Judge излизат правилно.

Въпроса ми е защо едното условие излиза а другото не, като и двете неща зависят от един и същи вход? Няма никаква логика.

Ето условието на задачата:

Every gamer knows what rage-quitting means. It’s basically when you’re just not good enough and you blame everybody else for losing a game. You press the CAPS LOCK key on the keyboard and flood the chat with gibberish to show your frustration.

Chochko is a gamer, and a bad one at that. He asks for your help; he wants to be the most annoying kid in his team, so when he rage-quits he wants something truly spectacular.

He’ll give you a series of strings followed by non-negative numbers, e.g. "a3"; you need to print on the console each string repeated N times; convert the letters to uppercase beforehand. In the example, you need to write back "AAA".

On the output, print first a statistic of the number of unique symbols used (the casing of letters is irrelevant, meaning that 'a' and 'A' are the same); the format shoud be "Unique symbols used {0}". Then, print the rage message itself.

The strings and numbers will not be separated by anything. The input will always start with a string and for each string there will be a corresponding number. The entire input will be given on a single line; Chochko is too lazy to make your job easier.

Input

The input data should be read from the console.
It consists of a single line holding a series of string-number sequences.
The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output should be printed on the console. It should consist of exactly two lines.
On the first line, print the number of unique symbols used in the message.
On the second line, print the resulting rage message itself.

Constraints

The count of string-number pairs will be in the range [1 … 20 000].
Each string will contain any character except digits. The length of each string will be in the range [1 … 20].
The repeat count for each string will be an integer in the range [0 … 20].
Allowed working time for your program: 0.3 seconds. Allowed memory: 64 MB.

Examples

Input

Output

Comments

Unique symbols used: 1

AAA

We have just one string-number pair. The symbol is 'a', convert it to uppercase and repeat 3 times: AAA.

Only one symbol is used ('A').

aSd2&5s@1

Unique symbols used: 5

ASDASD&&&&&S@

"aSd" is converted to "ASD" and repeated twice; "&" is repeated 5 times; "s@" is converted to "S@" and repeated once.

5 symbols are used: 'A', 'S', 'D', '&' and '@'.

Ето го и входа, който ми дава това разминаване в Judge:

e-!btI17z=E:DMJ19U1Tvg VQ>11P"qCmo.-0YHYu~o%/%b.}a[=d15fz^"{0^/pg.Ft{W12`aD<l&$W&)*yF1WLV9_GmTf(d0($!$`e/{D'xi]-~17 *%p"%|N>zq@ %xBD18<Y(fHh`@gu#Z#p"Z<v13fI]':\Iz.17*W:\mwV`z-15g@hUYE{_$~}+X%*nytkW15

Моя код с използване на метода .Distrinct(): https://pastebin.com/uab9YBFn

Код с попълване на данните в List(): https://pastebin.com/PndaSUif

Link към задачата в Judge: https://judge.softuni.bg/Contests/Practice/Index/1754#1

Моля, помагайте, някой който има някакви идеи къде бъркам да сподели.

Поздрави,

Тагове:

30/07/2019 22:21:36 Fundamentals Module

Виж всички отговори

Iv_Konov 383 Точки

Здравей,

1. Уникалните символи - броиш ги без оглед на броя на "умножаване" - repeated N times, т.е. допълваш символи дори и множителят да е нула. Вероятно точно затова е даден трети нулев тест - точно в него има 0 за повтаряне. :)

2.. Пробвай да си намериш вариант за решение като разделиш/опростиш регекс-а на две части - едната за числа, втората за символите.

В твоя код за трети нулев тест за регекса е нужно това време. Вероятно има и много по-яки тестове.

00:00:00.0030958

В моя код за двата разделени регекса е:

00:00:00.0001412

Пример за тест:

===

Stopwatch sw = Stopwatch.StartNew();
var dataWithoutDigits = Regex.Matches(text, @"(?<symbols>\D+)(?<count>\d+)");
Console.WriteLine(sw.Elapsed);

===

Решил съм я, но веротно не ти трябва решение...

Поздрави,

Иван

01/08/2019 11:49:56

Iv_Konov 383 Точки

p.s.

Пробвал съм няколко решения, но вариант с Array е по-леко решение в сравнение с MatchCollection .

Реално:

MatchCollection - Time: 0.262 s

Array - Time: 0.168 s

А на колега от групата има решение без регекс:... само за сравнение:

Memory: 16.01 MB
Time: 0.106 s

Поздрави,

Иван

01/08/2019 12:39:25

Joro_Paspalev 23 Точки

Здравей,

тук не е ли точно обратното:

"броиш ги без оглед на броя на "умножаване" - repeated N times, т.е. допълваш символи дори и множителят да е нула"

Аз си мисля, че ако има 0 след групата символи те не трябва да се отчитат като уникални(ако има такива) и от там ми дава разликата между 54 и 53 символа, защото аз ги броя още на входа а трябва да ги броя от StringBuilder-а? Може и аз да бъркам!

Относно

"2. Пробвай да си намериш вариант за решение като разделиш/опростиш регекс-а на две части - едната за числа, втората за символите."

немога да схвана как да го разделя т.е. ако го разделя само по числа в един List например и по символи в друг, как после ще знам кое колко пъти трябва да го повторя.

Може ли твоето решение да погледна?

Също и това не ми е ясно:

"Пробвал съм няколко решения, но вариант с Array е по-леко решение в сравнение с MatchCollection"

Как да ги вкарам в Array? По какво да ги сплитна? Шах Мат :)

Много питам, но това е защото много искам да науча ;)

Поздрави,

01/08/2019 17:41:52

Joro_Paspalev 23 Точки

Ето това успях да измисля: https://pastebin.com/Zgcdx20g но отново не получавам време под 0.262 s

Минава на 100/100, но искам по другия вариант и да смъкна времето на 0.168 s

Помощ!!!

01/08/2019 18:42:09

Iv_Konov 383 Точки

Здравей,

Заповядай:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace _2._Rage_Quit
{
    class Program
    {
        static void Main(string[] args)
        {
            string sequence = Console.ReadLine().ToUpper();

            Regex numChecker = new Regex(@"([\d]+)");
            Regex symChecker = new Regex(@"([\D]+)");
            StringBuilder resSequence = new StringBuilder();
            List<char> uniqueSymList = new List<char>();
            int[] numArr = numChecker.Matches(sequence).Select(x => x.Value).Select(int.Parse).ToArray();
            string[] symArr = symChecker.Matches(sequence).Select(x => x.Value).ToArray();

            for (int i = 0; i < symArr.Length; i++)
            {
                for (int j = 0; j < numArr[i]; j++)
                {
                    resSequence.Append(symArr[i]);
                }
            }

            for (int i = 0; i < symArr.Length; i++)
            {
                if (numArr[i] == 0)
                {
                    continue;
                }

                foreach (var sym in symArr[i])
                {
                    if (!uniqueSymList.Contains(sym))
                    {
                        uniqueSymList.Add(sym);
                    }
                }
            }

            Console.WriteLine($"Unique symbols used: {uniqueSymList.Count}");
            Console.WriteLine(resSequence);
        }
    }
}

Поздрави,

Иван

01/08/2019 20:48:42

Виж всички отговори