akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

struct RollingHash{
    vector<int64_t> hash;
    vector<int64_t> base_pow;
    int64_t base, mod;
    const int64_t DEFAULT_BASE = 1009, DEFAULT_MOD = 1e9+7;

    RollingHash(string S="", int64_t base_=-1, int64_t mod_=-1){
        base = base_ > 0 ? base_ : DEFAULT_BASE;
        mod = mod_ > 0 ? mod_ : DEFAULT_MOD;
        if(S.size() > 0) initialize(S);
    }

    void initialize(string& S){
        int N = S.size();
        vector<int> s(N);
        for(int i=0; i<N; i++) s[i] = S[i];
        initialize(s);
    }

    void initialize(vector<int>& S){
        hash.resize(S.size()+1);
        base_pow.resize(S.size()+1);
        hash[0] = 0;
        base_pow[0] = 1;
        for(int i=1; i<=S.size(); i++){
            hash[i] = (hash[i-1] * base + S[i-1]) % mod;
            base_pow[i] = base_pow[i-1] * base % mod;
        }
    }

    // 0-indexed, [a, b)
    int64_t between(int a, int b){
        return (mod + hash[b] - hash[a] * base_pow[b-a] % mod) % mod;
    }
};

int main(){
    int N;
    string S;
    cin >> N >> S;
    int ok = 0, ng = N/2+1;
    RollingHash rh1(S, 1007, 1e9+7), rh2(S, 2009, 1e9+9);

    while(ng-ok>1){
        int len = (ng+ok)/2;
        set<pair<int64_t, int64_t>> val;
        vector<pair<int64_t, int64_t>> v(N);
        bool success = false;
        for(int i=0; i+len<=N; i++){
            if(i >= len) val.insert(v[i-len]);
            v[i] = {rh1.between(i, i+len), rh2.between(i, i+len)};
            if(val.count(v[i])){
                success = true;
                break;
            }
        }
        (success ? ok : ng) = len;
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fun(ll n)
{
    switch(n & 3)
    {
    case 0:
        return n;
    case 1:
        return 1;
    case 2:
        return n + 1;
    case 3:
        return 0;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a,b;
    while(cin>>a>>b)
    {
        ll x=fun(b);
        x=x^fun(a-1);
        cout<<x<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
 
class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int w = Integer.parseInt(strArr[0]);
        int h = Integer.parseInt(strArr[1]);
        int x = Integer.parseInt(strArr[2]);
        int y = Integer.parseInt(strArr[3]);
        int r = Integer.parseInt(strArr[4]);
 
        if ( (x - r >= 0 && x + r <= w) && (y - r >= 0 && y + r <= h) ) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 24328
import java.util.*;
import java.math.*;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int P = sc.nextInt();
		for(int KK = 0; KK < P; KK++) {
			int n = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			Node start = new Node(sc.nextInt(),sc.nextInt());
			Node[] staff = new Node[n+1];
			for(int i = 0; i < n; i++) {
				staff[i] = new Node(sc.nextInt(),sc.nextInt());
			}
			for(int i = 0; i < n; i++) {
				int len = l(start,staff[i]);
				if(len > 10 * 10) continue;
				start.to.add(i);
			}
			for(int i = 0; i < n; i++) {
				for(int j = i + 1; j < n; j++) {
					int len = l(staff[i],staff[j]);
					if(len > 50 * 50) continue;
					staff[i].to.add(j);
					staff[j].to.add(i);
				}
			}
			int count = 0;
			int say   = 0;
			ArrayDeque<Data> queue = new ArrayDeque<Data>();
			for(int i = 0; i < start.to.size(); i++) {
				queue.add(new Data(start.to.get(i),0));
			}
			while(!queue.isEmpty() && count < 2000) {
				Data tmp = queue.pollFirst();
				Node check = staff[tmp.now];
				//????????????       //????????????
				if(check.time > tmp.time) continue;
				say = Math.max(tmp.time + x,say);
				count++;
				ArrayList<Integer> to = check.to;
				for(int i = 0; i < to.size(); i++) {
					queue.add(new Data(to.get(i),tmp.time + x));
				}
				//????????????
				check.time = tmp.time + x + y + 1;
			}
			if(count == 2000) System.out.println("You're always welcome!");
			else {
				System.out.println(say);
			}
		}
	}
	static class Data {
		int now;
		int time;
		Data(int now, int time) {
			this.now = now;
			this.time = time;
		}
	}
	static int l(Node a, Node b) {
		int k = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
		return k;
	}
	static class Node {
		int x;
		int y;
		int time;
		Node(int a, int b) {
			x = a;
			y = b;
		}
		ArrayList<Integer> to = new ArrayList<Integer>();
	}
}

Measured memory_bytes: 135688
#include <iostream>
#include <cstring>

using namespace std;

int main(){
	string s;
	int count = 0;
	int ans = 0;
	
	cin >> s;
	for(char c : s){
		if(c == 'S'){
			count = 0;
			}
		else{
			count++;
			}
		ans = max(ans, count);
		}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3600
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

ctr = {"r": P, "s": R, "p": S}
dp = [""] * N
ans = 0
for i in range(N):
    if i >= K and dp[i - K] == T[i]:
        continue

    ans += ctr[T[i]]
    dp[i] = T[i]

print(ans)


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

int main(){
	int a,b;
	cin >> a >> b;
	int counts = 0;
	for(int i = a; i <= b; i++){
		string s = to_string(i);
		if(s[0] == s[4] && s[1] == s[3]) counts++;
	}
	cout << counts << endl;
}

Measured memory_bytes: 3748
N, C, K = list(map(int, input().split()))

T = []
for i in range(N):
	T.append(int(input()))

T = sorted(T)

TT = []

for i in range(N - 1):
	TT.append(T[i + 1] - T[i])

ans = 1
c = 1
t = 0

for i in range(N - 1):
	t += TT[i]
	c += 1
	if t > K:
		ans += 1
		t = 0
		c = 1

	if c > C:
		ans += 1
		t = 0
		c = 1

print(ans)

Measured memory_bytes: 10824
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

#define rep0(i, n) for (i = 0; i < n; i++)
#define rep(s, i, n) for (i = s; i < n; i++)
using namespace std;
char s[10][10];

int main()
{
    int n, m, k, S, ans = 0;
    scanf("%d%d%d", &n, &m, &k), S = 1 << (n + m);
    for (int i = 0; i < n; i++)
        scanf("%s", s[i]);
    for (int i = 0; i < S; i++)
    {
        int w = 0;
        for (int j = 0; j < n; j++)
            for (int l = 0; l < m; l++)
                if (s[j][l] == '#' && (i & (1 << j)) == 0 && (i & (1 << (l + n))) == 0)
                    w++;
        ans += w == k;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3816
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()
mon = 0
d = 0
for i in range(n):
    mon += ab[i][0]*ab[i][1]
    d +=ab[i][1]
    if d == m:break
    if d >m:
        mon -= ab[i][0]*ab[i][1]
        d -= ab[i][1]
        mon += ab[i][0]*(m-d)
        break
print(mon)


Measured memory_bytes: 27760
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for d in range(1, n):
            ans = (ans + com(n * m - 2, k - 2) * (m ** 2) * (n - d) * d) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 71720
p=print
r=range
def a(i,j,k,l=0):p("+<"[l],i,j,k)
def b(i):a(i,i,i+1)
def d(x,i):
	for t in r(30):b(p:=i+t+30);a(q:=p+1,n,q);[*map(b,r(q,v:=i+60))];a(v,x,i+t,1);b(p);a(q,i+t,q)
p(n:=3933)
a(0,1,n)
a(2,n,n,1)
a(0,n,0)
a(1,n,1)
d(0,9)
d(1,60)
for t in r(59):a(2,2,2);[t<s+30<60!=(a(9+t-s,60+s,5),a(n,5,6,1),a(2,6,2))for s in r(t+1)]

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

// https://atcoder.jp/contests/abc149/tasks/abc149_c

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

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

  while (!isPrime(x)) x++;

  cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
// JavaProgram.cpp
// Author : Priydarshi Singh (@dryairship)
// One cat just leads to another. One bug leads to two others.

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

// I like my types defined.
typedef long long           ll;
typedef pair<int, int>      pii;
typedef pair<ll, ll>        pll;
typedef vector<int>         vi;
typedef vector<ll>          vl;
typedef vector<vector<ll>>  vvl;
typedef vector<pii>         vii;
typedef vector<pll>         vll;
typedef set<int>            si;
typedef map<string, int>    msi;
typedef map<int, int>       mii;

// Traditional science is all about finding "hashtag define"s.
#define fr(i, n)            for(int i=0; i<(n); ++i)
#define frC(i, n, c)        for(int i=0; (i<(n)) && (c); ++i)
#define frA(i, a, n)        for(int i=a; i<=(n); ++i)
#define frD(i, a, n)        for(int i=a; i>=(n); --i)
#define fill(a)             memset(a, 0, sizeof(a))
#define fill1(a)            memset(a, -1, sizeof(a))
#define revsort(a, b)       sort(a, b, greater<int>())
#define ff                  first
#define ss                  second
#define pb                  push_back 
#define dout                if(DEBUGGING) cout
#define dbg                 if(DEBUGGING) 
#define endl                "\n"

// When you realize MOD > INF...
int DEBUGGING    =          0;
const int INF    =          1000000000;
const int MOD    =          1000000007;
const ll LINF    =          1e18;
const double PI  =          3.1415926535897932;
const double EPS =          1e-7;

// I'D SPAM. Hehe.
ll gcdEx                    (ll a, ll b, ll *x, ll *y){if(!a){*x=0;*y=1;return b;} 
ll x1,y1,gcd=gcdEx          (b%a,a,&x1,&y1); *x=y1-(b/a)*x1;*y=x1; return gcd;}
ll modI(ll b, ll m)         {ll x,y;gcdEx(b,m,&x,&y);return (x%m+m)%m;}
ll modD(ll a, ll b)         {return (modI(b,MOD)*(a%MOD))%MOD;}
ll modS(ll a, ll b)         {return ((a%MOD)-(b%MOD)+MOD)%MOD;}
ll modP(ll x, ll y)         {ll r=1; x%=MOD; while(y>0){if(y&1){r=(r*x)%MOD;} y=y>>1; x=(x*x)%MOD;} return r;}
ll modA(ll a, ll b)         {return ((a%MOD)+(b%MOD))%MOD;}
ll modM(ll a, ll b)         {return ((a%MOD)*(b%MOD))%MOD;}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vvl id;

vvl matM(vvl m1, vvl m2){
    int l = m1.size();
    vvl ans(l, vl(l));
    fr(i,l){
        fr(j,l){
            fr(k,l){
                ans[i][j] = modA(ans[i][j], modM(m1[i][k], m2[k][j]));
            }
        }
    }
    return ans;
}

vvl matP(vvl mat, ll p){
    if(p==0) return id;
    if(p==1) return mat;
    vvl hf = matP(mat, p/2);
    vvl ans = matM(hf, hf);
    if(p&1) ans = matM(ans, mat);
    return ans;
}

void solve(int TEST_CASE){
    int n; ll k;
    cin >> n >> k;
    vvl mt(n, vl(n));
    fr(i,n) fr(j,n) cin >> mt[j][i];
    vvl amt = matP(mt, k);
    ll ans=0;
    fr(i,n){
        fr(j,n){
            ans = modA(ans, amt[i][j]);
        }
    }
    cout << ans;
}

int main(int argc, char* argv[]){
    if(argc==2 && argv[1][1]=='v') DEBUGGING = 1;
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin.exceptions(cin.failbit);
    int nTestCases=1;
    //cin >> nTestCases;
    frA(i,1,nTestCases) solve(i);
    return 0;
}

Measured memory_bytes: 4868
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
// #include "prettyprint.hpp"

int main() {
  int N;
  cin >> N;
  cout << (double)floor((double)(N + 1) / 2) / N << endl;
  return 0;
}

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

int main(void) {
    string s;
    getline(cin, s);

    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
#define nitro ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define pb push_back
#define pi 3.1415926535897932384626
#define mod 1000000007
#define endl '\n'
#define F first
#define S second

using namespace std;

int32_t main()
{
 nitro;
 /*#ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
 #endif*/
 int t=1;
 //cin>>t;
 while(t--)
 {
     double d,tt,s;
     cin>>d>>tt>>s;
     double x=d/s;
     if(tt>=x)
     cout<<"Yes";
     else
     cout<<"No";
 }
return 0;
}


Measured memory_bytes: 3732
#include<bits/stdc++.h>
#include <string>
#include <unordered_map>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Zero(dp) memset(dp,0,sizeof(dp))
using namespace std;
int32_t main(){
ios
int t=1;
//cin>>t;
while(t--)
{ 
    int n,m;cin>>n>>m;
    cout<<(n*(n-1))/2+(m*(m-1))/2<<'\n';
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
//#define num 1000000007
#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) (a>b)?(a>c)?a:c:(b>c)?b:c
#define min3(a,b,c) (a<b)?(a<c)?a:c:(b<c)?b:c
#define avg(a,b) ((a)+(b))/2
#define push push_back
#define pop pop_back
#define mp make_pair
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
typedef long long ll;

ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll gcd(ll a, ll b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b, a%b);
}
bool prime[3001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=3000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=3000; i += p) 
                prime[i] = false; 
        } 
    } 
}
ll powe[20];
void power()
{
	powe[0]=1;
	REP(i,1,20)
	{
		powe[i]=(powe[i-1]*10)%num;
        if(powe[i]<0)
        powe[i]+=num;
	}
}
ll A[300005],mx[300005],mn[300005],cur[300005];
void assign(ll n)
{
	REP(i,1,n)
	{
		A[i]=mx[i]=mn[i]=cur[i]=i;
	}
}
double dist(pll p1,pll p2)
{
	return (1.0)*(p1.f-p2.f)*(p1.f-p2.f)+(1.0)*(p1.s-p2.s)*(p1.s-p2.s);
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll a,b,k;
	cin>>a>>b>>k;
	if(k<a)
	{
		a-=k;
		k=0;
	}
	else
	{
	k-=a;
	a=0;
	}
	if(k<b)
	{
		b-=k;
		k=0;
	}
	else
	{
		k-=b;
		b=0;
	}
	cout<<a<<" "<<b;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[200005];
bool compare(int a,int b){
    return a>b;
}
int main(){
    ios::sync_with_stdio(0);
    int n,k,x;
    cin>>n>>k;
    for (int i=0;i<200005;i++)
    	a[i]=0;
    for(int i=0;i<n;i++){
        cin>>x;
        a[x]++;
    }
    int ans=0;
    sort(a,a+n,compare);
    for(int i=k;i<=n;i++){
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
  int N,M;
  std::cin>>N>>M;
  std::vector<std::vector<int>> sw(N);
  for(int i=0;i!=M;i++)
  {
    int k;
    std::cin>>k;
    for(;k!=0;k--)
    {
      int s;
      std::cin>>s;
      s--;
      sw[s].push_back(i);
    }
  }
  std::vector<int> p(M);
  for(int i=0;i!=M;i++)
  {
    std::cin>>p[i];
  }
  
  int result=0;
  std::vector<int> t;
  for(int i=0;i!=(1<<N);i++)
  {
    t=p;
    for(int j=0;j!=N;j++)
    {
      if(i&(1<<j))
      {
        for(int k=0;k!=sw[j].size();k++)
        {
          t[sw[j][k]]++;
        }
      }
    }
    result++;
    for(int j=0;j!=M;j++)
    {
      if(t[j]%2!=0)
      {
        result--;
        break;
      }
    }
  }
  
  std::cout<<result<<std::endl;
  
  return 0;
}

Measured memory_bytes: 256
a,b,c,k = map(int,input().split())

aa = list(map(int,input().split()))
aa.sort(reverse = True)
bb = list(map(int,input().split()))
bb.sort(reverse = True)
cc = list(map(int,input().split()))
cc.sort(reverse = True)
al = []
aal = []
for i in aa:
    for j in bb:
        al.append(i+j)
al.sort()
if len(al) > k:
    al = al[len(al)-k:]

for i in al:
    for j in cc:
        aal.append(i+j)
aal.sort()

if len(aal) > k:
    aal = aal[len(aal)-k:]
aal.reverse()
for i in aal:
    print(i)


Measured memory_bytes: 151504
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1LL << 61);
const int inf = 1001001001;
const int mod = 1000000007;

struct mint {
	ll x;
	mint() :x(0) {}
	mint(ll x) :x((x% mod + mod) % mod) {}
	// mint(ll x):x(x){}
	mint& fix() { x = (x % mod + mod) % mod; return *this; }
	mint operator-() const { return mint(0) - *this; }
	mint operator~() const { return mint(1) / *this; }
	mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; }
	mint& operator-=(const mint& a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; }
	mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; }
	mint& operator/=(const mint& a) { (x *= a.pow(mod - 2).x) %= mod; return *this; }
	mint operator+(const mint& a)const { return mint(*this) += a; }
	mint operator-(const mint& a)const { return mint(*this) -= a; }
	mint operator*(const mint& a)const { return mint(*this) *= a; }
	mint operator/(const mint& a)const { return mint(*this) /= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint res = pow(t / 2);
		res *= res;
		return (t & 1) ? res * x : res;
	}
	bool operator<(const mint& a)const { return x < a.x; }
	bool operator==(const mint& a)const { return x == a.x; }
};
mint ex(mint x, ll t) { return x.pow(t); }
istream& operator>>(istream & i, mint & a) { i >> a.x; return i; }
ostream& operator<<(ostream & o, const mint & a) { o << a.x; return o; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	vector<int> c(n + 1, 0);//色の変遷
	c[0] = 3;
	mint ans = 1;
	rep(i, n) {
		ans *= c[a[i]];
		c[a[i]]--;
		c[a[i] + 1]++;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    string str, op;
    int sum;
    cin >> str;
    for (int i = 0; i < 1 << (str.size() - 1); ++i) {
        sum = str[0] - '0';
        for (int j = 0; j < str.size() - 1; ++j) {
            if (i & (1 << j)) {
                op[j] = '+';
                sum += str[j + 1] - '0';
            }
            else {
                op[j] = '-';
                sum -= str[j + 1] - '0';
            }
        }
        if (sum == 7) break;
    }
    for (int i = 0; i < str.size() - 1; ++i) cout << str[i] << op[i];
    cout << str[3] << "=7" << endl;
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
nums = list(map(int, input().split()))
ans = 0
for x in range(1, n - 1):
    if nums[x - 1] > nums[x] and nums[x + 1] <= nums[x]:
        ans = ans + 1
    elif nums[x + 1] > nums[x] and nums[x - 1] <= nums[x]:
        ans = ans + 1
    elif nums[x + 1] > nums[x] and nums[x - 1] == nums[x + 1]:
        ans = ans + 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP2(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define INF 2e9
typedef long long ll;
typedef pair<int, int> P;

ll gcd(ll x, ll y)
{
  return y ? gcd(y, x % y) : x;
}
ll lcm(ll x, ll y)
{
  return x * y / gcd(x, y);
}
bool is_prime(int x)
{
  for (int i = 2; i * i <= x; i++)
  {
    if (x % i == 0)
      return 0;
  }
  return true;
}
vector<bool> prime_table(int n)
{
  vector<bool> prime(n + 1, 1);
  prime[0] = 0;
  prime[1] = 0;
  for (int i = 2; i * i <= n; i++)
  {
    if (!prime[i])
      continue;
    for (int j = i * i; j <= n; j++)
      prime[j] = 0;
  }
  return prime;
}
map<int, int> prime_factor(int n)
{
  map<int, int> res;
  for (int i = 2; i * i <= n; i++)
  {
    while (n % i == 0)
    {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1)
    res[n]++;
  return res;
}

ll modpow(ll a,ll n,ll mod){
  ll ret=1;
  while(n>0){
    if(n&1) ret=ret*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return ret;
}

int main()
{
  int n;
  cin>>n;
  vector<bool> f(1000000000,0);
  REP(i,n){
    int a;
    cin>>a;
    if(f[a-1]){
      cout<<"NO"<<endl;
      return 0;
    }else f[a-1]=1;
  }

  cout<<"YES"<<endl;
  
  return 0;
}


Measured memory_bytes: 122368
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

int main(){
    int n,m,ans=0;
    cin>>n>>m;
    int food[m];
    for(int i=0;i<m;i++){
        food[i]=0;
    }
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            food[a-1]++;
        }

    }
    for(int i=0;i<m;i++){
        if(food[i]==n) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>

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

using namespace std;

int K,N;
vector<ll> min_list;
int main()
{
  scanf("%d%d", &N, &K);
  ll h[N];
  rep(i,N) {
    scanf("%lld", &h[i]);
  }
  sort(h, h+N);
  for(int i = 0; i < N-K+1; i++) {
    ll min = h[i];
    ll max = h[i+K-1];
    min_list.push_back(max-min);
  }
  ll min = *min_element(min_list.begin(), min_list.end());
  printf("%lld\n", min);
  return 0;
}

Measured memory_bytes: 2168
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BC121B
{
    class Program
    {
        static void Main(string[] args)
        {
            // 整数の入力
            //int a = int.Parse(Console.ReadLine());
            // スペース区切りの整数の入力
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int C = int.Parse(input[2]);// 定数

            int[] B = new int[M]; // 係数
            int[]  A = new int[M];
            string[] inputB = Console.ReadLine().Split(' ');
            for(var i = 0; i < M; i++)
            {
                B[i] = int.Parse(inputB[i]);
            }

            int ans = 0;
            for(var j = 0; j < N; j++)
            {
                int partAB = 0;
                string[] inputA = Console.ReadLine().Split(' ');
                 for (var i = 0; i < M; i++)
                        {
                            A[i] = int.Parse(inputA[i]);
                        }
                for(var i = 0; i < M; i++)
                        {
                            partAB += A[i] * B[i];
                        }
                if (partAB + C > 0)
                    {
                        ans++;
                    }
              }
             Console.WriteLine(ans);
        }
    }
}


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

int main(){
  int K,S,i,j,k,cnt=0;
  cin >> K >> S;

  for(i=0;i<=K;i++){
    for(j=0;j<=K;j++){
      if(i+j<=S){
        if(S-j-i<=K)
        cnt++;
      }
    }
  }
  cout << cnt;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


int main(void)
{
	char S[1000] = {};
	int a = 0;
	scanf("%s",S);
	for (int i = 0; S[i] != NULL; i++)
	{
		a++;
	}
	
	if (S[a-1] == 's')
	{
		printf("%ses", S);
	}
	else
	{
		printf("%ss", S);
	}
	return 0;
}

Measured memory_bytes: 1680
w = gets.to_i
n = gets.to_i

arr = (1..w).to_a
n.times do
  a, b = gets.split(',').map(&:to_i)
  arr[a-1], arr[b-1] = arr[b-1], arr[a-1]
end

arr.each do |i|
  puts i
end

Measured memory_bytes: 6100
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int cur=1;
	while(cur<=k&&n)
	{
		cur*=2;
		n--;
	}
	while(n--)
		cur+=k;
	cout<<cur;
	return  0;
 } 

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    static int N, K;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inStr = br.readLine().split(" ");
        N = Integer.parseInt(inStr[0]);
        K = Integer.parseInt(inStr[1]);
        arr = new int[N];
        inStr = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(inStr[i]);
        }

        int min = Integer.MAX_VALUE;
        int left, right, num;
        for (int i = 0; i < N - K + 1; i++) {
            left = arr[i];
            right = arr[i + K - 1];
            if (right < 0) {
                num = Math.abs(left);
                min = Math.min(min, num);
                continue;
            }
            if (left >= 0) {
                num = right;
                min = Math.min(min, num);
                continue;
            }
            if (left < 0 && right >= 0) {
                num = Math.min(Math.abs(left) * 2 + right, Math.abs(left) + right * 2);
                min = Math.min(min, num);
            }
        }
        System.out.println(min);
    }
}

Measured memory_bytes: 37560
#include <bits/stdc++.h>
using namespace std;
const int64_t INF=999999999;

int main() {
   int x,a,b;
   cin>>x>>a>>b;
   if(abs(x-a)>abs(x-b)){cout<<"B"<<endl;}
   if(abs(x-a)<abs(x-b)){cout<<"A"<<endl;}
return 0;}

Measured memory_bytes: 256
#include <algorithm>/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i, b, e) for (typeof(b) i = (b); assert((i) <= (e)), i != (e); ++i)
#define SZ(a) ((int)a.size())
#define PB(e) push_back(e)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(),(v).rend())
#define F first
#define S second
#define MP(a, b) make_pair(a, b)
#define BIT(n) (1ULL << (n))

static const double PI (3.14159265358979323846);
static const double EPS (1e-10);

using namespace std;
typedef long long int LL;
typedef pair<int,int> P;/*}}}*/

int starts[24][60][60];
int arrivals[24][60][60];

int main(int argc, char const* argv[])
{
	int N;
	while (cin >> N, N) {
		FOR(i, 0, 24) {
			FOR(j, 0, 60) {
				FOR(k, 0, 60) {
					starts[i][j][k] = 0;
					arrivals[i][j][k] = 0;
				}
			}
		}
		FOR(i, 0, N) {
			int h, m, s;
			char buf;
			cin >> h >> buf >> m >> buf >> s;
			++starts[h][m][s];
			cin >> h >> buf >> m >> buf >> s;
			++arrivals[h][m][s];
		}

		int ans = 0;
		int stock = 0;
		FOR(i, 0, 24) {
			FOR(j, 0, 60) {
				FOR(k, 0, 60) {
					if (arrivals[i][j][k]) {
						//printf("arrive at %d:%d:%d\n", i, j, k);
						stock += arrivals[i][j][k];
					}
					if (starts[i][j][k]) {
						FOR(l, 0, starts[i][j][k]) {
							if (stock == 0) {
								++ans;
							} else {
								--stock;
							}
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    cout << n/3 << endl;
    return 0;
}


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

int main() {
  int N; cin >> N;
  long long K; cin >> K;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);

  const int INF = 1000000007;
  // dp[i][j] := 上から i 桁目を決めたときの最大値で、j = 1 のときは K 未満確定
  vector<vector<long long>> dp(41, vector<long long>(2, -INF));
  dp.at(0).at(0) = 0;
  for (int i = 0; i < 40; i++) {
    long long mask = 1LL << (39 - i);
    int num = 0;  // 数列 A で上から i+1 桁目のビットが 1 である要素数
    for (int j = 0; j < N; j++) {
      if (A.at(j) & mask) num++;
    }

    // dp[i][0] からの遷移 (K の i+1 桁目が 0 か 1 で対応を変える)
    if (dp.at(i).at(0) >= 0) {
      if (K & (1LL << (39 - i))) {
        // i+1 桁目に 0 を入れる (未満フラグ立つ)
        dp.at(i+1).at(1) = max(dp.at(i+1).at(1), dp.at(i).at(0) + mask * num);
        // i+1 桁目に 1 を入れる
        dp.at(i+1).at(0) = max(dp.at(i+1).at(0), dp.at(i).at(0) + mask * (N-num));
      }
      else {
        // i+1 桁目には 0 しか入れられない (1 だと K を超えてしまう)
        dp.at(i+1).at(0) = max(dp.at(i+1).at(0), dp.at(i).at(0) + mask * num);
      }
    }
    // dp[i][1] からの遷移 (i+1 桁目は 0 か 1 を自由に決める)
    if (dp.at(i).at(1) >= 0) {
      dp.at(i+1).at(1) = max(dp.at(i+1).at(1), dp.at(i).at(1) + mask * max(num, N-num));
    }
  }
  cout << max(dp.at(40).at(0), dp.at(40).at(1)) << endl;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	scanner *bufio.Scanner
	buffer  *bufio.Writer
	writer  io.Writer
)

func main() {
	defer flush()
	initWordScanner()
	initBufWriter()

	x := 1000
	n := readInt()
	var a []int
	for i := 0; i < n; i++ {
		a = append(a, readInt())
	}

	for i := 1; i < n; i++ {
		if a[i] > a[i-1] {
			x += (a[i] - a[i-1]) * (x / a[i-1])
		}
	}

	println(x)
}

func initLineScanner() {
	scanner = bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1e4)
	scanner.Buffer(buf, bufio.MaxScanTokenSize)
}

func initWordScanner() {
	initLineScanner()
	scanner.Split(bufio.ScanWords)
}

func readLine() string {
	if scanner.Scan() {
		return scanner.Text()
	}
	return ""
}

func readInt() int {
	scanner.Scan()
	n, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return n
}

func readFloat() float64 {
	scanner.Scan()
	n, err := strconv.ParseFloat(scanner.Text(), 64)
	if err != nil {
		panic(err)
	}
	return n
}

func readRunes() []rune {
	scanner.Scan()
	var ns []rune
	for _, v := range scanner.Text() {
		ns = append(ns, v)
	}
	return ns
}

func readString() string {
	if scanner.Scan() {
		return scanner.Text()
	}
	return ""
}

func readStrings() []string {
	scanner.Scan()
	var ss []string
	for _, v := range scanner.Text() {
		ss = append(ss, string(v))
	}
	return ss
}

func initWriter() {
	buffer = nil
	writer = os.Stdout
}

func initBufWriter() {
	buffer = bufio.NewWriter(os.Stdout)
	writer = buffer
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(writer, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(writer, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func flush() {
	if writer != nil {
		buffer.Flush()
	}
}

func string2int(s string) int {
	n, e := strconv.Atoi(s)
	if e != nil {
		panic(e)
	}
	return n
}

func int2string(n int) string {
	s := strconv.Itoa(n)
	return s
}

func string2float(s string) float64 {
	n, e := strconv.ParseFloat(s, 64)
	if e != nil {
		panic(e)
	}
	return n
}

func sum(ns []int) int {
	s := 0
	for _, n := range ns {
		s += n
	}
	return s
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}


Measured memory_bytes: 1796
#include <stdio.h>



int main(void)
{
	//変数の宣言
	int n,m;
	int max;
	int i;
	
	//データの読み込み
	scanf("%d %d",&n,&m);
	
	
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
	max=m/n;
	
	for(i=max;i>0;i--){
		if(m%i==0){
			printf("%d",i);
			break;
		}
	}
	
//	printf("計算部分終了\n");
	
	//出力
	
	
//	printf("結果の出力終了\n");
	
	return 0;
}



Measured memory_bytes: 128
n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
dp[0]=a[0]
for i in range(1,n):
  dp[i]=dp[i-1]+a[i]
ans1,ans2,cnt1,cnt2,flag=0,0,0,0,True
for i in range(n):
  if flag==True:
    if dp[i]+cnt1<=0:
      ans1+=abs(1-(dp[i]+cnt1))
      cnt1+=1-(dp[i]+cnt1)
    flag=False
  else:
    if dp[i]+cnt1>=0:
      ans1+=abs(-1-(dp[i]+cnt1))
      cnt1+=-1-(dp[i]+cnt1)
    flag=True

flag=False
for i in range(n):
  if flag==True:
    if dp[i]+cnt2<=0:
      ans2+=abs(1-(dp[i]+cnt2))
      cnt2+=1-(dp[i]+cnt2)
    flag=False
  else:
    if dp[i]+cnt2>=0:
      ans2+=abs(-1-(dp[i]+cnt2))
      cnt2+=-1-(dp[i]+cnt2)
    flag=True
print(min(ans1,ans2))

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

int main() {
    int A, B;
    cin >> A >> B;
    int ans = -1;

    rep(i,1500) {
        int tax8 = i * 8 / 100.0;
        int tax10 = i * 10 / 100.0;
        if (tax8 == A && tax10 == B) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}


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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N;
  cin >> N;
  N++;
  int count = 0;
  while (N >= 10) {
    N /= 10;
    count++;
  }
  cout << N - 1 + 9 * count << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define DBG(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const ll p = 1e9+7;
const ll INF = 1LL << 60;

int n,k,a[111];
int dp[111111];

int rec(int x){
  //  DBG(x);
  if(dp[x]!=-1)return dp[x];
  int s[111]={};
  for(int i=0;i<n;i++){
    if(x<a[i])continue;
    s[rec(x-a[i])]=1;
  }
  for(int i=0;i<111;i++){
    if(s[i])continue;
    return dp[x]=i;
  }
}

int main(){  
  cin>>n>>k;
  for(int i=0;i<n;i++)cin>>a[i];
  fill_n(dp,111111,-1);
  dp[0]=0;
  cout<<(rec(k)?"First":"Second")<<endl;
  return 0;
}


Measured memory_bytes: 49152
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(v) v.begin(),v.end()
#define ll long long
#define pb(a) push_back(a)
#define pf(a) push_flont(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
	int x;
	cin >> x;
	if(x == 3 || x== 5 || x==7){
		cout << "YES" <<endl;
	}
	else cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    d = Counter()
    d.update(A)
    ans = 0
    for k, v in d.items():
        if k < v:
            ans += v - k
        if k > v:
            ans += v
        

    print(ans)
if __name__ == "__main__":
    main()




Measured memory_bytes: 19852
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
	int countYear = 0;
	long nowmoney = 100;
	while(nowmoney < x){
	    nowmoney *= 1.01;
	    countYear++;
	}
	System.out.print(countYear);
    }
}


Measured memory_bytes: 35704
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/
ll gcd(ll a, ll b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

ll lcm(ll number1,ll number2){
	return number1 * number2 / gcd(number1,number2);	
}

int main() {
	
	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n), plus;
	rep(i, n)scanf("%d", &a[i]);
	rep(i, n)scanf("%d", &b[i]);
	ll minus = 0, ans = 0;
	rep(i, n){
	  if(a[i] >= b[i]){
	    plus.pb(a[i] - b[i]);
		}else{
		minus += a[i] - b[i];
		++ans;
		}
	}
	if(ans == n){
	  printf("-1\n");
	  Please AC;
	}
	sort(all(plus), greater<int>());
	for(auto aa : plus){
	  if(minus >= 0)break;
	  ++ans;
	  minus += aa;
	}
	if(minus < 0)ans = -1;
	printf("%lld\n", ans);
	
	Please AC;
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 5e3 + 5;

vi g[MAXN];

ll f[MAXN];
ll dp[MAXN][MAXN][2];
ll tmp[MAXN][2];
int sz[MAXN];
int prv[MAXN];

void dfs(int s) {
	dp[s][1][0] = 1;
	sz[s] = 1;
	REP(i, 0, SZ(g[s])) {
		int to = g[s][i];
		if (to == prv[s]) {
			continue;
		}
		prv[to] = s;
		dfs(to);
		REPN(j, 0, sz[s] + sz[to]) {
			tmp[j][0] = tmp[j][1] = 0;
		}
		REPN(j, 1, sz[s]) {
			REPN(k, 1, sz[to]) {
				REP(l, 0, 2) {
					REP(h, 0, 2) {
						ll add = (dp[s][j][l] * dp[to][k][h]) % MOD;
						tmp[j + k][l ^ h] += add;
						if (tmp[j + k][l ^ h] >= MOD) {
							tmp[j + k][l ^ h] -= MOD;
						}
						if (!(k % 2)) {
							tmp[j][l ^ h ^ 1] = (tmp[j][l ^ h ^ 1] + add * f[k]) % MOD;
						}
					}
				}
			}
		}
		REPN(j, 0, sz[s] + sz[to]) {
			REP(k, 0, 2) {
				dp[s][j][k] = tmp[j][k];
			}
		}
		sz[s] += sz[to];
	}
	
	/*printf("%d:", s);
	REPN(i, 0, sz[s]) {
		printf(" %lld", dp[s][i]);
	}
	putchar('\n');*/
}

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 1, n) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	f[2] = 1;
	for(int i = 4; i <= n; i++) {
		f[i] = (f[i - 2] * (i - 1)) % MOD;
	}
	dfs(1);
	ll ans = 0ll;
	REPN(i, 1, n) {
		ans = (ans + dp[1][i][0] * f[i]) % MOD;
		ans = (((ans - dp[1][i][1] * f[i]) % MOD) + MOD) % MOD;
	}
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 391296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod998 = 998244353;
const ll intmax = 2147483647;
const ll llmax = 9223372036854775807;
const char sp = ' ';

ll N, D, d[500000], Q, q, a[500001], b[500001];

int main() {
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		cin >> d[i];
	}
	a[0] = D;
	for (int i = 0; i < N; i++) {
		a[i + 1] = min(a[i], abs(a[i] - d[i]));
	}
	b[N] = 1;
	for (int i = N - 1; i >= 0; i--) {
		if (d[i] >= b[i + 1] + b[i + 1])b[i] = b[i + 1];
		else b[i] = b[i + 1] + d[i];
	}
	cin >> Q;
	while (Q--) {
		cin >> q;
		if (a[q - 1] >= b[q]) {
			puts("YES");
		}
		else {
			puts("NO");
		}
	}
}

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

int main(){
  int N;
  cin >> N;
  int a = 0;
  int b = 0;
  int c = 0;
  int d = 0;
  string S;
  rep(i,N){
    cin >> S;
    if(S == "AC")a++;
    if(S == "WA")b++;
    if(S == "TLE")c++;
    if(S == "RE")d++;
  }
  cout << "AC" << " " << "x" << " " << a << endl;
  cout << "WA" << " " << "x" << " " << b << endl;
  cout << "TLE" << " " << "x" << " " << c << endl;
  cout << "RE" << " " << "x" << " " << d << endl;
}

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

namespace ABC107C
{
    class Program
    {
        static void Main(string[] args)
        {
            var dg = Console.ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();
            var n = dg[0];
            var k = dg[1] - 1;

            var x = Console.ReadLine().Split(' ').Select(v => double.Parse(v)).ToArray();

            var min = double.MaxValue;
            for (int i = 0; i < (n-k); ++i)
            {
                var start = x[i];
                var end = x[i + k];

                //Console.Write(start);
                //Console.Write(" ");
                //Console.WriteLine(end);
                //Console.WriteLine("---");

                double res = calc(start, end);

                if (res < min)
                {
                    min = res;
                }

                if (start >= 0)
                {
                    break;
                }
            }

            Console.WriteLine(min);
        }

        static double calc(double start, double end)
        {
            if (start < 0)
            {
                if (end < 0)
                {
                    return Math.Abs(start);
                }

                return getMin(start, end);
            }

            return end;
        }

        static double getMin(double start, double end)
        {
            var a = Math.Abs(end) + Math.Abs(start) * 2;
            var b = Math.Abs(end) * 2 + Math.Abs(start);

            //Console.Write(a);
            //Console.Write(" ");
            //Console.WriteLine(b);
            //Console.WriteLine("---");
            
            return a < b ? a : b;
        }
    }
}


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

int main() {
  string s;
  cin >> s;
  int cnt = 0;
  for (int i = 0; i < 3; i++) {
    if (s.at(i) == '1') {
      cnt++;
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

using Graph = vector<vector<int>>;

constexpr int INF = numeric_limits<int>::max() / 3;

void dfs(Graph const& tree, vector<int>& dists, int pos) {
  for (auto v : tree[pos]) {
    if (dists[v] < INF) continue;
    dists[v] = dists[pos] + 1;
    dfs(tree, dists, v);
  }
}

int diameter(Graph const& tree) {
  int V = tree.size();
  vector<int> dists(V, INF);
  dists[0] = 0;
  dfs(tree, dists, 0);
  auto farthest = max_element(begin(dists), end(dists));
  int v = farthest - begin(dists);
  vector<int> dists2(V, INF);
  dists2[v] = 0;
  dfs(tree, dists2, v);
  return *max_element(begin(dists2), end(dists2));
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  Graph tree(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  int d = diameter(tree);
  cout << (d % 3 == 1 ? "Second" : "First") << endl;
}


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

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll K;


cin >> K;

ll x=7%K;

set<ll> s;
ll ans = 1;

while(s.count(x) == 0){

  if(x == 0){
    cout << ans << endl;
    return 0;
  }
  s.insert(x);
  x = (x*10+7)%K;
  ++ans;
}

cout << "-1" << endl;

return 0;

}   


Measured memory_bytes: 50416