Олимпиадное хобби. Разминка

[borisko]

Другой интересный подход к таким задачам — пытаться использовать комбинировать стандартные средства своего любимого языка программирования — например, std::next_permutation.

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

[goldenalfer]

Это задача одного алгоритма, и если использовать предложенную вами функцию, то хобби становится неинтересным. Но вы безусловно правы, хотя я честно надеялся, что компилятор запретит использовать std::next_permutation.
Кстати, очень жаль, что ни один из предложенных языков программирования на uva.onlinejudge.org не является моим любимым.

[Pr0grammer]

Предложите решение с помощью std:next_permutation, мне кажется что это будет задачка покруче исходной)

[Pr0grammer]

А, да. Я думал, что перестановки работают только с чистыми перестановками (я давно на плюсах не пишу).

[borisko]

#include <algorithm>                                                                                                                                                                                                             
#include <string>                                                                                                                                                                                                                
#include <iostream>                                                                                                                                                                                                              
                                                                                                                                                                                                                                 
std::string perm;                                                                                                                                                                                                                
                                                                                                                                                                                                                                 
int main()                                                                                                                                                                                                                       
{                                                                                                                                                                                                                                
        for(;;)                                                                                                                                                                                                                  
        {                                                                                                                                                                                                                        
                std::cin >> perm;                                                                                                                                                                                                
                if(perm[0] == '#') break;
                if(std::next_permutation(perm.begin(), perm.end()))
                {
                        std::cout << perm << std::endl;
                }
                else
                {
                        std::cout << "No Successor" << std::endl;
                }
        }
        return 0;
}

Accepted (но 0.012)

[Pr0grammer]

Да, я понял, что неправ) Думал, что стандартные перестановки работают только с перестановками без повторяющихся элементов. Эта задача старая. В те времена были задачи, которые сейчас можно решить стандартными средствами (их немного).

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

[tolikblik]

Они всё-таки хотят это сделать!!!
(я про имплантанты...)

[kefiijrw]

эхх, где мои 17 лет на spoj.pl
*хлынули воспоминания*

[Bkmz]

А я люблю там на питоне по писать))
Классный проект, все наши городские олимпиады просто рядом не стояли…

[ZloeSabo]

Еще есть acm.timus.ru/ — вроде должен быть известен каждому олимпиаднику.

[kashey]

гм, берем строку — baseconvert из 25тичной системы в 10тичную.
далее ++
далее обратно в 25тичную систему.
Перед этим пройтись и сделать символам шифт на '9' влево(в конце обратно) чтобы сместиться в начала всех систем — 0-9, перейдя из сета a-z в 0-('z'-9), с которым возможна работа стандартными операторами.

Я это про то что эта задача, по сути, на знание обычной арифметики :)

[garifzyanov]

Придется писать много длинной арфиметики или использовать соответсвующие библиотеки. К тому же, такое решение будет сильно медленнее.

[ABrandt]

Бред.
Здесь можно использовать только те символы, которые уже есть в строке. А у вас получится такое что при aaaa вы получите aaab.

[kashey]

еще проще — считаем сколько разных символов в строке. делаем map. делаем выше описанный base convert. делаем обратный map.
суть всеравно не меняется — надо посчитать арифметическую операцию в заданом кольце(базизе).
«Теория полей и колец», прикладная математика, третий курс. А я все думал нахрена нам этот бред читали

[Aesthete]

чтобы решать далёкие от реальности олимпиадные задачи.

[goldenalfer]

Не поверите, первый мой вариант был именно такой. Только 1 надо прибавлять до тех пор, пока не останется только начальный набор символов, т.е. в отличие от предложенного в топике решения, придется написать гораздо больше кода, с большим числом шагов. А также, тест показал, что такое решение, которые вы предлагаете, уже на 30 символах при некоторых исходных последовательностях выходит за лимит времени.

[ABrandt]

Опять не верно. Тогда у вас будет aaba -> aabb, а количество разных символов тоже не должно меняться.

[ABrandt]

Упс, промахнулся)