akhauriyash/Code-Regression huggingface dataset:
fun main(arg: Array<String>) {
    val S = next().map { it }.toMutableList()
    var p = 1
    fun T(): Boolean {
        if (S.size < 3) return false
        for (n in p until S.size - 1) {
            if (S[n - 1] != S[n + 1]) {
                S.removeAt(n)
                p = if (n > 1) n - 1 else 1
                return true
            }
        }
        return false
    }
    while (true) {
        if (!T()) return println("Second")
        if (!T()) return println("First")
    }
}

fun next() = readLine()!!


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

using namespace std;

vector<int> inv;
vector<int> fac;
vector<int> invfac;

void init(int n, int P) {
    inv.resize(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (long long)(P - (P / i)) * inv[P % i] % P;
    }
    fac.resize(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = (long long)fac[i - 1] * i % P;
    }
    invfac.resize(n + 1);
    invfac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        invfac[i] = (long long)invfac[i - 1] * inv[i] % P;
    }
}

int C(int n, int m, int P) {
    if (m > n) return 0;
    return (long long)fac[n] * invfac[m] % P * invfac[n - m] % P;
}

int pow(int a, int b, int P) {
    a %= P;
    int res = 1;
    while (b) {
        if (b & 1) res = (long long)res * a % P;
        a = (long long)a * a % P;
        b >>= 1;
    }
    return res;
}

int inverse(int x, int P) {
    return pow(x, P - 2, P);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    const int MOD = 1e9 + 7;
    init(n + n, MOD);
    vector<int> G[n];
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    vector<int> f(n), g(n);
    function<void(int, int)> dp = [&](int u, int fa) {
        f[u] = 1;
        g[u] = 0;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v == fa) continue;
            dp(v, u);
            f[u] = (long long)f[u] * f[v] % MOD * C(g[u] + g[v], g[v], MOD) % MOD;
            g[u] += g[v];
        }
        ++g[u];
    };
    dp(0, -1);
    vector<int> ans(n);
    function<void(int, int)> rotate = [&](int u, int fa) {
        if (fa == -1) {
            ans[u] = f[u];
        }
        else {
            ans[u] = (long long)f[u] * ans[fa] % MOD * inverse(f[u], MOD) % MOD * inverse(C(n - 1, g[u], MOD), MOD) % MOD * C(n - 1, g[u] - 1, MOD) % MOD;
        }
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v == fa) continue;
            rotate(v, u);
        }
    };
    rotate(0, -1);
    for (int i = 0; i < n; ++i) cout << ans[i] << endl;
    return 0;
}



Measured memory_bytes: 20980
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define SZ size()
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define REP(i, n) FOR((i), 0, (n))
#define GET(a) cin >> (a)
#define GET2(a, b) cin >> (a) >> (b)
#define GET3(a, b, c) cin >> (a) >> (b) >> (c)
#define SHOW(v) cout << (v) << endl
#define SHOW2(a, b) cout << (a) << " " << (b) << endl
#define SHOW3(a, b, c) cout << (a) << " " << (b) << " " << (c) << endl
#define MOD 1000000007
template<class T> void GETV(T &v) { REP(i, v.size()) { GET(v[i]); } }
template<class T> void SHOWV(T &v) { REP(i, v.size()) { SHOW(v[i]); } }

typedef long long ll;

int main() {
	int v[5];
	for(int i = 0; i < 5; i++) {
		cin >> v[i];
	}
	
	int k;
	cin >> k;
	
	for(int i = 0; i < 5; i++) {
		for(int j = i + 1; j < 5; j++) {
			if(abs(v[i] - v[j]) > k) {
				cout << ":(" << endl;
				return 0;
			}
		}
	}
	
	cout << "Yay!" << endl;
	
    return 0;
}

Measured memory_bytes: 256
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/
#include <bits/stdc++.h>
#define LL              long long
#define ll              long long
#define SL(n)           scanf("%lld",&n)
#define LF              double
#define SF(n)           scanf("%lf",&n)
 
#define pb              push_back
#define mp              make_pair
 
#define ON(n,i)         (n|(1LL<<i))
#define OFF(n,i)        (n&(~(1LL<<i)))
#define CHK(n,i)        (n&(1LL<<i))
 
#define ff              first
#define ss              second
 
#define SET(arr)        memset( arr , -1 , sizeof arr)
#define RESET(arr)      memset( arr,0,sizeof arr)
 
#define srt(v)          sort(v.begin(),v.end())
#define uniq(v)			v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define found( s,d )    (s.find(d) != s.end())
 
#define FOR(i,s,e)      for( LL i = s ; i<=e ; i++ )
#define RFOR(i,e,s)     for( LL i = e ; i>=s ; i-- )
         
 
#define FILEIN          freopen("in.txt","r",stdin)
#define FILEOUT         freopen("WA.txt","w",stdout)
 
#define DEBUG(x)        cerr<<#x<<" = "<<x<<endl
#define PRINTALL(v)     {cerr<<endl<<"Printing: "<<#v<<endl;for(LL i = 0 ; i<v.size(); i++) DEBUG(v[i]); cerr<<endl;}
 
#define sz(v)			((LL)v.size())
#define pi 				(acos(-1.0));
using namespace std;



int main(){ 
	
	LL X,K,D;
	SL(X); SL(K); SL(D);
	if(X>0) X = -X;
	
	LL l = abs(X)/D;
	LL r = l+1;
	l--,r++;
	
	LL mn = -1;
	for( LL i = max(0LL,l); i<=r; i++ )if( i<=K ){
		if( i%2 == K%2 ){
			if(mn==-1) mn = abs(X+i*D);
			else mn = min( mn , abs( X + i*D)  );
		}
	}
	if(mn==-1) mn = abs(X+K*D);
	cout<<mn<<endl;
return 0;}



Measured memory_bytes: 3736
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range (N-1,1,-1): 
  s = 0 
  l = i - 1
  while l > s:
    if L[s] + L[l] > L[i]:
      ans = ans + (l - s)
      l = l - 1
    else:
      s = s + 1
print(ans)

Measured memory_bytes: 3188
def main():
    N, M = map(int, input().split())
    S = []
    C = []
    for i in range(M):
        s, c = map(int, input().split())
        S.append(s)
        C.append(c)

    for x in range(10 ** N):
        num = str(x)
        ok = True
        if len(num) != N:
            ok = False
        else:
            for i in range(M):
                if int(num[S[i] - 1]) != C[i]:
                    ok = False
                    break
        if ok:
            print(x)
            break
    else:
        print(-1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
import bisect
n, m, k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0]
sb = [0]
for i in range(n):
    sa.append(sa[-1] + a[i])
for i in range(m):
    sb.append(sb[-1] + b[i])
ans = 0
for i in range(n+1):
    if sa[i] > k:
        continue
    else:
        j = bisect.bisect_right(sb, k-sa[i])
        ans = max(ans, i+j-1)
print(ans)

Measured memory_bytes: 131708
#!python3.8
# -*- coding: utf-8 -*-
# abc167/abc167_c
import sys
import itertools

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M, X = i2nn()
    C = [None] * N
    A = [None] * N
    sum_C_min = 0
    sum_A = [0] * M
    for i in range(N):
        C[i], *A[i] = i2nn()
        sum_C_min += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            print(-1)
            return
    for n in range(N - 1, 0, -1):
        sum_C_prev = sum_C_min
        for v in itertools.combinations(range(N), n):
            sum_C, ok = func(N, M, X, C, A, v)
            if ok and sum_C < sum_C_min:
                sum_C_min = sum_C
        if sum_C_prev == sum_C_min:
            print(sum_C_min)
            return
    print(sum_C_min)
    return

def func(N, M, X, C, A, v):
    sum_A = [0] * M
    sum_C = 0
    for i in v:
        sum_C += C[i]
        for j in range(M):
            sum_A[j] += A[i][j]
    for a in sum_A:
        if a < X:
            return sum_C, False
    return sum_C, True
main()


Measured memory_bytes: 9332
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using tii = tuple<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}
};

ll n, m, q;

void solve() {
	string ou = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	vs s,b;
	vl ans(m,((ll)1<<n)-1);
	string in1, in2;
	rep(i, q) {
		cin >> in1 >> in2;
		s.push_back(in1);
		b.push_back(in2);
	}
	//cout << ans[0];
	//cout << bitset<64>(ans[0]) << endl;
	rep(i, q) {
		ll tr=0;
		ll fa=0;
		rep(j, n) {
			if (s[i][n - j - 1] == '1')tr += 1;
			if(j!=n-1)tr *= 2;
		}
		fa = ((ll)1 << n) - 1 - tr;
		rep(j, m) {
			bool bo;
			if (i != 0)bo = (b[i][j]-'0')^(b[i-1][j] - '0');
			else bo = (b[i][j] != '0');
			if (bo) {
				ans[j]=ans[j]&tr;
			}
			else {
				ans[j] = ans[j] & fa;
			}
		}

		//cout << bitset<64>(tr) << endl;
		//cout << bitset<64>(fa) << endl;
		//cout << bitset<64>(ans[8]) << endl;
	}
	rep(i, m) {
		//cout << bitset<64>(ans[i]) << endl;
		ll che = 1;
		rep(j,n) {
			if (che == ans[i]) {
				cout << ou[j];
				j += n;
			}
			if (j != n - 1) che *= 2;
			else cout << "?";
		}
	}
	cout << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (cin >> n >> m >> q,n) {
		solve();
	}
}



Measured memory_bytes: 4200
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int H = l[0], W = l[1];
            var a = new int[H][];
            for (var i = 0; i < H; i++) {
                a[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
            }

            var ans = new List<string>();
            for (var i = 0; i < H; i++) {
                for (var j = 0; j < W; j++) {
                    if (a[i][j] % 2 == 1) {
                        if (j+1 < W) {
                            a[i][j]--;
                            a[i][j+1]++;
                            ans.Add($"{i+1} {j+1} {i+1} {j+2}");
                        } else if (i+1 < H) {
                            a[i][j]--;
                            a[i+1][j]++;
                            ans.Add($"{i+1} {j+1} {i+2} {j+1}");
                        }
                    }
                }
            }

            Console.WriteLine(ans.Count);
            foreach (var an in ans) {
                Console.WriteLine(an);
            }
        }
    }
}


Measured memory_bytes: 31012
import math
X = int(input())

i1 = math.floor(X/100)

for i in range(i1+1):
  for j in range(i1-i+1):
    for k in range(i1-i-j+1+1):
      for l in range(i1-i-j-k+1+1):
        for m in range(i1-i-j-k-l+1):
          for n in range(i1-i-j-k-l-m+1):
            if X==100*i + 101*j + 102*k +103*l +104*m +105*n:
              print(1)
              exit()
print(0)

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

using namespace std;

int main() {
  int n, r;
  cin >> n >> r;
  if (n >= 10) {
    cout << r << endl;
  } else {
    int ans = r + (100 * (10 - n));
    cout << ans << endl;
  }
  return 0;
}



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

int main() {
  int N,Y;
  bool finished =false;
  cin>>N>>Y;
  Y/=1000;
  for(int i=0; i<=N;i++){
    for(int j=0; j<=N;j++){
      if(i+j>N) continue;
      if((Y-i-j*5)==(N-i-j)*10){
        cout<<N-i-j<<" "<<j<<" "<<i<<endl;
        finished=true;
        break;
      }
    }
     if(finished) break;
  }
    if(finished==false){
      cout<<"-1 -1 -1"<<endl;
    }
}

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

int main() {
 int N;
 string S,T,u;

 cin >> N;
 cin >> S >> T;
 for (int i = 0; i < N; ++i){
 
 u += S.at(i);
 u += T.at(i); 
 
 } 
 
  
 cout << u << endl;

  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;

signed main(){
    ll N,W;
    cin >> N >> W;
    ll dp[N][1+N*(ll)1e3] = {};
    ll w[N],v[N];
    rep(i,0,N) cin >> w[i] >> v[i];

    rep(i,0,N){
        rep(j,1,1+N*1e3){
            dp[i][j] = LINF;
        }
    }
    dp[0][v[0]] = w[0];

    rep(i,1,N){
        rep(j,1,1+N*1e3){
            if(j-v[i] >= 0) dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]] + w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }

    ll ans = 0;
    rep(i,0,1+N*1e3){
        if(dp[N-1][i] <= W){
            ans = i;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 81724
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;

template <typename T> inline bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> inline bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    int n;
    cin >> n;
    vector<int> G[n];
    vector<pair<int, int>> p;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
        p.emplace_back(a, b);
    }

    int k = 0;
    map<pair<int, int>, int> mp;
    bool used[n] = {};
    used[0] = true;
    queue<pair<int, int>> que;
    que.emplace(0, 0);
    while(!que.empty()) {
        int v = que.front().first;
        int c = que.front().second;
        que.pop();
        chmax<int>(k, G[v].size());
        int cu = 1;
        for(int u : G[v]) {
            if(used[u]) continue;
            if(cu == c) cu++;
            que.emplace(u, cu);
            mp[{u, v}] = mp[{v, u}] = cu++;
            used[u] = 1;
        }
    }

    cout << k << endl;
    for(auto q : p)
        cout << mp[q] << endl;

    return 0;
}

Measured memory_bytes: 19448
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
void solve(){
    int a, b;
    cin>>a>>b;
    cout<<(1+2+3)-a-b; 
}
signed main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Measured memory_bytes: 256
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
using Data = deque<pair<char,int> >;

char conv(char c, int change) {
    if (change & 1) return (c == 'A' ? 'B' : 'A');
    else return c;
}
    
string recon(const Data &v, int change) {
    string res = "";
    for (auto p : v) for (int i = 0; i < p.second; ++i) res += conv(p.first, change);
    return res;
}

int main() {
    int N, K; string S;
    cin >> N >> K >> S;
    Data v;
    for (int i = 0; i < S.size();) {
        int j = i+1;
        while (j < S.size() && S[j] == S[i]) ++j;
        v.push_back({S[i], j-i});
        i = j;
    }
    int LIMIT = (int)S.size() * 10;
    if ((K - LIMIT) & 1) ++LIMIT;
    if (K > LIMIT) K = LIMIT;
    int change = 0;
    for (int i = 0; i < K; ++i) {
        char c = conv(v[0].first, change);
        if (c == 'A') {
            auto p = v[0];
            v.pop_front();
            if (p.second > 1) v.push_front({conv('A', change), p.second - 1});
            v.push_front({conv('B', change), 1});
        }
        else {
            ++change;
            v[0].second--;
            if (v[0].second == 0) v.pop_front();
            v.push_back({conv('A', change), 1});
        }
    }
    cout << recon(v, change) << endl;
}


Measured memory_bytes: 2724
#include <iostream>

using namespace std;

void explode(char board[][9], int x, int y)
{
	board[y][x] = '0';
	
	for (int i=3; i>0; i--) {
		if (x-i<0) break;
		if (board[y][x-i] != '0') explode(board, x-i, y);
	}
	for (int i=1; i<=3; i++) {
		if (x+i>=8) break;
		if (board[y][x+i] != '0') explode(board, x+i, y);
	}
	for (int i=3; i>0; i--) {
		if (y-i<0) break;
		if (board[y-i][x] != '0') explode(board, x, y-i);
	}
	for (int i=1; i<=3; i++) {
		if (y+i>=8) break;
		if (board[y+i][x] != '0') explode(board, x, y+i);
	}
}

void show(char board[][9])
{
	for (int i=0; i<8; i++) cout << board[i] << endl;
}

int main()
{
	int data_set_n;
	cin >> data_set_n;
	
	for (int k=0; k<data_set_n; k++) {
		char board[8][9];
		int init_x, init_y;
		for (int i=0; i<8; i++) cin >> board[i];
		cin >> init_x >> init_y;
		explode(board, init_x - 1, init_y - 1);
		cout << "Data " << k+1 << ":" << endl;
		show(board);
	}
	
	return 0;
}

Measured memory_bytes: 3056
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n,k;
  cin >> n >> k;

  cout << (n%k!=0) << endl;

  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int a[100100],b[100100],deg[100100],ans[100100];
bool visited[100100];
queue<P> q;

vector<P> g[100100];

int main(void){
	int n,i,u,v,c,p;
	cin >> n;
	for(i=1; i<n; ++i){
		cin >> a[i] >> b[i];
		--a[i]; --b[i];
		g[a[i]].push_back(P(b[i],i));
		g[b[i]].push_back(P(a[i],i));
	}
	for(i=0; i<n; ++i){
		ans[0] = max(ans[0],(int)g[i].l_ength());
	}
	q.push(P(0,0));
	while(!q.empty()){
		u = q.front().first;
		p = q.front().second;
		q.pop();
		visited[u] = true;
		c = 1;
		for(i=(g[u].l_ength()-1); i>=0; --i){
			v = g[u][i].first;
			if(visited[v]){
				continue;
			}
			if(c==p){
				++c;
			}
			ans[g[u][i].second] = c;
			q.push(P(v,c));
			++c;
		}
	}
	for(i=0; i<n; ++i){
		cout << ans[i] << endl;
	}
	return 0;
}


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

bool isPrime(int x) {
    for(int i = 2; i < x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    int x;
    cin >> x;

    while(!isPrime(x)) {
        x++;
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
program main
  implicit none

  integer(8) :: a, b, c

  read(*,*) a, b, c

  if (mod(a,2) == 0 .or. mod(b,2) == 0 .or. mod(c,2) == 0) then
     write(*,*) 0

  else
     write(*,*) min(a*b, b*c, c*a)

  end if
  stop
  
end program main


Measured memory_bytes: 640
#include <iostream>
#include<vector>
using namespace std;
int main(void){
   int n;
   cin >> n;
   string s,t;
   cin >> s;
   cin >> t;
   int res = 0;
   for(int i = 0;i <= n;i++){
         if(s.substr(n - i,i) == t.substr(0,i)) res =i;
   }
   cout << 2 * n - res << endl;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define S second
#define F first
const int  MOD = 1e9 + 7;
const int  N = 1e5 + 7;
int dp[N][3] , a[N] , b[N] , c[N];


//  a d f j k  l  ;
int main(){
    ios::sync_with_stdio(0);  cin.tie(0);
    int n;
    cin>>n;
    for(int i = 0 ; i < n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for(int i = 1; i < n ; i++){
        dp[i][0] = max(dp[i-1][1] , dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0] , dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0] , dp[i-1][1]) + c[i];
    }
    cout<<max( max(dp[n-1][0] , dp[n-1][1]) , dp[n-1][2])<<endl;

    return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(int argc, char*argv[])
{
  for(;;) {
    int p, q;
    cin >> p >> q;
    if(p == 0 && q == 0) break;
    auto analyze = [](const string &line) {
      vector<int> bs = {0,0,0,0};
      int ind = 0;
      bool fst = true;
      for(int j = 0; j < line.length(); j++) {
        if(fst && line[j] == '.') { ind++; continue; }
        fst = false;
        switch(line[j]) {
        case '(' : { bs[0]++; break; }
        case ')' : { bs[0]--; break; }
        case '{' : { bs[1]++; break; }
        case '}' : { bs[1]--; break; }
        case '[' : { bs[2]++; break; }
        case ']' : { bs[2]--; break; }
        }
      }
      bs[3] = ind;
      return bs;
    };
    vector<vector<int>> pbs, qbs;
    for(int i = 0; i < p; i++) {
      string line;
      cin >> line;
      vector<int> bs = analyze(line);
      pbs.push_back(bs);
    }
    for(int i = 0; i < q; i++) {
      string line;
      cin >> line;
      vector<int> bs = analyze(line);
      qbs.push_back(bs);
    }
    auto indent = [](const vector<vector<int>> &bss, int r, int c, int s) {
      int rs = 0, cs = 0, ss = 0;
      vector<int> inds;
      for(int i = 0; i < bss.size(); i++) {
        int ind = rs * r + cs * c + ss * s;
        inds.push_back(ind);
        rs += bss[i][0];
        cs += bss[i][1];
        ss += bss[i][2];
      }
      return inds;
    };
    auto check = [&pbs,&indent](int r, int c, int s) {
      vector<int> inds = indent(pbs,r,c,s);
      for(int i = 0; i < pbs.size(); i++) {
        if(inds[i] != pbs[i][3]) return false;
      }
      return true;
    };
    vector<vector<int>> rcss;
    for(int r = 1; r <= 20; r++) {
      for(int c = 1; c <= 20; c++) {
        for(int s = 1; s <= 20; s++) {
          if(check(r,c,s)) {
            rcss.push_back({r, c, s});
          }
        }
      }
    }
    vector<int> ans;
    for(auto rcs : rcss) {
      vector<int> inds = indent(qbs, rcs[0], rcs[1], rcs[2]);
      if(ans.size() == 0) {
        ans = inds;
      } else {
        for(int i = 0; i < ans.size(); i++) {
          if(ans[i] != inds[i]) ans[i] = -1;
        }
      }
    }
    for(int i = 0; i < ans.size(); i++) {
      if(i > 0) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3456
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <cmath>
#include <iomanip>
using namespace std;
#define sL(i) i << 1
#define sR(i) i << 1 | 1
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pair<int,int>, int> ppi;
const int MOD = 1e9 + 7;
const int INF = 2e9 + 5;
const int maxn = 3e5 + 5;
int N, east[maxn], west[maxn];
string S;
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> S;
    east[0] = west[0] = 0;
    for(int i = 0; i < N; i++){
        east[i+1] = east[i];
        west[i+1] = west[i];
        if(S[i] == 'W') west[i+1]++;
        else east[i+1]++;
    }
    int best = maxn;
    for(int i = 0; i < N; i++){
        // choose i
        best = min(best, west[i] + east[N] - east[i+1]);
    }
    cout << best;
}

Measured memory_bytes: 2964
/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define loop(i,n) for(int i=0;i<(n);i++)
#define cont(i,n) for(int i=1;i<=(n);i++)
#define circ(i,a,b) for(int i=(a);i<=(b);i++)
#define range(i,a,b,c) for(int i=(a);((c)>0?i<=(b):i>=(b));i+=(c))
#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin(),_e_D_=(v).end();it!=_e_D_;it++)
#define y0 y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1 y1II11II11III11I1III11II111IIII1II1I1
#define pub push_back
#define pob pop_back
#define mak make_pair

typedef long long ll;
typedef long double lf;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

int main(){
	puts("32957");
	puts("< 2 0 3");
	puts("+ 0 3 0");
	range(j,30,0,-1){
		puts("< 2 0 5");
		loop(k,j)puts("+ 5 5 5");
		puts("+ 4 5 10");
		puts("< 10 0 6");
		printf("< 10 0 %d\n",j+100);
		loop(k,j)puts("+ 6 6 6");
		puts("+ 4 6 4");
	}
	puts("< 0 2 4");
	puts("+ 1 3 1");
	range(j,30,0,-1){
		puts("< 2 0 5");
		loop(k,j)puts("+ 5 5 5");
		puts("+ 4 5 10");
		puts("< 10 1 6");
		printf("< 10 1 %d\n",j+200);
		printf("< %d 3 %d\n",j+200,j+200);
		loop(k,j)puts("+ 6 6 6");
		puts("+ 4 6 4");
	}
	loop(i,31)loop(j,31){
		printf("< %d %d 1000\n",i+200,j+100);
		loop(k,i+j)puts("+ 1000 1000 1000");
		puts("+ 2 1000 2");
	}
	return 0;
}

Measured memory_bytes: 3652
#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>;
void Yes() {
    cout << "Yes" << endl;
}
void No() {
    cout << "No" << endl;
}
int main(void) {
    int a, b; cin >> a >> b;
    cout << a * b;
}


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

int main(void) {

    int n, k;
    cin >> n >> k;

    vector<bool> haveOkasi(n, false);

    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            a--;
            haveOkasi[a] = true;
        }
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (!haveOkasi[i]) sum++;
    }

    cout << sum << endl;

    return 0;

}


Measured memory_bytes: 3632
#include<stdio.h>
int main(){
    int n,i,j;
    double tmp;
    double v[50];
    
    scanf("%d",&n);
    for(i = 0 ; i < n ; i++) scanf("%lf",&v[i]);
    
    for(i = 0 ; i < n-1 ; i++){
        for(j = i+1 ; j < n ; j++){
            if(v[i] > v[j]){
                tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
            }
        }
    }
    for(i = 0 ; i < n-1 ; i++){
        v[i+1] = (v[i]+v[i+1])/2;
    }
    printf("%lf\n",v[n-1]);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  int k;
  cin >> k;
  k--;
  for(int i=0; i<n; ++i)
   if (s[i]!=s[k]) cout << '*'; else cout << s[i];
  return 0;
}

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

int main() {
  int h,w,k,ans=0,cnt=0;
  cin >> h >> w >> k;
  char table[h][w];
  char pre[h][w];

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> table[i][j];
      pre[i][j] = table[i][j];
    }    
  }
  
// h=3,w=3
  int l = h+w;
  for (int tmp = 0; tmp < (1<<l); tmp++) {
    bitset<12> s(tmp); //最大12個
    //配列のコピー
    for (int b=0; b < h; b++) {
      for (int c = 0; c< w; c++) {
        table[b][c] = pre[b][c];
      }
    }


    for (int i = 0; i < l; i++) {
      if (i < h) {
        if (s.test(i)) {
          for (int p = 0; p < w; p++) {
            table[i][p] = '.';
          } 
        }
      }
      else {
        if (s.test(i)) {
          for (int p = 0; p < h; p++) {
            table[p][i-h] = '.';
          }
        }
      }
    }
    cnt = 0; 
    for (int x = 0; x < h; x++) {
        for (int y = 0; y < w; y++) {
          if (table[x][y] == '#') cnt++;
        }
      }
      if (cnt == k) ans++; 
  }
  cout << ans << endl;
}

Measured memory_bytes: 3604
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, max = 10000000000, ans = 0;
  scanf("%lld", &n);
  ll a[n], b[n];
  for(i = 0; i < n; ++i) {
    scanf("%lld%lld", &a[i], &b[i]);
    ans += a[i];
    if(a[i] > b[i] && max > b[i]) max = b[i];
  }
  if(max != 10000000000) printf("%lld", ans - max);
  else printf("0");
  return 0;
}

Measured memory_bytes: 512
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::HashSet;
use std::cmp;
use std::f64::consts;

fn main() {
    let n: i32 = read();
    let vec: Vec<i32> = (0..n).map(|_| read()).collect();
    let mut odd: HashMap<i32, i32> = HashMap::new();
    let mut even: HashMap<i32, i32> = HashMap::new();

    for (e, &i) in vec.iter().enumerate() {
        if e % 2 == 0 {
            if odd.contains_key(&i) {
                let v = odd.get(&i).unwrap().clone();
                odd.insert(i, v + 1);
            } else {
                odd.insert(i, 1);
            }
        } else {
            if even.contains_key(&i) {
                let v = even.get(&i).unwrap().clone();
                even.insert(i, v + 1);
            } else {
                even.insert(i, 1);
            }
        }
    }

    let mut saihin_odd: i32 = 0;
    let mut saihin_odd_key: i32 = 0;
    let mut saihin_even: i32 = 0;
    let mut saihin_even_key: i32 = 0;
    let mut next_odd: i32 = 0;
    let mut next_odd_key: i32 = 0;
    let mut next_even: i32 = 0;
    let mut next_even_key: i32 = 0;

    for (&key, &value) in odd.iter() {
        if value > saihin_odd {
            saihin_odd = value.clone();
            saihin_odd_key = key;
        }
    }

    for (&key, &value) in odd.iter() {
        if key != saihin_odd_key && value > next_odd {
            next_odd = value.clone();
            next_odd_key = key;
        }
    }

    for (&key, &value) in even.iter() {
        if value > saihin_even {
            saihin_even = value.clone();
            saihin_even_key = key;
        }
    }

    for (&key, &value) in even.iter() {
        if key != saihin_even_key && value > next_even {
            next_even = value.clone();
            next_even_key = key;
        }
    }

    let mut ans = (n/2) as i32 - saihin_odd + (n/2) as i32 - saihin_even;

    let set: HashSet<i32> = vec.into_iter().collect();

    if ans == 0 && set.len() == 1 {
        ans = (n/2);
    } else if saihin_odd_key == saihin_even_key {
        let a = (n/2) as i32 - saihin_odd + (n/2) as i32 - next_even;
        let b = (n/2) as i32 - next_odd + (n/2) as i32 - saihin_even;
        ans = cmp::min(a, b);
    }

    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 12540
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

#define mp make_pair
#define ll long long
#define fi first
#define se second
#define vi vector< int > 
#define pii pair<int,int>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
multiset<int> s[200005];
set<pair<int,int>> g;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,k,x1,x2,y1,y2;
	cin >> n >> m >> k;
	vector<vector<bool> > v(n+1,vector<bool>(m+1)),vis(n+1,vector<bool>(m+1));
	vector<vector<int> > dis(n+1,vector<int>(m+1));
	cin >> x1 >> y1 >> x2 >> y2;
	char c;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <=m; j++) {
		 cin >> c;
		v[i][j] = (c == '.');
		if (c != '.') vis[i][j] = 1;
	}
	if (!v[x1][y1] || !v[x2][y2]) {
		cout << -1;
		exit(0);
	}             
	queue<pair<int,int> > q;
	q.push({x1,y1});
	vis[x1][y1] = 1;
	while (!q.empty()) {
		int x = q.front().fi;	
		int y = q.front().se;
		q.pop();
		if (x  == x2 && y == y2) {
			cout << dis[x][y];
			exit(0);
		}
		for (int i = 0;i < 4; i++) {
			for (int f = 1; f <= k; f++) {
			int ax = dx[i]*f + x;
			int ay = dy[i]*f + y;
			if (ax <= 0 || ay <= 0 || ax > n || ay > m) break;
			if (vis[ax][ay] && dis[ax][ay] <= dis[x][y]) break;
			if (vis[ax][ay] && dis[ax][ay] == dis[x][y]+1) continue;
			vis[ax][ay] = 1;
			dis[ax][ay] = dis[x][y] + 1;
			q.push({ax,ay});
	}
		}	
	}
	cout << -1;	
}

Measured memory_bytes: 24880
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <stack>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;

void getmoney(int n, int m){
    int v = m/n;
    int s = 0;
    int x;
    for (int i = 0; i < n; i++){
      cin >> x;
        s += min(x, v);
    }
    cout << s << endl;
}


int main()
{
    int n, m, status;
  	status = 1;
    while(status){
        cin >> n >> m;
        if (n == 0 && m == 0){
            status = 0;
        }
        else {
            getmoney(n, m);
        }
    }
    return 0;
}




Measured memory_bytes: 2988
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<functional>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(int)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

char m(char a, char b) {
	if(a == 'T' && b == 'F') return 'F';
	else return 'T';
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<char> p(n);
	REP(i, n) cin >> p[i];
	char tmp = m(p[0], p[1]);
	FOR(i, 2, n) {
		tmp = m(tmp, p[i]);
	}
	cout << tmp << endl;
}
/* --------------------------------------- */



Measured memory_bytes: 3276
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()
T = inintl()
m = inint()

for i in range(m):
    p, x = inintm()
    t = T[p-1]
    T[p-1] = x
    print(sum(T))
    T[p-1] = t

Measured memory_bytes: 62988
#include <iostream>
#include <vector>
#include <assert.h>
#include <cmath>
#include <algorithm>

//int32_t gcd(int32_t a, int32_t b){
//    int32_t big = std::max(a,b);
//    int32_t small = std::min(a,b);
//    if(small == 0) return big;
//    int32_t res = small;
//    int32_t mod = big % small;
//    while(mod != 0){
//        big = small;
//        res = mod;
//        mod = small % mod;
//    }
//    return res;
//}

int32_t gcd(int32_t a, int32_t b) { return b ? gcd(b, a%b) : a;}

int main(){
    int32_t N;
    std::cin >> N;
    std::vector<int32_t> A(N);
    for(auto& i : A){
        std::cin >> i;
    }
    
    std::vector<int32_t> left(N+1,0);
    std::vector<int32_t> right(N+1,0);
    for(int32_t i = 0; i < N; i++){
        left[i+1] = gcd(left[i],A[i]);
        right[i+1] = gcd(right[i],A[N - i -1]);
        //std::cout << "i,left,right" << i << "," << left[i+1] << "," << right[i+1] << std::endl;
    }

    int32_t res = 0;
    for(int32_t j = 0; j < N; j++){
        res = std::max(res, gcd(left[j], right[N-j-1]));
    }
    std::cout << res;


    return 0;
}


Measured memory_bytes: 1408
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections
import copy


class Node(object):

  def __init__(self, n, m):
    self.lamps = [[0] * n for _ in range(m)]
    self.status = [[0, 0] for _ in range(m)]
    self.index = 0

  def create_children(self):
    children = []

    child0 = copy.deepcopy(self)
    child1 = copy.deepcopy(self)

    for i in range(len(self.status)):
      child0.status[i][0] -= child0.lamps[i][self.index]
      child1.status[i][0] -= child1.lamps[i][self.index]
      child1.status[i][1] += child1.lamps[i][self.index]

    child0.index += 1
    child1.index += 1

    if child0.is_valid():
      children.append(child0)

    if child1.is_valid():
      children.append(child1)

    return children

  def is_valid(self):
    for r, v in self.status:
      if r == 0 and v % 2 == 1:
        return False

    return True


def main():
  n, m = map(int, input().split())
  root = Node(n, m)

  for i in range(m):
    v = list(map(int, input().split()))[1:]

    for j in v:
      root.lamps[i][j - 1] = 1

    root.status[i][0] = len(v)

  for i, v in enumerate(map(int, input().split())):
    root.status[i][1] = v

  stack = collections.deque()
  stack.append(root)
  count = 0

  while len(stack) != 0:
    node = stack.pop()

    children = node.create_children()

    for child in children:
      if child.index == n:
        count += 1
      else:
        stack.append(child)

  print(count)


if __name__ == '__main__':
  main()



Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int mod = 1e9+7;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
int size[5050];
struct node{
	int to,next;
}e[100010];
ll base[5050],f[5050][5050],g[5050],h[5050],tot,n;
inline void add_edge(int from,int to){e[++tot].next=h[from];h[from]=tot;e[tot].to=to;}
inline void DFS(int now,int ffa)
{
	size[now]=1;
	for(register int i=h[now];i;i=e[i].next)
	{
		int to=e[i].to;if(to==ffa) continue;
		DFS(to,now);size[now]+=size[to];
	}
	f[now][1]=1;int las=1;
	for(register int i=h[now];i;i=e[i].next){
		int to=e[i].to;if(to==ffa) continue;
		for(register int j=1;j<=las;++j) g[j]=f[now][j],f[now][j]=0;
		for(register int j=1;j<=las;++j){
			for(register int k=1;k<=size[to];++k){
				f[now][k+j]=(f[now][j+k]+1ll*g[j]*f[to][k]%mod)%mod;
				if(k%2==0){
					f[now][j]=(f[now][j]+mod-(1ll*g[j]*f[to][k]%mod*base[k/2]%mod))%mod;
				}
			}
		}las+=size[to];
	}
}
int main()
{
	n=read();
	for(register int i=1,u,v;i<n;++i) u=read(),v=read(),add_edge(u,v),add_edge(v,u);
	base[0]=1;for(register int i=1;i<=n;++i) base[i]=1ll*base[i-1]*(2ll*i-1ll)%mod;
	DFS(1,0);ll ans=0;
	for(register int i=1;i<=n;++i) if(i%2==0) ans=(ans+f[1][i]*base[i/2]%mod)%mod;
	cout<<ans%mod;
	return 0;
}

Measured memory_bytes: 198272
n = int(input())
a = [int(i) for i in input().split()]
x = [0]*(n+1)
m = 0
ans = []
for i in reversed(range(1,n+1)):
  tmp = 0
  for j in range(2*i,n+1,i):
    if x[j] == 1:
      tmp += 1
  if tmp % 2 != a[i-1]:
    x[i] = 1
    m += 1
    ans.append(i)
print(m)
for i in ans:
  print(i,end=" ")

Measured memory_bytes: 12116
#include <bits/stdc++.h>
#define int long long int
#define IOS ios_base::sync_with_stdio(false), cin.tie(NULL);
#define fr(i,a,b)  for(int i=a;i<=b;i++)
#define rf(j,b,a)  for(int j=b;j>=a;j--)
#define frr(k,a,b) for(int k=a;k<=b;k++)
#define mp make_pair
#define pb push_back
#define MOD 1000000007
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
signed main()
{   
	IOS
  /*  #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif*/
int n;
cin>>n;
double p[n+1];
for(int i=1;i<=n;i++)
{
	cin>>p[i];
}
double dp[n+1][n+1];
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++)
{
	for(int j=0;j<=i;j++)
	{	
	if(i==1&&j==0)
	{
	dp[i][j]=1-p[i];
	}	
	else if(j==0)
	{
    dp[i][j]=dp[i-1][j]*(1-p[i]); 
	}
	else if(i==1&&j==1)
    {
    dp[i][j]=p[i];
    continue;	
    }
    else
    {
    dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];	
    }	

	}
}

double ans =0;

for(int i=n/2+1;i<=n;i++)
{
	ans = ans + dp[n][i];
}
cout<<setprecision(12)<<fixed;
cout<<ans<<endl;

}









Measured memory_bytes: 70656
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	int a[100000];
	int k,s;
	int n, m;
	int x, y, z;
	int ans;


	scanf("%d %d %d", &x,&y,&z);


	if(x==y)printf("%d\n", z);
	else if (z == y)printf("%d\n", x);
	else if (x == z)printf("%d\n", y);

	return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <stack>
#include <cstdio>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>
#include <sstream>
#define popcount(x) __builtin_popcount(x)
#define oddparity(x) __builtin_parity(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define sf scanf
#define pf printf
using namespace std;

int i, j, l, x, n, k;

int main()
{
    sf("%d%d", &n, &k);
    int a[k];
    for (i = 0; i < k; i++) {
        sf("%d", &a[i]);
    }
    for (j = n; ; j++) {
        l = j;
        bool test = true;
        while (l) {
            x = l % 10;
            l /= 10;
            for (i = 0; i < k; i++) {
                if (x == a[i]) {
                    test = false;
                    break;
                }
            }
        }
        if (test) {
            pf("%d\n", j);
            break;
        }
    }
    return 0;
}

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

int main() {
  
  int N, sum;
  sum = 0;
  cin >> N;
  
  for(int i = 1; i <= N; i++){
	if(i % 15 != 0){
      sum += 800;
      //cout << '!' << sum << endl;
    }
    if(i % 15 == 0){
      sum += 600;
      //cout << "!!" << sum << endl;
    }
  }
  
  cout << sum << endl;
  
}


Measured memory_bytes: 256
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int A = sc.nextInt();
		System.out.println(N % 500 <= A?"Yes":"No");
	}
}

Measured memory_bytes: 21588
time = []
rem = []
for _ in range(5):
    n = int(input())
    time.append(n)
    if n % 10 != 0:
        rem.append(10 - n % 10)

rem.sort()
ans = sum(time) + sum(rem[:len(rem)-1])
# print(time, rem)
print(ans)


Measured memory_bytes: 2940
//Tran Thuy Duong
#include <bits/stdc++.h>
#define maxn 400005
#define maxc 1000000009
#define MOD 1000000007
#define reset(x) memset(x, 0, sizeof x)
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;

int n, res = 0;

int main()
{
    //freopen("inp.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; i*=100)
    {
        if (n < i*10) {res += n - i + 1; break;}
        res += i*9;
    }
    cout << res;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <cmath>

#define INF 100000000
#define MOD 1000000007
using namespace std;


int main(){
    int N;
    cin >> N;
    
    int divisor[N+1]={};
    
    for(int i=2; i<=N; i++){
        int k=i;
        for(int j=2; j<=N; j++){
            if(k%j==0){
                divisor[j]++;
                k/=j;
                j--;
            }
        }
    }
    
    long long ans=1;
    for(int i=0; i<=N; i++){
        ans*=divisor[i]+1;
        ans%=MOD;
    }
    
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
S = input()
ans = [0]*(len(S)+1)

for i in range(len(S)):
    if S[i] == "<":
        ans[i+1] = max(ans[i+1], ans[i]+1)

for i in range(len(S)-1, -1, -1):
    if S[i] == ">":
        ans[i] = max(ans[i], ans[i+1]+1)
print(sum(ans))

Measured memory_bytes: 28944
from collections import deque
INF=10**10
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
d=[[INF]*W for _ in range(H)]
d[s[0]][s[1]]=0
q=deque()
q.append(s)
while q:
    y,x=q.pop()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.' and d[ny][nx]>d[y][x]:
            q.append((ny,nx))
            d[ny][nx]=d[y][x]
    for dy in range(-2,3):
        for dx in range(-2,3):
            if abs(dy)+abs(dx)<=1:
                continue
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and d[ny][nx]>d[y][x]+1:
                q.appendleft((ny,nx))
                d[ny][nx]=d[y][x]+1
ans=d[g[0]][g[1]]
if ans<INF:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 127192