I have got error so many times. Wonder wht I am missing..
Here is my Python 3.4 Code

n,m=map(int,input().split())
g=list(map(int,input().split()))
b=list(map(int,input().split()))

g.sort()
b.sort()

minUpset=0


for i in range(0,n):
    minUpset+=g[i]

for s in range(0,min(n,m)):
    girlsUpset=0
    boysUpset=0
    for i in range(0,n-s):
        girlsUpset+=g[i]
    for j in range(0,m-s):
        boysUpset+=b[j]
    minUpset=min(girlsUpset+boysUpset*s,minUpset)

print(minUpset)

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = 100;
int a[maxn], b[maxn];

int main() {
    int n, m;
    cin >> n >> m;
    fo(i, n) cin >> a[i];
    fo(i, m) cin >> b[i];
    sort(a, a + n), sort(b, b + m);
    reverse(a, a + n), reverse(b, b + m);
    int ans = (int) 1e9, cur;
    fo(k, min(n, m) + 1) {
        cur = 0;
        for (int j = k; j < n; ++j) cur += a[j];
        for (int j = k; j < m; ++j) cur += b[j] * k;
        ans = min (ans, cur);
    }
    cout << ans << endl;
}

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

int calc () {
    string str;
    cin >> str;
    re (str[0] - '0') * 600 + (str[1] - '0') * 60 + stoi(str.substr(3, 2));
}

int main() {
    int n1, n2, n3, c1, c2, t;
    cin >> n1 >> c1 >> n2 >> t >> c2 >> n3;
    int k, time;
    int ans = 0;
    cin >> k;
    while (k--) {
        time = calc();
        if (time <= 6) continue;
        ans += (time + 59) / 60;
    }
    cout << "Basic:     " << n1 + ans * c1 << endl;
    cout << "Combined:  " << n2 + max(0, ans - t) * c2 << endl;
    cout << "Unlimited: " << n3 << endl;
}

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

int main() {
    string a = "tram", b = "trolleybus", str;
    int ans = 0;
    while (cin >> str) {
        fo(i, (int)str.size() - (int)a.size() + 1) {
            if (str.substr(i, a.size()) != a) continue;
            if (!i && (str.size() == a.size() || 'a' > str[a.size()] || str[a.size()] > 'z')) ++ans;
            if (i && ('a' > str[i - 1] || str[i - 1] > 'z') && (i + a.size() == str.size() || 'a' > str[i + a.size()] || str[i + a.size()] > 'z')) ++ans;
        }
        fo(i, (int)str.size() - (int)b.size() + 1) {
            if (str.substr(i, b.size()) != b) continue;
            if (!i && (str.size() == b.size() || 'a' > str[b.size()] || str[b.size()] > 'z')) --ans;
            if (i && ('a' > str[i - 1] || str[i - 1] > 'z') && (i + b.size() == str.size() || 'a' > str[i + b.size()] || str[i + b.size()] > 'z')) --ans;
        }
    }
    if (ans > 0) cout << "Tram driver\n";
    else if (ans < 0) cout << "Trolleybus driver\n";
    else cout << "Bus driver\n";
}

n=100: 168
n=555: 984
n=1000: 1785
n=1100: 1963
n=2000: 3598

I solved the equation x(x-1) % 10^i = 0 for every i>1 and i<=n by linear algorithm, using roots for i-1.

Test 2 is something like this
3 2
0
Good luck!

Use   if(c> 8000000000LL || c< -8000000000LL)  break ; this line in BInary search...


code :
[deleted]

Edited by author 01.06.2018 17:02

Edited by moderator 20.11.2019 22:45

plz can someone give the 4th test

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
 class Program
 {
  static void Main(string[] args)
  {
            int n = Convert.ToInt16(Console.ReadLine());
            int s = 2;
            for (int i = 1; i<=n; i++)
            {
                string a = Console.ReadLine();
                if (a.Contains("+one"))
                    s += 2;
                else s++;
            }
            if (s == 13) s++;
            Console.WriteLine(s * 100);
  }
 }
}

Did anybody get AC with the MaxFlow algorithm?

4
2 3 2 11.
.
2 3 0 10, 4 3 0 19.
.

4
2 0 0 47, 3 17 17 25, 4 0 0 38.
1 17 17 31, 3 0 0 23, 4 0 0 96.
1 0 0 96, 2 0 0 48, 4 17 17 91.
.
=
69
2 0, 3 17, 4 1.
1 18, 3 0, 4 0.
1 0, 2 0, 4 17.
.


8
.
1 0 0 39, 5 13 13 21.
5 0 0 87, 8 41 41 92.
5 38 38 85.
6 41 41 14, 8 10 10 49.
2 10 10 69, 3 41 41 58, 4 0 0 73.
6 3 3 59.
.
=
49
.
1 0, 5 13.
5 0, 8 41.
5 38.
6 40, 8 11.
2 10, 3 41, 4 0.
6 3.
.

Edited by author 16.06.2008 04:40

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = 5;
int sz[2][maxn];
bool how[maxn];
int pos1[maxn], pos2[maxn];

bool check_intersection () {
    bool check = true;
    fo(i, 5) {
        fo(j, i) {
            check = false;
            if (pos1[i] + sz[how[i]][i] <= pos1[j]) check = true;
            if (pos1[j] + sz[how[j]][j] <= pos1[i]) check = true;
            if (pos2[i] + sz[!how[i]][i] <= pos2[j]) check = true;
            if (pos2[j] + sz[!how[j]][j] <= pos2[i]) check = true;
            if (!check) re false;
        }
    }
    re true;
}

bool check_area () {
    int x = -1, y = -1;
    fo(i, 5) {
        x = max(x, pos1[i] + sz[how[i]][i]);
        y = max(y, pos2[i] + sz[!how[i]][i]);
    }
    int s1 = 0, s2 = x * y;
    fo(i, 5) s1 += sz[0][i] * sz[1][i];
    re s1 == s2;
}

bool major_check() {
    bool ans = check_area() && check_intersection();
    re ans;
}

vector <pair <ii, bool> > v;

bool f (int mask) {
    if (__builtin_popcount(mask) == 5) re major_check();
    fo(a, 5) {
        if (((1 << a) & mask) == 0) {
            fo(q, 2) {
                how[a] = q;
                fo(i, v.size()) {
                    if (v[i].se) continue;
                    ii j = v[i].fi;
                    v[i].se = true;
                    v.pb(mp(mp(j.fi + sz[how[a]][a], j.se), false));
                    v.pb(mp(mp(j.fi, j.se + sz[!how[a]][a]), false));
                    pos1[a] = j.fi;
                    pos2[a] = j.se;
                    if (f(mask | (1 << a))) re true;
                    v[i].se = false;
                    v.pop_back();
                    v.pop_back();
                }
            }
        }
    }
    re false;
}

int main() {
    fo(i, 5) fo(j, 2) cin >> sz[j][i];
    v.eb(mp(0, 0), 0);
    if (f(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

This problem is very easy.
I use idea similar dp.

Edited by author 30.05.2018 19:11

https://e-maxx-eng.appspot.com/string/prefix-function.html
https://ru.coursera.org/learn/algorithms-on-strings/lecture/exytr/prefix-function
https://brilliant.org/wiki/knuth-morris-pratt-algorithm/
https://stackoverflow.com/questions/13792118/kmp-prefix-table

GooD LucK!!!

I used an O(n*n) method and got TLE#9. Does anyone know of any O(n) method. I actually checked every cyclic shift to see if it is a valid expression.

Instead of "if you enemy..." it should be "if your enemy...".

The problem is very easy. If you solved every geometry problem up to this one you should be able to solve it easily, so you might want to stop reading this.
The axis of symmetry can be drawn in 2 places: through a pair of opposite point or through a pair of midpoints of opposite segments. Why only the midpoints? Because when you "fold" the figure your points must go one ever the other. If the distance is not equal, this is impossible(hint 1).
M A N
__.__
| \  \
|  \  \
|___\__\
      B
M is the top-left point
N is the top-right point
This figure for example. A and B are the midpoints. But this is clearly not an axis of symmetry. After the folding, the top-left point will go above the top-right point.
After the folding, the angle relative to the axis of symmetry will be the same. This is a midpoint. The angle with the center in A for example must have 180 degrees;
angle(MAB) + angle(NAB) = 180
angle(MAB) = angle(NAB)
x + x = 180
x = 90
It is now clear that the vector MN must be perpendicular on the vector AB(hint 2)
I think this is more that enough for you to solve the problem/
Good luck!

Edited by author 27.05.2018 15:16

Edited by author 27.05.2018 15:17

x[n] = J[n]/2^(n-1), J[n] - Jacobsthal number and J[n] = (2^n - (-1)^n)/3.

https://en.wikipedia.org/wiki/Jacobsthal_number

Help! What's wrong with my code?


#include <bits/stdc++.h>
#define forn( i, n )    for( int i = 0; i < n; i ++ )

using namespace std;

int main() {
   int qq[10000];
   int k, l; double m , n;
   l = 0;
   cin >> k >> n;
   forn( i , n)
     cin >> qq[i];
   forn( i, k+1 ){
     forn( j , n)
       if (qq[j] == i)  l = l+1;
    if ( i != 0 ) {
     m = (l / n * 100);
     l = (int) round(m*100)/100;
     if ( l - m == 0)
       cout << round(m*100)/100 << ".00%" << endl;
     else
       cout << round(m*100)/100 << "%" << endl;
     l = 0;
    }
     }
return 0;
}