akhauriyash/Code-Regression huggingface dataset:
use std::io;
use std::str::FromStr;
use std::collections::HashSet;
use std::cmp::max;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn input_tuple() -> (u64, u64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn prime_numbers(limit: u64) -> HashSet<u64> {
    let mut is_candidate = vec![true; (limit + 1) as usize];
    let mut prime_numbers: HashSet<u64> = HashSet::new();
    for i in 2..(limit+1) {
        if is_candidate[i as usize] {
            prime_numbers.insert(i);
            let mut j = 2;
            while i * j < limit + 1 {
                is_candidate[(i * j) as usize] = false;
                j += 1;
            }
        }
    }
    prime_numbers
}

fn binary_search<F>(mut ok: i32, mut ng: i32, is_ok: F) -> i32
    where
        F: Fn(usize) -> bool
    {
        while (ok - ng).abs() > 1 {
            let mid = (ok + ng) / 2;
            if is_ok(mid as usize) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok
}

fn main() {
    let q: u64 = input();    
    let prime_nums = prime_numbers(200_000);
    let mut candidates: Vec<u64> = Vec::new();
    // println!("len = {}", prime_nums.len());
    for p in &prime_nums {
        if *p != 2 && prime_nums.contains(&((p + 1) / 2)) {
            candidates.push(*p);
        }
    }
    candidates.sort();
    // println!("{:?}", candidates);
    for _ in 0..q {
        let (l, r) = input_tuple();
        let upper_bound = binary_search(candidates.len() as i32, -1, |idx| {
            candidates[idx] >= l
        });
        let lower_bound = binary_search(-1, candidates.len() as i32, |idx| {
            candidates[idx] <= r
        });
        // println!("{}", upper_bound);
        // println!("{}", lower_bound);
        println!("{}", max(0, lower_bound - upper_bound + 1));
    }
}


Measured memory_bytes: 2816
#include <iostream>

typedef long long ll;

int main(){
  int N;
  std::cin >> N;
  ll a[N];
  for(int i = 0; i < N; ++i){
    std::cin >> a[i];
    if(a[i] == 0){
      std::cout << 0 << std::endl;
      return 0;
    }
  }
  
  ll max = 1e18;
  ll multi = 1;
  
  for(ll i; i < N; ++i){
    if(multi > max / a[i]){
      std::cout << -1 << std::endl;
      return 0;
    };
    multi *= a[i];
  }
  if(multi <= max){std::cout << multi << std::endl;}
  return 0;
}


Measured memory_bytes: 4356
import queue

q = queue.Queue()

num = int(input())
if num < 13:
    print(num)
    exit()
for _ in range(1,10):
    q.put(_)
for _ in range(num):
    x = q.get()
    t = x % 10

    if x % 10 != 0:
        q.put(10 * x -1 + t)
    q.put(10 * x + t)
    if x % 10 != 9:
        q.put(10 * x +1 + t)
print(x)

Measured memory_bytes: 57560
import pdb


def main():
    tmp = input().split()
    n = int(tmp[0])
    k = int(tmp[1])

    tree = []
    for i in range(n):
        tree.append(int(input()))

    tree.sort()
    #print(tree)
    min_num = -1
    
    for i in range(0, n-k+1):
        #print(tree[i], tree[i+k-1])
        tmp = tree[i+k-1] - tree[i]
        if min_num == -1:
            min_num = tmp
        elif min_num > tmp:
            min_num = tmp

    print("%d" % min_num)

        
if __name__ == '__main__':
    main()


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


int main() {
	
	int n;
	cin >> n;
	int cnt=0;
	int m=n+1;
	for(int j=0; j<n; j++) {
		int i;
		cin >> i;
		if(i<m) cnt++;
		m = min(i,m);
	}
	cout << cnt << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,m;
    int mini=100000;
    int cnt=0;
    cin>>n>>x;
    for(int i=0; i<n; i++)
    {
        cin>>m;
        if(x>=m)
        {
            x-=m;
            cnt++;
        }
        else
            break;
        if(mini>m)
            mini=m;
    }
    while(x>=mini)
    {
        x-=mini;
        cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    ll h;
    cin >> h;
    ll n = log2(h);
    ll ans =  (pow(2, n+1) - 1);
    out(ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll p = c * d / __gcd(c,d);
    ll aa = (a-1)/c + (a-1)/d - (a-1)/p;
    ll bb = b/c + b/d - b/p;

    cout << (b - bb) - (a - aa - 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll a, b;
ll gcd(ll a, ll b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}
int main()
{
	while(cin >> a >> b)
		cout << gcd(a, b) << " " << a/gcd(a, b)*b << endl;
	return 0;
}


Measured memory_bytes: 3056
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int mod_pow(int x,int y) {
    int res = 1;
    while(y > 0) {
        if(y%2) {
            res = res*x%mod;
        }
        x = x*x%mod;
        y/=2;
    }
    return res;
}
signed main(){
    int N,K;
    cin >> N >> K;
    vector<int>cnt(K+1);
    int res = 0;
    for(int i = K; i >= 2; i--) {
        cnt[i] += mod_pow(K/i,N);
        cnt[i] %= mod;
        for(int j = 2; j*j <= i; j++) {
            if(i%j == 0) {
                if(j*j != i) {
                    cnt[j] = (cnt[j]+mod-cnt[i])%mod;
                    cnt[i/j] = (cnt[i/j]+mod-cnt[i])%mod;
                }
                else {
                    cnt[j] = (cnt[j]+mod-cnt[i])%mod;
                }
            }
        }
        res += cnt[i];
    }
    int ans = (mod_pow(K,N)+mod-res)%mod;
    for(int i = 2; i <= K; i++) {
        ans += cnt[i]*i;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

string s;

int main() {
	fastio; cin >> s;
  if (s == "ABC") cout << "ARC";
  else cout << "ABC";
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
//1/(-x^4+2x^3-2x+1)^5
const int mod=1e9+7;
int test,n,p[11],res[22],fuck[22],iv[22],cur,ans;
struct mat
{
	int a[22][22];
	mat()
	{
		for (int i=1;i<=21;i++)
		{
			for (int j=1;j<=21;j++)
			a[i][j]=0;
		}
	}
	mat operator * (const mat &u) const
	{
		mat res;
		for (int i=1;i<=21;i++)
		{
			for (int j=1;j<=21;j++)
			{
				for (int k=1;k<=21;k++)
				{
					res.a[i][j]=(1ll*a[i][k]*u.a[k][j]+res.a[i][j])%mod;
				}
			}
		}
		return res;
	}
}ma,mb;
mat binpow(mat a,int t)
{
	mat res,p=a;
	for (int i=1;i<=21;i++) res.a[i][i]=1;
	for (int i=t;i;i>>=1)
	{
		if (i&1) res=res*p;
		p=p*p;
	}
	return res;
}
int main()
{
	p[0]=1;p[1]=-2;p[3]=2;p[4]=-1;
	res[0]=1;
	for (int i=1;i<=5;i++)
	{
		memset(fuck,0,sizeof(fuck));
		for (int j=(i-1)*4;j>=0;j--)
		{
			for (int k=4;k>=0;k--)
			{
				fuck[j+k]=(1ll*res[j]*p[k]+fuck[j+k])%mod;
			}
		}
		memcpy(res,fuck,sizeof(fuck));
	}
	iv[0]=1;
	for (int i=1;i<=20;i++)
	{
		cur=0;
		for (int j=1;j<=i;j++)
		{
			cur=(-1ll*res[j]*iv[i-j]+cur)%mod;
		}
		iv[i]=cur;
	}
	for (int i=0;i<=20;i++) iv[21]+=iv[i];
	for (int i=1;i<20;i++)
	{
		ma.a[i][i+1]=1;
	}
	for (int i=1;i<=20;i++)
	{
		ma.a[i][1]=-res[i];
		ma.a[i][21]=-res[i];
	}
	ma.a[21][21]=1;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d",&n);
		if (n<5) printf("0\n");
		else
		{
			n-=5;
			if (n<=20)
			{
				ans=0;
				for (int i=0;i<=n;i++) ans=(ans+iv[i])%mod;
				printf("%d\n",(ans+mod)%mod);
			}
			else 
			{
				mb=binpow(ma,n-20);ans=0;
				for (int i=1;i<=20;i++)
				{
					ans=(1ll*iv[21-i]*mb.a[i][21]+ans)%mod;
				}
				ans=(1ll*iv[21]*mb.a[21][21]+ans)%mod;
				printf("%d\n",(ans+mod)%mod);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3844
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
// #define MOD 1000000007
#define rp(i,n) for(int i=0;i<(n);++i)
#define up(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define ot(x) cout<<(x)
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()

int main(){
	int a,b; cin>>a>>b;
	if(a+b>=10) ote("error");
	else ote(a+b);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

map<char, int> mp;
int main() {
	mp['R'] = 0;
	mp['G'] = 1;
	mp['B'] = 2;
	int n; cin >> n;
	string s; cin >> s;
	int a[n];
	for(int i = 0; i < n; ++i) {
		a[i] = mp[s[i]];
	}
	int cnt[n][3] = {};
	for(int i = n - 1; i >= 0; --i) {
		for(int j = 0; j < 3; ++j) {
			if(i + 1 < n) cnt[i][j] = cnt[i + 1][j];
			if(a[i] == j) {
				++cnt[i][j];
			}
		}
	}
	int64_t ans = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j + 1 < n; ++j) {
			if(a[i] == a[j]) continue;
			for(int x = 0; x < 3; ++x) {
				if(x == a[i] or x == a[j]) continue;
				ans += cnt[j + 1][x];
				if(j + j - i < n and a[j + j - i] == x) ans--;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void)
{
    int a, b, c;
    char buf[256], op;

    while (1)
    {
        fgets(buf, 256, stdin);
        sscanf(buf, "%d %c %d", &a, &op, &b);
        switch (op)
        {
        case '?':
            goto end;
        case '+':
            c = a + b;
            break;
        case '-':
            c = a - b;
            break;
        case '*':
            c = a * b;
            break;
        case '/':
            c = a / b;
            break;
        default:
            continue;
        }
        printf("%d\n", c);
    }
end:
    return 0;
}



Measured memory_bytes: 2048
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 2000005
#define inf 0x7fffffff
//#define INF 1e18
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long  ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e9 + 7;
#define Mod 1000000000
#define sq(x) (x)*(x)
#define eps 1e-4
typedef pair<int, int> pii;
#define pi acos(-1.0)
//const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii;
inline ll rd() {
	ll x = 0;
	char c = getchar();
	bool f = false;
	while (!isdigit(c)) {
		if (c == '-') f = true;
		c = getchar();
	}
	while (isdigit(c)) {
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	return f ? -x : x;
}

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}
int sqr(int x) { return x * x; }


/*ll ans;
ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1; y = 0; return a;
	}
	ans = exgcd(b, a%b, x, y);
	ll t = x; x = y; y = t - a / b * y;
	return ans;
}
*/

ll  n;
ll A, B;
ll h[maxn];
bool chk(ll x) {
	ll tot = 0;
	ll q = A - B;
	for (int i = 1; i <= n; i++) {
	
		if (h[i]-B*x <= 0)continue;
		else {
			ll tp = h[i] - B * x;
			if (tp%q)tot += (tp / q + 1);
			else tot += (tp / q);
		}
	}
	if (tot <= x)return true;
	else return false;
}

int main() {
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> A >> B;
	for (int i = 1; i <= n; i++)rdllt(h[i]);
	sort(h + 1, h + 1 + n);
	ll l = 1, r = 1e9 + 1;
	ll ans = 0;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (chk(mid))r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main() {

    bool P[1000001];
    fill(P, P + 1000001, true);
    P[0] = P[1] = false;

    for (int i = 0; i <= 1000; i++) {
        if (P[i]) {
            for (int j = i * 2; j <= 1000000; j += i) P[j] = false;
        }
    }

    int n, x;
    while (cin >> n >> x) {
        if ((n | x) == 0) break;

        bool dp[x + 1];
        fill(dp, dp + x + 1, false);
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            int v;
            cin >> v;
            for (int j = 0; j <= x - v; j++) {
                if (dp[j] && !dp[j + v])
                    dp[j + v] = true;
            }
        }

        int ans = -1;
        for (int i = x; i >= 0; i--) {
            if (dp[i] && P[i]) {
                ans = i;
                break;
            }
        }

        if (ans != -1) {
            cout << ans << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}


Measured memory_bytes: 5040
#include <bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
const int N=5100;
int n,dp[N][N],ans,vi[N];
struct node
{
	int h,p;
}sh[N];
bool cmp(node a,node b)
{
	return (a.h+a.p<b.h+b.p || (a.h+a.p==b.h+b.p && a.p<b.p));
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld%lld",&sh[i].h,&sh[i].p);
	sort(sh+1,sh+1+n,cmp);
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++) dp[i][j]=inf;
	}
	dp[0][0]=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			dp[i][j]=min(dp[i][j],dp[i-1][j]);
			if (dp[i-1][j-1]<=sh[i].h) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+sh[i].p);
		}
	}
	for (int i=n;i>=1;i--)
	{
		if (dp[n][i]!=inf)
		{
			printf("%d\n",i);
			return 0;
		}
	}
}

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

using ll = long long; using vi = vector<int>; using vll = vector<ll>;
using vvi = vector<vi>; using vvll = vector<vll>;
const int MOD = 1e9 + 7;
const int INF = numeric_limits<int>::max();
const ll INF_MAX = numeric_limits<ll>::max();

int main() {
  int k, s;
  cin >> k >> s;
  int cnt = 0;
  for (int x = 0; x <= k; ++x) {
    for (int y = 0; y <= k; ++y) {
      int z = s - x - y;
      if (z >= 0 && z <= k) ++cnt;
    }
  }
  cout << cnt << endl;
}


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

int main()
{
	string s1;
	int l;
    cin>>s1;
    l=s1.size();
    for( int i=0;i<l;i++)
        if(s1[i]=='C')
            for( int j=i+1;j<l;j++)
                if(s1[j]=='F'){
                    cout<<"Yes";
                    return 0;
                }
       
     
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
#define MAX_N (105)
bool G[MAX_N][MAX_N];
int main()
{
    int n;
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
	int u, k;
	scanf("%d %d", &u, &k);
	for ( int j = 0; j < k; j++ ) {
	    int v;
	    scanf("%d", &v);
	    G[u-1][v-1] = true;
	}
    }

    for ( int i = 0; i < n; i++ ) {
	for ( int j = 0; j < n; j++ ) {
	    printf("%d%c", (int)G[i][j], (j == n - 1) ? '\n' : ' ');
	}
    }

    return 0;
}

Measured memory_bytes: 1036
# 偶奇が何組できるかで場合分けする

A, B = map(int, input().split())

if A % 2 == 0 and B % 2 == 0:  # 両方偶数の場合
    if ((B-1) - A + 1) % 4 == 0:
        print(0 ^ B)
    else:
        print(1 ^ B)

if A % 2 == 0 and B % 2 == 1:
    if (B - A + 1) % 4 == 0:
        print(0)
    else:
        print(1)

if A % 2 == 1 and B % 2 == 0:
    if ((B-1) - (A+1) + 1) % 4 == 0:
        print(0 ^ A ^ B)
    else:
        print(1 ^ A ^ B)

if A % 2 == 1 and B % 2 == 1:
    if (B - (A+1) + 1) % 4 == 0:
        print(A ^ 0)
    else:
        print(A ^ 1)


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

int main(){
    int N; int M; cin >> N >> M;
    int c[20];
    for(int i=0; i<M; i++){
        cin >> c[i];
    }
    int INF = 100000000;
    int dp [21][50010];
    for(int i=0; i<21; i++){
        for(int j=0; j<50010; j++){
            dp[i][j] = INF;
        }
    }
    for(int i=0; i<21; i++){
        dp[i][0]=0;
    }
    for(int i=0; i<M; i++){
        for(int j=1; j<50005; j++){
            if(j<c[i]) dp[i+1][j] = dp[i][j];
            else{
                dp[i+1][j] = min (dp[i][j], dp[i+1][j-c[i]]+1);
            }
        }
    }
    cout << dp[M][N] << endl;
}


Measured memory_bytes: 7196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[6001][6001],b[6001];
int n,m,x,y,mn;
unordered_set<ll> st;

bool check(int A,int B,int C){
  for(int i=0;i<=min(mn,a[A][B]);i++)
    for(int j=0;i+j<=min(mn,a[B][C]+i);j++){
      int k=x-i-j;
      if(i+k>4||j+k>4||a[A][C]<k)continue;
      if(A==C&&(a[A][A]<x||b[A]<12-2*(i+j+k)))continue;
      if(A==B&&(a[A][C]<j+k||b[A]<8-(2*i+j+k)))continue;
      if(B==C&&(a[A][B]<i+k||b[B]<8-(i+2*j+k)))continue;
      if(b[A]>=4-i-k&&b[B]>=4-i-j&&b[C]>=4-j-k)return 1;
    }
  return 0;
}

int main(){
  int t[6000],v[6000];
  cin>>n>>m>>x>>y;
  for(int i=0;i<n;i++){
    cin>>t[i];
    if(i>=m)b[t[i]]++;
  }
  for(int i=0;i<m;i++){
    cin>>v[i];
    int p=t[i]-v[i];
    if(v[i]>p)swap(v[i],p);
    a[v[i]][p]++;
  }
  if(x){
    ll M=6001;
    mn=min(4,x);
    for(int i=0;i<m;i++)
      for(int j=1;j<=6000;j++){
	ll p1=v[i],p2=t[i]-v[i],p3=j;
	if(p2>p3)swap(p2,p3);
	if(p1>p2)swap(p1,p2);
	ll s=p1*M*M+p2*M+p3;
	if(!st.count(s)&&check(p1,p2,p3))st.insert(s);
      }
    cout<<st.size()<<endl;
  }
  else{
    ll c4=0,c8=0,c12=0;
    for(int i=1;i<=6000;i++){
      if(b[i]>=4)c4++;
      if(b[i]>=8)c8++;
      if(b[i]>=12)c12++;
    }
    cout<<c4*(c4-1)*(c4-2)/6+c8*(c4-1)+c12<<endl;
  }
  return 0;
}

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

#define rep(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef long long ll;

main(){
  int n; cin >> n;
  rep(i,10){
    if(pow(2,i+1) > n){
      cout << pow(2,i) << endl;
      break;
    }
  }
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int f(int a, int b, int c){
    return 121*a + 11*b + c;
}

int main(void){
    Cin(int, n);
    Cin(string, s);
    
    vc<vc<bool>> dp(n+1, vc<bool>(1331, false));
    dp[0][f(10, 10, 10)] = true;
    
    For(i, n) For(j, 1331){
        if(dp[i][j]){
            dp[i+1][j] = true;
            dp[i+1][(j*11)%1331 + (s[i]-'0')] = true;
        }
    }
  	int ans = 0;
    For(a, 10) For(b, 10) For(c, 10) if(dp[n][f(a, b, c)]) ans ++;
  	Cout(ans);
}




Measured memory_bytes: 6656
#include <iostream>
#include <bits/stdc++.h>
#define f(i,a,b) for (int i=a; i<b; i++)
#define F(i,a,b) for (int i=a; i<=b; i++)
#define fod(i,a,b) for (int i=a; i>=b; i--)
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define MOD 1000000007

using namespace std;

template<class t> inline t read(t &x){
	x=0;char c=getchar();bool f=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
	if(x<0){putchar('-'),write(-x);}
	else{if(x>9)write(x/10);putchar('0'+x%10);}
}

typedef long long ll;
typedef pair<int, int> pii;
typedef map<int,int> mii;

const int N=1e5+10;
long long a[N]; // weight
long long b[N]; // value
long long dp[N];
int main()
{

    long long n,ans=0,w;
    read(n), read(w);

    for(int i=0;i<n;i++)
        read(a[i]), read(b[i]);

    for(long long i=0;i<n;i++){
        for(long long j=w-a[i];j>=0;j--){
            dp[a[i]+j]=max(dp[a[i]+j],dp[j]+b[i]);
            }
        }
    for(int i=0;i<=w;i++)
        ans=max(ans,dp[i]);

    write(ans);
}


Measured memory_bytes: 1024
module Main where
    import Data.List
    import Control.Monad
    
    main = do
        {-
        n <- getLine
        lines<-getLines (read n ::Int)
        -}        
        inputs<-getInputs        
        print ( foldr (*) 1 (map pred inputs))
        
        
    read' s = read s ::Integer

    getInputs = do
        line <- getLine
        let inputs = map read' (words line)
        return inputs

    getLines n = do
        lines <- (replicateM n getLine)
        return lines

    getGCD::Integer->Integer->Integer
    getGCD m n 
        | m < n = (getGCD n m)
        | n == 0 = m
        | otherwise = getGCD (mod m n) n

    getLCM::Integer->Integer->Integer
    getLCM m n = div (m * n) (getGCD m n)
   

Measured memory_bytes: 508
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int K = sc.nextInt();
      int A = sc.nextInt();
      int B = sc.nextInt();
      int C = 0;
      for(int i=A;i<B+1;i++){
        if(i%K==0){
          C=C+1;
        }else{
          continue;
        }
      }if(C>0){
        System.out.println("OK");
      }else{
        System.out.println("NG");
      }
    }
}

Measured memory_bytes: 35704
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = A[0] // 2
    s = A[0] % 2
    for a in A[1:]:
        diff_p = min(s, a)
        self_p = (a - diff_p) // 2
        ans += diff_p + self_p
        s = a - diff_p - 2 * self_p
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 13676
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//#define ll long long
#define pb emplace_back
#define mp make_pair
#define nt _ll128
#define ld long double
long double PI =3.14159265358979323846;
using ll = long long;



const ll modo=1e9+7;
const ll inf=LONG_LONG_MAX;
const ll ms=(2e5)+5;




int main()
{
    idfc;
    ll n;
    cin>>n;
    ll p;
    char e;
    vector<char> vv;
  ll nn=26;
    while(n)
    {
        p=(n%nn);
        if(!p){p=26;n--;}
        e=p+96;
        vv.pb(e);
        n/=26;
    }

    for(ll i=vv.size()-1;i>=0;i--)cout<<vv[i];


    return 0;
}


Measured memory_bytes: 3652
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    slen = len(s)
    ans = 0
    for i in range(1,slen):
        if s[i-1]!= s[i]:
            ans += 1
    
    print(ans)


solve()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<typename T> inline istream& operator>>(istream &i, vector<T> &v) {rep(j, size(v)) i >> v[j]; return i;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> T gcd(T a, T b) {if(b==0)return a; else return gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return a/gcd(a,b)*b;}
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    V<ld> a(n);
    cin >> a;
    ld sum = 0;
    rep(i, n) sum += 1.0 / a[i];
    ld ans = 1 / sum;
    printf("%.10Lf\n", ans);
}

Measured memory_bytes: 3864
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
MOD = 10**9 + 7

n,k = map(int,input().split())
ans = 0
d = [i for i in range(n+1)]
for i in range(k,n+2):
    l = (d[i-1])*(d[i-1]+1)//2
    r = (n)*(n+1)//2 - (n+1 - i-1)*(n+2-i-1)//2
    ans += r-l +1
print(ans%MOD)

Measured memory_bytes: 17304
dice = map(int, raw_input().split())

table = [ [1,2,4,3], # top:1
          [5,2,0,3], # top:2
          [1,5,4,0], # top:3
          [1,0,4,5], # top:4
          [0,2,5,3], # top:5
          [4,2,1,3]] # top:6

q = input()
for i in xrange(q):
    top, front = map(int, raw_input().split())
    tt = dice.index(top)          # get top side's index
    tf = dice.index(front)        # get front side's index
    tf = table[tt].index(tf) + 1  # get right side's index using talbe
    if tf > 3: tf = 0
    print dice[table[tt][tf]]

Measured memory_bytes: 6352
#include<bits/stdc++.h>
using namespace std;
//double prob(double ar[],int n){
//	int dp[n+1][((n+1)/2)+1];
//	for(int i=1;i<=n;i++)
//	dp[i][0]=1;
//	for(int x=1;x<=(n+1)/2;x++)
//	dp[0][x]=0;
//	for(int i=2;i<=n;i++){
//		for(int x=2;x<=(n+1)/2;x++){
//			dp[i][x]=ar[i]*dp[i-1][x-1]+(1-ar[i])*dp[i-1][x];
//		}
//	}
//	return dp[n][(n+1)/2];
//}
double dp[3001][3001];
double prob(vector<double>&ar,int i,int heads){
	if(heads<=0){
		return 1;
	}
	if(i==0){
		return 0;
	}

	if(dp[i][heads]>-0.9){
		return dp[i][heads];
	}
	return dp[i][heads]=ar[i]*prob(ar,i-1,heads-1)+(1-ar[i])*prob(ar,i-1,heads);
}
signed main(){
	int n;
	cin>>n;
	vector<double>ar(n+1);
	memset(dp,-1,sizeof dp);
	for(int i=1;i<=n;i++){
		cin>>ar[i];
	}
	cout<<fixed<<setprecision(10)<<prob(ar,n,(n+1)/2)<<endl;
	return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using P = pair<int,int>;
void Yes() {
    cout << "Yes" << endl;
}
void No() {
    cout << "No" << endl;
}
int main(void) {
    int x; cin >> x;
    if (x >= 30) Yes();
    else No();
}


Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;

const int MAX = 100000;

int main(){
  stack<char> P;
  char r;
  string X;
  cin >> X;
  for(int i=0;i<X.size();i++){
    r=X[i];
    if(P.empty()){
      P.push(r);
      continue;
    }
    if(P.top()=='S' && r=='T'){
      P.pop();
    } else{
      P.push(r);
    }
  }
  cout << P.size() << endl;
  return 0;
}

Measured memory_bytes: 644
// https://atcoder.jp/contests/agc029/tasks/agc029_c
//
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::fmt::*;
use std::io::*;
use std::str::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn isok(k: usize, a: &Vec<i32>) -> bool {
    // (char, length)
    let mut d: VecDeque<(usize, i32)> = VecDeque::new();
    let mut len = 0;
    for &ai in a {
        if len < ai {
            d.push_back((0, ai - len));
            len = ai;
        } else {
            while len > ai {
                let mut w = d.pop_back().unwrap();
                if len - w.1 >= ai {
                    len -= w.1;
                    continue;
                }
                w.1 -= len - ai;
                len = ai;
                d.push_back(w);
            }

            // increment one
            let mut kuri = 0;
            while d.len() >= 1 {
                let mut w = d.pop_back().unwrap();
                if w.0 != k - 1 {
                    if w.1 >= 2 {
                        d.push_back((w.0, w.1 - 1));
                    }
                    d.push_back((w.0 + 1, 1));
                    break;
                } else {
                    kuri += w.1;
                }
            }
            if kuri == ai {
                return false;
            }
            if kuri >= 1 {
                d.push_back((0, kuri));
            }
        }
    }
    return true;
}

fn main() {
    input! {
        n: usize,
        a: [i32; n]
    };

    let mut ng = 0;
    let mut ok = n;
    while ok - ng > 1 {
        let med = (ok + ng) / 2;
        if isok(med, &a) {
            ok = med;
        } else {
            ng = med;
        }
    }
    println!("{}", ok);
}


Measured memory_bytes: 12920
#include <stdio.h>

/* 90度単位の回転行列 */
int ROTATION[4][2][2] = {
	{{1, 0}, {0, 1}},
	{{0, -1}, {1, 0}},
	{{-1, 0}, {0, -1}},
	{{0, 1}, {-1, 0}}
};

typedef struct { int x; int y; } Vector;

Vector rotate(Vector v, int angle) {
	Vector w;
	w.x = v.x * ROTATION[angle][0][0] + v.y * ROTATION[angle][0][1];
	w.y = v.x * ROTATION[angle][1][0] + v.y * ROTATION[angle][1][1];
	return w;
}

/* 折れ線 */
typedef struct {
	int m;
	int x[10];
	int y[10];
} Polygon;

/* 標準入力から折れ線を読み込む */
void scanPolygon(Polygon *p) {
	int i;
	scanf("%d", &(p->m));
	for (i = 0; i < p->m; i++) scanf("%d%d", &(p->x[i]), &(p->y[i]));
}

/* 2つの折れ線が同じ形状か判定する */
int congruent(Polygon p1, Polygon p2) {
	int i, j;
	if (p1.m != p2.m) return 0;
	/* 90度づつ回転させて判定する */
	for (i = 0; i < 4; i++) {
		/* 各辺を比較する */
		for (j = 0; j < p1.m - 1; j++) {
			Vector v = {p2.x[j+1] - p2.x[j], p2.y[j+1] - p2.y[j]};
			v = rotate(v, i);
			if (p1.x[j+1] - p1.x[j] != v.x || p1.y[j+1] - p1.y[j] != v.y) break; /* 不一致 */
		}
		if (j == p1.m - 1) return 1;
	}
	return 0;
}

int main(void) {
	int n; /* データセット数 */
	Polygon s0, s1, p; /* 折れ線 */
	int i;

	/* データセット毎の処理 */
	while (scanf("%d", &n) == 1 && n >= 1 && n <= 50) {
		/* 折れ線0をs0として入力する */
		scanPolygon(&s0);
		/* 折れ線0の頂点を逆順にしたs1を生成する */
		s1.m = s0.m;
		for (i = 0; i < s0.m; i++) {
			s1.x[s0.m - 1 - i] = s0.x[i];
			s1.y[s0.m - 1 - i] = s0.y[i];
		}

		/* 折れ線毎の処理 */
		for (i = 1; i <= n; i++) {
			scanPolygon(&p); /* 折れ線1?nを入力する */
			if (congruent(s0, p)) printf("%d\n", i);
			else if (congruent(s1, p)) printf("%d\n", i);
		}

		printf("+++++\n"); /* データセットの区切り */
	}

    return 0;
}

Measured memory_bytes: 612
/*
    Author      : Dinesh Verra
    College     : ABV-IIITM
    Date        : 20/08/2020
*/
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp> 
// using namespace boost::multiprecision; 
using namespace std;
typedef long long ll;
// #define ll int
typedef unsigned long long ull;
#define cu continue
#define br break
#define pb push_back
#define eb emplace_back
#define mod 1000000007
#define inf LLONG_MAX
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define F first
#define S second
#define vll vector <ll>
#define vpll vector <pll>
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define all(v) v.begin(),v.end()
#define nl cout<<'\n'

template <typename A1>
void prn(A1&& arg)
{
	cout<<arg<<'\n';
}
template <typename A1, typename... A>
void prn(A1&& arg, A&&... args)
{
	cout<<arg<<' ';
	prn(args...);
}

#define N 300005
ll r[N],c[N];

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

	ll n,m,q,x,y;
	cin>>n>>m>>q;
	map <pll,ll> mp;
	while(q--)
	{
		cin>>x>>y;
		r[x]++;
		c[y]++;
		mp[{x,y}]=1;
	}
	ll tmp,mxr=0,mxc=0,idx,idy;
	for(ll i=1;i<=n;i++) 
	{
		if(r[i]>mxr)
		{
			mxr=r[i];
			idx=i;
		}
	}
	for(ll i=1;i<=m;i++)
	{
		tmp=c[i];
		if(mp.find({idx,i})!=mp.end()) tmp--;
		mxc=max(mxc,tmp);
	}
	ll ans=mxr+mxc;

	mxr=0,mxc=0;
	tmp=0;

	for(ll i=1;i<=m;i++) 
	{
		if(c[i]>mxc)
		{
			mxc=c[i];
			idy=i;
		}
	}
	for(ll i=1;i<=n;i++)
	{
		tmp=r[i];
		if(mp.find({i,idy})!=mp.end()) tmp--;
		mxr=max(mxr,tmp);
	}
	ans=max(mxr+mxc,ans);

	prn(ans);
}

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

using namespace std;

int a[100100];

int main()
{
//    freopen("int.txt","r",stdin);
    int n;
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
        {
            int x=i;
            if(x%3==0)
            {
                cout<<" "<<i;
                continue;
            }
            do
            {
                if(x%10==3)
                {
                    cout<<" "<<i;
                    break;
                }
                x/=10;
            }while(x);

        }
        cout<<endl;
    }

}



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

#define ff first
#define endl "\n"
#define ss second
using namespace std;
#define maxn 2000006
#define pb push_back
#define ll long long
#define lll __int128
#define vll vector<ll>
#define mll map<ll,ll>
#define MOD 1000000007
#define pll pair<ll,ll>
#define ull unsigned long long
#define f(i,x,n) for(ll i=x;i<=n;i++)
#define fr(i,x,n) for(ll i=x;i>=n;i--)
inline ll min(ll a, ll b, ll c) { return min(min(a, b), c);}
inline ll max(ll a, ll b, ll c) { return max(max(a, b), c);}
inline void fastio(){ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);}

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



int main(){
	fastio();

	ll h,n; cin>>h>>n;
	ll a[n+1]={}, b[n+1]={};
	f(i,1,n) cin>>a[i]>>b[i];

	ll dp[h+1]={};
	f(i,1,h){
		dp[i]=LLONG_MAX;
		f(j,1,n) dp[i]=min(dp[i],dp[max(0ll,i-a[j])]+b[j]);
	}

	cout<<dp[h];

	return 0;
}


Measured memory_bytes: 384
package main

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

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	s := sc.Text()
	x, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return x
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	as := make([]int, n)
	for i := 0; i < n; i++ {
		as[i] = nextInt(sc)
	}
	sort(as, n)
}

func printArray(as []int) {
	fmt.Println(strings.Trim(fmt.Sprint(as), "[]"))
}

func sort(as []int, n int) {
	cnt := 0
	for i := 0; i < n; i++ {
		minIndex := i
		for j := i; j < n; j++ {
			a := as[j]
			if as[minIndex] > a {
				minIndex = j
			}
		}
		if minIndex != i {
			tmp := as[i]
			as[i] = as[minIndex]
			as[minIndex] = tmp
			cnt = cnt + 1
		}
	}
	printArray(as)
	fmt.Println(cnt)
}



Measured memory_bytes: 1152
#B - Contest with Drinks Easy
N = int(input())
T = list(map(int,input().split()))
M = int(input())
P = []
X = []
for _ in range(M):
    Pi,Xi = map(int,input().split())
    P.append(Pi)
    X.append(Xi)

A = []
for i in range(M):
    T_copy = T.copy()
    T_copy[P[i]-1] = X[i]
    A.append(sum(T_copy))    

for k in range(M):
    print(A[k])

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
int n,p[25],cnt;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=2;i<=n-1;i++){
        if(p[i]>min(p[i-1],p[i+1])&&p[i]<max(p[i-1],p[i+1]))cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vs vector<string>
#define pb push_back
#define vb vector<bool>
#define rep(i,n) for(int i = 0;i<n;i++)
#define repk(k,n) for(int i = k;i<n;i++)
#define all(v) v.begin(),v.end()
#define print(v) for(auto n:v){cout << n << "\t";}
#define input(v) for(auto &i:v){cin >> i;}
#define mod 1000000007
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
using namespace std;

void addedge(int a, int b, vector<int>v[]){
	v[a].push_back(b);
	v[b].push_back(a);
}
void dfs(vector<int>v[],vb &visited, map<int,int>&mp,int val, int node){
	if(visited[node]){
		return;
	}
	else{
		visited[node]=true;
		mp[val]++;
	}
	for(int i =0;i<v[node].size();i++){
		dfs(v,visited, mp, val,v[node][i]);
	}
}
void solve(){
	ll n,m;
	cin >> n >> m;

	vector<int>v[n+1];
	for(int i =0;i<m;i++){
		int t,u;
		cin >>t>>u;
		addedge(u,t,v);
	}
	map<int, int>mp;
	vb visited(n+1,false);
	int t = 0;
	for(int i =0;i<n;i++){
		if(visited[i]==false){
			dfs(v,visited,mp, ++t,i);
		}
	}
	int mx = 0;
	for(auto i:mp){
		mx = max(mx,i.second);
	}
	cout << mx << endl;

}


int main(){
	ll t = 1;
	// cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

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

using namespace std;

#define N 1200000

int n,ans;
char s[N];

bool check(int t){
	int l=0,r=t,p=0;
	for (int i=1;i<=n;++i){
		if (s[i]=='0'){++l; ++r;}
		if (s[i]=='1'){--l; --r;}
		if (s[i]=='?'){--l; ++r;}
		if (!p){
			l=max(l,0);
			r=min(r,t);
		}
		else{
			if (l<0) l=1;
			if (r>t) r=t-1;
		}
		if (l>r) return 0;
		if (l==r) p=1;
	}
	return 1;
}

int main(){
	scanf("%s",s+1); n=strlen(s+1);
	int l=1,r=n;
	while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid)){ans=mid; r=mid-1;}
		else l=mid+1;
	}
	printf("%d\n",ans);
	
	return 0;
}
			

Measured memory_bytes: 4804
#include<iostream>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;

int H,W;
char c[505][505];
char r[505][505];
char b[505][505];
int main(){
    cin>>H>>W;
    for(int i=0;i<H;i++){
        cin>>c[i];
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(j==0){
                r[i][j]='#';
                b[i][j]='.';
            }else if(j==W-1){
                r[i][j]='.';
                b[i][j]='#';
            }else{
                if(i%2==0){
                    r[i][j]='.';
                    b[i][j]='#';
                }
                else{
                    r[i][j]='#';
                    b[i][j]='.';
                }
            }
        }
    }

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(c[i][j]=='#'){
                if(i%2==0){
                    r[i][j]='#';
                }
                else{
                    b[i][j]='#';
                }
            }
        }
    }
    cout<<endl;
    for(int i=0;i<H;i++){
        cout << r[i] <<endl;
    }
    cout<<endl;
    for(int i=0;i<H;i++){
        cout << b[i] <<endl;
    }

    return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;





int main(void) {
    
    
    int h,n;
    cin>>h>>n;
    vi dp(h+10,INF);
    dp[h]=0;
    vi a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    for(int i=h;i>=0;i--){
        if(dp[i]==INF)continue;
        for(int j=0;j<n;j++){
            int next = max(i-a[j],0);
            chmin(dp[next],dp[i]+b[j]);
        }
    }
    cout<<dp[0]<<endl;
    
}


Measured memory_bytes: 256
N=int(input())
H=[0]+[int(x) for x in input().split()]
P=max(H)
count=0
for i in range(P):
  Q=P-i
  for j in range(1,N+1):
    if H[j-1]<Q and H[j]>=Q:
      count +=1
print(count)

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

int main() {
	int N;
	cin >> N;
	if( N >= 2){
		vector<unsigned> f;
		f.push_back(1);
		f.push_back(1);
		for(int i = 2; i <= N; i++){
			int temp = f.at(i-1) + f.at(i-2);
			f.push_back(temp);
		}
		cout << f.at(N) << endl;;
	}else{
		cout << 1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3112
#include <stdio.h>

int main(){

  int N,minv,maxv=0,i,j;

  scanf("%d",&N);
  
  int R[N];

  for(i=0;i<N;i++){
    scanf("%d",&R[i]);
  }
  
  minv = R[0];

  maxv = R[1] - R[0];

  for(j=1;j<=N-1;j++){
    if(maxv < R[j] - minv){
      maxv = R[j] - minv;
    }
    else{
      maxv = maxv;
    }

    if(minv < R[j]){
      minv = minv;
    }
    else{
      minv = R[j];
    }
    
    
  }

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

  return 0;
}



Measured memory_bytes: 2516
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
#define vpl vector<pair<ll,ll>>
#define vvl vector<vector<ll>> //a(縦行,vector<ll>(横列));
#include<algorithm>//__gcd(a,b)

int main(){
    int a,b,c,d;cin>>a>>b>>c>>d;
    bool ta=1;

    rep(i,1000){
        if(c-b<=0){ta=1;break;}
        c-=b;
        if(a-d<=0){ta=0;break;}
        a-=d;
        
    }

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

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <complex>

using namespace std;

const double PI=3.14159265;

int main()
{
	int n,w,a,b,*ans;
	cin>>w>>n;

	ans=new int[w];
	for(int i=0;i<w;i++) ans[i]=i+1;

	for(int i=0;i<n;i++){
		scanf("%d,%d",&a,&b);
		swap(ans[a-1],ans[b-1]);
	}

	for(int i=0;i<w;i++) cout<<ans[i]<<endl;

	return 0;

}

Measured memory_bytes: 1240
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
 
int main(){
  int n, next, repeat=0;
  long long k, step;
  cin >> n >> k;
  vector<int> A(n), path(n), log(0);
  
  for(int i=0;i<n;i++){
    cin >> A[i];
    path[i]=0;
  }
  
  int flag=0, flagB=0;
  step=0;
  next=1;
  while(flag==0){
    if(path[next-1]==1 && flagB==0){
      flagB=1;
      int j=0;
      while(log[j]!=next-1){
        j++;
      }
      repeat = step-j;
      step = step + ((k-step)/repeat)*repeat;
    if(step==k){flag=1;}
      
    }else{
     path[next-1]=1;
     log.push_back(next-1);
     step++;
     next=A[next-1];
     
    if(step==k){flag=1;}
    }
  }

  cout << next << endl;
}

Measured memory_bytes: 5880
weight = [512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

while n = gets
  n = n.to_i
  arr = []
  weight.each{|w|
    if n >= w
      n -= w
      arr.unshift(w)
      break if n == 0
    end
  }
  puts arr.join(" ")
end

Measured memory_bytes: 8644