akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int in[MAX_N];
vi G[MAX_N];
int dp[MAX_N];
int M;

void dfs(int v, int p) {
	multiset<int> S;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		dfs(n, v);
		if(dp[n] != -1) S.insert(-(dp[n] + 1));
	}
	if(in[v] % 2) S.insert(0);
	while(!S.empty()) {
		int t = -(*S.begin());
		S.erase(S.begin());
		auto b = S.lower_bound(-(M - t));
		if(b != S.end()) {
			S.erase(b);
		}
		else {
			if(dp[v] == -1) dp[v] = t;
			else dp[v] = M + 1;
		}
	}
}

bool ok(int m) {
	M = m;
	memset(dp, -1, sizeof(dp));
	dfs(0, -1);
	if(dp[0] == -1) return true;
	else return false;
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
		in[a]++; in[b]++;
	}
	int A = 0;
	rep(i, 0, N) {
		A += in[i] % 2;
	}
	int lv = 0, rv = N;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(ok(m)) rv = m;
		else lv = m;
	}
	cout << A / 2 << " " << rv << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 21504
#include "bits/stdc++.h"
using namespace std;

int main(){
    int s;
    cin >> s;
    bool upper_is_YY = false, lower_is_YY = false;
    
    int upper = s / 100;
    int lower = s - upper * 100;
    
    if(upper > 12 || upper == 0) upper_is_YY = true;
    if(lower > 12 || lower == 0) lower_is_YY = true;

    string ans;
    if(upper_is_YY && lower_is_YY) ans = "NA";
    if(upper_is_YY && !lower_is_YY) ans = "YYMM";
    if(!upper_is_YY && lower_is_YY) ans = "MMYY";
    if(!upper_is_YY && !lower_is_YY) ans = "AMBIGUOUS";

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


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

using namespace std;

#define LOG(...) fprintf(stderr,__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct P {
    vi pos;
    int from;
    int cost;

    bool operator >(const P& p) const {
        return cost > p.cost;
    }
};

const int moveto[9][4] = {
    {2,4,9,7},
    {3,5,1,8},
    {4,6,2,9},
    {5,7,3,1},
    {6,8,4,2},
    {7,9,5,3},
    {8,1,6,4},
    {9,2,7,5},
    {1,3,8,6},
};

inline int keypos(vi& pos) {
    int pp = 0;
    REP(i, 9) {
        pp *= 10;
        pp += pos[i];
    }
    return pp;
}

int main() {
    int c[2];
    while (cin >> c[0] >> c[1], c[0]|c[1]) {
        vi start(9), goal(9);
        REP(i, 9) cin >> start[i];
        REP(i, 9) cin >> goal[i];

        unordered_map<int, int> G;

        priority_queue<P, vector<P>, greater<P>> que;
        G[keypos(start)] = 0;
        int from = find(ALL(start), 0) - start.begin();
        que.push({start, from, 0});

        while (!que.empty()) {
            P p = que.top(); que.pop();
            if (p.pos == goal) {
                cout << p.cost << endl;
                break;
            }

            REP(i, 4) {
                int to = moveto[p.from][i]-1; // oops
                swap(p.pos[p.from], p.pos[to]);
                int cost = p.cost + c[i%2];
                int k = keypos(p.pos);
                if (!EXIST(G, k) || G[k] > cost) {
                    G[k] = cost;
                    que.push({p.pos, to, cost});
                }
                swap(p.pos[p.from], p.pos[to]);
            }
        }
    }
}

Measured memory_bytes: 31096
#include <stdio.h>
int main(void){
	int num[100];
	int x, i;
	int max = 0, max_i;

	for(i=0; i<100; i++){
		num[i] = 0;
	}
	while(scanf("%d", &x) != EOF){
		num[x-1]++;
	}
	for(i=0; i<100; i++){
		if(max < num[i]){
			max = num[i];
		}
	}
	for(i=0; i<100; i++){
		if(max == num[i]){
			printf("%d\n", i+1);
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>

int main()
{
  unsigned N;
  long x;
  std::cin >> N >> x;
  
  std::vector<long> a(N);
  for(unsigned n = 0; n < N; ++n)
  {
    std::cin >> a[n];
  }
  
  long p = 0;
  for(unsigned n = 1; n < N; ++n)
  {
    long s = a[n] + a[n-1];
    if(s > x)
    {
      long d = s - x;
      
      if(a[n] >= d)
      {
        a[n] -= d;
      }
      else // a[n] <= d
      {
        a[n-1] -= d - a[n];
        a[n] = 0;
      }
      
      p += d;
    }
  }
  
  std::cout << p << std::endl;
  
  return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        FastScanner sc = new FastScanner();

        int counter = 0;
        int i;
        while((i=sc.nextInt())!=0){
            counter++;
            System.out.println("Case "+counter+": "+i);
        }

    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}



Measured memory_bytes: 31748
n=int(input())
P=list()
N=n
y=2
while y*y<=N:
    while N%y==0:
        P.append(y)
        N//=y
    y+=1
if N>1:
    P.append(N)
print(n,":",sep="",end="")
print("",*P,sep=" ")



Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,k;
    cin>>n;
    k=2;
    ll h[n];
    for(ll i=0;i<n;i++){
        cin>>h[i];
    }
    ll dp[n];
    memset(dp,1e9+5,sizeof(dp));
    dp[0]=0;
    for(ll i=0;i<n;i++){
        for(ll j=i+1;j<=i+k;j++){
            if(j<n){
                dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]));
            }
        }
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
  string S;
  int Q, T, F;
  char C;

  cin >> S;

  list<char> SS;
  for(int i=0; i<S.size(); i++)
  {
    SS.push_back(S[i]);
  }

  cin >> Q;

  bool inv = false;
  for(int i=0; i<Q; i++)
  {
    cin >> T;
    if(T == 1)
    {
      inv = !inv;
    }
    else
    {
      cin >> F >> C;
      if(F == 1)
      {
        if(inv)
        {
          SS.push_back(C);
        }
        else
        {
          SS.push_front(C);
        }
      }
      else
      {
        if(inv)
        {
          SS.push_front(C);
        }
        else
        {
          SS.push_back(C);
        }
      } 
    }
  }

  if(inv)
  {
    reverse(SS.begin(), SS.end());
  }

  list<char>::iterator itr;
  for (itr = SS.begin(); itr != SS.end(); itr++) {
        cout << *itr;
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  vector<ll> A(n);
  vector<ll> pos, neg;
  rep(i, n) {
    cin >> A[i];
    if(A[i] >= 0) pos.push_back(A[i]);
    else neg.push_back(-A[i]);
  }
  int np = pos.size(), nn = neg.size();
  if(n == k) {
    ll ans = 1;
    rep(i, k) (ans *= A[i]) %= mod;
    cout << (ans+mod)%mod << "\n";
  } else if(n == nn && k%2) {
    sort(all(neg));
    ll ans = 1;
    rep(i, k) (ans *= neg[i]) %= mod;
    cout << mod-ans << "\n";
  } else {
    ll ans = 1;
    sort(all(pos), greater<ll>());
    sort(all(neg), greater<ll>());
    int cnt = 0;
    int i=0, j=0;
    auto addpos = [&]() {
      (ans *= pos[i]) %= mod;
      i++;
      cnt++;
    };
    auto addneg = [&]() {
      (ans *= neg[j]) %= mod;
      (ans *= neg[j+1]) %= mod;
      j += 2;
      cnt += 2;
    };
    while(cnt < k) {
      if(k-cnt == 1) {
        addpos();
      } else if(i == np) {
        addneg();
      } else if(j >= nn-1) {
        addpos();
      } else if(i == np-1) {
        if(pos[i] > neg[j]*neg[j+1]) addpos();
        else addneg();
      } else {
        if(pos[i]*pos[i+1] > neg[j]*neg[j+1]) addpos();
        else addneg();
      }
    }
    cout << ans << "\n";
  }
  return 0;
}


Measured memory_bytes: 6976
n, m = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
total = 0
x_total = 0
y_total = 0
for i in range(len(x)):
    x_total += x[i] * i - x[i] * (n - (i + 1))
for i in range(len(y)):
    y_total += y[i] * i - y[i] * (m - (i + 1))
print((x_total * y_total) % mod)


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

#define AndIamIronMan ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); 
 
using namespace std;
 
typedef long long int lli; 
	int main(){
     AndIamIronMan;
      int i,j;
      cin>>i>>j;
      cout<<i*j;
    return 0;
}    

Measured memory_bytes: 3640
# include <iostream>
using namespace std;
int main(){
  string str;
  string a[7]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
  cin >> str;
  for (int i;i<7;i++){
    if (str==a[i]){
      int b=7-i;
      cout << b ;
    }
  }
  return 0;
}
  


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc126/tasks/abc126_c

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

class UnionFind {
  public:
    vector<int> data;
    UnionFind(size_t size) : data(size, -1) {}
    bool connect(size_t x, size_t y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x])
                swap(x, y);
            data[x] += data[y];
            data[y] = (int)x;
        }
        return x != y;
    }
    inline bool same(size_t x, size_t y) { return root(x) == root(y); }
    inline size_t root(size_t x) {
        return (size_t)(data[x] < 0 ? x : data[x] = root(data[x]));
    }
    inline int size(size_t x) { return -data[root(x)]; }
};

// X, Yのグループが何個あるか調べればいい
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    UnionFind tree(n);
    set<int> st;
    int k = n;

    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        k -= tree.connect(--x, --y);
    }
    cout << k << endl;

    return 0;
}

Measured memory_bytes: 640
x, y = map(int, input().split())
n, m = 0, 0
for i in range(x+1):
    j = (x - i)/2
    if 2*i + j== y:
        n, m = int(i+j), int(i)
        
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result

if n == 0 and m == 0:
    a = 0
else:
    a = cmb(n,m)%(10**9+7)
    
print(a)

Measured memory_bytes: 44148
#include<cstdio>
#include<iomanip>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#define R register
#define EN std::puts("")
#define LL long long
int main(){
	std::string s;
	std::cin>>s;
	if(s=="SUN") std::putchar('7');
	else if(s=="MON") std::putchar('6');
	else if(s=="TUE") std::putchar('5');
	else if(s=="WED") std::putchar('4');
	else if(s=="THU") std::putchar('3');
	else if(s=="FRI") std::putchar('2');
	else if(s=="SAT") std::putchar('1');
	return 0;
}


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

int main() {
  int h,w;
  cin >>h>>w;
  vector<vector<char>>a(h+2,vector<char>(w+2));
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      cin>>a[i][j];
    }
  }
  vector<vector<int>>kotae(h+2,vector<int>(w+2));
  for(int i=0;i<h+2;i++){
    for(int j=0;j<w+2;j++){
      kotae[i][j]=0;
    }
  }
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      int count=0;
      int tmp=kotae[i][j];
      if(a[i-1][j-1]=='#')count++;
      if(a[i][j-1]=='#')count++;
      if(a[i-1][j]=='#')count++;
      if(a[i+1][j+1]=='#')count++;
      if(a[i][j+1]=='#')count++;
      if(a[i+1][j]=='#')count++;
      if(a[i-1][j+1]=='#')count++;
      if(a[i+1][j-1]=='#')count++;
      kotae[i][j]=tmp+count;
    }
  }
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      if(a[i][j]=='#')cout<<a[i][j];
      else cout<<kotae[i][j];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    static int[][] dir2 = new int[][] {  { 0, 1 }, { 1, 0 } };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        char[][] a = new char[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = sc.next().toCharArray();
        }
        boolean[][] used = new boolean[h][w];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(0);
        used[0][0] = true;
        while(!q.isEmpty()){
            int nex = q.poll();
            int ch = nex/10;
            int cw = nex%10;
            for(int[] d : dir2){
                int nh = ch + d[0];
                int nw = cw + d[1];
                if(h <= nh || w <= nw)continue;
                if(used[nh][nw] || a[nh][nw] == '.')continue;
                used[nh][nw] = true;
                q.add(10*nh + nw);
                break;
            }
        }
        boolean ans = true;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(a[i][j] == '#' && !used[i][j]){
                    ans = false;
                    break;
                }
            }
        }
        System.out.println(ans ? "Possible" : "Impossible");
        sc.close();

    }

}


Measured memory_bytes: 22996
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
string S;
vector<vector<int>> v(26);
int A[26] = {0},id[26] = {0};

ll merge_count(vector<ll> &a){
	int n = a.size();
	if(n<=1) return 0;
	ll cnt = 0;
	vector<ll> b(a.begin(),a.begin() + n/2);
	vector<ll> c(a.begin() + n/2, a.end());
	cnt += merge_count(b);
	cnt += merge_count(c);
	int ai = 0,bi = 0,ci = 0;
	while(ai<n){
		if(bi<b.size() && (ci == c.size() || b[bi] <= c[ci])){
			a[ai++] = b[bi++];
		}else{
			cnt += n/2 - bi;
			a[ai++] = c[ci++];
		}
	}
	return cnt;
}


int main(){
	cin >> S;
	int N = S.size();
	for(int i=0;i<N;i++){
		int t = S[i]-'a';
		A[t]++;
		v[t].push_back(-1);
	}
	int count = 0;
	for(int i=0;i<26;i++){
		if(A[i]%2==1) count++;
	}
	if(count>=2){
		cout << -1 << endl;
		return 0;
	}
	vector<ll> L,R;
	int l = 0;
	for(int i=0;i<N;i++){
		int c = S[i]-'a';
		if(A[c]%2==1 && 2*id[c]+1==v[c].size()){
			L.push_back(N/2);
			id[c]++;
		}
		else{
			if(id[c]*2<v[c].size()){
				L.push_back(l);
				v[c][id[c]] = l;
				l++;
				id[c]++;
			}else{
				int t = v[c].size()-id[c]-1;
				L.push_back(N-v[c][t]-1);
				id[c]++;
			}
		}
	}
/*	l = 0;
	for(int i=0;i<26;i++) id[i] = 0;
	for(int i=0;i<N;i++){
		int c = T[i]-'a';
		if(A[c]%2==1&& 2*id[c]+1==v[c].size()){
			R.push_back(N/2);
			id[c]++;
		}
		else{
			if(id[c]*2<v[c].size()){
				R.push_back(l);
				v[c][id[c]] = l;
				l++;
				id[c]++;
			}else{
				int t = v[c].size()-id[c]-1;
				R.push_back(N-v[c][t]-1);
				id[c]++;
			}
		}
	}
	cout << min(merge_count(L),merge_count(R)) << endl;*/
	cout << merge_count(L) << endl;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	ll n,k;
	cin >> n >> k;

	ll a[n];
	rep(i,n) cin >> a[i];

	vector<ll> ps(200001,0);

	rep(i,n){
		ps[a[i]]++;
	}

	sort(ps.begin(),ps.end());

	// count num of kinds
	ll cnt = 0;
	rrep(i,200001){
		if(ps[i]> 0) cnt++;
	}

	if(cnt <= k) {
		cout << 0 << endl;	
		return 0;
	}

	ll ans = 0;
	ll dif = cnt - k;
	rep(i,200001){
		if(dif > 0 && ps[i] > 0){
			ans += ps[i];
			dif--; 
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 3328
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<bits/stdc++.h>
using namespace std;

int main(){
    int k;
    cin>>k;
    if(k%2==0 || k%5==0){
        cout<<-1<<"\n";
    }
    else{
        int rem= 7%k, ans= 1;
        while(rem!= 0){
            rem*=10;
            rem+=7;
            rem%= k;
            ans++;
        }
        cout<<ans<<"\n";
    }
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define For(i,a,b) for(int (i)=(a); (i)<(b); (i)++)

int main() {
    int n;
    cin >> n;
    vector<int> v;
    REP(i,n) {
        int j;
        cin >> j;
        v.push_back(j);
    }
    reverse(v.begin(), v.end());
    REP(i,n-1) {
        cout << v[i] << " ";
    }
    cout << v[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1216
origin_time = []
wait_time = []
dead_time = []
for i in range(5):
    origin = int(input())
    origin_time.append(origin)
    wait = int((origin + 9)/10) * 10
    wait_time.append(wait)
    dead = wait - origin
    dead_time.append(dead)

print(str(sum(wait_time)-max(dead_time)))

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int p = sc.nextInt();
        sc.close();

        int ans = (3 * a + p) / 2;
        System.out.println(ans);
    }

}


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

using namespace std;
using ll =long long;
using db = double;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;

//ここから書き始める

int main()
{
	cout << setprecision(10);

//	ll n;cin >> n;
//	vector<ll> V(n);
//	rep(i,n) cin >> V[i];
	int n;
	cin >> n;
	int k = (n +1)/2;
	cout << k - 1 << endl;

		
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int a, b, k;
  int i, n;
  int ary[100];
  
  scanf("%d%d%d", &a, &b, &k);
  for (i = 1, n = 0; i <= a && i <= b; i++) {
    if (a % i  == 0 && b % i == 0) {
      ary[n] = i;
      n++;
    }
  }
  printf("%d\n", ary[n - k]);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int lcm(int n,int m){
  return n==m?n:lcm(min(n,m),abs(n-m));
}
int ans(int n,int m){
  int a=n;
  for (int i=1;i<m;i++){
    a--;
    while(n%a!=0){
      a--;
    }
  }
  return a;
}
int main(){
  int A,B,K;
  cin >> A >> B >> K;
  cout << ans(lcm(A,B),K) << endl;
}


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

int main(){
	int a , b , c,d;
	cin >> a >> b >> c;

	a = a*100;
	b = b*10;

	d = a+b+c;
	if(d%4 == 0)cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
n=int(input())
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
cc=list(map(int,input().split()))

ans=0
for i in range(n):
  ans+=bb[aa[i]-1]
  if i>0 and (aa[i]-1)==aa[i-1]:
    ans+=cc[aa[i-1]-1]
    
print(ans)

Measured memory_bytes: 9140
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;
using ll  = long long;
template <typename T> T In() {
    T t;
    cin >> t;
    return t;
}
template <typename T> vector<vector<T>> Vec2(int i, int j, T ini = 0) {
    vector<vector<T>> vec(i, vector<T>(i, ini));
    return move(vec);
}
template <typename T> vector<vector<vector<T>>> Vec3(int i, int j, int k, T ini = 0) {
    vector<vector<vector<T>>> vec(i, vector<vector<T>>(j, vector<T>(k, ini)));
    return move(vec);
}


int main() {
    string S = In<string>();
    int N = S.length();
    vector<int> vec(N, 1);
    for(int i = 0; i < N; i++) {
        if(S[i] == 'R' && S[i+1] == 'R'){
            vec[i + 2] += vec[i];
            vec[i] = 0;
        }
    }
    for(int i = N-1; i >= 0; i--) {
        if(S[i] == 'L' && S[i - 1] == 'L') {
            vec[i - 2] += vec[i];
            vec[i] = 0;
        }
    }
    for(int v : vec)
        cout << v << " ";
    cout << endl;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    cout<<n*800-n/15*200<<endl;
    return 0;
}


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

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

  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  
  int i = 0; 
  for (int total = 0; total < n; total++) {
    if (a[i] == 2) {
      total++;
      cout << total << endl;
      return 0;
    }
      
    if (a[i] != i + 1) {
      i = a[i] - 1;
    } else {
      break;
    }
  }

  cout << -1 << endl;
}


Measured memory_bytes: 640
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	static PrintWriter out;
	static InputReader ir;

	static void solve() {
		char[] s=ir.next().toCharArray();
		int i;
		for(i=0;i<s.length;i++)
			if(s[i]=='A')
				break;
		int j;
		for(j=s.length-1;;j--)
			if(s[j]=='Z')
				break;
		out.println(j-i+1);
	}

	public static void main(String[] args) throws Exception {
		ir = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static class InputReader {

		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;

		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}

		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}

		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}

		public boolean hasNext() {
			skip();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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

	
	int N, M;
	cin >> N >> M;
	int A[701][701] = {};
	rep(i, M) {
		int a, b;
		cin >> a >> b;
		A[a][b] = 1;
		A[b][a] = 1;
	}
	vector<int> E[701];
	rep1(i, N) rep1(j, N) {
		if (A[i][j] == 0 && i != j) E[i].pb(j);
	}

	vector<pair<int, int>> V;




	int dame = 0;
	int tukatta[701] = {};

	rep1(q, N) {
		if (tukatta[q] == 0) {
			tukatta[q] = 1;
			int X = 1;
			int XX[701] = {};
			rep1(i, N) XX[i] = 1;
			int Y = 0;
			int YY[701] = {};
			rep1(i, N) YY[i] = 1;
			rep1(i, N) XX[i] &= A[q][i];

			vector<pair<int, int>> que;
			que.pb(mp(q, 0));
			while (que.size()) {
				vector<pair<int, int>> que2;
				for (auto p : que) {
					int i = p.first;
					for(int j : E[i]) {
						if (tukatta[j] == 0) {
							tukatta[j] = 1;
							que2.pb(mp(j, p.second ^ 1));
							if (p.second == 0) {
								if (YY[j] == 0) dame = 1;
								Y++;
								rep1(k, N) YY[k] &= A[j][k];
							}
							else {
								if (XX[j] == 0) dame = 1;
								X++;
								rep1(k, N) XX[k] &= A[j][k];
							}
						}
					}
				}
				que = que2;
			}
			V.pb(mp(X, Y));

			cesp(X);
			ce(Y);
		}
	}

	set<int> dp;
	dp.insert(0);
	for (auto p : V) {
		set<int> dp2;
		for (int i : dp) {
			dp2.insert(i + p.first);
			dp2.insert(i + p.second);
		}
		dp = dp2;
	}


	if (dame) {
		co(-1);
	}
	else {
		int saishou = 1e9;
		for (auto i : dp) {
			saishou = min(saishou, abs(N - 2 * i));
		}
		int X = (N + saishou) / 2;
		int Y = (N - saishou) / 2;
		int kotae = X * (X - 1) / 2 + Y * (Y - 1) / 2;
		co(kotae);
	}

	Would you please return 0;
}

Measured memory_bytes: 4992
using System;

namespace ChokudaiScanner
{
    class MainClass
    {
        static void Main()
        {
            Scanner cin = new Scanner();

            int N = cin.NextInt();
            int[] a = cin.ArrayInt(N);
            int A = 0;
            int B = 0;
            int C = 1;
            Array.Sort(a);
            Array.Reverse(a);
            for(int i = 0; i < a.Length; i++)
            {
                if (C % 2 == 0)
                {
                    B += a[i];
                    C++;
                }
                else
                {
                    A += a[i];
                    C++;
                }
            }
            Console.WriteLine(A - B);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string Next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return Next();
            i = 0;
            return s[i++];
        }

        public string[] ArrayNext(int N)
        {
            string[] Array = new string[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Next();
            }
            return Array;
        }

        public int NextInt()
        {
            return int.Parse(Next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextInt() + add;
            }
            return Array;
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextLong() + add;
            }
            return Array;
        }

        public double NextDouble()
        {
            return double.Parse(Next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = NextDouble() + add;
            }
            return Array;
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <math.h>
using namespace std;
 
const int MAX_N=100;
long long int n,a[MAX_N]={};
 
long long gcd(long long a,long long b){
	if(b==0) return a;
	else return gcd(b, a%b);
}

long long lcm(long long a,long long b){
	return (a/gcd(a,b))*b;
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	sort(a,a+n);
	long long b=a[n-1];
	for(int i=0;i<n;i++){
		b=lcm(a[n-1-i],b);
	}
	cout << b << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

#define vi vector<int>
#define vl vector<long long>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPD(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORD(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define INF 1e18
#define INFTY 1e9
#define MOD 1e9+7
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

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

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

struct edge {int to, cost;};
vector< vector<edge> > es;
const int MAX_N = 10010;

int main() {
    int N;
    cin >> N;
    vi x(N);
    vi y(N);

    REP(i, N) {
        cin >> x[i] >> y[i];
    }

    double res = 0;
    vi v(N);
    REP(i, N) v[i] = i;

    do {
        double ret = 0;
        REP(i, N-1) {
            ret += sqrt(pow(x[v[i+1]]-x[v[i]], 2)+pow(y[v[i+1]]-y[v[i]], 2));
        }
        res += ret;
    } while (next_permutation(v.begin(), v.end()));
    int perm = 1;
    FOR(i, 1, N+1) {
        perm *= i;
    }
    res /= perm;
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
int main(){
  int W,H,x,y,r;
  std::cin >> W >> H >> x >> y >> r;
  if(y+r>H || x+r>W || y-r<0 || x-r<0){
    std::cout << "No" << std::endl;
  } else {
    std::cout << "Yes" << std::endl;
  }
}



Measured memory_bytes: 3108
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

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

    vector<int> W(N);
    for(int i = 0; i < N; i++) {
        cin >> W[i];
    }

    int min_abs = 100000;
    for(int T = 0; T < N; T++) {
        int s1 = 0;
        int s2 = 0;
        for(int i = 0; i < N; i++) {
            if(i < T) {
                s1 += W[i];
            } else {
                s2 += W[i];
            }
        }
        int num = abs(s1 - s2);
        if(num < min_abs) {
            min_abs = num;
        }
    }
    cout << min_abs << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import math

def f(b, n):
    return n if (n < b) else f(b, n // b) + n % b

n = int(input())
s = int(input())

ans = -1
if n == s:
    ans = n + 1
else:
    for b in range(2, math.floor(n ** 0.5) + 1):
        if f(b, n) == s:
            ans = b
            break
    else:
        for p in range(1, math.ceil(n ** 0.5)):
            if (n - s) % p != 0:
                continue
            b = (n - s) // p + 1
            if math.floor(n ** 0.5) < b <= n and f(b, n) == s:
                ans = b
print(ans)


Measured memory_bytes: 3188
def ARC059D():
    s = input()

    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            print(i + 1, i + 2)
            return 0

    for i in range(len(s) - 2):
        if s[i] == s[i + 2]:
            print(i + 1, i + 3)
            return 0

    print(-1, -1)
ARC059D()

Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>

int max(int,int);
int lc(char *,char *);

int main(){
  int q,l;
  char x[1001];
  char y[1001];

  scanf("%d",&q);
  while(q>0){
    scanf("%s",x);
    scanf("%s",y);

    printf("%d\n",lc(x,y));
    q--;
  }
  return 0;
}


int max(int a,int b){
  if(a<b) return b;
  else return a;
}

int lc(char *x,char *y){

  int i,j,xl,yl;
  int d[1001][1001];

  xl=strlen(x);
  yl=strlen(y);
  for(i=0;i<=xl;i++) d[i][0]=0;
  for(j=0;j<=yl;j++) d[0][j]=0;
  for(i=0;i<xl;i++){
    for(j=0;j<yl;j++){
      if(x[i]==y[j]) d[i+1][j+1]=d[i][j]+1;
      else d[i+1][j+1]=max(d[i+1][j],d[i][j+1]);
    }
  }
  return d[xl][yl];
}



Measured memory_bytes: 5648
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}

const ll MX=1000000000000000000LL;

inline ll cnt(ll a){return a-a/3-a/5+a/15;}

inline ll nagasa(ll a){
  ll ret=a/3*4+a/5*4;
  ret+=19*cnt(a);
  for(ll i=10;;i*=10){
    ret-=cnt(min(i-1,a));
    if(i==MX){break;}
  }
  return ret;
}


int main(){
  ll idx;
  cin>>idx;
  idx--;
  ll l=0,r=idx+1;
  while(r-l>1){
    ll m=(l+r)>>1;
    if(nagasa(m)>=idx){r=m;}
    else{l=m;}
  }
  string ans;
  for(ll i=l+1;i<l+100;i++){
    if(i%3==0){
      ans+="Fizz";
    }
    if(i%5==0){
      ans+="Buzz";
    }
    if(i%3!=0 && i%5!=0){
      ans+=to_string(i);
    }
  }
  ll z=nagasa(l);
  for(int i=0;i<20;i++){
    cout<<ans[idx+i-z];
  }
  cout<<endl;
  
  return 0;
}



Measured memory_bytes: 3264
#include <iostream>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
int main()
{
   long long a,b;
   cin>>a>>b;
   if((a<0&&b>0)||(a==0)||(b==0))cout<<"Zero"<<endl;
   else if(((b-a+1)%2==0)||(a>0&&b>0)) cout<<"Positive"<<endl;
   else cout<<"Negative"<<endl;
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;

ll cnt;
ll cnt2;
bool go(ll x) {
	vector<ll> v;
	while (x > 0) {
		v.push_back(x % (ll)10);
		x /= (ll)10;
	}
	cnt = 1;
	cnt2 = 1;
	for (int i = 1; i < v.size(); i++) {
		if (abs(v[i] - v[i - 1]) > 1) {
			if (v[i] > v[i - 1]) {
				cnt = (v[i] - v[i - 1] - 1) * cnt;
			}
			else {
				cnt = (ll)(10 - v[i - 1]) * cnt;
			}
			return false;
		}
		cnt2 *= (ll)10;
		cnt *= (ll)10;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int k; cin >> k;
	ll x = 1;
	while (1) {
		if (go(x)) {
			k -= 1;
			if (k == 0) {
				cout << x << '\n'; return 0;
			}
			x += 1;
		}
		else {
			x = x + cnt;
			if (cnt2 > 0) {
				x = x - (x % cnt2);
			}
		}
	}



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
ll dp[10010], dpn[10010];
int main() {
	int N, ns;
	cin >> N;
	string S;
	cin >> S;
	ns = S.size();

	dp[ns] = 1;
	for (int i = N;i > 1;i--) {
		for (int j = max(0, ns - (N - i));j <= ns + (N - i);j++) {
			dpn[max(j - 1, 0)] += dp[j];
			dpn[j + 1] += dp[j] * 2;
		}
		for (int j = max(0, ns - (N - i) - 1);j <= ns + (N - i) + 1;j++) {
			dp[j] = dpn[j] % MOD;
			dpn[j] = 0;
		}
	}
	cout << (dp[0] + dp[1]) % MOD << endl;
}

Measured memory_bytes: 512
# import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    b = list(map(int,ipti().split()))

    res = [0] * n

    for i in range(1, n + 1):
        for j in range(n - i, -1, -1):
            if b[j] == j + 1:
                res[n-i] = b.pop(j)
                break
        else:
            print(-1)
            sys.exit()

    for i in range(n):
        print(res[i])




if __name__ == '__main__':
    main()

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 1e5 + 10;

vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code

llt dp[N];
ll arr[N];
int a, b;
llt findans(int n)
{
  if(n == 1) return 0;
  if(dp[n] != -1) return dp[n];
  llt zz = findans(n-1) + (arr[n] - arr[n-1])*a;
  llt xx = findans(n-1) + b;
  return dp[n] = min(xx, zz);
}

int main()
{
  int n;
  cin>>n>>a>>b;
  repn(i, 1, n)
  {
    cin>>arr[i];
    dp[i] = -1;
  }
  dp[1] = 0;
  cout<<findans(n)<<endl;
  return 0;
}


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

string S;

int main() {
    cin >> S;
    // S = "1905";
    // char p1 = S[0];
    // char p2 = S[1];
    // cout << stoi("01") << endl;
    // cout << S.substr(0, 2) << endl;
    // cout << S.substr(2, 2) << endl;

    int p1 = stoi(S.substr(0, 2));
    int p2 = stoi(S.substr(2, 2));

    if (1 <= p1 && p1 <= 12) {
        if (1 <= p2 && p2 <= 12) {
            printf("AMBIGUOUS\n");
        } else {
            printf("MMYY\n");
        }
    } else {
        if (1 <= p2 && p2 <= 12) {
            printf("YYMM\n");
        } else {
            printf("NA\n");
        }
    }
    
    // cout << S[0] + S[1] << endl;
}

Measured memory_bytes: 256
/*
* @Author: wxyww
* @Date: 2020-04-01 11:25:14
* @Last Modified time: 2020-04-01 11:49:33
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
vector<int>t[N];
queue<int>q;
int V[N],U[N];
vector<int>::iterator it;
struct node {
	int v,nxt,w;
}e[N << 1];
int head[N],ejs = 1,cur[N];
void add(int u,int v,int w) {
	e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
	e[++ejs].v = u;e[ejs].nxt = head[v];head[v] = ejs;e[ejs].w = 0;
}
int dep[N],S,T;
int bfs() {
	q.push(S);
	memset(dep,0,sizeof(dep));
	dep[S] = 1;
	while(!q.empty()) {
		int u = q.front();q.pop();
		for(int i = head[u];i;i = e[i].nxt) {
			int v = e[i].v;
			if(!dep[v] && e[i].w) {
				dep[v] = dep[u] + 1;
				q.push(v);
			}
		}
	}
	return dep[T];
}
int dfs(int u,int now) {
	if(u == T) return now;
	int ret = 0;
	for(int &i = cur[u];i;i = e[i].nxt) {
		int v = e[i].v;
		if(dep[v] == dep[u] + 1 && e[i].w) {
			int k = dfs(v,min(now - ret,e[i].w));
			e[i].w -= k;
			e[i ^ 1].w += k;
			ret += k;
			if(ret == now) return ret;
		}
	}
	return ret;
}
int dinic() {
	int ret = 0;
	while(bfs()) {
	// puts("!!!!");
		memcpy(cur,head,sizeof(cur));
		ret += dfs(S,10000000);
	}
	return ret;
}
int flag[N];
int main() {
	int n = read();
	S = 1,T = n + n;
	for(int i = 2;i <= n;++i)
		add(S,i,1);
	for(int i = n + 1;i < n + n;++i)
		add(i,T,1);
	for(int i = 2;i <= n;++i) {
		int tot = read();
		for(int j = 1;j <= tot;++j) {
			int x = read();
			t[x].push_back(i);
			if(x == 1) continue;
			add(i,x + n - 1,1);
		}
	}

	if(dinic() != n - 1) {
		puts("-1");return 0;
	}


	for(int u = 2;u <= n;++u)
		for(int i = head[u];i;i = e[i].nxt)
			if(!e[i].w)
				V[u] = e[i].v - n + 1;

	// for(int i = 2;i <= n;++i) printf("%d ",V[i]);
	// puts("");

	q.push(S);

	while(!q.empty()) {
		int u = q.front();q.pop();
		for(int i = head[u];i;i = e[i].nxt) {
			for(it = t[u].begin();it != t[u].end();++it) {
				if(flag[*it]) continue;
				flag[*it] = 1;
				U[*it] = u;
				q.push(V[*it]);
			}
		}
	}
	for(int i = 2;i <= n;++i) {
		if(!U[i]) {
			puts("-1");return 0;
		}
	}
	for(int i = 2;i <= n;++i) {
		printf("%d %d\n",U[i],V[i]);
	}

	return 0;
}

Measured memory_bytes: 61824
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>

using namespace std;
int main() {
	string s;
    cin>>s;
    if(s[5]=='0'&&(s[6]=='4'||s[6]=='3'||s[6]=='2'||s[6]=='1'))
        cout<<"Heisei"<<endl;
    else
        cout<<"TBD"<<endl;
}


Measured memory_bytes: 256