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

Сначала плывут 2 мальчика, один остается там, а второй возвращается. Мальчик остается на берегу, а на другой берег плывет один солдат. Он остается там, а сюда приплывает обратно мальчик. Опять плывут 2 мальчика, опять один остается, а другой возвращается с лодкой. Плывет второй солдат, а с лодкой возвращается второй мальчик. Солдаты на том берегу, а мальчики и лодка - на этом. Вуаля!

#include <iostream>

#include <vector>

#include <set>

#define ll long long

using namespace std;

signed main() {

   ll n;

   cin >> n;

   vector<pair<ll,ll>> a(n);

   vector<ll> pref(n,0),d(n,0),ans(n,0);

   set<ll> s;

   for(ll i = 0; i < n; i++){

       cin >> a[i].first;

       a[i].second = i;

       s.insert(a[i].first);

       if(i == 0)

           pref[i] = a[i].first;

       else

           pref[i] = pref[i-1] + a[i].first;

       d[i] = s.size();

   }

   if(d[n-1] > 1 || n == 1)

       ans[a[n-1].second] = 1;

   for(ll i = n - 2; i >= 0; i--){

       if(pref[i] > a[i + 1].first && ans[a[i+1].second] == 1 && d[i] > 1)

           ans[a[i].second] = 1;

   }

   for(ll i = 0; i < n; i++)

       cout << ans[i] << " ";

}

P.S. Откуда задача, уж больно часто я ее встречаю на подобных сайтах

ответ:

после выполнения шага 1 на столе лежит яблоко, которое достали из корзины первым, а вторая корзина пуста. после каждого выполнения шага 2 большее яблоко перемещается в корзину, а меньшее остается на столе. в результате на столе окажется самое маленькое яблоко.

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

подробнее - на -

объяснение: