Перевёртыш строки на JavaScript

[Ktina]

Seman в сообщении #1327869 писал(а):

Вот видео, как мальчик к успеху пришел.

(Классический случай)

Мальчик произносит "облЕгчить", "трёхста" и "начать заработать", но зарабатывает больше меня. Особенно режет уши "трёхста". В Израиле есть русскоязычное радио, косноязычные ведущие которого частенько выдают подобные перлы. "Трёхста", "семиста", "двух тысячи восемнадцатого года", "двенадцать суден" (имеются в виду военные корабли), "поскандалил забрать ребёнка", "последствия лИтого свинца" (имелась в виду военная операция "Литой Свинец"). Но особенно тронуло: "Кнессет работает по-большому три дня в неделю" (имелось в виду, что Кнессет, по большому счёту, работает три дня в неделю).

[_Ivana]

Про кучу камней даже без мемоизации (хотя ее тривиально добавить) прошли тесты:

Используется синтаксис C++

int N, S, a[20];

int f (int s, int i) { return s<0 ? S : i>=N ? s : min(f(s-2*a[i], i+1), f(s, i+1)); }

int main() { cin>>N; for(int i=0; i<N; i++) {cin>>a[i]; S+=a[i];} cout<<f(S, 0); }

ЗЫ список языков на этом всеми забытом сайте древен и ограничен, поэтому ортодоксальный Си

ЗЗЫ мальчик, полагаю, показан как пример, что

Seman в сообщении #1327869 писал(а):

Зарабатывать совсем же отдельный навык

, никак не коррелирующий ни с какими другими.

-- 20.07.2018, 18:07 --

Про Ханойские башни можно просто и тупо (за что там 100 баллов непонятно совсем)

Используется синтаксис C++

char a,b;

int f (char x, char y, char z, int i) { return i<=0 ? 0 : (x==a && y==b) + f(x,z,y,i-1) + f(z,y,x,i-1); }

int main() { int n; cin>>n; cin>>a>>b; cout << f('A', 'B', 'C', n); }

[Munin]

Ktina
Я так понял, меня вы тщательно игнорируете?

[Ktina]

Munin в сообщении #1327954 писал(а):

Ktina
Я так понял, меня вы тщательно игнорируете?

Упаси, природа-мать!
Просто чувствую, что не потяну пока.

[Munin]

А вы не чувствуйте, а берите и делайте. Это самые элементарные упражнения по программированию.

[_Ivana]

Инверсии - читерство с tree, работает только в GNU С++

Используется синтаксис C++

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

int main() {
    tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
    int x, r=0, n=0; cin>>x;
    while (cin>>x) {
        r += n++ - s.order_of_key(x);
        s.insert(x);
    }
    cout<<r;           
}

[_Ivana]

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

Используется синтаксис C++

vector<int> a;
vector<pair<int,int>> r;

vector<int> fc (int n) {
    vector<int> v; v.push_back(1);
    if (n==1) return v;
    v.push_back(n);    
    for (int d=2; d*d <= n; d++) if (n%d==0) { v.push_back(d); v.push_back(n/d); }
    return v;
}
void t(int p, int q) {
    int g=__gcd(abs(p), q); p/=g; q/=g;
    if (find(r.begin(), r.end(), make_pair(p,q)) != r.end()) return;
    double y=0; for (int i=0; i<a.size(); i++) y = y*p/q+a[i];
    if (abs(y)<1E-15) r.push_back(make_pair(p,q));
}
int main() {
    int x; cin>>x; while(cin>>x) a.push_back(x);
    if    (a[a.size()-1]==0) r.push_back(make_pair(0,1));
    while (a[a.size()-1]==0) a.pop_back();

    vector<int> an=fc(abs(a[0])), a0=fc(abs(a[a.size()-1])); 
    for (int i=0; i<a0.size(); i++) for (int j=0; j<an.size(); j++) { t(a0[i], an[j]); t(-a0[i], an[j]); }
    sort(r.begin(), r.end(), [](pair<int,int> a, pair<int,int> b) {return 1.0*a.first/a.second < 1.0*b.first/b.second;});
    for (int i=0; i<r.size(); i++) cout<<r[i].first<<" "<<r[i].second<<'\n';
    if (r.size()==0) cout<<"NO SOLUTION";
}
 

[Xaositect]

_Ivana в сообщении #1327998 писал(а):

    double y=0; for (int i=0; i<a.size(); i++) y = y*p/q+a[i];
    if (abs(y)<1E-15) r.push_back(make_pair(p,q));

Ох. Таких вещей без знания теории делать нельзя.
Многочлен $907 x^{10} + 335 x^9 + 774 x^8 + 464 x^7 + 256 x^6 + 671 x^5 + 804 x^4 - 305 x^3 + x^2 - 907 x + 3$ в точке $x = 3/907$ имеет значение порядка $10^{-26}$: Wolfram Alpha

[Munin]

Xaositect
Тем не менее, тесты на сайте решение _Ivana прошло:

http://atpp.vstu.edu.ru/cgi-bin/statistica.pl?id_prb=6


Последние решения этой задачи:
Номер   Дата   Автор   Компилятор   Результат   Тест   Время работы (сек)   Исп-но памяти (KB)
472386   21.07.2018 2:12:20   Ivana   GNU C++ 4.8.1   Верно       0   280

[Xaositect]

Тем не менее, результат в этом случае неверный, хотя под ограничения он подходит. Значит, тесты слишком добрые.
В этой задаче теоретически нужна точность $10^{-27}$, так что double вряд ли подойдет из-за проблем с сокращениями.
Правильный подход - считать $q^n f(p/q)$ в 64-битных целых.

[Munin]

Xaositect в сообщении #1328041 писал(а):

Правильный подход - считать $q^n f(p/q)$ в 64-битных целых.

А хватит цифр?

[Xaositect]

Ой, действительно не хватает. Значит, надо считать по двум взаимно простым модулям в районе $2^{57}$ (или по четырем в районе $2^{29}$).
Я проверил - вычисление в double методом Горнера выдает на моем примере $+0$.

[_Ivana]

Xaositect в сообщении #1328033 писал(а):

Ох. Таких вещей без знания теории делать нельзя.

Но если очень хочется нет бортовой длинной арифметики, то можно. И о знании какой теории речь? Мне тоже не нравится использование плавающей арифметики в этой задаче, я в курсе, что точности 15 знаков не хватит при 10-й степени, но я увидел, что и целочисленной 64-битной арифметики при наивной реализации (без взаимно простых модулей) также не хватит, и написал такой хак, с целью проверить прохождение тестов, не усложняя расчет - они прошли. Тем более, этот момент не является хоть сколь-нибудь критичным в плане самого алгоритма. При наличии более серьезных тестов разумеется я бы рассчитал в целых, написав для этого свой велосипед или подключив какую-нибудь либу.

ЗЫ если на то пошло, там и функцию сортировки результата надо поменять, ибо она сортирует через приведение к даблам, а на близких рациональных числах при больших числителях/знаменателях это тоже может привести к ошибке - и я отлично это понимаю, и знаю, что таких вещей делать нельзя

ЗЗЫ если бы я добавлял эту задачу на сайт, я бы разумеется добавил самые жесткие тесты, чтобы подобная халява не проходила - как я делал в подобных случаях, например в моих катах на Кодоворсах. Результат - народ просто не решает и все А в случае данной задачи достаточно просто один в один переписать алгоритм на Питоне, где тоже есть авторесайзящиеся вектора и из коробки длинная арифметика - благо в списке языков для проверки решений он есть И пары на Питоне тоже в ядре и не такие страшные по синтаксису, и скорость алгоритма позволяет его реализовать на любом медленном скрипте - прямо все аргументы за Питон, действительно зря я по инерции на плюсах решал.

[Xaositect]

_Ivana, извините, если что не так. Здесь все-таки тема для обучения начинающих, нельзя же просто так без объяснения такие хаки писать.

[_Ivana]

Xaositect, и Вы тоже извините меня за несдержанность.

GAA:

Замечание за уход от тематики программирования на обсуждение личных отношений. Оффтопик в этом сообщении удалён. Последующие сообщения с оффтопиком на эту тему удалены.

Кстати, пользуясь случаем (С), предлагаю Вам попробовать мои вышеупомянутые каты на Кодоворсах. Адрес Вы знаете. По крайней мере, пара-тройка из них народу весьма понравилась - бурные обсуждения и портирования на кучу других языков, а пару пока так никто и не решил

ЗЫ а по сабжу - я бы и в кучу камней добавил жестких тестов, чтобы наивная рекурсия без мемоизации не проходила.