akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int m = Integer.parseInt(in.next());
            int x = Integer.parseInt(in.next());
            int y = Integer.parseInt(in.next());
            int xn[] = new int[n];
            int ym[] = new int[m];
            for (int i = 0; i < n; i++) {
                xn[i] = Integer.parseInt(in.next());
            }
            for (int i = 0; i < m; i++) {
                ym[i] = Integer.parseInt(in.next());
            }

            Arrays.sort(xn);
            Arrays.sort(ym);

            int x1, y1;

            x1 = Math.max(x, xn[n - 1]);
            y1 = Math.min(y, ym[0]);

            out.println(y1 - x1 > 0 ? "No War" : "War");

        }

    }
}



Measured memory_bytes: 23764
from sys import exit

N = int(input())
A = list(int(x) for x in input().split())

break_count = 0

for key, a in enumerate(A, 1):
    if not a == key - break_count:
        break_count += 1

if break_count == N:
    print(-1)

else:
    print(break_count)


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

int judgenum(int n){
  if(n == 1){
    n = 6000;
  }else if(n == 2){
    n = 4000;
  }else if(n == 3){
    n = 3000;
  }else if(n == 4){
    n = 2000;
  }
  return n;
}


int main(){

  int t1,n1,t2,n2,t3,n3,t4,n4;
  cin >> t1 >> n1;
  cin >> t2 >> n2;
  cin >> t3 >> n3;
  cin >> t4 >> n4;

  t1 = judgenum(t1);
  t2 = judgenum(t2);
  t3 = judgenum(t3);
  t4 = judgenum(t4);

  cout << t1*n1 << endl;
  cout << t2*n2 << endl;
  cout << t3*n3 << endl;
  cout << t4*n4 << endl;

  return 0;
}

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

int main() {
	string S;
	cin >> S;

	int Q = count(S.begin(), S.end(), '0');
	int W = count(S.begin(), S.end(), '1');
	int E = min(Q, W);

	cout << E * 2 << endl;
}

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

using namespace std;

#define ii pair<int,int>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vii vector<ii>
#define all(X) (X).begin(),(X).end()
#define xx first
#define yy second
#define FOR(i,l,r) for( int i = l-(l>r); i != r-(l>r); i += 1-2*(l>r) )

int main() {
    int n,q; cin>>n>>q;
    vector<pair<int,ii>> v;
    FOR(i,0,n) {
        int s,t,x; cin>>s>>t>>x;
        v.pb({x,{s-x,t-1-x}});
    }
    sort(all(v));
    set<ii> s;
    FOR(i,0,q) {
        int u; cin>>u;
        s.insert({u,i});
    }
    int ans[q];
    memset(ans,-1,sizeof(ans));
    for( auto e : v ) {
        if( !s.size() ) break;
        auto i1 = s.lb({e.yy.xx,-1});
        auto i2 = s.ub({e.yy.yy,n+5});
        auto i = i1;
        vii temp;
        while( i != i2 ) {
            temp.pb(*i);
            i++;
        } 
        for( auto ee : temp ) {
            s.erase(ee);
            ans[ee.yy] = e.xx;
        }
    }
    for( auto e : ans ) cout<<e<<"\n";
    return 0;
}

Measured memory_bytes: 16112
//Princess's Gamble
#include<bits/stdc++.h>
using namespace std;

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

int main(){
  while(true){
    int N, M, P;
    cin>>N>>M>>P;
    if(N==0 && M==0 && P==0)break;
    int sum=0, winner;
    rep(i,N){
      int tmp;
      cin>>tmp;
      sum+=tmp;
      if(i+1==M)winner=tmp;
    }
    if(winner==0)cout<<"0"<<endl;
    else cout<<(int)((double)(sum*(100-P))/(double)(winner))<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
void find_longest_dist(vector<ll> g[],ll s,vector<ll> &v,vector<ll> &ind,vector<ll> &dp){
    queue<ll> q;
    q.push(s);
    v[s] = 1;
    while(!q.empty()){
        ll vertex = q.front();
        for(ll i=0;i<g[vertex].size();i++){
            ind[g[vertex][i]]--;
            dp[g[vertex][i]] = max(dp[g[vertex][i]],dp[vertex] + 1);
            if(!ind[g[vertex][i]] && !v[g[vertex][i]]){
                v[g[vertex][i]] = 1;
                q.push(g[vertex][i]);
            }
        }
        q.pop();
    }
}
int main() {
    ll n,m,x,y,ans = 0;
    cin>>n>>m;
    vector<ll> g[n+1],dp(n+1,0),v(n+1,0),ind(n+1,0);
    /*
    State: 
    dp[i]: Denotes the longest directed path ending at vertex i
    Recurence:
    dp[i] = max(dp[i],dp[j]+1) for all j, where j is the set of all incoming vertices to i,
    i.e vertices for which head of an edge is in j and tail is in i.
    */
    for(ll i=0;i<m;i++){
        cin>>x>>y;
        g[x].pb(y);
        ind[y]++;    
    }
    for(ll i=1;i<=n;i++){
        if(!v[i] && !ind[i])
            find_longest_dist(g,i,v,ind,dp);
    }
    for(ll i=1;i<=n;i++)
        ans = max(ans,dp[i]);
    cout<<ans;	
	return 0;
}


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

int main() {
  vector<int> N(3);
  for(int i = 0; i < 3; i++){
      cin >> N.at(i);
  }
  sort(N.begin(), N.end());
if(N.at(0)+N.at(1) == N.at(2)){
    cout << "Yes" << endl;
}
else {
    cout << "No" << endl;
}

}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
  int n, v1, v2;
  cin >> n;
  vector<int> hist1(100003, 0);
  vector<int> hist2(100003, 0);
  for(int i = 0; i < n / 2; ++i)
  {
    cin >> v1 >> v2;
    hist1[v1]++;
    hist2[v2]++;
  }

  vector<P> h1{ P(0, -1) };
  vector<P> h2{ P(0, -1) };
  for(int i = 0; i < (int)hist1.size(); ++i)
  {
    if (hist1[i] > 0) h1.emplace_back( P(hist1[i], i) );
  }
  for(int i = 0; i < (int)hist2.size(); ++i)
  {
    if (hist2[i] > 0) h2.emplace_back( P(hist2[i], i) );
  }
  sort(h1.rbegin(), h1.rend());
  sort(h2.rbegin(), h2.rend());

  ll ans = 0;
  int i1 = 0, i2 = 0;
  if (h1[0].second == h2[0].second)
  {
    if (h1[0].first == h2[0].first)
    {
      h1[1] > h2[1] ? i1++ : i2++;
    }
    else
    {
      h1[0] < h2[0] ? i1++ : i2++;
    }
  }
  ans = n - h1[i1].first - h2[i2].first;
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 4976
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> pos;
const ll N = 100010, MOD = 1000000007;
int n, m,dp[N];
string s;
deque<pos> dq;

bool comp(pos v1,pos v2) {
	if (v1.first > v2.first)return true;
	if (v1.first < v2.first)return false;
	if (v1.second < v2.second)return true;
	return false;
}

int main() {
	cin >> n >> m >> s;
	reverse(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '1')continue;
		if (i != 0) {
			while (!dq.empty() && i - dq.front().second > m)dq.pop_front();
			if (dq.empty()) 
			{ cout << -1 << endl; return 0; }
			dp[i] = i - dq.front().second;
		}
		pos cv;
		if (i != 0)cv=mk(dq.front().first + 1, i);
		else cv=mk(1, i);
		while (!dq.empty() && comp( dq.back(), cv))dq.pop_back();
		dq.push_back(cv);
	}
	for (int i = s.size() - 1; i > 0;) {
		if (i != s.size() - 1)cout << ' ';
		cout << dp[i];
		i -= dp[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10**6)

n, u, v = map(int, input().split())
u, v = u-1, v-1
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append(bi)
    edges[bi].append(ai)

def dfs(already, node, depth):
    depth += 1
    children = edges[node]
    for child in children:
        if already[child] == 0:
            already[child] = depth
            already = dfs(already, child, depth)
    return already

already_u = [0 for i in range(n)]
already_u[u] = -1
already_u = dfs(already_u, u, 0)
already_u[u] = 0
already_v = [0 for i in range(n)]
already_v[v] = -1
already_v = dfs(already_v, v, 0)
already_v[v] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already_v[i]:
        maxi = max(maxi, already_v[i])
print(maxi-1)

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

using namespace std;

int main() {
    string s;
    cin >> s;

    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if (s[i] == '+') {
            ans++;
        } else {
            ans--;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long
int main() {
	string s, ref = "keyence";
	cin >> s;
	int i = 0;
	string sb;
	if (s.size() < ref.size())
		return printf("NO\n"), 0;

	int j = 0;
	if (ref[j] == s[i]) {
		int index = i;
		while (ref[j] == s[index] && j < (int) ref.size()) {
			j++;
			index++;
		}
		if (j == (int) ref.size())
			return printf("YES\n"), 0;

		sb = ref.substr(j);
		//cout << sb << endl;
		string tmp = s.substr(s.size() - sb.size());
		//cout << tmp << endl;
		if (tmp == sb)
			printf("YES\n");
		else
			printf("NO\n");

	}else
		printf("NO\n");

}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <list>
#include <math.h>
#include <algorithm>
#include <chrono>
#include <random>
#include <queue>
#include <fstream>
#include <iterator> // std::back_inserter
#include <chrono>
#include <string>
#include <stdio.h>
#include <iomanip>
#include <float.h>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    long long int N;

    cin >> N;

    long long int a[5];

    cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

    vector<long long int> time;

    for(int i=0; i<5; i++){
        time.push_back(a[i]);
    }

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

    cout << (N+time[0]-1)/time[0] + 4;
 
    return 0;
}

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

using namespace std;

template <class T>
class Edge
{
public:
	int u, v;
	T w;

	Edge(void) : u(0), v(0), w(0)
	{

	}

	Edge(const int & u, const int & v, const T & w) : u(u), v(v), w(w)
	{

	}
};

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

	int L;
	cin >> L;

	int N = 20;
	vector<Edge<int> > ans;
	for (int u = 1; u + 1 < N; u++)
	{
		ans.emplace_back(u, u + 1, 0);
		ans.emplace_back(u, u + 1, 1 << N - u - 2);
	}

	int R = 0;
	for (int k; L > 0; )
	{
		k = min(N - 3, 31 - __builtin_clz(L));
		ans.emplace_back(0, N - k - 1, R);
		L -= 1 << k;
		R += 1 << k;
	}

	cout << N << ' ' << ans.size() << '\n';
	for (const auto & e : ans)
		cout << e.u + 1 << ' ' << e.v + 1 << ' ' << e.w << '\n';

	return 0;
}


Measured memory_bytes: 3624
// g++ hello.cpp -o hello & hello
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define MP make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void test();

int main()
{
//freopen("input.in","r",stdin);freopen("output.in","w",stdout);
int t=1;
//   cin>>t;
for(int i=1;i<=t;i++)
{    
//	cout<<"Case #"<<i<<": ";
	test();
cout<<endl;
}
return 0;
}
void test() 
{ll n;
cin>>n;
//ll arr[n]={};
ll a1,a2,b1,b2,c1,c2;
cin>>a1>>b1>>c1;
for(int i=1;i<n;i++)
{cin>>a2>>b2>>c2;
ll a,b,c;
a=a2+max(b1,c1);
b=b2+max(a1,c1);
c=c2+max(b1,a1);
a1=a;b1=b;c1=c;
}
ll ans=max(a1,max(b1,c1));
cout<<ans;
}

Measured memory_bytes: 256
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = 0

while A[a] <= K:
    K -= A[a]
    a += 1
    if a == N:
        break
        
x = a
b = 0
while a>=0:
    if b < M:
        while B[b] <= K:
            K -= B[b]
            b += 1
            if b == M:
                break
    if a+b > x:
        x = a+b
    a -= 1
    K += A[a]

print(x)

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

int main(){
    string s;
    cin >> s;
    for(int i = 1; i < 3; i++){
        if(s[i] != s[i-1]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n;
  cin >> n;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];

  vector<ll> a(n, 0);
  ll ans = 0;

  rep(j, *max_element(h.begin(), h.end())) {
    bool is_bound = true;
    rep(i, n) {
      if (a[i] >= h[i]) {
        is_bound = true;
        continue;
      }
      a[i]++;
      if (is_bound == true) {
        is_bound = false;
        ans++;
      }
    }
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
        int i=0,j=0,k,n[1000],m[1000];

        scanf("%d",&k);
        for(i=0; i<k; i++)
            scanf("%d%d",&n[i],&m[i]);

        for(i=0; i<k; i++){
          j+=m[i]-n[i]+1;
        }
        printf("%d\n",j);
                return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100,V_I=1000;
int v[N+1],w[N+1],dp[2][N*V_I+1],Sum[N+1];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i],Sum[i]=Sum[i-1]+v[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++)for(int j=0;j<=Sum[i];j++){
		dp[i&1][j]=dp[i-1&1][j];
		if(j>=v[i])dp[i&1][j]=min(dp[i&1][j],dp[i-1&1][j-v[i]]+w[i]);
	}
	for(int i=Sum[n];;i--)if(dp[n&1][i]<=m)return cout<<i,0;
	return 0;
}
/*1
3 8
3 30
4 50
5 60
*/
/*2
1 1000000000
1000000000 10
*/
/*3
6 15
6 5
5 6
6 4
6 6
3 5
7 2
*/

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

N,K = map(int,input().split())
A = list(map(int,input().split()))

def is_divide(d):
    Rs = [a%d for a in A]
    Rs.sort()
    cumsum = [0] * (N + 1)
    for i in range(N - 1,-1,-1):
        cumsum[i] = cumsum[i + 1] + d - Rs[i]
    cum = 0
    for i in range(N):
        if max(cum,cumsum[i]) <= K:
            return True
        cum += Rs[i]
    return False

S = sum(A)
ans = 0
for i in range(1,S + 1):
    if i*i > S:
        break
    if S%i == 0:
        if is_divide(i):
            ans = max(ans,i)
        if is_divide(S//i):
            ans = max(ans,S//i)
print(ans)


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

int main(){
	int N;
	cin >> N;
	string S;
	cin >> S;
	string A = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";

	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j < 26; j++) {
			if (S.at(i) == A.at(j)) {
				cout << A.at(j + N%26);
			}
		}
	}
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int p[55];
int n;

int main() {
  cin >> n;

  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    if (p[i] != i) {
      cnt++;
    }
  }

  if (cnt == 0 || cnt == 2) {
    cout << "YES" << endl;
    return 0;
  }

  cout << "NO" << endl;
}


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

int main(){
  int n;
  cin >> n;
  int a[n] = {};
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a, a+n);
  int alice = 0, bob = 0;
  bool flag = false;
  for(int i = n-1; i >= 0; i--){
    if(!flag) alice += a[i];
    if(flag) bob += a[i];
    flag = !flag;
  }
  cout << alice - bob << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int N,i,j,c[10001],e[10001],m[7]={0,1,2,3,1,2,3},t,r;

int ch(int *x,int p)
{
	int lp=p,rp=p+1,cl,lt,rt;
	while(lp>=0)
	{
		cl=c[lp];
		for(lt=lp;c[lt]==cl;lt--);
		for(rt=rp;c[rt]==cl;rt++);
		if((lp-lt)+(rt-rp)<4)
			break;
			lp=lt,rp=rt;
	}
	return lp+(N-rp)+1;
}

int main()
{
	for(;scanf("%d",&N),N;)
	{
		memset(c,-1,sizeof(c));
		for(i=0;i<N;i++)
			scanf("%d",&c[i]);
		memcpy(e,c,sizeof(c));
		for(i=0,r=N;i<N;i++)
		{
			for(j=1;j<3;j++)
			{
				memcpy(c,e,sizeof(c));
				c[i]=m[c[i]+j];
				t=ch(c,i);
				r=r>t?t:r;
			}
		}
		printf("%d\n",r);
	}
	return 0;
}

Measured memory_bytes: 700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {  
  return b != 0 ? gcd(b, a % b) : a;
}//MAX
int lcm(int a, int b) { 
   return a * b / gcd(a, b);
   }
//MIN

 main() {
int n;
string s;
cin >> n >> s;
 if(s.size()%2==0){
   string r,l;
   for(int i=0;i<s.size()/2;i++){
     r+=s.at(i);
   }
   for(int j=s.size()/2;j<s.size();j++){
     l+=s.at(j);
   }
   if(r==l){
     cout <<"Yes"<<endl;
   }
   else{
     cout<<"No"<<endl;
   }
 }
 else{
   cout << "No"<<endl;
 }
 }


Measured memory_bytes: 256
N, X = map(int, input().split())
x = list(map(int, input().split()))

x = list(map(lambda x: abs(x - X), x))


def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

ans = x[0]
for i in x:
    ans = min(ans, gcd(i, ans))
print(ans)

Measured memory_bytes: 14224
import Control.Arrow
import Data.Bits
import Data.Char
import Data.List

main :: IO ()
main = do
  xs <- getInts
  k <- getInt
  print $ sum xs + maximum xs * (2 ^ k - 1)

getInt :: IO Int
getInt = readLn

getInts :: IO [Int]
getInts = map read . words <$> getLine


Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

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

  int l, r, d;
  cin >> l >> r >> d;
  cout << r / d - (l - 1) / d << "\n";
}


Measured memory_bytes: 3520
from pprint import pprint
n,w=map(int,input().split())
V=[]
W=[]
for _ in range(n):
    x,y=map(int,input().split())
    V.append(x)
    W.append(y)
dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if W[i]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-W[i]]+V[i],dp[i+1][j-W[i]]+V[i])
            
# pprint(dp)
print(dp[n][w])


Measured memory_bytes: 16568
#include <iostream>
int main() {
  int n,i,a=0;
  std::cin >> n;
  int d[101] = {};
  while(std::cin >> i)++d[i];
  for(i=0; i<sizeof(d)/sizeof(d[0]); ++i)(d[i]>0?++a:0);
  std::cout << a << "\n";
}
  

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

class Main{
	public static void main(String[] args) {
		int INF=1000000007;
		Scanner sc=new Scanner(System.in);
		int V=sc.nextInt();
		Vec[] v=new Vec[V+1];
		for(int i=0; i<=V; i++) {
			v[i]=new Vec();
		}
		for(int i=0; i<V-1; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			v[a].add(b);
			v[b].add(a);
		}
		int[] Fe=new int[V+1];
		int[] Su=new int[V+1];
		boolean[] Fe_V=new boolean[V+1];
		boolean[] Su_V=new boolean[V+1];
		Arrays.fill(Fe, INF);
		Arrays.fill(Su, INF);
		Fe[1]=0;
		Su[V]=0;
		Stack<Integer> Q=new Stack<Integer>();
		Q.add(1);
		while(!Q.isEmpty()) {
			int tmp=Q.pop();
			for(int i=0; i<v[tmp].size(); i++) {
				if(!Fe_V[v[tmp].get(i)] && Fe[tmp]+1<Fe[v[tmp].get(i)]) {
					Fe_V[v[tmp].get(i)]=true;
					Fe[v[tmp].get(i)]=Fe[tmp]+1;
					Q.push(v[tmp].get(i));
				}
			}
		}

		Q.add(V);
		while(!Q.isEmpty()) {
			int tmp=Q.pop();
			for(int i=0; i<v[tmp].size(); i++) {
				if(!Su_V[v[tmp].get(i)] && Su[tmp]+1<Su[v[tmp].get(i)]) {
					Su_V[v[tmp].get(i)]=true;
					Su[v[tmp].get(i)]=Su[tmp]+1;
					Q.push(v[tmp].get(i));
				}
			}
		}
		int Su_w=0;
		int Fe_w=0;
		for(int i=1; i<=V; i++) {
			if(Fe[i]<=Su[i]) {
				Fe_w++;
			}
			else {
				Su_w++;
			}
		}
		if(Su_w>=Fe_w) {
			System.out.println("Snuke");
			System.out.flush();
		}
		else {
			System.out.println("Fennec");
			System.out.flush();
		}
	}
	public static class Vec{
		ArrayList <Integer> rinsetu=new ArrayList<Integer>();
		public void add(int V) {
			rinsetu.add(V);
		}
		public void show() {
			for(int i=0; i<rinsetu.size(); i++) {
				System.out.println(rinsetu.get(i));
			}
		}
		public int get(int i) {
			return rinsetu.get(i);
		}
		public int size() {
			return rinsetu.size();
		}
		public int lowerBound(final int value) {
			int low = 0;
			int high = rinsetu.size();
			int mid;
			while (low < high) {
				mid = ((high - low) >>> 1) + low;
				if (rinsetu.get(mid) < value) {
					low = mid + 1;
				} else {
					high = mid;
				}
			}
			if(low<rinsetu.size()) {
				return low;
			}
			else {
				return -1;
			}
		}
	}
}

Measured memory_bytes: 104848
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;

int main() {
	vector<int>a(3);
	cin >> a.at(0) >> a.at(1) >> a.at(2);
	sort(a.begin(), a.end());
	cout << a.at(0) + a.at(1);
}

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

using namespace std;

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

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

double cross(P p,P q){
    return p.first*q.second-p.second*q.first;
}

double dot(P p,P q){
    return p.first*q.first+p.second*q.second;
}

double norm(P p){
    return sqrt(pow(p.first,2)+pow(p.second,2));
}

int ccw(P p0,P p1,P p2){
    p1.first -= p0.first;
    p1.second -= p0.second;
    p2.first -= p0.first;
    p2.second -= p0.second;

    if(cross(p1,p2) > 0) return 1; // counter_clockwise
    if(cross(p1,p2) < 0) return -1; // clockwise
    if(dot(p1,p2)<0) return 2 ;//on_line back
    if(norm(p1)<norm(p2)) return -2; //on_line front
    return 3; // on_segment
}

int main()
{
    P p0,p1;
    cin >> p0.first >> p0.second >> p1.first >> p1.second;
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        P p2;
        cin >> p2.first >> p2.second;
        int res = ccw(p0,p1,p2);
        string ans;
        if(res==1) ans = "COUNTER_CLOCKWISE";
        if(res==-1) ans = "CLOCKWISE";
        if(res==2) ans = "ONLINE_BACK";
        if(res==-2) ans = "ONLINE_FRONT";
        if(res==3) ans = "ON_SEGMENT";

        cout << ans << endl;
    }


    return 0;
}


Measured memory_bytes: 3292
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <queue>
#include <unordered_map>
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
ll pow(ll N, ll P){
    if(P==0) return 1;
    if(P%2==0){
        ll t = pow(N, P/2);
        return t*t;
    }
    return N * pow(N, P-1);
}
ll modpow(ll N, ll P,ll k){
    if(P==0) return 1;
    if(P%2==0){
        ll t = modpow(N, P/2,k)%k;
        return t*t%k;
    }
    return N * modpow(N, P-1,k)%k;
}
ll modkai(ll n,ll m,ll k){//n*(n-1)*(n-2)*...(m+1)%k
    if(n == m)return 1;
    return modkai(n-1,m,k)*n%k;
}
ll mod_cnb(ll n,ll m,ll k){//nCm%k,kは十分大きい素数
  int m_=modkai(m,0,k);
  return modkai(n,n-m,k)*modpow(m_,k-2,k)%k;
}
ll gcd(ll n,ll m){
    ll n_ = max(n,m);
    ll m_ = min(n,m);
    if(n_%m_ == 0)return m_;
    return gcd(m_,n_%m_);
}
ll lcm(ll n,ll m){
    return n*m/gcd(n,m);
}
int main(){
    ll x,y,a,b,c;cin>>x>>y>>a>>b>>c;
    vector<ll>p(a),q(b);
    priority_queue<ll> r;
    rep(i,a)cin>>p[i];
    rep(i,b)cin>>q[i];
    rep(i,c){
        ll v;cin>>v;
        r.push(v);
    }
    sort(p.begin(),p.end());
    sort(q.begin(),q.end());
    p.erase(p.begin(),p.begin()+a-x);
    q.erase(q.begin(),q.begin()+b-y);

   int pn,qn;
   pn=qn=0;
    while(!r.empty()){
        if((p[pn]>=r.top()||pn==x)&&(q[qn]>=r.top()||qn==y))break;
        if(p[pn]<r.top()&&(p[pn]<=q[qn]||qn==y)){
            p[pn]=r.top();
            r.pop();
            pn++;
        }
        else if(q[qn]<r.top()&&(p[pn]>q[qn]||pn==x)){
            q[qn]=r.top();
            r.pop();
            qn++;
        }

    }
ll ans=0;
rep(i,x)ans+=p[i];
rep(i,y)ans+=q[i];
cout<<ans<<endl;

}

Measured memory_bytes: 2936
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	int SB=0,EA=0,B=0;
	int sum = 0;
	REP(i,N){
		string S=in<string>();
		for(int j=0,ej=S.size()-1;j<ej;j++){
			if(S[j]=='A' && S[j+1]=='B') sum++;
		}
		if(S.front()=='B'){
			if(S.back()=='A') B++;
			else SB++;
		}
		else if(S.back()=='A') EA++;
	}

	if(B){
		if(EA+SB>0){
			sum += B+min(EA,SB);
		}
		else sum += B-1;
	}
	else sum += min(EA,SB);
	
	out(sum);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int X;
main()
{
	cin>>X;
	int ans=1;
	for(int i=2;i<=X;i++)
	{
		int t=i*i;
		while(t<=X)
		{
			if(ans<t)ans=t;
			t*=i;
		}
	}
	cout<<ans<<endl;
}


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

int main() {
    ll x;
    cin >> x;
    ll ans;
    if (x%11 == 0) {
        ans = x/11*2;
    }
    else if (x%11 <= 6) {
        ans = x/11*2 + 1;
    } else {
        ans = x/11*2 + 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/*    特徴    */

/*    教訓    */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld  = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-9; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

#define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; i++ )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define p_b push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

// -------- template end - //


// - library ------------- //



// --------- library end - //




int main(){

  ll a = il();
  ld B = stold(is());


  ll b = round(B * 100);


  cout << ( a * b ) / 100 << endl;



}


Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

lli dp[100];

int main(){
    // cout << fixed << setprecision(5);

    dp[0]=1000;
    lli n;
    cin>>n;
    vector<lli> a(n);
    REP(i,0,n)cin>>a[i];

    REP(i,0,n){
        REP(j,i+1,n){
            dp[j]=dp[i];
            lli money = dp[i];
            lli kabu = money/a[i];
            lli nowMoney = money%a[i]+kabu*a[j];
            chmax(dp[j],nowMoney);
        }
    }

    cout<<dp[n-1]<<endl;

    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ms(x, t) memset(x, t, sizeof(x))
#define ff first
#define ss second
#define all(ar) ar.begin(), ar.end()
#define rall(ar) ar.rbegin(), ar.rend()
#define endl "\n"
typedef pair<int, int> pll;
typedef pair<int, pll> plll;
typedef vector<int> vl;
typedef vector<vector<int>> vvl;
typedef vector<pll> vpll;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

const int limit = 1e5 + 1;
const int inf = 1e7;
const int mod = 1e17 + 7;

int modExpItr(int a, int b) {
  int ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b = b >> 1;
  }
  return ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int x;
  cin >> x;
  vl v;
  for (int i = 0; i < 1000; i++) {
    int n = pow(i, 5);
    v.push_back(n);
  }
  for (int i = 0; i < v.size(); i++) {
    for (int j = 0; j < v.size(); j++) {
      if (v[i] + v[j] == x) {
        cout << i << " " << -j << endl;
        return 0;
      } else if (v[i] - v[j] == x) {
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 4056
n,m = map(int,input().split())
L = []
R = []
for i in range(m):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
ansl = max(L)
ansr = min(R)
print(0 if ansl > ansr else ansr-ansl+1)

Measured memory_bytes: 10996
#include <stdio.h>
int gcdf(int vx,int vy)
{
 int temp;
 temp = (vy==0) ? vx : gcdf(vy,vx%vy);
 return temp;
}
int gcd(int vx,int vy)
{
  return (vx>=vy) ? gcdf(vx,vy) : gcdf(vy,vx);
}
int main(void)
{
  int x,y;
  while(scanf("%d %d",&x,&y) != EOF)
 {
  printf("%d",gcd(x,y));
  putchar('\n');
 }
return 0;
}
 

Measured memory_bytes: 600
use std::collections::*;
use std::io::*;
use std::*;
// template {{{
macro_rules! get {
    ($($t:tt),*; $n:expr) => {
        {
            let stdin = std::io::stdin();
            let ret = std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
                let line = line.unwrap();
                let mut it = line.split_whitespace();
                _get!(it; $($t),*)
            }).collect::<Vec<_>>();
            ret
        }
    };
    ($($t:tt),*) => {
        {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut it = line.split_whitespace();
            _get!(it; $($t),*)
        }
    };
}
macro_rules! _get {
    ($it:ident; [char]) => {
        _get!($it; String).chars().collect::<Vec<_>>()
    };
    ($it:ident; [u8]) => {
        _get!($it; String).bytes().collect::<Vec<_>>()
    };
    ($it:ident; usize1) => {
        $it.next().unwrap().parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
    };
    ($it:ident; [usize1]) => {
        $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
    };
    ($it:ident; [$t:ty]) => {
        $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
    };
    ($it:ident; $t:ty) => {
        $it.next().unwrap().parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
    };
    ($it:ident; $($t:tt),+) => {
        ($(_get!($it; $t)),*)
    };
}
// }}}

fn main() {
    let n = get!(usize);
    let c = get!([char]);
    let v: Vec<_> = c.iter().map(|c| if *c == 'W' { 1 } else { 0 }).collect();
    let v: Vec<_> = iter::once(&0)
        .chain(v.iter())
        .scan(0, |acc, &x| {
            *acc += x;
            Some(*acc)
        })
        .collect();
    let mut ans: i64 = 1 << 60;
    for i in 0..=n {
        let w = (v[i] - v[0]) as i64;
        let r = (n - i - (v[n] - v[i])) as i64;
        ans = ans.min(w.max(r));
    }
    println!("{}", ans);
}


Measured memory_bytes: 6180
N = int(input())
A = list(map(int, input().split()))
B = [1]*N
for i, ai in enumerate(reversed(A)):
  count = 0
  for j in range(N-i, N+1, N-i):
    count += B[j-1]
  if ai != count%2:
    B[N-1-i] = 0


M = sum(B)
l = [i+1 for i, bi in enumerate(B) if bi == 1]
print(M)
print(*l)

Measured memory_bytes: 14132
a = {}
a['11'],a['12'],a['13'] = gets.chomp.split(' ')
a['21'],a['22'],a['23'] = gets.chomp.split(' ')
a['31'],a['32'],a['33'] = gets.chomp.split(' ')
N = gets.to_i
b = []
N.times do
  b << gets.chomp
end

a.delete_if do |k,v|
  b.include?(v)
end

[
  ['11','12','13'],
  ['21','22','23'],
  ['31','32','33'],
  ['11','22','33'],
  ['13','22','31'],
  ['11','21','31'],
  ['12','22','32'],
  ['13','23','33'],
].each do |arr|
  unless (a[arr[0]] || a[arr[1]] || a[arr[2]])
    puts 'Yes'
    exit
  end
end
  
puts 'No'


Measured memory_bytes: 1788
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long x = sc.nextInt();
		long[] arr = new long[n];
		long total = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			total += arr[i];
		}
		long[] minArr = (long[])arr.clone();
		long min = total;
		for (int i = 1; i < n; i++) {
			total = 0;
			long w = minArr[n - 1];
			for (int j = n - 1; j > 0; j--) {
				minArr[j] = Math.min(minArr[j - 1], arr[j]);
				total += minArr[j];
			}
			minArr[0] = Math.min(w, arr[0]);
			total += minArr[0];
			total += i * x;
			if (min > total) {
				min = total;
			}
		}
		System.out.println(min);
	}
}


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

int main() {
  string s;
  cin >> s;
  int total = 0;
  for(int i=0;i<s.size();i++) {
    for(int j=i+1;j<s.size();j++) {
      if(s[i] == s[j]) total++;
    }
  }
  if(total == 2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int a, b;
	cin >> a >> b;
	int ans = 0;
	repn(i, a, b + 1){
		string s = to_string(i);
		string s1 = s;
		reverse(all(s1));
		ans += (s == s1);
	}
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c, counter;
    cin >> a >> b >> c;
    for(int i = a; i <= b; i++){
        if(c % i == 0){
            counter++;
        }
    }
    cout << counter << "\n";
}



Measured memory_bytes: 3204
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

long long pow_mod(long long x, long long n, long long mod_num) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) { res = (res * x) % mod_num; }
        x = (x * x) % mod_num;
        n = (n >> 1);
    }
    return res;
}


const int MAX_N = 5010;
const long long MOD = 1000000007;
int N;
std::string s;

//Combi_Num combi_num = Combi_Num(MAX_N, MOD);

long long dp00[MAX_N][MAX_N] = {}; // dp00[i][j] i回入力してj文字
 
int main(int argc, char **argv) {
    std::cin >> N;
    std::cin >> s;

    dp00[0][0] = 1;
    //dp01[0][0] = 1;

    for (int i = 0; i <= N - 1; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp00[i+1][j] = (dp00[i+1][j] + dp00[i][j]) % MOD;
            } else {
                dp00[i+1][j-1] = (dp00[i+1][j-1] + dp00[i][j]) % MOD;
                //dp01[i+1][j-1] = (dp01[i+1][j-1] + dp01[i][j]) % MOD;
            }
            dp00[i+1][j+1] = (dp00[i+1][j+1] + dp00[i][j] * 2) % MOD;
            //dp01[i+1][j+1] = (dp01[i+1][j+1] + dp01[i][j] * 2) % MOD;
        }
    }

    long long ret = dp00[N][s.size()];
    long long inv2 = pow_mod(2, MOD - 2, MOD);
    for (int i = 0; i < s.size(); i++) {
        ret = (ret * inv2) % MOD;
    }
    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 194176
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dp[100000+9][3];
int main(){
    int n;
    scanf("%d",&n);
    int arr[n][3];
    for(int i= 0;i<n;i++)
        for(int j = 0;j<3;j++)
            cin>>arr[i][j];
    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    for(int i = 1;i<n;i++){
        for(int j = 0;j<3;j++){
            for(int h = 0;h<3;h++){
                if(h == j)
                    continue;
                dp[i][j] = max(dp[i-1][h] + arr[i][j] , dp[i][j]);
            }
        }
    }
    printf("%d",*max_element(dp[n-1] , dp[n-1]+3));
    return 0;
}

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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
template<class T> inline bool is_overlap(const T& a, const T& b, const T& p, const T& q)
{ return p <=b && a <= q; }
#define MOD = 1000000007;
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
#define ANS(a) cout<<a<<endl
void yes(bool f){cout<<(f?"yes":"no")<<endl;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    ll N; cin >>N;
    vector<ll> A(N); cin >> A;
    
    ll ans = 1;

    int f = 0;
    for (ll i = 1; i < N; i++) {
        if (f == 0) {
            if (A[i] > A[i-1])  f = 1;
            if (A[i] < A[i-1])  f = -1;
        } else if (f == -1) {
            if (A[i] > A[i-1]) {
                ans++;
                f = 0;
            }
        } else if (f == 1) {
            if (A[i] < A[i-1]) {
                ans++;
                f = 0;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
def c_factors_of_factorial(N, MOD=10**9 + 7):
    from math import factorial
    from functools import reduce
    from operator import mul
    from collections import defaultdict

    def prime_factorization(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    ans = reduce(mul, [v + 1 for v in prime_factorization(factorial(N)).values()])
    return ans % MOD

N = int(input())
print(c_factors_of_factorial(N))


Measured memory_bytes: 3572
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#define N 1009
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;

LL fun(LL n, LL m)
{
    if((m / 2) < n) return  m / 2;
    LL ans = n;
    m = m - n * 2;
    ans = ans + m / 4;
    return ans;
}


int main()
{
    LL n, m;
    scanf("%lld%lld", &n, &m);
    LL ans = fun(n, m);
    printf("%lld\n", ans);
    return 0;
}


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

int main(){
	int hand[5],num[3],result[5],win;
  while(cin>>hand[0]>>hand[1]>>hand[2]>>hand[3]>>hand[4]){
		for(int i=0;i<3;i++){
			num[i] = 0;
			result[i] = 0;
		}
		for(int i=0;i<5;i++){
			hand[i]--;
			num[hand[i]]++;
		}
		if(num[0]*num[1]*num[2] == 0 
			 && (num[0]+1)*(num[1]+1)*(num[2]+1) != 6){
			for(win = 0;num[win] != 0;win++);
			win = (++win)%3;
			for(int i=0;i<5;i++){
				result[i] = (hand[i] == win) ? 1 : 2;
			}
		}
		else{
			for(int i=0;i<5;i++)
				result[i] = 3;
		}
		for(int i=0;i<5;i++)
			cout<<result[i]<<endl;
	}
  return 0;
}

Measured memory_bytes: 0
import numpy as np

n = int(input())
even_count = [0 for i in range(n)]
for i in range(1,n+1):
  j = i
  count = 0
  while True:
    if i % 2 == 0:
      count += 1
      i = int(i / 2)
    else:
      break
  even_count[j-1] = count
print(np.argmax(even_count)+1)

Measured memory_bytes: 27104
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

const long long MOD = 1000000007;

int dp1[110][31700], dp2[110][31700];

void solve(long long N, long long K){
    int M;
    for(M = 1; M * M <= N; ++M) ;
    for(int i = 1; i * i <= N; ++i) {
        dp1[0][i] = 1;
        if (N / i > i) {
            dp2[0][i] = N / i - N / (i + 1);
        }
    }

    for(int i = 1; i < K; ++i) {
        int a = 0;
        for(int j = 1; j * j <= N; ++j) {
            a = (a + dp1[i-1][j]) % MOD;
            if (N / j > j) {
                dp2[i][j] = a * (N / j - N / (j + 1)) % MOD;
            }
        }
        for(int j = 1; j * j <= N; ++j) {
            dp1[i][j] = a;
        }
        int c = 0;
        for(int j = M - 1; j >= 1; --j) {
            c = (c + dp2[i - 1][j]) % MOD;
            dp1[i][j] = (dp1[i][j] + c) % MOD;
        }
    }
    int res = 0;
    for(auto a: dp1[K - 1]) {
        res = (res + a) % MOD;
    }
    for(auto a: dp2[K - 1]) {
        res = (res + a) % MOD;
    }
    cout << res << endl;

    if (N > 10) return;
    for(int i = 0; i < K; ++i) {
        for (int j = 0; j < M; ++j) {
            fprintf(stderr, "%3d ", dp1[i][j]);
        }
        cerr << endl;
        for (int j = 0; j < M; ++j) {
            fprintf(stderr, "%3d ", dp2[i][j]);
        }
        cerr << endl;
        cerr << endl;
    }
}

signed main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}

Measured memory_bytes: 53504