akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main() {
  string ans;

  for (int i=0; i<3; i++) {
    string in;
    cin >> in;
    ans += in[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	vector<string> s(n);
	rep(i, n) {
		cin >> s[i]; 
		sort(s[i].begin(), s[i].end());
	}
	//*rep(i, n) cout << s[i] << endl;*//
	sort(s.begin(), s.end());
	ll ans = 0;
	ll count = 1;
	for (int i = 0; i < n-1; i++) {
		if (s[i] == s[i + 1]) {
			count++;
		}
		else {
			ans += (count * (count - 1)) / 2;
			count = 1;
		}
	}
	if (count != 1) { ans += (count * (count - 1)) / 2; }

	cout << ans << endl;
}


Measured memory_bytes: 5760
import java.util.Scanner;

/**
 * A - Circle Pond
 * 半径 R の円の周長を出力してください。
 */
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner( System.in );
        // 入力された整数
        int r = sc.nextInt();
        double circumference = r * 2 * Math.PI;

        System.out.println( circumference );

        sc.close();
    }
}

Measured memory_bytes: 36000
<?php
$in = explode(" ",trim(fgets(STDIN)));
$a = $in[0];
$b = $in[1];
if($a < $b)
{
    echo "a < b\n";
}
elseif($a > $b)
{
    echo "a > b\n";
}
else
{
    echo "a == b\n";
}

Measured memory_bytes: 15252
from collections import Counter

n = int(input())
S = list(map(int,input().split()))

Odd = Counter(S[::2]).most_common()+([(0,0)])
Even = Counter(S[1::2]).most_common()+([(0,0)])

if Odd[0][0] != Even[0][0]:
	print(n-Odd[0][1]-Even[0][1])
else:
	print(min(n-Odd[1][1]-Even[0][1],n-Odd[0][1]-Even[1][1]))

Measured memory_bytes: 20572
// https://atcoder.jp/contests/abc114/tasks/abc114_d

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

ll dp[110][101];
int main() {
    int n;
    cin >> n;
    vector<int> cnt(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        int tmp = i;
        for (int j = 2; j <= i; j++) {
            while (tmp % j == 0) {
                cnt[j]++;
                tmp /= j;
            }
        }
    }
    dp[0][1] = 1;
    for (int i = 0; i <= n; i++) {
        for (int have = 0; have <= 75; have++) {
            for (int take = 1; take <= cnt[i] + 1; take++) {
                if (have * take > 75)
                    continue;
                dp[i + 1][have * take] += dp[i][have];
            }
        }
    }
    cout << dp[n][75] << endl;

    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

using i64 = long long;
using f64 = double;
using f80 = long double;
using pii = pair<int, int>;
using pll = pair<i64, i64>;
using ptx = pair<f64, f64>;

int main() {
#ifdef HOME
	freopen("cf.in", "r", stdin);
	freopen("cf.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	string str;
	i64 ant = 0;
	int w = 0;

	cin >> str;
	for (int i = str.size() - 1; i >= 0; --i) {
		w+= int(str[i] == 'W');
		if (str[i] == 'B')
			ant+= w; }

	cout << ant << endl;

	return 0; }



Measured memory_bytes: 720
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        if (a >= b && a >= c) {
            System.out.println(10*a + b + c);
        } else if (b > a && b >= c) {
            System.out.println(10*b + c + a);
        } else {
            System.out.println(10*c + a + b);
        }
    }
}


Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long long long 

class Graph{
    long int v;
    list<long int> *adj;
    vector<long int> values;

    public:
        Graph(long int v) : v(v){
            adj = new list<long int>[v];
            values.resize(v);   
        }

        void addEdge(long int u, long int v){
            adj[u-1].push_back(v-1);
            adj[v-1].push_back(u-1);
        }

        void update(long int r, long int val){
            values[r-1] += val;
        }

        void BFS(){
            vector<bool> visited(v);
            queue<pair<long int,long int>> q;
            q.push(make_pair(0,0));
            visited[0] = true;

            map<long int, long int> mp;
            while(!q.empty()){
                auto ele = q.front();
                q.pop();

                mp[ele.first] = ele.second + values[ele.first];

                for(auto itr = adj[ele.first].begin(); itr != adj[ele.first].end(); itr++){
                    if(!visited[*itr]){
                        visited[*itr] = true;
                        q.push(make_pair(*itr,mp[ele.first]));
                    }
                }
            }
            for(auto ele : mp)
                cout<<ele.second<<" ";
        }
};

int main() {
    IOS;

    long int n,q;
    cin>>n>>q;

    Graph g(n);

    for(long int i = 0; i < n-1; i++){
        long int a,b;
        cin>>a>>b;
        g.addEdge(a,b);
    }

    for(long int i = 0; i < q; i++){
        long int r,x;
        cin>>r>>x;
        g.update(r,x);
    }
    g.BFS();
    return 0;
}


Measured memory_bytes: 32256
#include <bits/stdc++.h>
#include <atcoder/all>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;
using namespace atcoder;

signed main(){
    ll N, Q, a;
    cin >> N >> Q;
    fenwick_tree<ll> bit(N);
    REP(i, N){
        cin >> a;
        bit.add(i, a);
    }    
    ll q, l, r;
    REP(i, Q){
        cin >> q >> l >> r;
        if(q == 0) bit.add(l, r);
        else PRINT(bit.sum(l, r));
    }
    return 0;
}

Measured memory_bytes: 8212
#if 0
date +%Y.%m.%d

题解先咕着。
#endif
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef std::pair<int, int> Par;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 200005;
Par pr[maxn];

int r, c;
int getpos(int x, int y) {
	if(x == 0) return c - y;
	if(y == 0) return c + x;
	if(x == r) return r + c + y;
	if(y == c) return (r + c) * 2 - x;
	return -1;
}

bool vis[maxn];
int stack[maxn], sp;

int main() {
	read(r, c);
	int n = read;

	int p = 0;
	for(int i = 1; i <= n; i ++) {
		int x1 = read, y1 = read, x2 = read, y2 = read;
		int p1 = getpos(x1, y1), p2 = getpos(x2, y2);
		if(p1 == -1 or p2 == -1) continue;
		pr[++ p] = Par(p1, i);
		pr[++ p] = Par(p2, i);
	}

	std::sort(pr + 1, pr + p + 1);
	for(int i = 1; i <= p; i ++) {
		int id = pr[i].second;
		if(!vis[id]) {
			vis[id] = 1;
			stack[++ sp] = id;
		}
		else if(stack[sp] != id)
			return puts("NO"), 0;
		else
			-- sp;
	}

	puts("YES");
}


Measured memory_bytes: 1920
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;ll A,B;
    cin >> N >> A >> B;
    vector<ll> v(N);
    rep(i,0,N){
        cin >> v[i];
    }
    ll ans = 0ll;
    rep(i,1,N){
        ans += min(A * (v[i] - v[i-1]),B);
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 1024
# Problem D - Double Dots

from collections import deque

# input
N, M = map(int, input().split())
graph_list = {}
for i in range(M):
    a, b = map(int, input().split())
    if a in graph_list:
        graph_list[a].append(b)
    else:
        graph_list[a] = [b]

    if b in graph_list:
        graph_list[b].append(a)
    else:
        graph_list[b] = [a]

# initialization
visit_list = [0]*N
distance_list = [float("INF")]*N
distance_list[0] = 0
visit_queue = deque([1])
queue_count = 1

# bfs search
while queue_count>0:
    v = visit_queue.popleft()
    queue_count -= 1

    graph = graph_list[v]
    for n in graph:
        if distance_list[v-1]+1<distance_list[n-1]:
            distance_list[n-1] = distance_list[v-1] + 1
            visit_list[n-1] = v
            visit_queue.append(n)
            queue_count += 1

# output
print("Yes")
for i in range(1, N):
    print(visit_list[i])


Measured memory_bytes: 108444
#include<cstdio>
const int N=200005;
int n,v[N],l,r,I,a,s[N][2],t;
inline int p1()
{
	for(int i=2;i<=n;++i)
		if(v[i]<=v[i-1])return 0;
	return 1;
}
inline int ck(int x)
{
	t=0;
	for(int i=1;i<=n;++i)if(v[i]<=v[i-1])
	{
		for(;s[t][0]>v[i];--t);
		for(int j=v[i],k=t;;--j,--k)
		{
			if(!j)return 0;
			else if(j!=s[k][0])
			{
				for(int w=t++;w>k;--w)
					s[w+1][0]=s[w][0],s[w+1][1]=s[w][1];
				s[k+1][0]=j,s[k+1][1]=2;break;
			}
			else if(s[k][1]<x){++s[k][1];break;}
			else s[k][1]=1;
		}
	}
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&v[i]);
	if(p1())return printf("1"),0;
	for(l=2,r=n;l<=r;)
		ck(I=l+r>>1)?(a=I,r=I-1):(l=I+1);
	return printf("%d",a),0;
}

Measured memory_bytes: 2468
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

signed main() {
	int n;
	cin >> n;

	int tc = 0, fc = 0, ec = 0;

	REP(i, n) {
		int a;
		scanf("%d", &a);
		if (!(a % 4))
			fc++;
		else if (!(a % 2))
			tc++;
		else
			ec++;
	}

	bool ans = 0;
	tc = min(tc, 1);
	if ((ec + tc) <= (fc + 1)) {
		ans = 1;
	}
	else if (!ec)
		ans = 1;

	printf(ans ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    string a,b;
    cin>>a>>b;
    a+=b;
    int t=stoi(a);
    int st=(int)sqrt(t);
    if(st*st==t) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


int N, K, C;

using pint = pair<int,int>;
vector<pint> sub(const string &S) {
    int N = S.size();
    int cur = 0, last = -C-1;
    vector<pint> res(N+1, {cur, C});
    for (int i = 0; i < N; ++i) {
        if (i - last > C && S[i] == 'o') ++cur, last = i;
        res[i+1] = pint(cur, i - last);
    }
    return res;
}

void solve(const string &S) {
    const auto &left = sub(S);
    string T = S;
    reverse(T.begin(), T.end());
    const auto &right = sub(T);
    vector<int> res;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'x') continue;
        auto l = left[i];
        auto r = right[N-i-1];
        if (l.first + r.first < K) res.push_back(i+1);
        else if (l.first + r.first == K && l.second + r.second + 1 < C) 
            res.push_back(i+1);
    }
    for (auto v : res) cout << v << endl;
}

int main() {
    string S;
    cin >> N >> K >> C >> S;
    solve(S);
}

Measured memory_bytes: 5880
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
if N >= M:
    print(0)
else:
    X.sort()
    diff = []
    for i in range(M - 1):
        diff.append(abs(X[i + 1] - X[i]))
    diff.sort()
    print(sum(diff[:len(diff) - (N - 1)]))

Measured memory_bytes: 13968
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t; cin >> s >> t;
    vector<vector<int> > dp(s.size() + 2, vector<int>(t.size() + 2));
    rep (i, s.size() + 1) {
        rep (j, t.size() + 1) {
            chmax(dp[i + 1][j], dp[i][j]);
            chmax(dp[i][j + 1], dp[i][j]);
            if (i < s.size() && j < t.size()) chmax(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]));
        }
    }
    rep (i, s.size() + 1) {
        rep (j, t.size() + 1) eprintf("%d ", dp[i][j]); eprintf("\n");
    }
    eprintf("len:%d\n", dp[s.size()][t.size()]);
    
    int a = s.size(), b = t.size();
    vector<char> lcs;
    while (a >= 1 || b >= 1) {
        eprintf("a:%d b:%d\n", a, b);
        if (a >= 1 && b >= 1 && dp[a][b] == dp[a - 1][b - 1] + 1 && s[a - 1] == t[b - 1]) {
            a--; b--; 
            lcs.push_back(s[a]);
        }
        else if (a >= 1 && dp[a][b] == dp[a - 1][b]) a--;
        else if (b >= 1 && dp[a][b] == dp[a][b - 1]) b--;
    }
    reverse(all(lcs));
    for (char c : lcs) cout << c;
    cout << "\n";
    return 0;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 1000000007

typedef pair<int, int> pii;
ll exp(ll taban, ll us) {
    ll carpan = taban % mod;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
    }
    return res;
}
ll ebob(ll a, ll b){
	if(!a)return b;
	return ebob(b%a, a);
}
ll ekok(ll a, ll b){
	return (a*b)/ebob(a, b);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int k, n; cin>>k>>n;
	int sayi; cin>>sayi;
	int ans = 1e9;
	int ilk = sayi;
	for(int i = 1; i < n; i++){
		int sayi2; cin>>sayi2;
		ans = min(ans, k - (sayi2 - sayi));
		sayi = sayi2;
	}
	ans = min(ans, k - (ilk + (k - sayi)));
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		Pattern p = Pattern.compile("[A-Z]");
		Matcher m = p.matcher(a);
		if (m.find()) {
			System.out.println("A");
		} else {
			System.out.println("a");
		}
	}

}


Measured memory_bytes: 35672
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int N, W;
  int w[110], v[110];
  cin >> N >> W;
  for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

  static int dp[110][101010];
  dp[0][0] = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= W; j++) {
      dp[i + 1][j] = dp[i][j];
      if (w[i] <= j) {
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
      }
    }
  }

  cout << dp[N][W] << endl;
  return 0;
}


Measured memory_bytes: 79360
//Atcoder Beginner Contest 174 D 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;

#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define one 1.0
#define inf 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
#define FOR(i,a,n) for(int i=a;i<n;i++) 
#define FORE(i,a,n) FOR(i,a,n+1)
#define Endl endl
#define eNdl endl
#define enDl endl
#define endL endl
#define PI 3.14159265358979323846

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n;string s;
	cin>>n>>s;
	ll ans = 0;
	ll l = 0,r = n-1;
	while(l<r)
	{
		if(s[l] == 'R')l++;
		else if(s[r] == 'W')r--;
		else ans++,l++,r--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <cmath>
#include <tuple>
#include <bitset>
#include <utility>

#define push emplace_back
#define each(i, x) for (auto i=0; i < x; i++)
using ull = unsigned long long;

using namespace std;
template <typename T> inline void dump(const T& x) { cout << "[" << x << "]" << endl; }
template <typename T> inline void dump(const vector<T>& x) { for (const auto v : x) { cout << v << " "; } cout << endl; }
template <typename T> inline void sort_asc(vector<T>& x) { std::sort(x.begin(), x.end()); }
template <typename T> inline void sort_desc(vector<T>& x) { std::sort(x.begin(), x.end(), greater<T>()); }

int main() {
  ull n, q;
  string s;
  cin >> n >> q;
  cin >> s;

  // count "AC" on S
  vector<ull> counts;
  ull ac_count = 0;
  bool was_a = false;
  each(i, n) {
    if (was_a) {
      if (s[i] == 'C') {
        ac_count++;
      }
    }

    if (s[i] == 'A') {
      was_a = true;
    } else {
      was_a = false;
    }

    counts.push(ac_count);
  }

  // l,r
  vector<ull> ls;
  vector<ull> rs;
  each(i, q) {
    ull tmp1, tmp2;
    cin >> tmp1 >> tmp2;
    ls.push(tmp1);
    rs.push(tmp2);
  }

  each(i, q) {
    auto l = ls[i] - 1;
    auto r = rs[i] - 1;
    cout << counts[r] - counts[l] << endl;
  }

  return 0;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i, n) { cin >> vec.at(i); }

  int ans = 0;
  for (int i = 1; i <= n - 2; i++) {
    if ((vec.at(i - 1) < vec.at(i) && vec.at(i) < vec.at(i + 1)) ||
        (vec.at(i + 1) < vec.at(i) && vec.at(i) < vec.at(i - 1))) {
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
S = input()

if S =="SUN":
    print(7)
elif S =="MON":
    print(6)
elif S =="TUE":
    print(5)
elif S =="WED":
    print(4)
elif S =="THU":
    print(3)
elif S =="FRI":
    print(2)
else:
    print(1)



Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#define inf 1e30

using namespace std;

typedef pair<int, int> pos;
typedef pair<long double, pos> P;

int W, H;
char map[505][505];
int sx, sy, gx, gy;
long double dist[505][505];
const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

void dijkstra(long double m)
{
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			dist[x][y] = inf;
		}
	}
	priority_queue< P, vector<P>, greater<P> > Q;
	dist[gx][gy] = 0, Q.push( make_pair(0, make_pair(gx, gy)) );
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			if(map[x][y] == '*') dist[x][y] = m, Q.push(make_pair(m, make_pair(x, y)));
		}
	}
	
	int x, y;
	long double d;
	while(Q.size()){
		d = Q.top().first;
		x = Q.top().second.first;
		y = Q.top().second.second;
		Q.pop();
		if(dist[x][y] < d) continue;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i], ny = y + dy[i];
			if(nx <= 0 || nx > W || ny <= 0 || ny > H) continue;
			if(map[nx][ny] != '.') continue;
			if(dist[nx][ny] > d + 1){
				dist[nx][ny] = d + 1;
				Q.push( make_pair(dist[nx][ny], make_pair(nx, ny)) );
			}
		}
	}
}

long double calc(long double m)
{
	dijkstra(m);
	long double ret = 0; int cnt = 0;
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			if(map[x][y] == '.' && (x != gx || y != gy)){
				ret += dist[x][y];
				cnt++;
			}
		}
	}
	ret /= cnt;
	return ret;
}

int main(void)
{
	cin >> W >> H;
	for(int y = 1; y <= H; y++){
		for(int x = 1; x <= W; x++){
			cin >> map[x][y];
			if(map[x][y] == 's'){
				map[x][y] = '.';
				sx = x, sy = y;
			}
			if(map[x][y] == 'g'){
				map[x][y] = '.';
				gx = x, gy = y;
			}
		}
	}
	
	long double ub = 1e18, lb = 0.0, mid;
	for(int i = 0; i < 100; i++){
		mid = (ub + lb) * 0.5;
		long double val = calc(mid);
		if(val < mid) ub = mid;
		else if(val > mid) lb = mid;
	}
	mid = (ub + lb) * 0.5;
	calc(mid);
	
	long double ret = 0; int cnt = 0;
	for(int x = 1; x <= W; x++){
		for(int y = 1; y <= H; y++){
			if(map[x][y] == '.' && (x != gx || y != gy)){
				ret += dist[x][y];
				cnt++;
			}
		}
	}
	ret /= cnt;
	
	printf("%.11Lf\n", dist[sx][sy]);
	return 0;
}


Measured memory_bytes: 8500
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int x, n;
	cin >> x >> n;

	map<int, int> mp;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		mp[num] = 1;
	}
	
	int add = 0;
	while (1) {
		if (mp[x - add]) {
			if (mp[x + add])
				add++;
			else
				break;
		} else {
			add *= -1;
			break;
		}
	}
	cout << x + add << endl;

	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MAXN = 1e5+10;

ll n, m;
ll a[MAXN], b[MAXN], c[MAXN];

void solve() {
  priority_queue<P> que;
  for (int i=0;i<n;i++) {
    que.push(P(a[i], 1));
  }
  for (int i=0;i<m;i++) {
    que.push(P(c[i], b[i]));
  }
  ll sum = 0;
  ll i = 0;
  while(i < n) {
    P p = que.top();
    que.pop();
    ll cnt = min(p.second, n - i);
    sum += cnt * p.first;
    i += cnt;
  }
  cout << sum << endl;
}

int main() {
  cin >> n >> m;
  for (int i=0;i<n;i++) {
    cin >> a[i];
  }
  for (int i=0;i<m;i++) {
    cin >> b[i] >> c[i];
  }
  solve();
}


Measured memory_bytes: 8816
s = input()
n = len(s)
s = list(s)
s.pop(len(s)-1)
s.pop(len(s)-2)
for i in range(2,n+1,2):
    if s[:(n-i)//2]==s[(n-i)//2:]:
        print(n-i)
        exit()
    s.pop(n-i-1)
    s.pop(n-i-2)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define FASTIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inf 1e18
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define mod 1000000007
#define pb push_back
#define all(s) s.begin(),s.end()
#define pie 3.14159265358979323846
#define fr(i,a,b)  for(ll i=a;i<b;i++)
#define frr(i,a,b) for(ll i=b-1;i>=a;i--)
#define gcd __gcd
#define con continue
#define pii pair<ll,ll>
signed main(){
    FASTIO;
    ll tt=1;
    //cin>>tt;
    while(tt--){
         ll a,b,c;cin>>a>>b>>c;
         cout<<(a+b-1)/b*c<<"\n";
    }
}


Measured memory_bytes: 3624
N = int(input())
m=[]
line = ''
m = [[[0 for k in range(10)] for j in range(3)] for i in range(10)]
for i in range(N):
    n = input().split()
    b = int(n[0])
    f = int(n[1])
    r = int(n[2])
    v = int(n[3])
    m[b-1][f-1][r-1] += v

for i in range(4):
    for j in range(3):
        for k in range(10):
            line += ' {0}'.format(m[i][j][k])
        print(line)
        line = ''
    if i < 3:
        print('#'*20)

Measured memory_bytes: 7716
#ABC090-B
a,b = map(int,input().split())

def kaibun(n):
    flg = True
    for i in range(len(str(n))//2):
        if str(n)[i] != str(n)[-1-i]:
            flg = False
            break
            
    if flg:
        return True
    else:
        return False
    
cnt = 0
for i in range(a,b+1):
    if kaibun(i):
        cnt += 1
        
print(cnt)

Measured memory_bytes: 3060
# frozen_string_literal: true

n, @k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
f = gets.split.map(&:to_i).sort_by(&:-@)

@b = []
@c = []
0.upto(n - 1) do |i|
  @b.push [a[i], f[i]]
end

def ok(m)
  count = 0
  @b.each do |e|
    a = e[0]
    f = e[1]
    break if a * f <= m

    count += a - m / f
    return false if count > @k
  end
  return true
end

@b = @b.sort_by { |e| -e[0] * e[1] }
max = @b.map { |e| e[0] * e[1] }.max

ans = (0..max).bsearch { |e| ok(e) }

puts ans


Measured memory_bytes: 44076
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
  
int main()
{
    int H, W;
    int h, w;
  
    while (1) {
        scanf("%d%d", &H, &W);
        if (H == 0 && W == 0) break;
        for (h = 0; h < H; h++) {
            for (w = 0; w < W; w++) putchar('#');
            putchar('\n');
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 2144
#include<stdio.h>
int main(){
    int a[50],b,i,j,sum=0;
    scanf("%d",&b);
    for (i=0;i<b;i++){
        scanf("%d",a+i);
    }
    for (i=0;i<b;i++){
        for (j=i+1;j<b;j++){
            sum+=a[i]*a[j];
        }
    }
    printf("%d",sum);
    return 0;
}


Measured memory_bytes: 128
/*  (: ///////|||||| BEGINS |||||||\\\\ :) */
/* REMEMBER
Deletes all characters except first one     Deletes 4 characters from index number 1
    str.erase(1);                               str.erase(1,4);
Deletes character at position 4
 str.erase(str.begin() + 4);
bool compare(const pair<int, int>&a, const pair<int, int>&b)
{
   return a.second<b.second;
}
maxn = max_element(mp.begin(), mp.end(), compare)->second;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.second < b.second);
}
min(a,b,c,d)==min({a,b,c,d});
priority_queue <int, vector<int>, greater<int>> gquiz; // to create min heap
*/
#include<bits/stdc++.h>
using namespace std;
#define ll             long long int
#define endl           '\n'
#define mod            1000000007
#define fo(i,n)        for(int i=1;i<=n;i++)
#define tol(s)         transform(s.begin(),s.end(),s.begin(),::tolower)
#define tou(s)         transform(s.begin(),s.end(),s.begin(),::toupper)
#define all(x)         (x).begin(), (x).end()
#define pb             push_back
#define lb             lower_bound
#define ub             upper_bound
#define tr(it, a)      for(auto it = a.begin();it!=a.end();it++)
#define gcd(a,b)       __gcd(a,b)
#define pq             priority_queue
#define fr             first
#define sc             second
#define sz(x)          x.size()

const int inf=0x3f3f3f3f;
bool ispalindrome(string s) 
{ 
    ll len=s.length(); 
    for(ll i=0;i<len;i++){ 
        if(s[i]!=s[len-i-1]) 
        return false; 
    } 
    return true; 
} 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
long long isprime(long long n)
{
    for(long long i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)return 0;
    }
    return 1;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

int x,n;
cin>>x>>n;
int a[n];
int h[105]={0};
for(int i=0;i<n;i++)
{
    cin>>a[i];
    h[a[i]]=1;
}
if(n==0)cout<<x<<endl;
else
{
vector<pair<int,int>>v;
for(int i=0;i<=102;i++)
{
    if(h[i]==0)v.pb({abs(i-x),i});
}
sort(all(v));
cout<<v[0].second<<endl;
}











return 0;
}

Measured memory_bytes: 3648
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = 0
for i in range(n - 1, n - k - 1, -1):
    ti, di = sushi[i]
    if ti in t.keys():
        x.append(di)
        t[ti] += 1
    else:
        t[ti] = 1
    z += di

p = len(t.keys())
ans = z + p ** 2
idx = 1
for i in range(n - k - 1, -1, -1):
    if idx == len(x) + 1:
        break
    ti, di = sushi[i]
    if ti not in t.keys():
        t[ti] = 1
        z += di - x[-idx]
        p += 1
        idx += 1
        ans = max(ans, z + p ** 2)

print(ans)


Measured memory_bytes: 32176
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[6][1010];//動的計画法
int prime[1000001];
char str[1010][1010];
vector<pair<int,int> > pc[5];
int ABS(int a){return max(a,-a);}
int main(){
    string s,t;
    cin>>s>>t;
    int ch=1;
    for(int j=0;j<s.length();j++){
        s.insert(0,s.substr(s.length()-1,1));
        s.pop_back();
        if(s==t){
            cout<<"Yes"<<endl;
            ch=0;
            break;
        }
    }
    if(ch) cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin


def main():
    lines = stdin.readlines()
    A = tuple(map(int, lines[1].split()))
    B = tuple(map(int, lines[2].split()))
    pre = A[0]
    ans = 0
    for a, b in zip(A[1:], B):
        tmp1 = pre if pre < b else b
        b -= tmp1
        tmp2 = a if a < b else b
        ans += tmp1 + tmp2
        pre = a - tmp2
    print(ans)
    return


main()


Measured memory_bytes: 20800
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(long long i=0; i<(int)n; i++)
#define rep2(i,a,n) for(long long i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
const int mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a * b / gcd(a, b);}

int N, M, K, H, W, L, R, X;
//string S, T;
int swpa(vi a){
  int ans = 0;
  if(a[N-1]==N-1){ swap(a[N-1],a[N-2]); ans++;}
  rep(i,N-1){
    if(a[i]==i){
      swap(a[i], a[i+1]);
      ans++;
    }
  }
  
  return ans; 
}

int swpb(vi b){
  int ans = 0;
  if(b[0]==0){ swap(b[0],b[1]);  ans++;}
  for(int i = N-1; i>0; i--){
    if(b[i]==i){
      swap(b[i], b[i-1]);
      ans++;
    }
  }
  return ans; 
}


signed main(){
  cin >> N;
  vi a(N);
  rep(i,N) {cin >> a[i]; a[i]--;}
  vi b(N); b = a;
  int ans = min(swpb(b), swpa(a));
  cout << ans << endl; 
  return 0;
}

Measured memory_bytes: 6332
#include<iostream>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    int x[n];
    for(int i=0;i<n;i++){
        cin >> x[i];
    }
    int ans =0 ;
    for(int i=0;i<n;i++){
        ans += 2*min(x[i],k-x[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H;
  cin >> H;

  ll ans = 0;
  ll num = 1;
  while (H>0){
    ans += num;
    H /= 2;
    num *= 2;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
struct Edge{
  ll to,id;
};
typedef vector<vector<ll>> Graph;
typedef vector<pii> vpii;

ll F(ll a, ll b) {
  return max(to_string(a).length(),to_string(b).length());
}

int main() {
  ll N; cin>>N;
  ll ans = INF;
  for (ll i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      ans = min(ans, F(i, N / i));
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*10**9
dp[1]=1
dp[0]=0
#dp[i+1]　iをちょうど引き出すのに必要な最小回数
for i in range(1,N):
  dp[i+1]=(dp[i-L+1]+1).min()

  
print(int(dp[N]))
#print(len(L))

Measured memory_bytes: 88744
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define all(c) begin(c),end(c)
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
//最大公約数
ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}
//最小公倍数
ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}
//素因数分解
vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}
 
 
 
 
int main() {
  ll n;
  cin>>n;
  ll count=0;
  ll t=n;
  for(int i=1;i<n;i++){
    t--;
    if(t==n/2){
      continue;
    }else if(t>n/2){
      count++;
    }
  }
  cout<<count;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i<n;++i)
using ll = long long;
using P = pair<int,int>;

int main(){
  string s;
  cin >> s;
  bool flag = false;
  if(s == "a") flag = true;
  if(s == "i") flag = true;
  if(s == "u") flag = true;
  if(s == "e") flag = true;
  if(s == "o") flag = true;
  if(!flag) puts("consonant");
  else puts("vowel");
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
int n;
int p[maxn], a[maxn], b[maxn], deltaa[maxn], deltab[maxn];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i]);
		
	//puts("qwq");
		
	for (int i = 1; i <= n; i++)
		a[i] = i, b[i] = n - i + 1;
		
//			puts("qwq");
		
	for (int i = 1; i <= n; i++)
		deltaa[p[i] + 1] += 20000 - i, deltab[p[i] - 1] += 20000 - i;
		
			//puts("qwq");
		
	for (int i = 1; i <= n; i++)
		deltaa[i] += deltaa[i - 1], a[i] += deltaa[i];
		
		//	puts("qwq");
		
	
	for (int i = n; i; i--)
		deltab[i] += deltab[i + 1], b[i] += deltab[i];//, printf("i:%d b[i]:%d deltab[i]:%d\n", i, b[i], deltab[i]);
		
		//	puts("qwq");
		
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	puts("");

	for (int i = 1; i <= n; i++)
		printf("%d ", b[i]);
	puts("");

}

Measured memory_bytes: 4200
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
double eps=1e-9;
typedef double D;
typedef complex<D> P;
struct C{
	P p;D r;
	C(P p,D r) :p(p),r(r){}
};
bool comp(const C& l,const C& r){
	return l.r<r.r;
}
bool contain(C c,P p){
	return c.r>abs(c.p-p);
}
bool containCC(C a,C b){
	return abs(a.p-b.p)+b.r+eps<a.r;
}
int main(){
	while(true){
		int N;
		cin>>N;
		if(N==0) break;
		int sx,sy,tx,ty;
		cin>>sx>>sy>>tx>>ty;
		P s=P(sx,sy),t=P(tx,ty);
		vector<C> A,B;
		rep(i,N){
			D x,y,r;
			cin>>x>>y>>r;
			C c(P(x,y),r);
			if(contain(c,s)&&!contain(c,t)) A.pb(c);
			if(contain(c,t)&&!contain(c,s)) B.pb(c);
		}
		int da[1001]={},db[1001]={};
		int ans=0;
		sort(all(A),comp);
		sort(all(B),comp);
		rep(i,A.size()){
			da[i]=1;
			rep(j,i) if(containCC(A[i],A[j])) chmax(da[i],da[j]+1);
			chmax(ans,da[i]);
		}
		rep(i,B.size()){
			db[i]=1;
			rep(j,i) if(containCC(B[i],B[j])) chmax(db[i],db[j]+1);
			chmax(ans,db[i]);
		}
		rep(i,A.size()) rep(j,B.size()){
			if(abs(A[i].p-B[j].p)>A[i].r+B[j].r+eps) chmax(ans,da[i]+db[j]);
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1308
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 200009;
int t, T, n, last, ans = 0;

int main(){
	scanf("%d%d", &n, &T);
	for (int i=1; i<=n; i++){
		scanf("%d", &t);
		if (t <= last) { ans += t+T-last; }
		else ans += T;
		last = t+T;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    now = 0
    P = list( map( int, input().split()))
    for i in range(1, N+1):
        if i != P[i-1]:
            now += 1
    if now == 2 or now == 0:
        print("YES")
    else:
        print("NO")
if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 50;
ll f(ll x, ll y) {
	if(x > y) return INF;
	return y - x;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll x, y;
	cin >> x >> y;

	if(x == y) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = INF;
	ans = min(ans, f(x, y));
	ans = min(ans, 1 + f(-x, y));
	ans = min(ans, 1 + f(x, -y));
	ans = min(ans, 2 + f(-x, -y));
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
  int n,m,l;
  double p[100];
  int t[100],v[100];
  double time[100][51],prob[100][51];

  cin >> n >> m >> l;
  for(int i=0;i<n;i++){
    cin >> p[i] >> t[i] >> v[i];
    p[i] /= 100;
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<=m;j++)time[i][j] = (double)l/v[i] + t[i]*j;
  }
  
 
  for(int i=0;i<n;i++){
    if(abs(p[i]-1.0)<1e-10){
      for(int j=0;j<m;j++)prob[i][j] = 0.0;
      prob[i][m] = 1.0;
    }else{
      prob[i][0] = pow(1-p[i],m);
      for(int j=1;j<=m;j++){
	prob[i][j] = ( prob[i][j-1] * p[i] * (m-j+1) ) / ( (1-p[i])*j );
      }
    }
  }

  for(int i=0;i<n;i++){
    double ans = 0.0;
    if(!v[i])printf("%.8lf\n",ans);
    else{
      for(int j=0;j<=m;j++){
	double tmp = 1.0;
	for(int k=0;k<n;k++){
	  if(k!=i){
	    double hoge = 0.0;
	    for(int l=m;l>=0;l--){
	      if(time[k][l] > time[i][j]){
		hoge += prob[k][l];
	      }
	    }
	    tmp *= hoge;
	  }
	}
	ans += tmp*prob[i][j];
      }
      printf("%.8lf\n",ans);
    }
  }
}

Measured memory_bytes: 1064
a = gets.chomp.to_i
result = 1
x = gets.chomp.split(" ").map(&:to_i)
if a != x.length
  print 0
  exit
end
x.sort.each { |num|
  if num.zero?
    result = 0
    break
  end
  result = num * result
  if result > 10**18
    result = -1
    break
  end
}

print result

Measured memory_bytes: 25012
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

int main(){
  ll K,A,B;
  cin>>K>>A>>B;
  if(A >= B - 2){
    cout<<K+1<<endl;
    return 0;
  }
  ll ans = 1;
  if(K <= A - 1){
    ans += K;
    cout<<ans<<endl;
    return 0;
  }
  K -= A - 1;
  ll num = K / 2;
  ll sur = K % 2;
  ans = num * (B-A) + sur;
  ans += A;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
h,w = list(map(int, input().split()))
mt = [list(input()) for _ in range(h)]
mod = 10**9+7
dp = [[0]*(w+1) for _ in range(h+1)]
dp[1][1] = 1

j = 1
for i in range(1, h+1):
    dp[i][j] = dp[i][j]%mod
    if i < h:
        if mt[i][0] == ".":
            dp[i + 1][1] = dp[i][1]
        else:
            dp[i + 1][1] = 0
    for j in range(1, w):
        if mt[i-1][j] == ".":
            dp[i][j+1] = dp[i][j] + dp[i-1][j+1]
        else:
            dp[i][j+1] = 0

print(dp[-1][-1]%mod)

Measured memory_bytes: 244188
#include <stdio.h>

int count(int n) {
	return n == 0 ? 0 : count(n / 10) + 1;
}

int main() {
	int n, x, cnt;

	scanf("%d", &n);
	cnt = 0;
	for (x = 1; x <= n; x++)
		if (count(x) % 2)
			cnt++;
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 128
/*************************************************************************
    > File Name: b.cpp
    > Author: samcompu
    > Mail: admin@samcompu.com
    > Created Time: 2018年05月05日 星期六 20时18分54秒
************************************************************************/

#include<bits/stdc++.h>

using namespace std;
/*Constant*/

/*Class*/

/*Variable*/

/*Declare*/

int main() {
  int a;
  int b;
  int c;
  scanf("%d%d%d", &a, &b, &c);
  int maxNum = max(max(a, b), c);
  int ans = a + b + c - maxNum;
  int k;
  scanf("%d", &k);
  for (int i = 1; i <= k; i++) maxNum = maxNum * 2;
  printf("%d\n", ans + maxNum);
  return 0;
}

/*Define*/



Measured memory_bytes: 256