akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using P = pair<int,int>;
using ll = long long;
static const int INF = 1000000000;
static const ll MOD = 1000000007;

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	ll n, k;
	cin >> n >> k;
	vector<P> tmp;
	rep(i, n){
		int a, b;
		cin >> a >> b;
		tmp.push_back(P(a, b));
	}
	sort(tmp.begin(), tmp.end());
	
	rep(i, n){
		k -= tmp[i].second;
		if(k <= 0){
			cout << tmp[i].first << endl;
			return 0;
		}
	}
	return 0;
}



Measured memory_bytes: 1400
#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()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

template <typename T1, typename T2>
inline void chmin(T1& a, T2 b) {
    if (a > b) a = b;
}

template <typename T>
vector<T> compress(vector<T> vec) {
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

template <typename T>
map<T, int> dict(vector<T>& vec) {
    map<T, int> res;
    for (int i = 0; i < (int)vec.size(); i++) {
        res[vec[i]] = i;
    }
    return res;
}

signed main() {
    int n, K;
    cin >> n >> K;
    vector<ll> h(n);
    rep(i, n) {
        cin >> h[i];
    }
    h.emplace_back(0);
    auto c = compress(h);
    auto d = dict(c);
    int m = d.size();
    ll dp[n + 1][m + 1][K + 1];
    fill(dp[0][0], dp[n + 1][0], LINF);
    dp[0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= K; k++) {
                if (k < K) chmin(dp[i + 1][j][k + 1], dp[i][j][k]);
                chmin(dp[i + 1][d[h[i]]][k],
                      dp[i][j][k] + max(0LL, h[i] - c[j]));
            }
        }
    }
    ll ans = LINF;
    for (int j = 0; j < m; j++) {
        for (int k = 0; k <= K; k++) {
            chmin(ans, dp[n][j][k]);
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    for (char c : s) {
        if (c == 'S') {
            st.push(c);
        }
        else {
            if (st.size() > 0 and st.top() == 'S') {
                st.pop();
            }
            else {
                st.push(c);
            }
        }
    }
    cout << st.size() << endl;
}


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

int main(){
  int n;
  string a;
  cin >> n >> a;
  
  int k=n;
  
  for(int i=0;i<n-1;i++){
    if(a.at(i)==a.at(i+1))
      k--;
  }
  cout << k << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>

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

int res[100][100];

int main() {
    int H, W; cin >> H >> W;
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
 
    int k = 0;
    for (int i = 0; i < H; i++) {
        if (i % 2 == 0) 
        for (int j = 0; j < W; j++) {
            res[i][j] = k+1;
            a[k]--;
            if (a[k] == 0) k++;
        }
        else 
        for (int j = W-1; j >= 0; j--) {
            res[i][j] = k+1;
            a[k]--;
            if (a[k] == 0) k++;
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << res[i][j] << " ";
        } cout << endl;
    }
}


Measured memory_bytes: 384
n=input()
for _ in [0]*n:
  i,b,c=0,0,0
  while i<3:
    s="IOU".index(raw_input()[1])
    if s==0:
      if b==3: c+=1
      else: b+=1
    elif s==1:
      c+=b+1
      b=0
    elif s==2: i+=1
  print c

Measured memory_bytes: 4208
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = 0

for i, ai in enumerate(a):
    sum += b[ai-1]
    try:
        if a[i] == a[i+1] -1:
            sum += c[ai-1]
    except:
        break
print(sum)

Measured memory_bytes: 3064
m=input()
round = len(m)

n = 0

for i in range(round):
    if i % 2 == 0:
        if m[i] == '0':
            n = n+1
            
    else:
        if m[i] =='1':
            
            n = n+1

if n>round/2:
    print(round-n)
else:
    print(n)

Measured memory_bytes: 3188
#include <iostream>
#include <cmath>

using namespace std;

int main () {
    int n, k;

    cin >> n;
    cin >> k;

    int ans = 1;

    for (int i = 0; i < n; i++) {
        if (k > pow(2, (double)i)) {
            ans *= 2;
        }
        else {
            ans += k;
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 256
S = list(input())
ACGT = set(["A","C","G","T"])
ans = 0
acgt_length = 0

for i in range(len(S)):
  if S[i] in ACGT:
    acgt_length += 1
  else:
    ans = max(ans,acgt_length)
    acgt_length = 0
    
ans = max(ans,acgt_length)

print(ans)

Measured memory_bytes: 3060
#![allow(unused_imports)]
// use itertools::Itertools;
use proconio::{input, marker::*};

fn main() {
    input! {
        n: usize,
        llrr: [(usize, usize); n]
    };
    let sum = llrr.iter().fold(0, |acc, &(l, r)| acc + r - l + 1);
    println!("{}", sum);
}


Measured memory_bytes: 2148
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int GCD(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   if(_a % _b == 0){
      return _b;
   }
   else{
      return GCD(_b, _a % _b);
   }
}

int LCM(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   return (_a*_b)/(GCD(_a, _b));
}

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

   cout << s[0] << s.size()-2 << s[s.size()-1] << endl;

   return 0;
}

Measured memory_bytes: 256
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

points = [k-q] * n
ans = []
for i in a:
    points[i-1] += 1

for i in range(n):
    if points[i] <= 0:
        ans.append("No")
    else:
        ans.append("Yes")

print("\n".join(ans))


Measured memory_bytes: 61528
package main

/*
全探索.
*/

import (
	"bufio"
	"bytes"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func solve(k int, ms []int) bool {
	return solveK(k, 0, 0, ms)
}

func solveK(k, sum, idx int, ms []int) bool {
	if sum == k {
		return true
	}
	if sum > k {
		return false
	}
	if idx >= len(ms) {
		return false
	}
	return solveK(k, sum+ms[idx], idx+1, ms) || solveK(k, sum, idx+1, ms)
}

func isAssembleK(k int, ms []int) bool {
	for i, m := range ms {
		if k == m {
			return true
		}
		if m < k {
			if isAssembleK(k-m, ms[i+1:len(ms)]) {
				return true
			}
		}
	}
	return false
}

// func solve(k int, ms []int) bool {
// 	for i := range ms {
// 		if isAssembleK(k, ms[i:len(ms)]) {
// 			return true
// 		}
// 	}
// 	return false
// }
//
// func isAssembleK(k int, ms []int) bool {
// 	for i, m := range ms {
// 		if k == m {
// 			return true
// 		}
// 		if m < k {
// 			if isAssembleK(k-m, ms[i+1:len(ms)]) {
// 				return true
// 			}
// 		}
// 	}
// 	return false
// }

func main() {
	scanner := makeScanner(8192)
	eGetInt(scanner)
	ms := eGetInts(scanner)
	eGetInt(scanner)
	qs := eGetInts(scanner)
	for _, q := range qs {
		if solve(q, ms) {
			fmt.Println("yes")
		} else {
			fmt.Println("no")
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(max int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), max)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	var ints []int
	for _, f := range fields {
		ints = append(ints, eAtoi(f))
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

type ints []int

func (s ints) String() string {
	var buf bytes.Buffer
	sep := ""
	for _, v := range s {
		buf.WriteString(fmt.Sprintf("%s%d", sep, v))
		sep = " "
	}
	return buf.String()
}

func reverse(a ints) ints {
	r := make(ints, len(a))
	for i := 0; i < len(a); i++ {
		r[i] = a[len(a)-1-i]
	}
	return r
}
func max(a ints) (int, bool) {
	if len(a) == 0 {
		return 0, false
	}
	m := a[0]
	for _, e := range a {
		if e > m {
			m = e
		}
	}
	return m, true
}
func sum(a ints) int {
	if len(a) == 0 {
		return 0
	}
	sum := 0
	for _, e := range a {
		sum += e
	}
	return sum
}



Measured memory_bytes: 1184
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int k = sc.nextInt();
    for(int i = a; i <= b; i++){
      if(i < a + k || b - k + 1 <= i){
        System.out.println(i);
      }
    }
  }
}

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

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

    vector<double> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

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

    for (int i = 0; i < n - 1; i++) {
        v[i+1] = (v[i] + v[i+1]) / 2;
    }

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

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < n; i++)
#define P pair<ll, ll>

typedef vector<ll> vec;
typedef vector<vec> mat;

int main(){
    ll n;
    cin >> n;
    ll a[n];
    rep(i, n) cin >> a[i];
    ll ans = 0;
    ll mx = 0;
    rep(i, n){
        if(mx > a[i]){
            ans += mx - a[i];
        }else{
            mx = a[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5140
import itertools

n, k = map(int,input().split())
s = input()
seq = []

if s[0] == '0':
    seq.append(0)

i = 1
seq_cnt = 1
while i != n:
    if s[i] != s[i-1]:
        seq.append(seq_cnt)
        seq_cnt = 1
    else:
        seq_cnt += 1
    i += 1

seq.append(seq_cnt)
if s[-1] == '0':
    seq.append(0)

b = [0] + list(itertools.accumulate(seq))

ans = 0
for left in range(0, len(b), 2):
    right = left + 2*k + 1
    if right >= len(b):
        right = len(b)-1

    ans = max(ans, b[right] - b[left])

print(ans)


Measured memory_bytes: 8700
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
typedef long long int lli;
using namespace std;

int main(){
	string str;
	while(cin>>str&&str!="0"){
		map<string,int> d;
		queue<string> que;
		que.push(str);
		d[str]=0;
		int flag1=true;
		while(que.size()){
			string tmp=que.front();
			que.pop();
			int flag2=true;
			char a=tmp[0];
			for(int i=1; i<tmp.size(); ++i){
				if(a!=tmp[i]) {
					flag2=false;
					break;
				}
				a=tmp[i];
			}
			if(flag2){
				cout << d[tmp] << "\n";
				flag1=false;
				break;
			}
			for(int i=0; i+1<tmp.size(); ++i){
				if(tmp[i]!=tmp[i+1]){
					string nstr=tmp;
					if(tmp[i]!='r'&&tmp[i+1]!='r'){
						nstr[i]='r';
						nstr[i+1]='r';
					} else if(tmp[i]!='g'&&tmp[i+1]!='g'){
						nstr[i]='g';
						nstr[i+1]='g';
					} else if(tmp[i]!='b'&&tmp[i+1]!='b'){
						nstr[i]='b';
						nstr[i+1]='b';
					}
					if(nstr[i]==nstr[i+1]&&d.count(nstr)==0){
						que.push(nstr);
						d[nstr]=d[tmp]+1;
					}
				}
			}
		}
		if(flag1) cout << "NA\n";
	}
	return 0;
}

Measured memory_bytes: 2884
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();    
        int N = r.i();
        int[] s = r.ii(N);
        int x = 0;
        for(int t : s)
            x += t;
        if(x%10 == 0){
            int min = x;
            for(int t : s)
                if(t%10 > 0 && t < min)
                    min = t;
            x -= min;
        }
        println(x);
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        int[] ii(int N) throws IOException{
            int[] ii = new int[N];
            for(int i = 0; i < N; i++) ii[i] = i();
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll p;

vector<ll> fact(3000);
vector<ll> finv(3000);

typedef vector<ll> poly;

poly mul(const poly& x, ll k){
	poly res(p+1, 0);
	REP(i, p+1){
		if(i == 0) continue;
		res[i] = (x[i-1]-k*x[i]);
		res[i] %= p;
		res[i] += p;
		res[i] %= p;
	}
	res[0] = -k*x[0];
	res[0] %= p;
	res[0] += p;
	res[0] %= p;
	return res;
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

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

    cin >> p;
    vector<ll> a(p);
    REP(i, p) cin >> a[i];

    ll tmp = 1;
    REP(i, 3000){
    	fact[i] = tmp;
    	tmp *= (i+1);
    	tmp %= p;
    }
    REP(i, 3000) finv[i] = modinv(fact[i], p);
    //cout << fact << endl;

    vector<ll> res(p+1, 0), now(p+1, 0);
    now[0] = 1;

    vector<ll> ks(p, 0);
    REP(i, p){
    	ll dif = a[i];
    	REP(j, i){
    		dif -= ks[j] * fact[i] * finv[i-j];
    	}
    	dif = ((dif%p)+p)%p;
    	ll k = dif * finv[i] % p;
    	ks[i] = k;

    	REP(j, p+1){
    		res[j] += k * now[j] % p;
    	}
    	now = mul(now, i);
    }

    REP(i, p) cout << res[i]%p << " ";
    cout << endl;

    return 0;
}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

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

	int f = 0;
	for (int i = 0; i < s.length(); i++)
	{
		f += atoi(s.substr(i, 1).c_str());
	}

	cout << (atoi(s.c_str()) % f == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
d = int(input()) #日にちは-1indexで
c = list(map(int, input().split()))
csum = 0
for i in range(26):
    csum += c[i]
s = [ [] for _ in range(d)]
for i in range(d):
    s[i] = list(map(int, input().split()))
t = [0 for _ in range(d)]
for i in range(d):
    maxp = -2
    for j in range(26):
        if (s[i][j] > maxp):
            maxp = s[i][j]
            t[i] = j
    print(t[i]+1)

Measured memory_bytes: 9388
#include <bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define sz size()
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)

#define ll long long

double sqr(double x) {
	return (double) x*x;
}

int main() {

	int n,d;
	cin>>n>>d;

	int br=0;
	int i;
	for (i=0;i<n;i++) {
		int x,y;
		cin>>x>>y;
		long long rast = (ll)x*x + (ll)y*y;

		// cout<<rast<<"\n";

		if (rast<=(ll)d*d) {
			br++;
		}
	}

	cout<<br<<"\n";


    return 0;
}

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

int group[13] = {0,1,3,1,2,1,2,1,1,2,1,2,1};
int main()
{
    int x, y;
    cin >> x >> y;
    printf("%s",group[x] == group[y]? "Yes":"No");
}

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

using namespace std;

typedef long long ll;
int x[100];


int main(int, char**)
{
	int  n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}

	sort(x, x+n);
	int w = 0;
	for (int i = 0; i < n - 1; ++i) {
		w += x[i];
	}

	if (w > x[n-1])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
import math

def is_prime(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

n = int(input())
counter = 0
for _ in range(n):
    test_num = int(input())
    if is_prime(test_num):
        counter += 1
print(counter)



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

using namespace std;

typedef long long ll;
typedef long double ld;

#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(v) v.begin(),v.end()

const int maxn = 1e5 + 100, maxlg = 30;
const ll inf = 2e18, mod = 1e9 + 7;

int n;
vector<int> graph[maxn];

int solve(int u, int prev = -1)
{
	int cnt[maxlg] = {0}, res = 0;
	for (int i : graph[u])
		if (i != prev)
		{
			int val = solve(i, u);
			for (int j = 0; j < maxlg; j++)
				cnt[j] += ((val >> j) & 1);
		}

	int pos = -1;
	for (int i = 0; i < maxlg; i++)
		if (cnt[i] > 1)
			pos = i;

	for (int i = pos + 1; i < maxlg; i++)
		if (!cnt[i])
		{
			res += (1 << i);
			for (int j = i; j < maxlg; j++)
				if (cnt[j])
					res += (1 << j);
			break;
		}
	
	return res;
}

int highBit(int mask)
{
	for (int i = maxlg - 1; i >= 0; i--)
		if ((mask >> i) & 1)
			return i;
	return -1;
}

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

	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		graph[--u].pb(--v);
		graph[v].pb(u);
	}

	cout << highBit(solve(0)) << endl;
}



Measured memory_bytes: 19456
num = int(input('')) #input()で入力を受け取ってint()で数字型に変換します。

num_100 = num / 100

num_10 = (num % 100) / 10

num_1 = (num % 10)

if int(num_100) == 7:
    print("Yes")
elif int(num_10) == 7:
    print("Yes")
elif int(num_1) == 7:
    print("Yes")
else:
    print("No")




Measured memory_bytes: 9208
def f(x):
	if x!=0:
		return 10-x
	else:
		return x
def g(x):
	if x%10==0:
		return 10
	else:
		return x%10
a=[]
for i in range(5):
	a.append(int(input()))
b=[]
for i in range(5):
	b.append((g(a[i]),i))
c=[]
for i in range(5):
	c.append(f(b[i][0])+a[i])
b.sort()
t=b[0][1]
ans=0
for i in range(5):
	if i !=t:
		ans+=c[i]
ans+=a[t]
print(ans)

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

using namespace std;
typedef long long ll;
const long long mod=1e9+7; //10^9+7

int main() {
    string ss;
    cin >> ss;
    int s[100002];
    int g[100002];

    // R = 0   L = 1

    int n = (int)ss.length();
    for(int i=0; i<n;i++){
        if(ss[i]=='R') s[i] = 0;
        else s[i] = 1;
        g[i]=0;
    }
    s[n] = 0;

    int start = 0;
    int point = 0;
    for(int i=0; i<n;i++){
        if(s[i]==0 && s[i+1]==1) point = i;
        else if(s[i]==1 && s[i+1]==0){
            int end = i;
            for(int j=start; j<=end; j++){
                int dis = abs(point-j);
                if(dis%2 == 0) g[point]++;
                else g[point+1]++;
            }
            start = i+1;
        }
    }

    for(int i=0; i<n;i++){
        cout << g[i] << " ";
    }
    cout << endl;

    return 0;
}


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

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

    int n = s.size();

    bool ans = true;

    for (int i = 0; i < n/2; ++i)
        if (s[i] != s[n-i-1]) ans = false;
    
    for (int i = 0; i < (n - 1)/2; ++i)
        if (s[i] != s[(n - 1)/2-i-1]) ans = false;

    for (int i = (n+3)/2-1; i < n; ++i) 
        if (s[i] != s[n-i-1]) ans = false;

    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}


Measured memory_bytes: 380
n,m=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
a=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    a.union(x-1,y-1)
ans=0
for i in range(n):
    ans=max(ans,a.size(i))
print(ans)

Measured memory_bytes: 14532
N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    if hon + AB[i][1] < M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        continue
    elif hon + AB[i][1] == M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        print(kane)
        break
    else:
        kane += (M - hon) * AB[i][0]
        print(kane)
        break

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

using namespace std;

typedef long long ll;

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

    ll Ans = 0;

    for(int x = 1; x <= n; x++)
        if(x % 3 && x % 5)
            Ans += (ll) x;

    cout << Ans << endl;
}


Measured memory_bytes: 3644
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
int main(){
    
    int N, K;cin >> N >> K;
    double ans = 0;
    
    for(int i = 1;i <= N;i++){
        
        int point = i;
        double probability = 1.0 / N;
        
        while(point < K){
            point *= 2;
            probability /= 2;
        }
        ans += probability;
    }
    printf("%.12f",ans);
}
            


Measured memory_bytes: 256
import java.util.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.ArrayDeque;

class Point{
    int h;
    int w;
    public Point(int x, int y){
        this.h = x;
        this.w = y;
    }
}

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int H = sc.nextInt();
        int W = sc.nextInt();
        char[][] s = new char[H][W];
        int white = 0;

        for(int i=0; i<H; i++){
            s[i] = sc.next().toCharArray();
            for(int j=0; j<W; j++){
                if(s[i][j]=='.'){
                    white++;
                }
            }
        }

        int[] dh = {1, 0, -1, 0};
        int[] dw = {0, 1, 0, -1};

        ArrayDeque<Point> que = new ArrayDeque<>();
        que.add(new Point(0, 0));
        boolean[][] memo = new boolean[H][W];
        memo[0][0] = true;
        int[][] d = new int[H][W];
        d[0][0] = 1;
        while(!que.isEmpty()){
            Point p = que.pop();
            for(int i=0; i<4; i++){
                int h = p.h + dh[i];
                int w = p.w + dw[i];
                if(h>=0 && h<H && w>=0 && w<W){
                    if(s[h][w]!='#' && memo[h][w]!=true){
                        que.add(new Point(h, w));
                        memo[h][w] = true;
                        d[h][w] = d[p.h][p.w] + 1;
                    }
                }
            }
        }
        if(!memo[H-1][W-1]){
            System.out.println(-1);
        }
        else{
            System.out.println(white - d[H - 1][W - 1]);
        }
    }
}

Measured memory_bytes: 22100
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Data{int x,y,dirty,cost;};
enum{CLEAN='.',DIRTY='*',FURNITURE='x',ROBOT='o'};
int main()
{
  int w,h;
  int dx[4]={0,1,0,-1};
  int dy[4]={1,0,-1,0};
  while(cin>>w>>h,w|h){
    queue<Data> q;
    Data start={0,0,0,0},goal={0,0,0,-1};
    vector< vector<char> >field(h,vector<char>(w));
    vector< vector<int> >dirty(h,vector<int>(w,0));
    int num=1;
    for(int i=0;i<h;i++)for(int j=0;j<w;j++){
      cin>>field[i][j];
      if(field[i][j]==DIRTY){
	start.dirty^=(1<<num);
	dirty[i][j]=num;
	num++;
      }
      if(field[i][j]==ROBOT){
	start.x=j;
	start.y=i;
	field[i][j]=CLEAN;
      }
    }

    vector< vector< vector<int> > >visited(h,vector< vector<int> >(w,vector<int>(1<<10,0)));
    q.push(start);
    while(q.size()){
      Data now=q.front();
      q.pop();
      if(visited[now.y][now.x][now.dirty])continue;
      visited[now.y][now.x][now.dirty]=1;
      if(field[now.y][now.x]==DIRTY){
	if(now.dirty&(1<<dirty[now.y][now.x]))
	  now.dirty^=(1<<dirty[now.y][now.x]);
      }
      if(now.dirty==0){
	goal=now;
	break;
      }

      for(int i=0;i<4;i++){
	Data next=now;
	next.x+=dx[i];
	next.y+=dy[i];
	next.cost++;
	if(next.x<0||w<=next.x)continue;
	if(next.y<0||h<=next.y)continue;
	if(field[next.y][next.x]==FURNITURE)continue;
	q.push(next);
      }
    }

    cout<<goal.cost<<endl;
  }
}

Measured memory_bytes: 2536
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};

bool f(string s,string t){
    for (int i = 0; i < min(s.length(), t.length()); i++) {
        if(s[i] < t[i]) return true;
        else if(s[i] > t[i]) return false;
    }
    return true;
}

int main(){
    int n;cin >> n;
    string ss,tt;cin >> ss >> tt;
    if(tt.length() < ss.length()) swap(ss, tt);
    string s = ss,t = tt;
    while(s.length() < n) s += ss;
    while(t.length() < n) t += tt;
    if(!f(s, t)){
        swap(ss,tt);
    }
    for (int i = 0; tt.length() * i <= n; i++) {
        int k = tt.length() * i;
        if((n - k) % ss.length() == 0){
            string ans = "";
            for (int j = 0; j < (n - k) / ss.length(); j++) {
                ans += ss;
            }
            for (int j = 0; j < i; j++) {
                ans += tt;
            }
            cout << ans << endl;
            return 0;
        }

    }
    return 0;
}


Measured memory_bytes: 1800
N,X=map(int,input().split())
a=list(map(int,input().split()))
total=sum(a)
if a[0]>X:
    a[0]=X
for i in range(N-1):
    if a[i]+a[i+1]>X:
        a[i+1]=X-a[i]
print(total-sum(a))

Measured memory_bytes: 14132
#include <stdio.h>
#define MAX 500000
#define S 1000000000


void merge(int *,int, int,int);
void mergeSort(int *,int,int);
int left[MAX/2+2],right[MAX/2+2];
int count,n;

int main(){
  int a[MAX],i;
  
  count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    if(a[i]>=S){
      return 1;
  }
  }
  mergeSort(a,0,n);

  for(i=0;i<n;i++){
    printf("%d",a[i]);
   if(i<n-1){
      printf(" ");
    }
  }
  printf("\n");

  printf("%d\n",count);

  return 0;
}

void merge(int a[],int left2,int mid,int right2){
  int i,j,k,n1,n2;

  n1=mid-left2;
  n2=right2-mid;
  for(i=0;i<n1;i++){
    left[i]=a[left2+i];
  }
  for(i=0;i<n2;i++){
    right[i]=a[mid+i];
  }
  left[n1]=S;
  right[n2]=S;
  i=0;
  j=0;
  for(k=left2;k<right2;k++){
    count++;
    if(left[i]<=right[j]){
      a[k]=left[i];
      i=i+1;
	}
    else{
      a[k]=right[j];
      j=j+1;
    }
  }
}

void mergeSort(int a[],int left,int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(a,left,mid);
    mergeSort(a,mid,right);
    merge(a,left,mid,right);
  }
}



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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    int sx, sy, tx, ty; cin >> tx >> ty >> sx >> sy;

    string path = string(sx - tx, 'L') + string(sy - ty, 'D');
    string rpath = string(sx - tx, 'R') + string(sy - ty, 'U');
    string res = path + rpath + "UL" + path + "DR" + "DR" + rpath + "UL";
    for (char &c : res){
        if (c == 'U') c = 'D';
        else if (c == 'D') c = 'U';
        else if (c == 'L') c = 'R';
        else c = 'L';
    }
    cout << res << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(it,st,en) for(int it=(st);it<(int)(en);++it)
#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;

int n;
vvi bip;
vi vis;

int dfs(int x, int p, vvi& g){
    vi Q;
    for(int y:g[x]) if(y != p)
        Q.pb(dfs(y,x,g));
    g[x] = move(Q);
    rep(j,0,g[x].size()/2){
        bip[g[x][2*j+0]].pb(g[x][2*j+1]);
        bip[g[x][2*j+1]].pb(g[x][2*j+0]);
    }
    return g[x].size()%2 ? g[x].back() : x;
}

void d(int x, int col = 1){
    if(vis[x]) return;
    vis[x] = col;
    for(int y:bip[x]) d(y,-col);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    vi a(n),b(n);
    vvi ga(n), gb(n);
    int ra = -1, rb = -1;
    rep(i,0,n){ cin>>a[i]; --a[i]; if(a[i]>=0) ga[a[i]].pb(i); else ra = i; }
    rep(i,0,n){ cin>>b[i]; --b[i]; if(b[i]>=0) gb[b[i]].pb(i); else rb = i; }
    rep(i,0,n){
        if(ga[i].size()%2 != gb[i].size()%2){
            cout<<"IMPOSSIBLE"<<endl;
            return 0;
        }
    }
    bip.resize(n);
    vis.resize(n,0);
    dfs(ra,-1,ga);
    dfs(rb,-1,gb);

    rep(i,0,n) if(!vis[i]) d(i);

    cout<<"POSSIBLE"<<endl;
    rep(i,0,n){
        if(ga[i].size()%2==1) cout<<"0 ";
        else cout<<vis[i]<<" ";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 18304
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define MOD7 1000000007
#define LL_INF 1LL << 60
#define LL_MINF -1LL << 60
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const long double PI = (acos(-1));


int main(){
    int N;
    cin >> N;
    map<pair<char,int>,int> M;
    for(int i = 0; i < N; i++){
        char s;
        int a;
        cin >> s >> a;
        pair<char,int> p = make_pair(s, a);
        M[p]++;
    }
    for(char s : {'S','H','C','D'}){
        for(int i = 1; i <= 13; i++){
            pair<char,int> p = make_pair(s,i);
            if(M[p] == 0) cout << s << ' ' << i << endl;
        }
    }
}


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


int main(){
  int n;
  cin>>n;
  vector<tuple<string,int,int>> v(n) ;
  rep(i,n){
    string a; int b;
    cin>>a>>b;
    v.at(i)=make_tuple(a,100-b,i+1);
  }

  sort(v.begin(), v.end()) ;
  rep(i,n){
    string a; int b,x;
    tie(a,b,x)=v.at(i);
    cout<<x<<endl;
  }
  return 0;
}

Measured memory_bytes: 3560
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cctype>
const int INT_INF = 1000000000;                 // 10^9
const long long LONG_INF = 1000000000000000000; // 10^18

using namespace std;

int main()
{
    int h, a;
    cin >> h >> a;

    int ans = h / a;

    if (h % a != 0)
    {
        ans++;
    }

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

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

int main(){
  ll n,x,ans;
  cin>>n;
  cin>>ans;
  for(int i=1;i<n;i++){
    cin>>x;
    ans=  ans/__gcd(ans,x)*x;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  string s;
  cin>>s;
  if(s==string(s.size(),s[0])){
    cout<<s.size()<<endl;
    return 0;
  }
  vector<int> cnt(26,0);
  for(char c:s) cnt[c-'a']++;
  priority_queue<int, vector<int>, greater<int> > pq;
  
  for(int i=0;i<26;i++)
    if(cnt[i]) pq.emplace(cnt[i]);

  int ans=0;
  while(pq.size()>1u){
    int x=pq.top();pq.pop();
    int y=pq.top();pq.pop();
    ans+=x+y;
    pq.emplace(x+y);
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3304
X, Y = map(int, input().split(' '))
if X % Y == 0: print(-1)
else:
    res = 0
    i = 1
    while res == 0:
        if X * i % Y != 0:
            res = X*i
            break
        else:
            i += 1
    if X*i <= 10**18:
        print(res)
    else:
        print(-1)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n,a,b;
    cin>>n>>a>>b;
    int z=abs(a-b+1);
    if(z&1)
        cout<<"Alice";
    else
        cout<<"Borys";


} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[16],b[16]={'C','O','D','E','F','E','S','T','I','V','A','L','2','0','1','6'};
int s;
int main(){
	gets(a);
	for(int i=0;i<16;i++){
		if(a[i]!=b[i])
			s++;
	}
	cout<<s<<endl;
	return 0; 
}

Measured memory_bytes: 256
l,r = gets.chomp.split(" ").map(&:to_i)

if  r - l > 2019
  puts 0
else
  min = 2020
  for i in l..r-1
    for j in i+1..r
      min = min < (i%2019) * (j%2019) % 2019 ? min : (i%2019) * (j%2019) % 2019
    end
  end
  puts min
end

Measured memory_bytes: 1788
def main():
    from bisect import bisect_left

    S = input()
    T = input()

    L = len(S)

    pos = tuple(list() for _ in range(26))
    orda = ord('a')
    for i, c in enumerate(S):
        j = ord(c) - orda
        pos[j].append(i)

    rep = 0
    curr = 0
    for c in T:
        j = ord(c) - orda

        if not pos[j]:
            print(-1)
            return

        i = bisect_left(pos[j], curr)
        if i == len(pos[j]):
            rep += 1
            i = 0  # pos[j][0]文字目がc
        curr = pos[j][i] + 1  # pos[j][i]にしたら同じ文字が続くケースでWA

    print(rep * L + curr)


if __name__ == '__main__':
    main()


Measured memory_bytes: 7628
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,d[200000];
    cin>>n;
    rep(i,n) cin>>d[i];
    sort(d,d+n);
    cout<<d[n/2]-d[n/2-1];
}

Measured memory_bytes: 768
#include <iostream>

using namespace std;

typedef long long ll;

ll N, M;
ll ans;

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

  if(N*2 <=  M) {
    ans += N;
    M -= (2 * N);
    ans += M / 4;
  }

  else ans = M / 2;

  cout << ans <<endl;
}
    

  


Measured memory_bytes: 256
#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>;

ll x[100010];

int main(){
    int n; ll k;
    cin>>n>>k;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        x[a]+=b;
    }
    ll cnt=0;
    rep(i,100010){
        cnt+=x[i];
        if(cnt>=k){
            cout<<i<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 4360
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    int r;
    cin >> r;
    cerr << "Error\n" << endl;
    cout << 2*r*3.141592 << endl;
    return 0;
}

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

int main()
{
    int x;
    cin >> x;
    cout << (x < 1200 ? "ABC" : "ARC") << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz size()
#define ll long long
#define all(_v) _v.begin(), _v.end()

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    string ans = "";
    for(int i = 0; i < s.sz; ++i) ans += t[i];
    if(ans == s) cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define maxn 5005
#define LL long long
#define iv2 500000004
#define mod 1000000007
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) 
using namespace std;

int n,f[maxn][maxn],sz[maxn],fac[maxn],pw[maxn],invf[maxn],inv[maxn];
vector<int>G[maxn];
int C2(int x){ return 1ll * x * (x-1) / 2 % mod; }

void dfs(int u,int ff){
	int v;f[u][1] = sz[u] = 1;
	rep(i,0,G[u].size()-1) if((v=G[u][i])^ff){
		dfs(v,u);
		static int g[maxn]={};
		rep(j,0,sz[u]+sz[v]) g[j] = 0;
		rep(j,0,sz[u]) rep(k,0,sz[v]) g[j+k] = (g[j+k] + 1ll * f[u][j] * f[v][k]) % mod;
		rep(j,0,sz[u]+sz[v]) f[u][j] = g[j];
		sz[u] += sz[v];
	}
	rep(j,1,sz[u]) if(j%2==0)
		f[u][0] = (f[u][0] + f[u][j] * 1ll * fac[j] % mod * pw[j/2] % mod * invf[j/2]) % mod;
	if(ff) f[u][0] = -f[u][0];
}

int main(){
	scanf("%d",&n);
	rep(i,1,n-1){
		int u,v;scanf("%d%d",&u,&v);
		G[u].push_back(v),G[v].push_back(u);
	}
	fac[0] = fac[1] = pw[0] = 1 , pw[1] = iv2;
	inv[0] = inv[1] = invf[0] = invf[1] = 1;
	rep(i,2,n) fac[i] = 1ll * fac[i-1] * i % mod , pw[i] = 1ll * iv2 * pw[i-1] % mod,inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
		invf[i] = 1ll * invf[i-1] * inv[i] % mod;
	dfs(1,0);
	printf("%d\n",f[1][0]);
}


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

#define int long long
#define ll long long
#define vi vector <int>
#define vii vector <pair<int,int> >
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>b;i--)
#define pb push_back
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define MOD 1000000007
#define PI 3.14159265359
/*

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace __gnu_pbds;
typedef tree<pii,null_type,less <pii>,rb_tree_tag,tree_order_statistics_node_update>ind_set;
*/
///*X.find_by_order("index")
///X.order_of_key("key")



#define deb(x) cerr<<#x<< " : " <<x<<"\n";
#ifndef local
	#define deb(x) ;
#endif
///----------------------------------------------------------------------------------


int n,arr[100005];
int pre[100005];
void solve()
{
	cin>>n;
	if (n%2)
	{
		cout<<0;return;
	}
	int T;
	memset(arr,0,sizeof arr);memset(pre,0,sizeof pre);
	rep(i,0,n)cin>>T,arr[T]++;
	int ans=0;
	pre[0]=arr[0];
	rep(i,1,100005)
	{
		pre[i]=pre[i-1]+arr[i];
		if (pre[i]==n/2)ans++;
	}
	cout<<ans;


}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    #ifdef local
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    clock_t qwertyuiop = clock();
    #endif


    int t=1;
    //cin>>t;
    
    rep(a,0,t)
    {
        ///cout<<"Case #"<<a+1<<": ";
        solve();
    }
    #ifdef local
	{qwertyuiop = clock() - qwertyuiop;double time_taken = ((double)qwertyuiop)/CLOCKS_PER_SEC;cerr<<fixed<<setprecision(5)<<"\n\nTime Taken : "<<time_taken<<" seconds\n";}
	#endif
}


Measured memory_bytes: 1792
t = gets.chomp.chars
(t.size).times do |i|
  next if t[i] != "?"
  
  if i == 0 || i == t.size - 1
    t[i] = "D"
  elsif t[i - 1] == "P"
    t[i] = "D"
  elsif t[i + 1] == "?"
    t[i] = "P"
  else
    t[i] = "D"
  end
end
puts t.join("")

Measured memory_bytes: 33396
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
    int q;
    cin >> q;
    rep(zz,q){
        ll a,b;
        cin >> a >> b;
        if(a>b)swap(a,b);
        ll res = 0;
        res += 2*(a-1);
        ll p = a*b;
        if(b>a+1){
            res++;
        }
        ll lo = a+1;
        ll up = b-2;
        if(up>=lo){
            ll s = 0;
            ll t = 1e9;
            while(t-s>1){
                ll mid = (s+t)/2;
                if(mid*mid<p){
                    s = mid;
                }else{
                    t = mid;
                }
            }
            ll q = s;
            ll tmp = 0;
            //cerr << p << " " << q*q << endl;
            if(lo<=q&&q<=up){
                tmp = 2*min(q-lo,up-q)+1;
                if(q*(q+1)<p){
                    tmp = max(tmp,2*min(q-lo+1,up-q));
                }
            }
            res += tmp;
        }
        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long int i,nt,n,t,j,p=0,sum=0,k,low,high;
    set<int>se;

    string s;
    cin>>n>>k;
    long long int ara[n],ar[n-k];
    for(i=0;i<n;i++){
        cin>>ara[i];
    }

   j=0;

    for(i=0;i<n;i++){

        p+=ara[i];
       if(i>=k-1){
         ar[j]=p;

         p=p-ara[j];
         j++;
       }
    }
    sum=0;
    for(i=0;i<=n-k;i++){
          //  cout<<ar[i]<<" ";
         if(ar[i]>sum){
            low=i;
            sum=ar[i];
         }
    }
    double g,h,lo=0;
    for(int ii=low;ii<low+k;ii++){
       // cout<<ara[ii]<<endl;
        g=double(ara[ii]*(ara[ii]+1))/2;
       // cout<<ara[ii]<<" "<<g<<endl;
        lo+=double(g/ara[ii]);
    }
   printf("%.8lf\n",lo);

}




Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] as = new int[n];
        Boolean[][] fdp = new Boolean[k + 1][2];
        fdp[0][0] = false;
        fdp[0][1] = false;
        for (int i = 0; i < n; i++) {
            as[i] = scanner.nextInt();
        }
        for (int i = 0; i < as[0]; i++) {
            fdp[i][1] = false;
        }
        System.out.println(calculate(fdp, as, k, 0) ? "First" : "Second");
    }

    private static boolean calculate(Boolean[][] fdp, int[] as, int k, int order) {
        if (fdp[k][order] != null) {
            return fdp[k][order];
        }
        fdp[k][order] = false;
        for (int i = 0; i < as.length; i++) {
            if (k - as[i] >= 0) {
                fdp[k][order] |= !calculate(fdp, as, k - as[i], (order + 1) % 2);
              	if (fdp[k][order]) {
                    break;
                }
            }
        }
        return fdp[k][order];
    }
}


Measured memory_bytes: 41428
n, *A = map(int, open(0).read().split())
A.sort(reverse=1)
if n % 2 == 0:
    print(sum(A[:n//2]) * 2 - A[0])
else:
    t = (n+1)//2
    print(sum(A[:t]) * 2 - A[0] - A[t-1])

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

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

    std::vector<long long> A(N + 1);
    for (int i = 0; i <= N; i++) std::cin >> A[i];

    std::vector<long long> sum(N + 1);
    sum[N] = A[N];
    for (int i = N - 1; i >= 0; i--) {
        sum[i] = sum[i + 1] + A[i];
    }

    long long ans = 0, res = 0;
    for (int i = 0; i <= N; i++) {
        res = std::min(sum[i], res * 2 - A[i] + (i == 0 ? 1 : 0));

        if (res < 0) {
            std::cout << "-1\n";
            return 0;
        }

        ans += std::min(sum[i], res + A[i]);
    }
    std::cout << ans << "\n";
}

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

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

  	int cnt[110] ={};
  	for(int i=0;i<K;i++){
    	int d;cin>>d;
      for(int j=0;j<d;j++){
      	int a;cin>>a;
  		a--;
        cnt[a]++;
      }
    }
  	
  	int ans=0;
    for(int i=0;i<N;i++){
    	if(cnt[i]==0)ans++;
    }
     cout <<ans <<endl;
      
      return 0;
     
    }
  

Measured memory_bytes: 3616