akhauriyash/Code-Regression huggingface dataset:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *X = list(map(int, read().split()))

X = np.array(X)
P = X.sum() // N

ans = 10**8 + 7

for i in range(-1, 2):
    acc = X - (P + i)
    acc = acc**2
    acc = acc.sum()

    ans = min(ans, acc)

print(ans)


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

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[a]; if (a != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)///
ll mypow(ll a, ll n) {
	if (n == 0)return 1;
	if (n % 2 == 0)return mypow(a, n / 2)*mypow(a, n / 2) % MOD;
	return (a*mypow(a, n / 2) % MOD)*mypow(a, n / 2) % MOD;
}
struct UnionFind {
	vector<int> par;
	vector<int> ran;

	UnionFind(int n) {
		par.resize(n);
		ran.resize(n);
		REP(i, n) {
			par[i] = i;
			ran[i] = 0;
		}
	}

	int root(int a) {
		return par[a] == a ? a : par[a] = root(par[a]);
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y]) ran[x]++;
		}
	}
};
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (1) {
		int n, m;
		cin >> n >> m;
		if (!n)break;
		UnionFind u(n);
		int cnt = 0;
		REP(i, m) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			if (!u.same(a, b)) {
				u.unite(a, b);
				cnt++;
			}
		}
		
		ll res = mypow(2, n-cnt);
		if (m != 0)res++;
		cout << res%MOD << endl;
	}
	return 0;
}

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

MOD = 10**9 + 7

# https://qiita.com/derodero24/items/91b6468e66923a87f39f


def cmb(n, r):
  if n - r < r:
    r = n - r
  if r == 0:
    return 1
  if r == 1:
    return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2, r + 1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p - 1, r, p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])
      result %= MOD

  return result


print((pow(2, n, MOD) - 1 - cmb(n, a) - cmb(n, b)) % MOD)


Measured memory_bytes: 27700
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n, m;
  cin >> n >> m;

  vector<int> x(m);
  REP(i,m){
    cin >> x[i];
  }

  if(n >= m){
    cout << "0\n";
    return 0;
  }
  SORTV(x);

  vector<int> l;
  REP(i,m-1){
    l.pb(x[i+1]-x[i]);
  }

  sort(ALL(l));
  llong ans = 0;
  for(int i = 0; i < m - n; ++i){
    ans += l[i];
  }

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



Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;
int n;
int a[N], b[N], c[N];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i < n; i++) cin >> c[i];
    int ans = 0;
    a[0] = -2;
    for(int i = 1; i <= n; i++) {
        ans += b[a[i]];
        if(a[i] == a[i - 1] + 1) ans += c[a[i - 1]];
    }
    cout << ans;
}

Measured memory_bytes: 3640
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int l,r,d;
  cin >> l >> r >> d;
  int ans = 0;
  for(int i = l; i <= r; i++) if(i % d == 0) ans++;
  cout << ans << endl;
}

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

const int N = 200010;
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;

typedef long long LL;

inline int Pow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = (LL)x * x % mod) if (y & 1) res = (LL)res * x % mod;
    return res;
}

int n;

struct FUCK {
	
int tree[N];
    
inline void update(int x, int y) {
    for (; x <= n; x += x & -x) tree[x] = (tree[x] + y) % mod;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x) res = (res + tree[x]) % mod;
    return res;
}

inline int query(int l, int r) {
    return (query(r) - query(l - 1) + mod) % mod;
}

} X, Y, Z;

int A[N], num[N], pre[N], lst[N], nxt[N], ct[N];
bool fuck[N];

int main() {
	scanf("%d", &n);
	for (int i = 1, a; i <= n; i++) scanf("%d", &a), A[a]++, num[i] = a;
	for (int i = n; i >= 0; i--) A[i] += A[i + 1];
	int tot = 1; pre[0] = 1;
	for (int i = 1; i <= n; i++) {
		A[i] -= n - i, tot = (LL)tot * A[i] % mod;
		if (A[i] <= 0) return puts("0"), 0;
		int t = (LL)(A[i] - 1) * Pow(A[i], mod - 2) % mod;
		if (t) pre[i] = (LL)pre[i - 1] * t % mod;
		else pre[i] = pre[i - 1], fuck[i] = true;
	} 
	nxt[n + 1] = n + 1;
	for (int i = n; i >= 1; i--) {
		nxt[i] = nxt[i + 1];
		if (fuck[i]) nxt[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		lst[i] = lst[i - 1];
		if (fuck[i]) lst[i] = i;
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res = (res + (LL)ct[num[i]] * tot % mod * inv2) % mod;
		if (num[i] != 1) {
			res = (res + (LL)Y.query(max(1, lst[num[i]]), num[i] - 1) * pre[num[i]] % mod
				* tot % mod * inv2) % mod;
		}
		if (num[i] != n) {
			res = (res + (LL)Z.query(num[i] + 1, n) * tot) % mod;
			res = (res - (LL)X.query(num[i] + 1, min(n, nxt[num[i] + 1] - 1)) * Pow(pre[num[i]], mod - 2) % mod
				* tot % mod * inv2 % mod + mod) % mod;
		}
		X.update(num[i], pre[num[i]]), Y.update(num[i], Pow(pre[num[i]], mod - 2)), Z.update(num[i], 1), ct[num[i]]++;
	}
	printf("%d\n", res);
}


Measured memory_bytes: 7424
using System;

 class Program
 {
     static void Main(string[] args)
     {
         double data1, data2, data3,temp;
         double[] result = new double[3];
         String nyuryoku;
         nyuryoku = Console.ReadLine();
         string[] data = nyuryoku.Split(' ');
         data1 = Double.Parse(data[0]); 
         data2 = Double.Parse(data[1]);
         data3 = Double.Parse(data[2]);
         result[0]=data1;
         if (result[0] > data2)
         {
             temp = result[0];
             result[0] = data2;
             data2 = temp;
         }
         if (result[0] > data3)
         {
             temp = result[0];
             result[0] = data3;
             data3 = temp;
         }
         result[1] = data2;
         if (result[1] > data3)
         {
             temp = result[1];
             result[1] = data3;
             data3 = temp;
         }
         result[2] = data3;
                  
         Console.WriteLine("{0} {1} {2}",result[0],result[1],result[2]);
     }
 }



Measured memory_bytes: 17900
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<class Z> V<Z> divisor(Z n) {
  V<Z> res;
  Z i;
  for (i = 1; i * i < n; ++i) if (n % i == 0) res.push_back(i), res.push_back(n / i);
  if (i * i == n) res.push_back(i);
  sort(begin(res), end(res));
  return res;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<lint> s(n); for (auto&& e : s) cin >> e;
  VV<lint> c(n);
  for (int d = 1; d < n; ++d) {
    c[d].resize(n / d + 1);
    for (int i = 0; i < n / d; ++i) {
      c[d][i + 1] = c[d][i] + s[d * i] + s[n - 1 - d * i];
    }
  }
  lint res = 0;
  for (int A = 1; A < n; ++A) for (int k : divisor(n - 1 - A)) {
    int B = A - (n - 1 - A) / k;
    if (B <= 0 or B >= A) continue;
    if (A <= k * (A - B) and !(A % (A - B))) continue;
    lint curr = c[A - B][k + 1];
    res = max(res, curr);
  }
  cout << res << '\n';
}

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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

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

    int a = stoi(s.substr(0, 2)), b = stoi(s.substr(2, 2));

    if (0 <= a && a <= 99 && 1 <= b && b <= 12)
    {
        if (1 <= a && a <= 12)
            OP("AMBIGUOUS");
        else
            OP("YYMM");
    }
    else if (0 <= b && b <= 99 && 1 <= a && a <= 12)
    {
        if (1 <= b && b <= 12)
            OP("AMBIGUOUS");
        else
            OP("MMYY");
    }
    else
    {
        OP("NA");
    }
    return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
grid = [set() for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    grid[u].add(v)
    grid[v].add(u)

cnt = 0
best = 0
visited = set()

import sys
sys.setrecursionlimit(1000000)

def dfs(x):
    global cnt
    if x in visited:
        return
    cnt += 1
    visited.add(x)
    for i in grid[x]:
        dfs(i)


for i in range(n):
    cnt = 0
    dfs(i)
    best = max(best, cnt)

print(best)


Measured memory_bytes: 245960
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int t = Integer.parseInt(in.next());
            int a = Integer.parseInt(in.next());
            int h[] = new int[n];
            for (int i = 0; i < n; i++) {
                h[i] = Integer.parseInt(in.next());
            }
            int ans = 0;
            double kouho = Double.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                double avg = t - h[i] * 0.006;
                if (kouho > Math.abs(a - avg)) {
                    kouho = Math.abs(a - avg);
                    ans = i;
                }
            }
            // 出力
            out.println(++ans);

        }

    }
}



Measured memory_bytes: 22356
import math
a,b,h,m=map(int,input().split())
hh=h/12*360 + m/60*30
mh=m/60*360 

#print(hh,mh)
x=abs(hh-mh)
if x==180:
    print(a+b)

else:
    
#print(round((a**2+b**2-abs(2*a*b*math.cos(x*math.pi/180)))**0.5,9))
    print ('%.9f'%(a**2+b**2-(2*a*b*math.cos(x*math.pi/180)))**0.5)

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

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printfin(a) printf(a ? "possible\n" : "inposible\n")
#define all(x) (x).begin(), (x).end()
using ll = long long;

const int INF = 2147483647;
//const ll LINF = ll();今度書く

//マクロとかここまで

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

int main() {

	map<int, bool> abc;
	int a;
	rep(i, 3) {
		scanf("%d", &a);
		abc[a] = true;
	}
	a = 0;
	for (auto itr = abc.begin(); itr != abc.end(); ++itr) {
		a += itr->second;
	}
	printf("%d\n", a);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define myfill(a, val, type) fill((type *)a, (type *)a+sizeof(a)/sizeof(type), val)
const int INF = 1001001001;

int main() {
	int n, m_a, m_b;
	cin >> n >> m_a >> m_b;
	const int MAX = 402;
	int dp[MAX][MAX]; myfill(dp, INF, int);
	dp[0][0] = 0;
	for (int k = 1; k <= n; k++) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int i = MAX-1; i >= 0; i--) {
			for (int j = MAX-1; j >= 0; j--) {
				if (i-a >= 0 && j-b >= 0) {
					dp[i][j] = min(dp[i][j], c + dp[i-a][j-b]);
				}
			}
		}
	}
	int ans = INF;
	for (int i = 1; i*m_a < MAX && i*m_b < MAX; i++) {
		ans = min(ans, dp[i*m_a][i*m_b]);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3804
X,Y,A,B,C=map(int, input().split())
plist=list(map(int, input().split())) 
qlist=list(map(int, input().split())) 
rlist=list(map(int, input().split())) 
plist.sort(reverse=True)
qlist.sort(reverse=True)

redlist = plist[:X]
greenlist = qlist[:Y]
RandG = redlist+greenlist+rlist
RandG.sort(reverse=True)
print(sum(RandG[:X+Y]))

Measured memory_bytes: 23328
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

	rep(i, s.size()) cout << "x";

	return 0;
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

ll ans,n;

int gcd(int x,int y) {return !x?y:gcd(y%x,x);}

int main() {
	qr(n); 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) {
			int k=gcd(i,j);
			for(int l=1;l<=n;l++)
				ans+=gcd(k,l);
		}
	pr2(ans);
	return 0;
}



Measured memory_bytes: 3592
class Stack():
    def __init__(self):
        self.l = []
    
    def push(self, e):
        self.l.append(e)
        
    def pop(self):
        return self.l.pop()

# def isint(s):
#     try: 
#         int(s)
#         return True
#     except ValueError:
#         return False

ope = {"+", "-", "*"}

s = Stack()
exp = input().strip().split()

for e in exp:
    if e in ope:
        if e == '+':
            s.push(s.pop() + s.pop())
        elif e == '-':
            tmp = s.pop()
            s.push(s.pop() - tmp)
        else:
            s.push(s.pop() * s.pop())
    else:
        s.push(int(e))
print(s.pop())

Measured memory_bytes: 5596
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner kb = new Scanner( System.in );

		String str = kb.nextLine();
		int n = Integer.parseInt( str );

		str = kb.nextLine();
		String[] arr = str.split( " " );
			
		for( int i=n-1; 0<=i; i-- ) {
			System.out.print( arr[i] );
			if( 0 != i ) {
				System.out.print( " " );
			} else {
				System.out.print( "\n" );
			}
		}
	}
}

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

int main(){
    long A,B,C,K;cin>>A>>B>>C>>K;
    long ans=0;
    for(int i=0;i<K;i++){
        if(A>0){
            ans++;
            A--;
        }
        else if(B>0){
            B--;
        }
        else{
            ans--;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int len;
int n;
int a[1010100];
int b[1010100];

bool check(int x){
    for (int i=1;i<=n;i++) b[i] = a[i]>=x;
    int Mid = (1+n)>>1;
    int le=Mid-1,ri=Mid+1;
    for (;le && ri<=n;le--,ri++)
      if (b[le] == b[le+1]) return b[le];
      else if (b[ri] == b[ri-1]) return b[ri];
    return b[1];
}

int main(){
    scanf("%d",&len);
    n = 2*len-1;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l = 0,r = 1e9;
    while (l+1<r){
	    int mid = l+r>>1;
	    if (check(mid)) l = mid;else r = mid;
	}
	printf("%d",check(l)?l:r);
	return 0;
}

Measured memory_bytes: 5248
N,M = map(int,input().split())
X_list = list(map(int,input().split()))
X_list.sort()
L_list = []
for i in range(1,M):
    L_list.append(X_list[i]-X_list[i-1])
L_list.sort()
if N >= M:
    print('0')
else:
    print(sum(L_list[:M-N]))

Measured memory_bytes: 13968
n = int(input())
tolls = [int(i) for i in input().split()]


max_n = 0
height_s = 0


for i in range(len(tolls)):
    if max_n < tolls[i]:
        max_n = tolls[i]
    height_s += max_n - tolls[i]


print(height_s)

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

#define ll long long
#define int ll
#define pii pair<int, int>
#define pb push_back
#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=a; i<b; i++)
#define REPD(i, n) for (int i=n-1; i>=0; i--)
#define FORD(i, a, b) for (int i=a; i>=b; i--)
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

using namespace std;

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};

mint C[5000][5000];
void init_comb() {
    C[0][0] = 1;
    for (int i = 0; i <= 4000; ++i) {
        for (int j = 0; j <= i; ++j) {
            C[i+1][j] += C[i][j];
            C[i+1][j+1] += C[i][j];
        }
    }
}

mint comb(int n, int k) {
    return C[n][k];
}

mint f(int x, int y) {
    return comb(x, y);
}

void solve() {
    int N, K;
    cin >> N >> K;
    
    init_comb();
   
    for (int i = 1; i <= K; ++i) {
        mint ans = f(K-1, i-1) * f(N-K+1, i);
        print(ans.x);
    }

}

signed main() {
    solve();
}


Measured memory_bytes: 195584
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);

	int num[3];
	cin >> num[0] >> num[1] >> num[2];
	sort(num, num+3);
	cout << num[0] << " " << num[1] << " " << num[2] << "\n";
	return 0;
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, M; cin >> N >> M; 
	int A[110] = {}; 
	int sum = 0; 
	for(int i = 0; i < N; i++){
		cin >> A[i]; sum += A[i];  
	}
	int cnt = 0; 
	for(int i = 0; i < N; i++){
		if(A[i] * 4 * M >= sum) cnt ++; 
	}
	if(cnt >= M) cout << "Yes" << endl; 
	else cout << "No" << endl; 
}

Measured memory_bytes: 256
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-9;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
	int n;cin>>n;
	if(n/100==n%10){cout<<"Yes"<<endl;}
	else{cout<<"No"<<endl;}
	return 0;
}

Measured memory_bytes: 888
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

template <class T>
inline bool chmax(T& a, T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline bool chmin(T& a, T b) {
    return a = (a > b) ? b : a;
}

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

// 素因数分解 O(√n)
map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;

    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }
    }

    if (n != 1) res[n] = 1;

    return res;
}

int main() {
    INIT;

    ll N;
    cin >> N;

    map<ll, ll> primes = prime_factor(N);

    // for (auto elem : primes) {
    //     cout << elem.first << " " << elem.second << endl;
    // }

    map<ll, ll> cnts;
    ll ans = 0;
    for (auto elem : primes) {
        while (elem.second > 0) {
            if (elem.second < cnts[elem.first] + 1) break;

            N /= pow(elem.second, cnts[elem.first] + 1);
            ans++;
            cnts[elem.first]++;
            elem.second -= cnts[elem.first];
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
    int N;
  	cin >> N;
    int e, o;
  	o = N / 2;
  	e = o + (N % 2);
    
  	cout << setprecision(6) << double(e) / (double)N << endl;
  return 0;
}


Measured memory_bytes: 256
X = int(input())

dp = [False]*(X+1)
dp[0] = True

for i in range(1, X+1):
    if i-100 < 0:
        dp[i] = False
    else:
        dp[i] = (dp[i-100] or dp[i-101] or dp[i-102] or dp[i-103] or dp[i-104] or dp[i-105])

print(int(dp[X]))

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

int A, B, C;
int K;
int sum;

int main() 
{
	ios::sync_with_stdio(false);
	cin >> A >> B >> C >> K;
	while(A--) 
	{
		K--;
		sum += 1;
		if(!K) 
		{
			cout << sum;
			return 0;
		}
	}
	while(B--) 
	{
		K--;
		if(!K) 
		{
			cout << sum;
			return 0;
		}
	}
	while(C--) 
	{
		K--;
		sum -= 1;
		if(!K) 
		{
			cout << sum;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3656
#include<stdio.h>
#include<stdlib.h>
int compare_short(const void *a, const void *b){
    return *(short*)b - *(short*)a;
}

int n, i;
short a[100];
int ans[2];
int main(){
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%hd", a+i);
  }
  qsort(a, n, sizeof(short), compare_short);
  for(i=0; i<n; i++){
    ans[i&1] += a[i];
  }
  printf("%d\n", ans[0]-ans[1]);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
#define EPS 1e-12
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

double lg(double x1,double y1){
  return sqrt(x1*x1+y1*y1);
}

int main(){
  double x[3],y[3];
  for(int i=0;i<3;i++)cin>>x[i]>>y[i];
  
  double vx[3],vy[3];
  for(int i=0;i<3;i++){
    int i1=(i+1)%3;
    int i2=(i+2)%3;
    
    double tx1=x[i1]-x[i];
    double ty1=y[i1]-y[i];
    double tl1=lg(tx1,ty1);
    tx1/=tl1;
    ty1/=tl1;
    
    double tx2=x[i2]-x[i];
    double ty2=y[i2]-y[i];
    double tl2=lg(tx2,ty2);
    tx2/=tl2;
    ty2/=tl2;
    
    vx[i]=tx1+tx2;
    vy[i]=ty1+ty2;
    double l=lg(vx[i],vy[i]);

    vx[i]/=l;
    vy[i]/=l;
  }
  /*
  for(int i=0;i<3;i++){
    dbg(vx[i]);
    dbg(vy[i]);
    cout<<endl;
  }
  //*/
  double a[3];
  for(int i=0;i<3;i++){
    int ni=(i+1)%3;
    a[i]=lg(x[i]-x[ni],y[i]-y[ni]);
  }
  double s=(a[0]+a[1]+a[2])/2.0;

  s=sqrt(s*(s-a[0])*(s-a[1])*(s-a[2]));
  double ma=2.0*s/(a[0]+a[1]+a[2]);
  
  //dbg(ma);
  
  double ok=0,ng=ma,mid;
  while(ng-ok>EPS){
    mid=(ok+ng)/2.0;
    
    /*
    cout<<endl;
    dbg(mid);
    //*/

    double px[3],py[3];
    int f=0;
    for(int i=0;i<3;i++){
	 int i1=(i+1)%3;
	 double tx=x[i1]-x[i];
	 double ty=y[i1]-y[i];
	 
	 double co2=vx[i]*tx+vy[i]*ty;
	 co2/=lg(vx[i],vy[i])*lg(tx,ty);

	 double l=fabs(mid/sqrt(1.0-co2*co2));
	 // dbg(l);
	 
	 px[i]=x[i]+vx[i]*l;
	 py[i]=y[i]+vy[i]*l;
	 
	 /*
	 dbg(i);
	 dbg(px[i]);
	 dbg(py[i]);
	 //*/
    }
    f=0;
    for(int i=0;i<3;i++){
	 for(int j=i+1;j<3;j++){
	   double l=lg(px[i]-px[j],py[i]-py[j]);
	   if(l>=mid*2.0)f=1;
	 }
    }

    if(f)ok=mid;
    else ng=mid;
  }

  printf("%.10lf\n",ok);
  
  return 0;
}


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

int main() {
  string s;
  cin >> s;
  bool a=true;
  int l=0,r=s.length()-1;
  int sum=0;
  for(int i=0;i<s.length()+1;i++){
    if(l>=r)break;
    if(s[l]==s[r]){
      l++;
      r--;
    }
    else if(s[l]=='x'){
      sum++;
      l++;
    }
    else if(s[r]=='x'){
      sum++;
      r--;
    }
    else{
      a=false;
      break;
    }
  }
  if(a)cout << sum;
  else cout << -1;
}

Measured memory_bytes: 512
from collections import deque
N = int(input())
path = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)

steps = [-99 for _ in range(N)]
steps[0] = 0
isVisited = [False for _ in range(N)]
toSearch = deque([0, ])
isVisited[0] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    nowStep = steps[nowP]
    if nowP == N-1:
        break
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
            steps[nextP] = nowStep + 1

fennecLength = ((nowStep-1)+1)//2

snukePoint = 0
isVisited = [False for _ in range(N)]
toSearch = deque([N-1, ])
isVisited[N-1] = True
while len(toSearch) > 0:
    nowP = toSearch.pop()
    snukePoint += 1
    nowStep = steps[nowP]
    # To FIX break condition
    if nowStep == fennecLength:
        snukePoint -= 1
        continue
    for nextP in path[nowP]:
        if not isVisited[nextP]:
            isVisited[nextP] = True
            toSearch.appendleft(nextP)
if snukePoint >= (N+1)//2:
    print("Snuke")
else:
    print("Fennec")
#print(snukePoint)
#print(steps)

Measured memory_bytes: 27084
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

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

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

const ll C_MAX = (ll)1e18;

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

	if (N[N.size() - 1] == '2' ||
		N[N.size() - 1] == '4' ||
		N[N.size() - 1] == '5' ||
		N[N.size() - 1] == '7' ||
		N[N.size() - 1] == '9')
	{
		cout << "hon" << endl;
	}

	if (N[N.size() - 1] == '0' ||
		N[N.size() - 1] == '1' ||
		N[N.size() - 1] == '6' ||
		N[N.size() - 1] == '8')
	{
		cout << "pon" << endl;
	}

	if (N[N.size() - 1] == '3')
	{
		cout << "bon" << endl;
	}
	return 0;
}

Measured memory_bytes: 3552
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())

def cos(x1, y1, x2, y2, x3, y3):
    x2 -= x1
    x3 -= x1
    y2 -= y1
    y3 -= y1
    return (x2*x3+y2*y3)/((x2**2+y2**2)**0.5 * (x3**2+y3**2)**0.5)

def tan(cos):
    return ((1-cos)/(1+cos))**0.5

def r(x1, y1, x2, y2, x3, y3):
    tan1 = tan(cos(x1, y1, x2, y2, x3, y3))
    tan2 = tan(cos(x3, y3, x1, y1, x2, y2))
    b = ((x1-x3)**2+(y1-y3)**2)**0.5
    return b*tan1*tan2 / (tan1+tan2+2*tan1*tan2)

r1 = r(x1, y1, x2, y2, x3, y3)
r2 = r(x2, y2, x3, y3, x1, y1)
r3 = r(x3, y3, x1, y1, x2, y2)
print(max([r1, r2, r3]))

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

const int MOD = 1e9 + 7;
const int MAX_N = 2e5;

long long a[MAX_N + 1], ps[MAX_N + 1], ans;

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
		ps[i] = a[i] + (i > 0? ps[i - 1] : 0);
		ps[i] %= MOD;
		ans += (a[i] * (i > 0? ps[i - 1] : 0)) % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 6756
#include<stdio.h>
int main(void){
	int a, b, c, tmp,i;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	for (i = 1; i <= 3; i++){
		if (a > b){
			tmp = b;
			b = a;
			a = tmp;
		}
		else if (b > c){
			tmp = c;
			c = b;
			b = tmp;
		}
	}

	printf("%d %d %d\n", a, b, c);

	return 0;



}

Measured memory_bytes: 1024
program Triangular_Relationship
	implicit none
	integer*8 ans
	integer*8 n,k,a

	read *, n, k
	ans = 0

	do a=1, k
		if (mod(a*2,k) == 0) ans = ans + (((n-a)/k)+1)**2
	enddo

	ans = ans * (n/k)

	do a = 1, mod(n,k)
		if (mod(a*2,k) == 0) ans = ans + (((n-a)/k)+1)**2
	enddo

    write(*,*)ans

end program Triangular_Relationship


Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int i;
  int num[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  scanf("%d",&i);
  printf("%d",num[i-1]);
}


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

int main()
{
    /*A
    int a,b;
    cin>>a>>b;
    if(a-2*b>0)
    cout<<a-2*b<<endl;
    else
    {
        cout<<0<<endl;
    }
    */

   //B
   int n;
   cin>>n;
   int sum=0;
   vector <int> a(n);
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }

   for(int i=0;i<n;i++)
   {
       for(int j=i+1;j<n;j++)
       {
           sum += a[i]*a[j];
       }
   }


    cout<<sum<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;//溢出会变成负值 
typedef long double ldb;
typedef unsigned long long ull;//自动取模2^64 
const double pi=acos(-1.0);
const int mod = 1e9+7; // 998244353;
const int inf = 0x7fffffff;//2^31-1
const ll INF = 0x7fffffffffffffff;
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
//ll begin_time=clock();    ll end_time=clock();  cout<<"time = "<<end_time-begin_time<<" ms!"<<endl;
//bool operator < (const mmp &a) const{return x<a.x||x==a.x&&y<a.y;}       //map<int,map<int,int> >z;
//map<int,int>::iterator it;for(it=z.begin();it!=z.end();it++)printf("%d %d\n",it->first,it->second);
//ll poww(ll a,ll b){ll s=1;while(b){if(b&1)s=(s*a)%mod;a=(a*a)%mod;b>>=1;}return s%mod;}  //快速幂取模 
//lower_bound(begin,end,num); 第一个>=num的数字 upper_bound(begin,end,num); 第一个>num的数字,返回地址
//freopen("input.in","r",stdin);     freopen("output.out","w",stdout);      //文件读写提交 
//reverse(s.begin(),s.end());   //翻转字符串        floor(); 向下取整  ceil(); 向上取整
//数轴上的n个点移动到同一位置，移动到该组数字的中位数的总距离最短
//bool isPrime(int n){if(n==2||n==3)return 1;if(n%6!=1&&n%6!=5)return 0;
//int t=sqrt(n);for(int i=5;i<=t;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;}//判断素数   


int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	ll a,b,c,d,e,f,g,T;   
	cin>>a>>b;
//	if(a*4>=b&&a*2<=b)cout<<"Yes"<<endl;
//	else cout<<"No"<<endl;
	bool z[105];
	d=999;
	f=666;
	a++;
	memset(z,0,sizeof(z));
	while(b--)
	{
		cin>>c;
		z[c+1]=1;
	}
	for(int i=0;i<=102;i++)
	{
		if(z[i])continue;
		e=fabs(a-i);
		if(e<d)
		{
			d=e;
			f=i;
		}
	}
	cout<<f-1<<endl;
	
}
	


Measured memory_bytes: 3644
using System;
using System.Collections.Generic;

namespace ALDS1_4_D
{
    class Program
    {
        static void Main(string[] args)
        {
            var v = Console.ReadLine();
            var n = int.Parse(v.Split(' ')[0]);
            var k = int.Parse(v.Split(' ')[1]);
            var baggageList = new List<int>();
            for(int i=0; i < n; i++)
            {
                baggageList.Add(int.Parse(Console.ReadLine()));
            }
            Console.WriteLine(solve(k, baggageList));
        }

        static int solve(int car,List<int>baggageList)
        {
            int left = 0;
            int right = 100000 * 10000;
            int mid;
            while(right - left > 1)
            {
                mid = (left + right) / 2;
                int v = checkMaxBaggage(car, mid, baggageList);
                if (v >= baggageList.Count)
                    right = mid;
                else
                    left = mid;
            }
            return right;
        }

        static int checkMaxBaggage(int car,int max, List<int>baggageList)
        {
            int sum = 0;
            int maxBaggage = 0;
            int j = 0;
            for(int i=0; i<car; i++)
            {
                while(sum + baggageList[j] <= max)
                {
                    sum += baggageList[j];
                    maxBaggage++;
                    if (maxBaggage == baggageList.Count)
                        return maxBaggage;
                    j++;
                }
                sum = 0;
            }
            return maxBaggage;
        }
    }
}



Measured memory_bytes: 20608
MOD = 10**9+7

N   = int(input())
A   = list(map(int,input().split()))
A2   = [0]*N
BitNum = [0]*(61)

for i in range(1,61):
    A2 = [0] * N
    for j in range(N):
        A2[j] = A[j] % 2
        A[j] //= 2
    BitNum[i] = sum(A2)

ans = 0
beki = 0
for i in range(1,61):
    x = BitNum[i]
    y = N - x
    ans += (x*y)*(2**beki)
    ans %= MOD
    beki += 1
print(ans)


Measured memory_bytes: 127492
#include <iostream>
#include <limits>
#include <string>
#include <vector>

int solve(const std::string& s)
{
  std::vector<int> left_black_counts(s.size());
  std::vector<int> right_white_counts(s.size());
  int black_count = 0;
  for (int i = 0; i < static_cast<int>(s.size()); ++i) {
    if (s[i] == '#') ++black_count;
    left_black_counts[i] = black_count;
  }

  int white_count = 0;
  for (int i = static_cast<int>(s.size()) - 1; i >= 1; --i) {
    if (s[i] == '.') ++white_count;
    right_white_counts[i - 1] = white_count;
  }

  int min = right_white_counts[0] + (s[0] == '.' ? 1 : 0);
  for (int i = 0; i < static_cast<int>(s.size()); ++i) {
    int value = left_black_counts[i] + right_white_counts[i + 1];
    if (value < min) {
      min = value;
    }
  }
  return min;
}

int main()
{
  int n;
  std::string s;
  std::cin >> n >> s;

  std::cout << solve(s) << std::endl;
}


Measured memory_bytes: 2180
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main(){
	int N;
	while(cin>>N){
		if(N==0)break;
		int dp[33]={};
		dp[0]=1;
		for(int i=0;i<N;i++){
			for(int j=1;j<=3;j++){
				dp[i+j]+=dp[i];
			}
		}
		if(dp[N-1]%365==0){
			cout<<dp[N]/3650<<endl;
		}
		else cout<<(dp[N]/3650)+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <stdio.h>

int main() {
	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if (x-r>=0 && x+r<=W && y-r>=0 && y+r<=H) {
		printf("Yes\n");
	}	else {
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 2048
s = str(input())
if s[0] == 'R' and s[1] == 'R' and s[2] == 'R':
    print(3)
elif (s[0] == 'R' and s[1] == 'R') or (s[1] == 'R' and s[2] == 'R'):
    print(2)
elif s[0] == 'R' or s[1] == 'R' or s[2] == 'R':
    print(1)
else:
    print(0)

Measured memory_bytes: 8988
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<unordered_map>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep2(i,n) for(int i = -1; i < (n); i++)
#define PI 3.141592653589793

using namespace std;
using ll = unsigned long long;


int main() {

	char a;

	cin >> a;

	if (a > 96)cout << 'a' << endl;
	else cout << 'A' << endl;

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vi32 ab;
  i64 bsum = 0;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    ab.emplace_back(a + b);
    bsum -= b;
  }
  sort(all(ab));
  reverse(all(ab));
  rep(i, n) {
    if (i % 2 == 0) bsum += ab[i];
  }
  cout << bsum << endl;
}


Measured memory_bytes: 892
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

typedef tuple<ll, ll, ll> tp;

int main(int argc, char const *argv[]) {
  // 不可能なものを削る
  ll a, b;std::cin >> a >> b;
  vvl d = VV(a+1, b+1, 0, ll);
  re(i, a) re(j, b) scanf("%lld", &d[i+1][j+1]);
  ll INF = 1000000000;
  vvl cost = VV(a+1, b+1, INF, ll);

  vector<tp> use;
  for(ll i=0;i<=99;i++){
    for(ll j=0;j<=99;j++){
      for(ll k=0;k<=100;k++){
        //i, j, kの時のコストが下回ったら絶対に使えない
        for(ll A=1;A<=a;A++){
          for(int B=1;B<=b;B++){
            if(i*A+j*B+k<d[A][B]) goto nxt;
          }
        }
        use.push_back(tp(i, j, k));//採用
        for(int A=1;A<=a;A++){
          for(int B=1;B<=b;B++){
            cost[A][B] = min(cost[A][B], i*A+j*B+k);
          }
        }
        break;
        nxt:;
      }
    }
  }
  for(int i=1;i<=a;i++){
    for(int j=1;j<=b;j++){
      if(cost[i][j]!=d[i][j]){
        std::cout << "Impossible" << '\n';
        return 0;
      }
    }
  }

  std::cout << "Possible" << '\n';
  vvl e;
  vvl ok = VV(301, 301, 0, ll);


  for(int i=1;i<100;i++){
    ok[i][i+1] = 1;
    e.push_back({i, i+1, -1});
  }
  for(int i=1;i<100;i++){
    ok[i+200][i+201] = 1;
    e.push_back({i+200, i+201, -2});
  }

  for(auto v:use){
    ll i = get<0>(v);
    ll j = get<1>(v);
    ll k = get<2>(v);
    ll x = i+1;
    ll y = 300 - j;
    if(ok[x][y]) return 1;
    ok[x][y] = 1;
    e.push_back({x, y, k});
  }

  //------output area-----
  std::cout << "300 " << e.size() << '\n';
  for(auto v:e){
    std::cout << v[0] << " " << v[1] << " ";
    if(v[2]==-1) std::cout << "X" << '\n';
    else if(v[2]==-2) std::cout << "Y" << '\n';
    else std::cout << v[2] << '\n';
  }
  std::cout << "1 300" << '\n';
  return 0;
}


Measured memory_bytes: 4692
n, K = map(int, input().split())
rec = [0] * (10 ** 5 + 5)
for i in range(n):
    a, b = map(int, input().split())
    rec[a] += b

for i in range(10 ** 5 + 1):
    if rec[i] > 0:
        K -= rec[i]
        if K <= 0:
            print(i)
            exit()

Measured memory_bytes: 5736
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>

using namespace std;

using ll = long long int; 

void prime(vector<int> &num, int n){
    for(int i=0;i<=n;i++){
        num[i] = 1;
    }
    num[0] = 0;
    num[1] = 0;
    num[2] = 1;

    for(int i=2;i<=sqrt(n);i++){
        if(num[i] == 1){
            for(int j=2;j<=n/i;j++){
                num[i*j] = 0;
            }
        }
    }
}


ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}
 
ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

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

   ll min = 1000000000000;

   for(ll i=1;i<=sqrt(n);i++){
       if(n%i == 0){
           ll calc = i + (n/i);
           //cout<<calc<<endl;
           if(calc < min) min = calc;
       }
   }

   cout<<min -2 <<endl;


    return 0;
}

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

map<long long, int> prime_factorize(long long n) {
    map<long long, int> res;
    for (long long p = 2; p * p <= n; ++p) {
        while (n % p == 0) { ++res[p]; n /= p; }
    }
    if (n != 1) res[n] = 1;
    return res;
}

int main() {
    int n; cin >> n;
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; i++) {
        for (auto &p: prime_factorize(i)) cnt[p.first] += p.second;
    }
    const int M = 100;
    vector<int> geq(M + 1);
    for (int i = 1; i <= n; i++) geq[cnt[i]]++;
    for (int i = M - 1; i >= 0; i--) geq[i] += geq[i + 1];
    int ans = 0;
    ans += geq[74];
    ans += geq[24] * (geq[2] - 1);
    ans += geq[14] * (geq[4] - 1);
    ans += geq[4] * (geq[4] - 1) / 2 * (geq[2] - 2);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

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

    vector<vector<char>> grid(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> grid[i][j];

    vector<vector<int>> dp(h, vector<int>(w, INT_MAX / 100));
    dp[0][0] = grid[0][0] == '#' ? 1 : 0;

    auto set = [&](int y, int x, int value) {
        cmin(dp[y][x], value);
    };

    rep(y, h) {
        rep(x, w) {
            if (y != 0) {
                if (grid[y][x] == '.') set(y, x, dp[y - 1][x]);
                else if (grid[y - 1][x] == '#')set(y, x, dp[y - 1][x]);
                else if (grid[y - 1][x] == '.' && grid[y][x] == '#') set(y, x, dp[y - 1][x] + 1);
                else __throw_runtime_error("konai");
            }
            if (x != 0) {
                if (grid[y][x] == '.') set(y, x, dp[y][x - 1]);
                else if (grid[y][x - 1] == '#')set(y, x, dp[y][x - 1]);
                else if (grid[y][x - 1] == '.' && grid[y][x] == '#') set(y, x, dp[y][x - 1] + 1);
                else __throw_runtime_error("konai");
            }
        }
    }

    cout << dp.back().back() << endl;
}


Measured memory_bytes: 256