akhauriyash/Code-Regression huggingface dataset:
A = int(input())
B = int(input())
C = int(input())
X = int(input())
t = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500 + j*100 + k*50 == X:
                t += 1
print(t)


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

int main() {
  ll k,a,b; cin>>k>>a>>b;
  ll ans=0;
  if(a+2>=b||a>=k+1){ans=k+1;}
  else{
    ans=a;
    ans+=(b-a)*((k-a+1)/2);
    if((k-a+1)%2==1){ans++;}
  }
  cout<<ans<<endl;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int s[200005];
int FDS[200005];
int main(){
	cin>>n;
	int ans1=0;
	for(int i=1;i<=n;i++){
		scanf("%d",s+i);
		FDS[s[i]]=FDS[s[i]-1]+1;
		ans1=max(FDS[s[i]],ans1);
		
	}
	cout<<n-ans1;
	return 0;
}

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

int n;
vector<int > a, b;

int main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		b.push_back(x);
	}
	bool fl = 0;
	for(int i = 0; i < (int)a.size(); ++i) {
		if(a[i] > b[i]) {
			fl = 1;
			break;
		}
		else if(a[i] < b[i])
			break;
	}
	if(fl) swap(a, b);
	int ans = 0;
	do {
		fl = 0;
		for(int i = 0; i < (int)a.size(); ++i) {
			if(a[i] != b[i]) {
				fl = 1;
				break;
			}
		}
		if(!fl) break;
		++ans;
	} while(next_permutation(a.begin(), a.end()));
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int a = x2 - x1;
    int b = y2 - y1;
    int x3 = x2 - b;
    int y3 = y2 + a;
    int x4 = x3 - a;
    int y4 = y3 - b;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, K, S = map(int, input().split())
res = [0] * N
for i in range(K):
  res[i] = S
for i in range(K, N):
  if S < 10 ** 9:
    res[i] = 10 ** 9
  else:
    res[i] = 1
print(*res)

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

int main() {
string s;
cin >> s;
int cnt = 0;
rep(i,s.size()-1){
  if(s.at(i) == s.at(i+1)){
    if(s.at(i) == '1') s.at(i+1) = '0';
    else s.at(i+1) = '1';
    cnt++;
  }
}

cout << cnt << endl;

}


Measured memory_bytes: 3736
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
#include<cctype>
using namespace std;
int main(){
	string w;
	string t;
	cin>>w;
	for(int i=0;i<w.size();i++){w[i]=tolower(w[i]);}
	int count=0;
	while(cin>>t){
		if(t=="END_OF_TEXT")break;
		for(int i=0;i<t.size();i++){t[i]=tolower(t[i]);}
		if(t==w)count++;	
	}
	cout<<count<<endl;
return 0;
}

Measured memory_bytes: 1192
num = int(input())
actions = []
for i in range(num):
    actions.append(list(map(int, input().split())))

dp = [[0 for i in range(3)] for j in range(num)]
for i in range(num):
    if i == 0:
        dp[i][0] = actions[i][0]
        dp[i][1] = actions[i][1]
        dp[i][2] = actions[i][2]
    else:
        dp[i][0] = max(dp[i-1][1] + actions[i][0], dp[i-1][2] + actions[i][0])
        dp[i][1] = max(dp[i-1][0] + actions[i][1], dp[i-1][2] + actions[i][1])
        dp[i][2] = max(dp[i-1][0] + actions[i][2], dp[i-1][1] + actions[i][2])

print(max( dp[num-1][0], dp[num-1][1] ,dp[num-1][2] ))

Measured memory_bytes: 47368
def q3():
    x, N = [int(i) for i in input().split(" ")]
    if N != 0:
        P = set([int(i) for i in input().split(" ")])
    else:
        P = set()

    if x not in P:
        print(x)
        return

    xm = x
    xp = x

    while True:
        xm = xm - 1
        if xm not in P:
            print(xm)
            return
        xp = xp + 1
        if xp not in P:
            print(xp)
            return


q3()

Measured memory_bytes: 9044
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
	ll n;
	cin >> n;
	ll x=1,y=1;
	for(ll i=2;i*i<=n;++i)
	{
		if(n%i==0)x=i;
	}
	cout<<x+n/x-2<<endl;
	return 0;
}

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

int MAX_N = 50010;
int MAX_C = 25;
int main()
{
    int N, M;
    cin >> N >> M;
    int coins[M];
    for (int i = 0; i < M; i++) {
        cin >> coins[i];
    }
    // dp[n][c] := コインcまで見た時にn円払うのに必要な硬貨の最小枚数
    int dp[MAX_N][MAX_C];
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_C; j++) {
            dp[i][j] = 100000;
        }
    }
    dp[0][0] = 0;
    for (int n = 0; n < N + 1; n++) {
        for (int m = 0; m < M; m++) {
            // 新しいコインを使える時
            if (n - coins[m] >= 0) {
                dp[n][m + 1] = min(dp[n][m], dp[n - coins[m]][m + 1] + 1);
            } else {
                dp[n][m + 1] = dp[n][m];
            }
        }
    }
    printf("%d\n", dp[N][M]);
}



Measured memory_bytes: 8096
N, Y = map(int, input().split())
flag = False
for x in range(0, N+1):
    for y in range(0, N-x+1):
        z = N-x-y
        if 10000*x+5000*y+1000*z==Y:
            print("{0} {1} {2}".format(x, y, z))
            flag = True
            break
    if flag:
        break
if not flag:
    print("-1 -1 -1")


Measured memory_bytes: 3064
import sys
input=sys.stdin.readline
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
#points=[tuple(map(int,input().split())) for _ in range(Q)]
score=[0]*N
for i in range(Q):
    point,sc=map(int,input().split())
    score[point-1]=score[point-1]+sc
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
v=0
d=deque()
d.append(v)
#print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")


Measured memory_bytes: 133152
#include <algorithm>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  int K; cin >> K;
  priority_queue<LL, vector<LL>, greater<LL>> que;
  for (int i = 1; i < 10; ++i) {
    que.push(i);
  }

  int n = 1;
  LL x;
  while (n < K) {
    ++n;
    x = que.top(); que.pop();
    LL r = x % 10;
    x *= 10LL;
    if (r != 0) {
      que.push(x + r - 1);
    }

    que.push(x + r);

    if (r != 9) {
      que.push(x + r + 1);
    }
  }
  cout << que.top() << endl;
}


Measured memory_bytes: 2420
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

void datasets(int h, int w) {
    
    char table[h][w];
    rep(i, h) rep(j, w) cin >> table[i][j];
    queue<pii> q;
    int sum = 1;
    rep(i, h) rep(j, w) if (table[i][j] == '@') {q.push({i, j}); table[i][j] = 'r';}
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        rep(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if (table[ny][nx] == '#' || table[ny][nx] == 'r') continue;
            q.push({ny, nx});
            table[ny][nx] = 'r';
            sum++;
        }
    }/*
    rep(i, h) {
        rep(j, w) cout << table[i][j] << " ";
        cout << endl;
    }*/
    cout << sum << endl;
    
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    while (cin >> w >> h && w) {
        datasets(h, w);
    }
}



Measured memory_bytes: 3008
#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005],n,k,dp[100005];
int main()
{
	cin>>n>>k;
	for(int i=0;i<k;i++)
		cin>>a[i]>>b[i];
	for(int i=0;i<=100000;i++)
		dp[i]=1e8;
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<k;j++)
			dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j]);
	}
	int ans=1e9;
	for(int i=n;i<=1e5;i++)
		ans=min(ans,dp[i]);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
import numpy as np

n = int(input())
ans = [0 for _ in range(n+1)]

tmp = int(np.sqrt(n)+1)
for i in range(1, tmp):
    for j in range(1, tmp):
        for k in range(1, tmp):
            v = i**2+j**2+k**2+i*j+i*k+j*k
            if v <= n:
                ans[v]+=1
for a in ans[1:]:
    print(a)


Measured memory_bytes: 27500
#![allow(unused_imports)]
use proconio::input;
use proconio::marker::*;
use std::collections::VecDeque;

fn main() {
  input!{
    n: usize,
    k: usize
  }
  
  let mut result = 0;
  for b in 1..=n {
    let v = if b < k {
      0
    } else {
      b - k
    };
    let p = n % b;
    let pv = if p + 1 < k {
      0
    } else {
      p - k + 1
    };

    let m = n / b;
    let v = m * v + pv;
    result += v;
  }
  
  if k == 0 {
    result -= n;
  }
  
  println!("{}", result);
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

struct edge{
    int from, to; lint cost;
    edge(int f, int t, lint c) : from(f), to(t), cost(c) {}
    edge(int t, lint c) : from(-1), to(t), cost(c) {}
};

struct dijkstra{
    vector<vector<edge> > G;
    vector<lint> d;
    int V, s;
    dijkstra(vector<vector<edge> > _G, int _s) : G(_G), s(_s){
        init();
    }
    void init(){
        V = G.size();
        d = vector<lint>(V, INF);
        priority_queue<P, vector<P>, greater<P> > que; que.push(P(0, s));
        d[s] = 0;
        while(!que.empty()){
            P p = que.top(); que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(int i = 0; i < G[v].size(); i++){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
    int dist(int t){
        return d[t];
    }
};

int main(){
    int n; cin>>n;
    vector<vector<edge>> G(n);
    rep(i,n){
        int u,k; cin>>u>>k;
        rep(j,k){
            lint v,c; cin>>v>>c;
            G[u].push_back(edge(u,v,c));
        }
    }

    dijkstra dij(G, 0);
    rep(v, n){
        outs(v); out(dij.dist(v));
    }
}



Measured memory_bytes: 3148
n = int(input())
numbers = [[0] * 19 for _ in range(19)]
offset = 9
for _ in range(n):
    a = input()
    log2 = 0
    log5 = 0
    if '.' in a:
        b, c = a.split('.')
        log2 -= len(c)
        log5 -= len(c)
        d = int(b + c)
    else:
        d = int(a)
    while d % 2 == 0:
        d //= 2
        log2 += 1
    while d % 5 == 0:
        d //= 5
        log5 += 1
    log2 = min(log2, 9)
    log5 = min(log5, 9)
    numbers[log2 + offset][log5 + offset] += 1

acc = [[0] * 19 for _ in range(19)]

for i in range(17, -1, -1):
    acc[i][-1] = numbers[i][-1] + acc[i + 1][-1]

for j in range(17, -1, -1):
    acc[-1][j] = numbers[-1][j] + acc[-1][j + 1]

for i in range(17, -1, -1):
    for j in range(17, -1, -1):
        acc[i][j] = numbers[i][j] + acc[i + 1][j] + acc[i][j + 1] - acc[i + 1][j + 1]

ans = 0

for i in range(19):
    for j in range(19):
        if numbers[i][j] == 0:
            continue
        log2 = i - offset
        log5 = j - offset
        pi = -log2 + offset
        pj = -log5 + offset
        tmp = acc[pi][pj]
        if pi <= i and pj <= j:
            tmp -= 1
        ans += numbers[i][j] * tmp

ans //= 2
print(ans)


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

int main(){
    ll a,b,n;
    cin>>a>>b>>n;
    ll ans;
    if(n<b){
        ans = (a*n/b)-a*(n/b);
    }else{
        n=b-1;
        ans = (a*n/b)-a*(n/b);
    }
    cout<<ans<<endl;
}

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


int N;
vector<int> x, y, h;


void input() {
    cin >> N;
    x = y = h = vector<int>(N);
    rep(i, N) cin >> x[i] >> y[i] >> h[i];
}


bool solve(pair<ll, ll> &H, ll l, ll r) {
    if (H.second < l || r < H.first) return false;
    H.first = max(H.first, l);
    H.second = min(H.second, r);
    return true;
}


int main() {
    input();
    rep(cx, 101) rep(cy, 101) {
        pair<ll, ll> H = make_pair(1, 1e15);
        bool j = true;
        rep(i, N) {
            int v = max(x[i] - cx, cx - x[i]) + max(y[i] - cy, cy - y[i]);
            ll l, r;
            if (h[i] == 0) {
                l = 1;
                r = v;                
            }
            else l = r = h[i] + v;
            j = solve(H, l, r);
            if (j == false) break;
        }
        if (j && H.first == H.second) {
            printf("%d %d %d\n", cx, cy, H.first);
            return 0;
        }
    }
}


Measured memory_bytes: 256
//============================================================================
// Name        : 0002.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int a,b,ans;
	while(cin>>a>>b){
		a += b;
		ans = 0;
		while( a>0 , ans++ , a/=10);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
int a[2][230];
//int t[100005] , x[100005] , y[100005];
int gcd(int a , int b , int c)
{
		int x = __gcd(a ,b);
		return __gcd(x , c);
}
bool check(string a){
		int i = 0 , j = (int)a.size() - 1;
		while(i < j){
			if(a[i] != a[j])
				return false;
			i++ , j--;
		}
		return true;
}
int main(){
	dhoom;
	int a , b;
	cin >> a >> b;
	int ans = 0;
	for(int i = a ; i <= b ; i++){
		if(check(to_string(i)))
			ans++;
	}
	cout << ans << endl;
	return 0;
	
}


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

ll n;
set<ll> r;

void dfs(string s, bool b3, bool b5, bool b7) {
  if (s.size()) {
    ll a = stoll(s);
    if (a > n) return;
    if (b3 && b5 && b7) r.insert(a);
  }
  dfs(s + "3", true, b5, b7);
  dfs(s + "5", b3, true, b7);
  dfs(s + "7", b3, b5, true);
}

int main() {
  cin >> n;
  dfs("", false, false, false);
  cout << r.size() << endl;
}


Measured memory_bytes: 1536
#include<stdio.h>
#include<stdlib.h>


int main(){
  int n,m,i,j,ans;
  int **A;
  int *b;
  scanf("%d%d",&n,&m);
  A=malloc(n*sizeof(int *));
  for(i=0;i<n;i++){
    A[i]=malloc(m*sizeof(int));}
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      scanf("%d",&A[i][j]);}}
  b=malloc(m*sizeof(int));
  for(i=0;i<m;i++){
    scanf("%d",&b[i]);}
  for(i=0;i<n;i++){
    ans=0;
    for(j=0;j<m;j++){
      ans=ans+ (A[i][j])*(b[j]);}
    printf("%d\n",ans);}
  for(i=0;i<n;i++){
    free(A[i]);}
  free(A);
  return 0;}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// aのb乗(MODした)を返す。
ll modpow(ll a, ll b, ll mod = 1000000007) {
  ll res = 1;
  for (a %= mod; b; a = a * a % mod, b >>= 1)
    if (b & 1) res = res * a % mod;
  return res;
}

// ====================================================================

int main() {
  ll n;
  cin >> n;
  vector<ll> v(n);
  for (ll i = 0; i < n; i++) { cin >> v[i]; }
  sort(v.begin(), v.end());

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ll r = n - i - 1;                                // 右側の個数
    ans += modpow(2, 2 * (n - 1) + 1) * v[i] % MOD;  // 自分が見てるところ
    ans %= MOD;
    ans += r * modpow(2, 2 * (n - 2) + 2) % MOD * v[i] % MOD;  // 自分より右側のぶん
    ans %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
/*---> 21 April 2020 <--- > 04:42:50 <---*/
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e12+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
const int N=1e2+5;
int n,W;
int v[N],w[N],dp[N][100001];
int solve(int ind,int V){
    if(V<0)
        return inf;
    int &ans=dp[ind][V];
    if(ans!=-1)
        return ans;
    if(ind==n){
        if(V==0)
            return ans=0;
        else
            return ans=inf;
    }
    else
        return ans=min(w[ind]+solve(ind+1,V-v[ind]),solve(ind+1,V));
}
int32_t main(){__
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    memset(dp,-1,sizeof dp);
    for(int i=100000;i>=0;i--){
        if(solve(0,i)<=W)
            return cout<<i<<"\n",0;
    }
return 0;
}

Measured memory_bytes: 82304
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ans = 0
    for a in range(1, n):
        b = n // a
        if n % a == 0:
            b -= 1
        ans += b
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 81436
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   998244353
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}

//=============================================ASIFAZAD==============================================//

struct scr
{
    int a, b, c, d;
};

scr ck[60];
vi sq(20);
int n,m, q, ans;

void dfs(int num, int pos)
{
    if(pos >= n)
    {
        int ac = 0;
        for(int i = 0; i < q; i++)
            if(sq[ck[i].b] - sq[ck[i].a] == ck[i].c)
                ac+= ck[i].d;
        ans =  max(ans, ac);
        return;
    }
    sq[pos] = num;
    for(int j = num; j <= m; j++)
        dfs(j, pos + 1);
}

int32_t main()
{
    io;
    cin>>n>>m>>q;
    for(int i = 0; i< q; i++)
    {
        cin>>ck[i].a >>ck[i].b>>ck[i].c >>ck[i].d;
        ck[i].a--;
        ck[i].b--;
    }
    for(int i = 1; i <= m; i++)
        dfs(i, 0);
    cout<<ans;
    return 0;
}



Measured memory_bytes: 3620
n = gets.to_i
1.upto(n) do |i|
	if i%3 == 0 then
		print(" #{i}")
	else
		x = i
		while x!=0 do
			if x%10==3 then
				print(" #{i}")
				break
			end
			x/=10
		end
	end
end
puts


Measured memory_bytes: 6856
#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() {
  string s;
  cin >> s;
  if (s.find("7") != string::npos) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3612
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;

const int L=1e6;
LL sum[L];
LL A[L];
P B[L][4];
int N;
int main() {
	cin >> N;
	for(int i=0;i<(1<<N);i++){
		cin >> A[i];
	}
	B[0][0]=B[0][1]=P(A[0],0);
	LL r=0;
	for(int k=1;k<(1<<N);k++){
		B[k][0]=P(A[k],k);
		int s=1;
		for(int i=0;i<N;i++){
			if(k&(1<<i)){
				for(int j=0;j<2;j++){
					B[k][s+j]=B[k^(1<<i)][j];
				}
				sort(B[k],B[k]+s+2,greater<P>());
				s=unique(B[k],B[k]+s+2)-B[k];
			}
		}
		
		r=max(r,B[k][0].first + B[k][1].first);
		cout << r << endl;
	}

	return 0;
}



Measured memory_bytes: 25600
use std::io::*;
use std::str::FromStr;

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

fn main(){
    let x: i64 = read();
    let n: usize = read();

    let mut v: Vec<bool> = (0..102).map(|_| false).collect();

    for _ in 0..n {
        let a: usize = read::<usize>();
        v[a] = true;
    }

    for i in 0..102 {
        if x - i >= 0 && !v[(x - i) as usize] {
            println!("{}", x - i);
            return;
        } else if x - i < 0 {
            println!("{}", x - i);
            return;
        }
        if x + i < 102 && !v[(x + i) as usize] {
            println!("{}", x + i);
            return;
        } else if x + i >= 102 {
            println!("{}", x + i);
            return;
        }
    }
}


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

int imosu[30][100002];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, C; cin >> N >> C;
	for(int i = 0; i < N; i++){
		int s, t, c; cin >> s >> t >> c;
		imosu[c-1][s]++;
		imosu[c-1][t]--;
	}
	int ans = 0;
	for(int i = 1; i < 100001; i++){
		int cnt = 0, pre = 0;
		for(int j = 0; j < C; j++){
			imosu[j][i] += imosu[j][i-1];
			cnt += (imosu[j][i]||imosu[j][i-1]);
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12032
#include <iostream>

using namespace std;

int main (){
  int c[3][3];
  for(int i=0;i<3;i++){
    cin >> c[i][0] >> c[i][1] >> c[i][2];
  }
  bool row;
  bool col;

  int buf1[3];
  int buf2[3];

  for(int i=0;i<3;i++){
    buf1[i] = c[i][0] - c[i][1];
    buf2[i] = c[i][0] - c[i][2];
  }

  row = ((buf1[0] == buf1[1] && buf1[0] == buf1[2])
	 &&
	 (buf2[0] == buf2[1] && buf2[0] == buf2[2]));

  for(int j=0;j<3;j++){
    buf1[j] = c[0][j] - c[1][j];
    buf2[j] = c[0][j] - c[2][j];
  }

  col = ((buf1[0] == buf1[1] && buf1[0] == buf1[2])
	 &&
	 (buf2[0] == buf2[1] && buf2[0] == buf2[2]));

  if(row && col){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  // for(int i=0;i<3;i++){
  //   cout << c[i][0] << " " << c[i][1] << " " << c[i][2] << endl;
  // }

  return 0;
}


Measured memory_bytes: 256
const input=require('fs').readFileSync('/dev/stdin', 'utf8').split(/[\s]/);const nin=()=>{const r = input[0];input.shift();return Number(r)};const nrin=(n)=>{const a:number[]=[];rep(n,()=>a.push(nin()));return a};const sin=()=>{const r = input[0];input.shift();return String(r)};const out=(...a)=>{console.log(...a)};const floor=(a)=>{return Math.floor(a)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const rep=(n, callback)=>{for(let i = 0;i < n; i++){callback()}};const strrep=(s, i, v)=>{return s.slice(0, i)+v+s.slice(i+1);};const permutation=({result=[],pre=[],post,n=post.length})=>{if(n>0){post.forEach((_,i)=>{const rest=[...post];const elem=rest.splice(i, 1);permutation({result, pre: [...pre,...elem],post:rest,n:n-1})})}else{result.push(pre)}return result};const sw=(s,a:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<a.length;i+=2){if(op==='=='){if(s==a[i])return a[i+1]}else if(op==='>='){if(s>=a[i])return a[i+1]}else if(op==='<='){if(s<=a[i])return a[i+1]}else if(op==='>'){if(s>a[i])return a[i+1]}else if(op==='<'){if(s<a[i])return a[i+1]}}return a[a.length-1];};const or=(a,...b)=>{for(let i=0;i<b.length;i++)if(a==b[i])return true;return false};const maxindex=(...a)=>{return a.indexOf(Math.max.apply(null,a))};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const ceil=a=>{return Math.ceil(a)};const srin=s=>{const a:string[]=[];rep(s,()=>a.push(sin()));return a};let ssinteger=-1;const ssin=()=>{ssinteger++;return input[0][ssinteger]};
const main = ()=>{
  let[a,b,c]=nrin(3)
  out(c>=a&&c<=b?'Yes':'No')
}
main()


Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(ll i = a; i <= (n); ++i)
#define repD(i, a, n) for(ll i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (long long) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define MAXN 5000000
const long double PI = 3.141592653589793238462643383;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long int> vll;
typedef vector<double> vd;
typedef vector<pii> vii;
const long long mod = 1000000007;
int Ceil(int a, int b){
    if(a%b==0) return a/b;
    else return (a/b)+1;
}
int main(){
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);   
    freopen("output.txt", "w", stdout);
    #endif
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int n;
    cin>>n;
    string s;
    cin>>s;
    ll ans = 0;
    vector<ll> red(n+1,0);
    vector<ll> green(n+1,0);
    vector<ll> blue(n+1,0);
    for(int i = n-1;i>=0;i--){
        if(s[i]=='R')
        red[i]++;
    else if(s[i]=='G')
        green[i]++;
    else if(s[i]=='B')
        blue[i]++;
    blue[i]+= blue[i+1];
    red[i]+= red[i+1];
    green[i]+= green[i+1];
    }
    for(int i = 0;i<n;i++){
        for(int j= i+1;j<n;j++){
            if(s[i]=='R' && s[j]=='B'){
                ans+= green[j+1];
                if((2*j-i)<n && s[2*j-i]=='G')
                    ans--;
            }
            else if(s[i]=='R' && s[j]=='G'){
                ans+= blue[j+1];
                if((2*j-i)<n && s[2*j-i]=='B')
                    ans--;
            }
            else if(s[i]=='G' && s[j]=='B'){
                ans+= red[j+1];
                if((2*j-i)<n && s[2*j-i]=='R')
                    ans--;
            }
            else if(s[i]=='B' && s[j]=='R'){
                ans+= green[j+1];
                if((2*j-i)<n && s[2*j-i]=='G')
                    ans--;
            }
            else if(s[i]=='G' && s[j]=='R'){
                ans+= blue[j+1];
                if((2*j-i)<n && s[2*j-i]=='B')
                    ans--;
            }
            else if(s[i]=='B' && s[j]=='G'){
                ans+= red[j+1];
                if((2*j-i)<n && s[2*j-i]=='R')
                    ans--;
            }

        }
    }
    cout<<ans;
return 0;
}

Measured memory_bytes: 3696
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::string S; std::cin >> S;
  if ( N % 2 == 1 ) {
    std::cout << "No" << std::endl;
    return 0;
  }
  else {
    int n = N/2;
    std::string s = S.substr(0,n) + S.substr(0,n);
    if ( S == s ) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,a,b,max=0,tmp;
  int imos[100003]={};
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    imos[a]++;
    imos[b+1]--;
  }
  for(int i=1;i<=n+1;i++){
    imos[i]=imos[i]+imos[i-1];
  }
  for(int i=0;i<=n;i++){
    if(imos[i+1]<i) continue;
    if(imos[i+1]>i)imos[i+1]=i;
    max=(imos[i+1]<max)?max:imos[i+1];
  }
  cout << max<<endl;
}



Measured memory_bytes: 3480
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    set<char> se;
    for(auto c : s){
        se.insert(c);
    }
    
    if(se.size()==2){
        int cnt=0;
        for(auto c : s){
            if(s[0] == c) cnt++;
        }
        if(cnt==2) cout << "Yes" << endl;
        else cout << "No" << endl;
            }
    else{
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
using namespace std;
int gap[100001];
int main(){
	int v,n,k,a,b;
	cin>>v;
	for(int u=0;u<v;u++){
		cin>>n>>k>>b;
		for(int i=1;i<n;i++){
			cin>>a;
			gap[i-1]=a-b;
			b=a;
		}
		sort(gap,gap+n-1);
		int ans=0;
		for(int i=0;i<n-k;i++)ans+=gap[i];
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1564
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		List<Integer> aList = Arrays.asList(sc.nextLine().split(" ")).stream().map(Integer::parseInt).sorted(Comparator.reverseOrder()).collect(Collectors.toList());
		Integer alice = 0;
		Integer bob = 0;
		for(int i=0; i< aList.size(); i++) {
			alice += aList.get(i);
			i++;
			if(i < aList.size()) {
				bob += aList.get(i);
			}
		}
		System.out.println(alice - bob);
	}
}


Measured memory_bytes: 29636
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;

 
int main(void){
    string a,b;
    string s="",t="";
    cin>>a>>b;
    int x = a[0]-'0';
    int y =b[0]-'0';
    for(int i=0;i<y;i++){
        s+=a;
    }
    for(int i=0;i<x;i++){
        t+=b;
    }
    if(s>t)cout<<t<<endl;
    else cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
using namespace std;
int line[101];
int main()
{
	int n;
	cin >> n;
	int sum=0;
	for(int i=1;i<=n;i++)
		scanf("%d", &line[i]);
	for(int i=1;i<=n;i++)
		sum+=line[i];
	int ave=round(sum*1.0/n);
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=(line[i]-ave)*(line[i]-ave);
	cout << ans;

		

	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int A,B,C,X,Y;
	cin >> A >> B >> C >> X >> Y;
	int r = 1<<30;
	for (int n = 0; n <= max(X,Y); ++ n) {
		int rr = n*2*C + max(0, X-n)*A + max(0, Y-n)*B;
		r = min(r, rr);
	}
	cout << r << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		//データ入力の準備
		Scanner sc = new Scanner(System.in);
		
		while(true){
			//データ入力
			int mid = sc.nextInt();
			int fin = sc.nextInt();
			int re = sc.nextInt();
			
			//終了条件の判定
			if(mid == -1 && fin == -1 && re == -1){
				break;
			}
			
			//試験を受けたかどうか分岐
			if (mid == -1 || fin == -1){
				System.out.println('F');
			}else{
				//成績の条件分岐
				int sum = mid + fin;
				
				if (sum >= 80){
					System.out.println('A');
				}else if (65 <= sum && sum < 80){
					System.out.println('B');
				}else if (50 <= sum && sum < 65){
					System.out.println('C');
				}else if (30 <= sum && sum < 50){
					if (re >= 50){
						System.out.println('C');
					}else{
						System.out.println('D');
					}
				}else{
					System.out.println('F');
				}
			}
		}
	}
}


Measured memory_bytes: 26268
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
const int INF = 1e7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define trep(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main()
{
    int a, b, n;
    cin >> n >> a >> b;
    int ans = 0;
    trep(i, 1, n + 1)
    {
        int j = i;
        int cc = 0;
        while (j != 0)
        {
            cc += j % 10;
            j /= 10;
        }
        if (cc >= a && cc <= b)
        {
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <algorithm>
#define ll long long
#include <unordered_map>
using namespace std;
 
int main() {
  vector<ll> x(5);
  for(ll i = 1; i <= 5; i++) {
    cin >> x.at(i - 1);
    if(x.at(i - 1) == 0) {
      cout << i << endl;
      break;
    }
  }
}

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

int main(){
  string c;
  cin >> c;
  if(c == "a"||c=="i"||c=="u"||c=="e"||c=="o"){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 256
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7


a, b, c, d = MAP()

while True:
    c -= b
    if c <=0:
        print('Yes')
        break
    a-=d
    if a <= 0:
        print('No')
        break
    

Measured memory_bytes: 72596
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::io::Read;
use std::io::{stdout, BufWriter, Write};
 
fn main() {
    let mut buf = String::new();
    
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
 
    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
 
    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();
 
    let a: i64 = iter.next().unwrap().parse().unwrap();
    let p: i64 = iter.next().unwrap().parse().unwrap();
            
    write!(out, "{}", (a * 3 + p) / 2);
 
}

Measured memory_bytes: 4352
//by Sshwy
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=5005,P=1e9+7;

int n;
vector<int> T[N];

int sz[N];
int f[N][N][2];//f[i,j,0/1]表示第i个点的子树，i所在的连通块大小为j，被割掉的边的奇偶性 的容斥贡献。
//转移的时侯在割边时才统计与i连通的部分的贡献。
int g[N];//g[i]表示有i个点的配对方案
int t[N][2];

void add(int &x,int y){x=(x+y)%P;}
void dfs(int u,int p){
    for(int v:T[u])if(v!=p)dfs(v,u);

    //printf("\033[32mdfs(%d,%d)\033[0m\n",u,p);
    sz[u]=1;
    f[u][1][0]=1;//方案数为1

    for(int v:T[u])if(v!=p){
        //printf("v = %d\n",v);
        memset(t,0,sizeof(t[0])*(sz[u]+sz[v]+1));
        //不割边
        FOR(i,1,sz[u]){
            FOR(j,1,sz[v]){
                add(t[i+j][0],1ll*f[u][i][0]*f[v][j][0]%P);
                add(t[i+j][0],1ll*f[u][i][1]*f[v][j][1]%P);
                add(t[i+j][1],1ll*f[u][i][0]*f[v][j][1]%P);
                add(t[i+j][1],1ll*f[u][i][1]*f[v][j][0]%P);
            }
        }
        //割边
        FOR(i,1,sz[u]){
            FOR(j,1,sz[v]){
                add(t[i][0],1ll*f[u][i][0]*f[v][j][1]%P*g[j]%P);
                add(t[i][0],1ll*f[u][i][1]*f[v][j][0]%P*g[j]%P);
                add(t[i][1],1ll*f[u][i][1]*f[v][j][1]%P*g[j]%P);
                add(t[i][1],1ll*f[u][i][0]*f[v][j][0]%P*g[j]%P);
            }
        }
        memcpy(f[u],t,sizeof(t[0])*(sz[u]+sz[v]+1));
        sz[u]+=sz[v];
        /*FOR(i,1,sz[u]){
            if(f[u][i][0])printf("f[%d,%d,%d]=%d\n",u,i,0,f[u][i][0]);
            if(f[u][i][1])printf("f[%d,%d,%d]=%d\n",u,i,1,f[u][i][1]);
        }*/
    }
    /*printf("\033[33m");
    FOR(i,1,sz[u]){
        if(f[u][i][0])printf("f[%d,%d,%d]=%d\n",u,i,0,f[u][i][0]);
        if(f[u][i][1])printf("f[%d,%d,%d]=%d\n",u,i,1,f[u][i][1]);
    }
    printf("\033[0m");*/
}
int main(){
    scanf("%d",&n);
    FOR(i,1,n-1){
        int u,v;
        scanf("%d%d",&u,&v);
        T[u].pb(v),T[v].pb(u);
    }

    g[2]=1;
    FOR(i,2,n/2)g[i*2]=g[i*2-2]*(i*2-1ll)%P;
    //FOR(i,1,n)printf("g[%d]=%d\n",i,g[i]);
    
    dfs(1,0);
    int ans=0;
    FOR(i,1,n){
        if(f[1][i][0])add(ans,f[1][i][0]*1ll*g[i]%P);
        if(f[1][i][1])add(ans,-f[1][i][1]*1ll*g[i]%P);
    }
    add(ans,P);
    printf("%d\n",ans);

    return 0;
}


Measured memory_bytes: 195456
//
//  main.cpp
//  CoderTest
//
//  Created by yuya on 2019/07/25.
//  Copyright © 2019 yuya. All rights reserved.
//

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


int main()
{
    int N;
    cin >> N;
    
    int base = 26;
    ll val;
    char c;
    vector<int> s(10);
    
    vector<ll> vec(0);
    for(int i=0;i<N;i++)
    {
        val = 0;
        for(int j=0;j<10;j++)
        {
            cin >> c;
            s[j] = c - 'a';
        }
        sort(s.begin(), s.end());
        for(int j=0;j<10;j++)
        {
            val += s[j] * pow(base, j);
        }
        vec.push_back(val);
    }
    sort(vec.begin(), vec.end());
    
    ll cnt = 0;
    ll seq = 1;
    for(int i=0;i<vec.size();i++)
    {
//        cout << vec[i]  << endl;
        if(i < vec.size() - 1 && vec[i] == vec[i+1])
        {
            seq++;
        }
        else
        {
            cnt += seq * (seq - 1) / 2;
            seq = 1;
        }
    }
    
    cout << cnt << endl;
    
    
    return 0;
}


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

using namespace std;

int H, W;
string a[301][301];

int main() {
  while(1){
    cin >> H >> W;
    if(H == 0 && W == 0) break;
    for(int i = 0; i < H*W; i++){
      int x = i%W;
      int y = i/W;
      a[y][x] = "#";
      cout << a[y][x];
      if(x == W-1) cout << endl;
    }
    cout << endl;
  }
}

Measured memory_bytes: 5024
n=int(input())
d=list(map(int,input().split()))
freq=[0]*(10**5+3)
for i in d:
    freq[i]+=1
ans=0
su=0
for i in range(1,10**5+1):
    su+=freq[i]
    if 2*su==n:
        ans+=1
print(ans)


Measured memory_bytes: 14396
#include <vector>
#include <cstdio>
using namespace std;
 
int main() {
  int n;
  vector<int> S;
  while (scanf("%d", &n) != EOF) {
    if (n == 0) {
      printf("%d\n", S.back());
      S.pop_back();
    } else {
      S.push_back(n);
    }
  }
}

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, d, x;
  cin >> n >> d >> x;
  vi a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= d; j += a[i]) {
      ans++;
    }
  }
  cout << ans + x << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C;
  cin>>A>>B>>C;
  
  if((A+B+C)%2!=0){
    cout<<"No"<<endl;
  }
  else{

  
  int ans=(A+B+C)/2;
  
  if(ans==A||ans==B||ans==C){
    cout<<"Yes"<<endl;
  }
else{
  cout<<"No"<<endl;
}
  }
}


Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
const double PI = acos(-1);

int main() {
	int x, k;
	cin >> x >> k;
	int r[100000];
	for (int i = 0; i < k; i++) {
		cin >> r[i];
	}
	int q;
	cin >> q;
	int t[100000], a[100000];
	for (int i = 0; i < q; i++) {
		cin >> t[i] >> a[i];
	}
	int L = 0, R = x;
	int j = 0, p = 0, d = 0;
	int lv = 0, uv = x;
	for (int i = 0; i < q; i++) {
		while (j < k&&r[j] <= t[i]) {
			if (j % 2 == 0) {
				p += r[j] - d;
				lv = max(lv - (r[j] - d), 0);
				uv = max(uv - (r[j] - d), 0);
			}
			else {
				p -= r[j] - d;
				lv = min(lv + (r[j] - d), x);
				uv = min(uv + (r[j] - d), x);
			}
			L = max(L, p);
			R = min(R, x + p);
			d = r[j++];
		}
		int c;
		if (L <= a[i] && a[i] <= R) c = a[i] - p;
		if (a[i]<L) c = lv;
		if (R<a[i]) c = uv;
		if (j % 2 == 0) c = max(c - (t[i] - d), 0);
		else c = min(c + (t[i] - d), x);
		cout << c << endl;
	}
}


Measured memory_bytes: 2432