Comments 19
Другой интересный подход к таким задачам — пытаться использовать комбинировать стандартные средства своего любимого языка программирования — например, std::next_permutation.
Возможно, это умение ещё более важно, чем знание алгоритма генерации след. перестановки, так как помогает экономить время и в больших спортивных задачах, и в «промышленном программировании».
Возможно, это умение ещё более важно, чем знание алгоритма генерации след. перестановки, так как помогает экономить время и в больших спортивных задачах, и в «промышленном программировании».
Это задача одного алгоритма, и если использовать предложенную вами функцию, то хобби становится неинтересным. Но вы безусловно правы, хотя я честно надеялся, что компилятор запретит использовать std::next_permutation.
Кстати, очень жаль, что ни один из предложенных языков программирования на uva.onlinejudge.org не является моим любимым.
Кстати, очень жаль, что ни один из предложенных языков программирования на uva.onlinejudge.org не является моим любимым.
Предложите решение с помощью std:next_permutation, мне кажется что это будет задачка покруче исходной)
UFO just landed and posted this here
#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)
Да, я понял, что неправ) Думал, что стандартные перестановки работают только с перестановками без повторяющихся элементов. Эта задача старая. В те времена были задачи, которые сейчас можно решить стандартными средствами (их немного).
Я хотел сказать, что стандарты знать надо, но большинство задач имеют алгоритм решения по месту.
Например, могли попросить генерировать правильные скобочные последовательности, какие-нибудь обходы или еще чего. Тут стандартом не обойдешься, придется думать алгоритм по месту. Но в целом ваше замечание правильное.
Я хотел сказать, что стандарты знать надо, но большинство задач имеют алгоритм решения по месту.
Например, могли попросить генерировать правильные скобочные последовательности, какие-нибудь обходы или еще чего. Тут стандартом не обойдешься, придется думать алгоритм по месту. Но в целом ваше замечание правильное.
Они всё-таки хотят это сделать!!!
(я про имплантанты...)
(я про имплантанты...)
эхх, где мои 17 лет на spoj.pl
*хлынули воспоминания*
*хлынули воспоминания*
Еще есть acm.timus.ru/ — вроде должен быть известен каждому олимпиаднику.
гм, берем строку — baseconvert из 25тичной системы в 10тичную.
далее ++
далее обратно в 25тичную систему.
Перед этим пройтись и сделать символам шифт на '9' влево(в конце обратно) чтобы сместиться в начала всех систем — 0-9, перейдя из сета a-z в 0-('z'-9), с которым возможна работа стандартными операторами.
Я это про то что эта задача, по сути, на знание обычной арифметики :)
далее ++
далее обратно в 25тичную систему.
Перед этим пройтись и сделать символам шифт на '9' влево(в конце обратно) чтобы сместиться в начала всех систем — 0-9, перейдя из сета a-z в 0-('z'-9), с которым возможна работа стандартными операторами.
Я это про то что эта задача, по сути, на знание обычной арифметики :)
Придется писать много длинной арфиметики или использовать соответсвующие библиотеки. К тому же, такое решение будет сильно медленнее.
Бред.
Здесь можно использовать только те символы, которые уже есть в строке. А у вас получится такое что при aaaa вы получите aaab.
Здесь можно использовать только те символы, которые уже есть в строке. А у вас получится такое что при aaaa вы получите aaab.
еще проще — считаем сколько разных символов в строке. делаем map. делаем выше описанный base convert. делаем обратный map.
суть всеравно не меняется — надо посчитать арифметическую операцию в заданом кольце(базизе).
«Теория полей и колец», прикладная математика, третий курс. А я все думал нахрена нам этот бред читали
суть всеравно не меняется — надо посчитать арифметическую операцию в заданом кольце(базизе).
«Теория полей и колец», прикладная математика, третий курс. А я все думал нахрена нам этот бред читали
Не поверите, первый мой вариант был именно такой. Только 1 надо прибавлять до тех пор, пока не останется только начальный набор символов, т.е. в отличие от предложенного в топике решения, придется написать гораздо больше кода, с большим числом шагов. А также, тест показал, что такое решение, которые вы предлагаете, уже на 30 символах при некоторых исходных последовательностях выходит за лимит времени.
Опять не верно. Тогда у вас будет aaba -> aabb, а количество разных символов тоже не должно меняться.
Sign up to leave a comment.
Олимпиадное хобби. Разминка