akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxN = (int)1e5 + 10;

int N, M;
int P[maxN], L[maxN], R[maxN];

void input()
{
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++)
        scanf("%d", P + i);
    for (int i = 1; i <= M; i++)
        scanf("%d%d", L + i, R + i);
}

int ufs[maxN];
void init() { for (int i = 1; i <= N; i++) ufs[i] = i; }
int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }
void unify(int x, int y) { ufs[find(x)] = find(y); }

int solve()
{
    init();
    for (int i = 1; i <= M; i++)
        unify(L[i], R[i]);
    int ans = 0;
    for (int i = 1; i <= N; i++)
        if (find(i) == find(P[i]))
            ans += 1;
    return ans;
}

int main()
{
    input();
    printf("%d\n", solve());
    return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
#include <math.h>
int main(void)
{

    double r;
    double syu, menseki;

    scanf("%lf", &r);

    syu = 2 * M_PI * r;
    menseki = r * r * M_PI;

    printf("%f %f\n", menseki, syu);
    return 0;
}

Measured memory_bytes: 648
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong(), k = scan.nextLong();
		
		if(n == 0 || k == 0) {
			System.out.println(n);
			
		}else if(n < k) {
			System.out.println(Math.min(n, k - n));
			
		}else {
			System.out.println(Math.min(n % k, k - ( n % k )));
			
		}
		
		
	}
}


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

using namespace std;
using VI = vector<int>;
using VPI = vector<pair<int, int>>;
using LL = long long;

#define FOR(a,n) for(int i=a;i<n;i++)
#define rFOR(a,n) for(int i=n-1;i>=a;i--)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]
#define pIN(n,t) for(int i=0;i<n;i++){int a,b; cin>>a>>b; t.emplace_back(a,b);}
#define SORT(a) sort(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()

LL gcd(LL m, LL n)
{
	LL temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

bool IsPrime(LL num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

int main()
{
	LL a, b, n, count = 1;
	cin >> a >> b;

	if (a < b)swap(a, b);

	n = gcd(a, b);

	FOR(2, sqrt(n) + 1)
	{
		if (n % i == 0)
		{
			if (IsPrime(i))count++;
			if (n / i > sqrt(n) + 1)
			{
				if(IsPrime(n / i))count++;
			}
		}
	}
	if (IsPrime(n))count++;

	cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define sd(t)       scanf("%d",&(t))
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define hii         cout << "hii" << endl
#define okay        cout << "okay" << endl
#define hey         cout << "hey" << endl
const int INF = 1e12;
const int MOD = 1e9+7;
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.x << ' ' << v.y; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.x << "=>" << i.y << ')' << ' '; return os; } 
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE
 
clock_t time_p=clock();
void starboy1299()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
 
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("jjj.txt", "w", stdout);
    #endif
}

const int N = 2e5+5;
int arr[N];
int n, k;

bool ok(int mid){

    int cnt = 0;
    for(int i=1; i<=n; i++){
        cnt += arr[i]/mid;
        if(arr[i]%mid == 0) cnt--;
    }

    return (cnt <= k);  
}

void solve(){

    cin >> n >> k;

    rep(i, 1, n+1){
        cin >> arr[i];
    }

    sort(arr+1, arr+n+1);
    int s = 1, e = arr[n];

    while(s <= e){
        int mid = s+e >> 1;

        if(ok(mid)){
            e = mid-1;
        }
        else s = mid+1;
    }


    cout << s << endl;
}         

int32_t main(){
    fast();
    int t = 1;
    // cin>> t;
    for(int i=1; i<=t; i++){
        // cout << "Case #" << i << ": ";
        solve();
    }
    starboy1299();
}

Measured memory_bytes: 5348
/*
********************
Author : Sahil Kundu
********************
*/
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb(i) push_back(i)
#define pp() pop_back()
#define f first
#define s second
#define mk(l,r) make_pair(l,r)
#define all(vc) vc.begin(),vc.end()
#define bg(vc) vc.begin()
#define ed(vc) vc.end()
#define w(t) while(t--)
const ll MAX=1e5+5;
const ll INF=2e18;
ll n;
ll dp[62][2][2];
ll call(int pos,int carry,int f)
{
    if(dp[pos][carry][f]!=-1)return dp[pos][carry][f];
    if(pos==60)return (!carry and !f);
    int nthbit = (n>>pos)&1;
    ll res=0;
    for(int a=0;a<2;a++)
    {
        for(int b=0;b<=a;b++)
        {
            int curcarry=(a+b+carry)/2;
            int curbit=(a+b+carry)%2;
            int ff=f;
            if(curbit<nthbit)ff=0;
            if(curbit>nthbit)ff=1;
            res=(res+call(pos+1,curcarry,ff))%mod;
        }
    }
    return dp[pos][carry][f]=res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin>>t;
    w(t)
    {
       cin>>n;
        memset(dp,-1,sizeof dp);
       cout<<call(0,0,0);
    }
}
/*ll msb(ll x)
{
	ll k=(ll)log2(x);
	return (ll)(pow(2,k));
}
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}*/

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot=lambda x,y:x+y,e=0,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=S[i]+B[i]

        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        cnt=0
        bit=BIT([0]*(n+1))
        for i in range(n+1):
            cnt+=bit.sum(S[i]+1)
            bit.add(S[i])

        return cnt*2>=n*(n+1)//2

    print(bisection(0,M,check))
resolve()

Measured memory_bytes: 127284
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define pb			    push_back
#define all(v)			((v).begin()), ((v).end())
#define SZ(v)			((int)((v).size()))
#define clr(v, d)		memset(v, d, sizeof(v))
#define has(c,i) 		((c).find(i) != end(c))
#define has_str(s, c)	((s).find(c) != string::npos)
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    map<string, int> mp;
    while (n--) {
        string s;
        cin >> s;
        mp[s]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
    return 0;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define int long long 
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
  x = 0;char c = getchar();bool f = 0;
  for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
  for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if(f) x = -x;
}
const int N = 6000, inf = 1e13 + 233;
vector<int> G[N];
int n, f[N], g[2][N], x[N];
inline void U(int &x, int y) {
  if(x > y) x = y;
}
inline void dfs(int u) {
  if(!(int)G[u].size()) return ;
  for(auto v: G[u]) dfs(v);
  f[u] = inf;
  memset(g, 38, sizeof g);
  int cur = 0;
  g[cur][0] = 0;
  for(auto v: G[u]) {
    cur ^= 1;
    memset(g[cur], 38, sizeof g[cur]);
    for(int i = 0; i <= x[u]; i ++) {
      if(i - f[v] >= 0)
	U(g[cur][i], g[cur ^ 1][i - f[v]] + x[v]);
      if(i - x[v] >= 0)
	U(g[cur][i], g[cur ^ 1][i - x[v]] + f[v]);
    }
  }
  for(int i = 0; i <= x[u]; i ++)
    U(f[u], g[cur][i]);
}

main(void) {
  read(n);
  for(int i = 2; i <= n; i ++) {
    int u; read(u);
    G[u].push_back(i);
  }
  for(int i = 1; i <= n; i ++)
    read(x[i]);
  dfs(1);
  cout << (f[1] == inf ? "IMPOSSIBLE" : "POSSIBLE") << "\n";
}


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

int main()
{
    int n, x, t, ans = 0,cnt=0;
    cin >> n >> x >> t;
    while (ans < n)
    {
        ans += x;
        cnt++;
    }
    cout << cnt * t << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii ;
#define f first
#define s second

priority_queue <pii> Q;

int main() {
    int N, K ;
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++) {
        int a ;
        scanf("%d", &a);
        Q.push({-a, i});
        if(i<K) continue;
        while(!Q.empty() && Q.top().s <= i-K)
            Q.pop();
        if(i!=K)
            printf(" ");
        printf("%d", -Q.top().f);
    }
    printf("\n");
}



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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll n;
vll a(40);

void f(){
  ll sum=0;
  ll i;
  for(i=0; sum+(1<<i)<n; i+=2){
    sum+=(1LL<<i);
  }
  a[i]=1;
  n-=(1LL<<i);
}

void g(){
  ll sum=0;
  ll tmp=abs(n);
  ll i;
  for(i=1; sum+(1LL<<i)<tmp; i+=2){
    sum+=(1LL<<i);
  }
  a[i]=1;
  n+=(1LL<<i);
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  cin>>n;
  if(n==0){
    cout<<0<<endl;
    return 0;
  }
  
  
  while(n!=0){
    if(n>0) f();
    else g();
  }
  
  string ans="";
  bool flg=false;
  rrep(i,40){
    if(flg){
      ans+=('0'+a[i]);
    }else if(a[i]==1){
      ans+='1';
      flg=true;
    }
  }
  cout<<ans<<endl;
}

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

a_min = float(a)*12.5
a_max = float(a+1)*12.5
b_min = float(b*10)
b_max = float((b+1)*10)

o_min = max(a_min, b_min)
o_max = min(a_max, b_max)

import math

if math.ceil(o_min) < o_max:
    print(str(math.ceil(o_min)))
else:
    print('-1')

Measured memory_bytes: 3064
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//円周率
const double PI = 3.14159265358979323846;

int main() {
	int N, K; cin >> N >> K;
	vector<ll> l(N);
	rep(i, N)cin >> l[i];

	sort(ALL(l));
	reverse(ALL(l));

	ll ans = 0;
	rep(i, K)ans += l[i];

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep0(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<string, int, int> TU;

int main()
{
    int N;
    cin >> N;
    double res=0;
    rep0(i,N){
        double a;
        string b;
        cin >> a >>  b;
        if(b=="JPY"){
            res+=a;
        }else{
            res+=a*380000;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3796
i=input
t=int
N=t(i())
A=list(map(t,i().split()))
c=0
f = 1
while f:
    f = 0
    for j in range(1,N)[::-1]:
        if A[j]<A[j-1]:
            A[j],A[j-1]=A[j-1],A[j]
            f=1
            c+=1
print(*A)
print(c)

Measured memory_bytes: 5608
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reve(a) reverse(a.begin(), a.end())
typedef long long ll;
const ll MOD = 1e9+7;

int main(){
  string s;
  cin >> s;
  int sz = s.size();
  int ans = 0;
  char p = s.at(0);
  for(int i=1; i<sz; i++){
    if(s.at(i)!=p){
      ans++;
      p = s.at(i);
    }
  }
  cout << ans << endl;
}

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

long long mpower(long long x, long long y, long long mod) {
  long long ans = 1;
  while (y>0) {
    int r = y % 2;
    if(r==1) {
      ans = x * ans % mod;
    }
    x = x * x % mod;
    y /= 2;
  }
  return ans;
}

long long minv(long long x, long long mod){
  long long ans;
  ans = mpower(x, mod-2, mod);
  return ans;
}

int main() {
  long long N,A,B,K;
  long long mod = 998244353;
  cin >> N >> A >> B >> K;
  //make factorial and invFactorial Table
  vector<long long> fact(N+1);
  vector<long long> invfact(N+1);
  fact.at(0)=1;
  for(int i=1; i<=N; i++){
    fact.at(i) = i * fact.at(i-1) % mod;
  }
  invfact.at(N) = minv(fact.at(N),mod);
  for(int i=N-1; i>=0; i--) {
    invfact.at(i) = (i+1) * invfact.at(i+1) % mod;
  }
  //solve Ax + By = K
  //put C = K - Ax
  long long ans = 0;
  for(int x=0;x<=N;x++){
    long long C = K - A*x;
    if(C>=0 && C%B==0) {
      long long y = C/B;
      if(y>=0 && y<=N) {
        long long nCx = fact.at(N) * invfact.at(x) % mod * invfact.at(N-x) % mod;
        long long nCy = fact.at(N) * invfact.at(y) % mod * invfact.at(N-y) % mod;
        long long patternNum = nCx * nCy % mod;
        ans += patternNum;
      }
      
    }
  }
  
  cout << ans % mod << endl;
}

Measured memory_bytes: 4992
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

add_all_count = [0,0,0,0,0,0]
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    add_all_count[i%6] += 1
  else:
    constant_term += add_single[i%6][int(s)]

def convolve(x,y):
  z = np.zeros(25,dtype=np.int64)
  for i in range(13):
    z[i:i+13] += x[i] * y % MOD
  z[:12] += z[13:25]
  return z[:13] % MOD

def nth_convolve(arr,n):
  if n == 0:
    x = np.zeros(13, dtype=np.int64)
    x[0] = 1
    return x
  if n == 1:
    return arr
  x = nth_convolve(arr,n>>1)
  x = convolve(x,x)
  return convolve(arr,x) if n & 1 else x

dp = np.zeros(13, dtype=np.int64)
dp[constant_term % 13] = 1
for arr,n in zip(add_all, add_all_count):
  dp = convolve(dp, nth_convolve(arr,n))

print(dp[5])


Measured memory_bytes: 12724
answers = Array.new

while s = $stdin.gets
	strary = s.chomp.split(//)

	i = 0
	outstr = ''
	while i < strary.size
		c = strary[ i ]
		if c == '@'
			i += 1
			n = strary[ i ].to_i
			i += 1	
			c = strary[ i ]

			1.upto( n ){
				outstr += c
			}
		else	
			outstr += c
		end
		i += 1
	end
	answers << outstr
end
answers.each{ |a| puts a }


Measured memory_bytes: 6104
S = gets.chomp
N = S.size

def lp(s)
  (s.size/2).times.all? {|i| s[i] == s[-(i+1)] }
end

if lp(S) && lp(S[0, N/2]) && lp(S[((N+3)/2-1)..-1])
  puts 'Yes'
else
  puts 'No'
end

Measured memory_bytes: 2044
a=int(input())
b=input().split()
c=input().split()
count=0
for i in c :
  count+=int(i)

d=input().split()
list1=[]

for i in range(len(b)-1) :
  if int(b[i+1])-int(b[i])==1 :
    
    count+=int(d[int(b[i])-1])
print(count)

Measured memory_bytes: 38384
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<string>
#include<random>
#include<numeric>
#include<string>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
	if (a<b) { return gcd(b, a); }
	else if (a%b) { return gcd(b, a%b); }
	else { return b; }
}
int main() {
	string s, t;
	cin >> s >> t;
	ll x = stoi(s + t);
	for (ll i = 1; i <= 1000; i++) {
		if (i*i == x) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

favorite = [0 for i in range(M)]
child = [input().split() for i in range(N)]

for i in range(N):
    for j in range(1, int(child[i][0]) + 1):
        favorite[int(child[i][j]) - 1] += 1


print(favorite.count(N))


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

#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi 3.14159265

using namespace std;
#define prime 1000000007

const ll N = 300005;

#define W(x) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << "\n";

int n;
int v[30], c[30];


using namespace std;

int ce(int a, int b){
	return (a+b-1)/b;
}

int main(){
	cin >> n;

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

	int ans = 0;
	for (int i = 0; i < n; ++i){
		cin >> c[i];
		if(v[i] > c[i]) ans += v[i]-c[i];
	}

	
	printf("%d\n", ans);
		
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int N,M,X,l;
	cin >> N >> M >> X;
	vector<int> v(N,0);
	for (int i = 0;i < M;i++){
		cin >> l;
		v[l] = 1;
	}
	ll ans_l = 0;
	ll ans_r = 0;
	for (int i = X;i < N;i++){
		if (v[i] == 1){
			ans_r++;
		}
	}
	for (int i = X;i > 0;i--){
		if (v[i] == 1){
			ans_l++;
		}
	}
	cout << min(ans_r,ans_l) << endl;
	return 0;
}

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

ll N, M;
vector<ll> E[100000];
ll dp[100000], ans[100000];

void dfs(ll v, ll p) {
  dp[v] = 1;
  for (ll u : E[v]) if (u != p) {
    dfs(u, v);
    dp[v] = (dp[v] * (dp[u] + 1) % M) % M;
  }
}

void dfs2(ll v, ll p, ll x) {
  ans[v] = (dp[v] * x) % M;

  vector<ll> l, r;
  l.push_back(1);
  for (ll u : E[v]) {
    ll w = u != p ? dp[u] + 1 : 1;
    l.push_back(w);
    r.push_back(w);
  }
  r.push_back(1);
  REP(i, 1, l.size()) l[i] = (l[i] * l[i - 1]) % M;
  for (ll i = (ll) r.size() - 2; i >= 0; i--) r[i] = (r[i] * r[i + 1]) % M;

  REP(i, 0, E[v].size()) {
    ll u = E[v][i];
    if (u == p) continue;
    ll y = l[i] * r[i + 1] % M;
    ll z = ((x * y % M) + 1) % M;
    dfs2(u, v, z);
  }
}

int main(void) {
  cin >> N >> M;
  REP(i, 0, N - 1) {
    ll x, y; cin >> x >> y; x--; y--;
    E[x].push_back(y);
    E[y].push_back(x);
  }

  dfs(0, -1);
  dfs2(0, -1, 1);

  REP(i, 0, N) cout << ans[i] << endl;
}

Measured memory_bytes: 26496
// AtCoder Group Contest
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N;
    long long int su = 0;
    cin >> N;
    vector<int> a(3*N);
    for (int i = 0; i < 3*N; i++) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());

    for (int i = 0; i < 2*N; i++) {
        if (i % 2 == 1) su += a[i];
    }
    cout << su << endl;
    return 0;
}

Measured memory_bytes: 1408
open System

// prelude
let readStr () = stdin.ReadLine()

let read f () = readStr() |> f
let reads f () = readStr().Split() |> Array.map f

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let quad = function
| [|a; b; c; d|] -> (a, b, c, d)
| _ -> failwith "owatta"

let readPair f g () =
  let (a,b) = readStr().Split() |> pair
  (f a, g b)

let readTriple f g h () =
  let (a,b,c) = readStr().Split() |> triple
  (f a, g b, h c)

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
let (A,B,H,M) = reads double () |> quad

let pi2=2.*Math.PI
let argH = (H+M/60.)/12.*pi2
let argM = M/60.*pi2

let diff = argH-argM

sqrt (A*A+B*B-2.*A*B*(Math.Cos diff))
|> printfn "%.16f"

Measured memory_bytes: 30548
#include <stdio.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
long long int sum = 0;
 
 
void merge(int A[],int left,int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    int L[n1+1],R[n2+1];
    for(int i = 0; i < n1; i++) L[i] = A[left + i];
    for(int i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1] = R[n2] =  INT_MAX;
 
    int i = 0, j = 0;
    for(int k = left;k < right; k++){
        if(L[i] < R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
            sum += n1 - i;
        }
    }
}
 
void mergeSort(int A[],int left,int right){
    if(left+1 < right){
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++) scanf("%d",&A[i]);
 
    mergeSort(A,0,n);
 
    printf("%lld\n",sum);
 
}


Measured memory_bytes: 4244
#include <iostream>
#include <cstdio>
#include <cstring>
#include <functional>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  vector<int> g[4], acc[4];
  int N, W, n[4];
  int w1 = -1;
  long long w_all[4], v_all[4];
  cin >> N >> W;
  for (int i=0;i<N;i++) {
    int w, v;
    cin >> w >> v;
    if (w1 < 0) {
      w1 = w;
    }
    g[w-w1].push_back(v);
  }
  for (int i=0;i<4;i++) {
    sort(g[i].rbegin(), g[i].rend());
    n[i] = g[i].size();
    acc[i].push_back(0);
    for (int j=0;j<n[i];j++) {
      acc[i].push_back(acc[i][j] + g[i][j]);
    }
  }
  long long result = 0;

  
  for (int i=0;i<=n[3];i++) {
    w_all[3] = i*(w1+3);
    if (w_all[3] > W)
      break;
    v_all[3] = acc[3][i];
    for (int j=0;j<=n[2];j++) {
      w_all[2] = w_all[3] + j*(w1+2);
      if (w_all[2] > W)
	break;
      v_all[2] = v_all[3] + acc[2][j];
      for (int k=0;k<=n[1];k++) {
	w_all[1] = w_all[2] + k*(w1+1);
	if (w_all[1] > W)
	  break;
	v_all[1] = v_all[2] + acc[1][k];
	for (int l=0;l<=n[0];l++) {
	  w_all[0] = w_all[1] + l*(w1);
	  if (w_all[0] > W)
	    break;
	  v_all[0] = v_all[1] + acc[0][l];
	  if (v_all[0] > result) {
	    result = v_all[0];
	  }
	}
      }
    }
  }
  cout << result << endl;
}


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

int main()
{
  cout << fixed << setprecision(15);
  
  int N, X[50], Y[50];
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  bool flag = N % 2;
  int x = X[0] + X[N / 2], y = Y[0] + Y[N / 2];
  for(int i = 1; i < N / 2; i++) {
    flag |= x != X[i] + X[i + N / 2];
    flag |= y != Y[i] + Y[i + N / 2];
  }
  if(flag) cout << "NA" << endl;
  else cout << x / 2.0 << " " << y / 2.0 << endl;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextInt();
  vector<ll> x(N), y(N);
  REP(i, N) {
    x[i] = nextInt();
    y[i] = nextInt();
  }
  vector<int> ord(N);
  REP(i, N) ord[i] = i;

  double ans = 0;
  int k = 0;
  do {
    double d = 0;
    REP(i, N-1) {
      int a = ord[i];
      int b = ord[i+1];
      d += sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
    }
    ans += d;
    k++;
  } while (next_permutation(ALL(ord)));
  ans /= k;
  printf("%.10f\n", ans);
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


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

using namespace std;

int main() {
	long long int n, k;
	cin >> n >> k;
	if (n < 3) {
		cout << 0 << endl;
	} else if (n < 13){
		long long int a = 81;
		long long int c = 0;
		for (long long int i = 0; i < n-2; i++) {
			long long int b = a;
			b %= 11;
			for (long long int j = 0; j < 7-2; j++) {
				if (b == k) {
					//cout << i << ' ' << j << endl;
					c++;
				}
				//cout << b << ' ';
				b+=9;
				b %= 11;
			}
			if (i > n-20) {
				//cout << c << endl;
			}
			a += 63;
			a %= 11;
		}
		cout << c << endl;
	} else {
		long long int a = 81;
		long long int c = 0;
		int p[11][5] = {0};
		for (long long int i = 0; i < 11; i++) {
			long long int b = a;
			b %= 11;
			for (long long int j = 0; j < 5; j++) {
				if (b == k) {
					c++;
				}
				p[i][j] = b;
				//cout << b << ' ';
				b+=9;
				b %= 11;
			}
			//cout << endl;
			a += 63;
			a %= 11;
		}
		//cout << c << endl;
		long long int cc = ((n-2)/11)*c;
		//cout << cc << endl;
		//cout << n%11 << endl;
		for (long long int i = 0; i < (n-2)%11; i++) {
			for (long long int j = 0; j < 5; j++) {
				if (p[i][j] == k) {
					//cout << i << ' ' << j << endl;
					cc++;
				}
			}
		}
		cout << cc << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int V[105];
int rez=1<<30;
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>V[i];
    }
    sort(V+1,V+1+N);
    for(int i=V[1];i<=V[N];i++)
    {
        rez=min(rez,min(i-V[1]+V[N]-V[1],V[N]-V[1]+V[N]-i));
    }
    cout<<rez;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int a,b,c;
    cin >> a >> b >> c;

    int str;

    if(b>c){
        str = b;
        b=c;
        c=str;
    }

    if(a>b){
        str=a;
        a=b;
        b=str;
    }

      if(b>c){
        str = b;
        b=c;
        c=str;
    }  

    cout << a << " " << b << " " << c << endl;

    return 0;

}


Measured memory_bytes: 3084
#include <iostream>
#include <queue>

using namespace std;

int main(){
  int N, K, tmp;
  priority_queue<int> Q;
  cin >> N >> K;
  for (int i=0; i<N; i++){
    cin >> tmp;
    Q.push(-tmp);
  }
  int ans = 0;
  for (int i=0; i<K; i++){
    ans -= Q.top();
    Q.pop();
  }
  cout << ans << "\n";
  return 0;
}

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

int main(){
  long long N, K, Q;
  cin >> N >> K >> Q;
  vector<int> A(Q);
  for(int i = 0;i < Q;i++){
    cin >> A[i];
  }
  vector<int> C(N);
  for(int i = 0;i < N;i++){
    C[i] = K - Q;
  }
  for(int i = 0;i < Q;i++){
    C[A[i] - 1] += 1;
  }
  for(int i = 0;i < N;i++){
    if(C[i] <= 0){
      cout << "No" << endl;
    }else{
      cout << "Yes" << endl;
    }
  }
} 

Measured memory_bytes: 1408
using System;
class Program
{
    static void Main(string[] args)
    {
        while (true)
        {
            string[] data = Console.ReadLine().Split(' ');
            int H = int.Parse(data[0]);
            int W = int.Parse(data[1]);
            if (H == 0 && W == 0)
            {
                return;
            }

            string line = "";
            string line2 = "";
            for (int i = 0; i < W; i++)
            {
                if (i % 2 == 0)
                {
                    line = line + ".";
                    line2 = line2 + "#";
                }
                else
                {
                    line = line + "#";
                    line2 = line2 + ".";
                }
            }

            for (int i = 0; i < H; i++)
            {
                if (i % 2 == 0)
                {
                    Console.WriteLine(line2);
                }
                else
                {
                    Console.WriteLine(line);
                }
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 5376
#define N 12
double M[N][1<<N],r,t;
D[N],n;
double dfs(p,f){if(M[p][f]<0){
	int i=0;
	M[p][f]=0;
	for(;i<n;i++){
		if(f&1<<i)continue;
		if(t=dfs(i,f|1<<i)+D[p]+D[i]-2*sqrt(D[p]*D[i]*1.0),M[p][f]<t)M[p][f]=t;
	}
}return M[p][f];}
main(l,i,j,d){for(;~scanf("%d",&l);){
	d=n=0;do{scanf("%d",D+n);d+=D[n++]*2;}while(getchar()!='\n');
	for(i=0;i<N;i++)for(j=0;j<1<<N;j++)M[i][j]=-1;
	for(r=i=0;i<n;i++)if(t=dfs(i,1<<i),r<t)r=t;
	puts(d-r<l+1e-5?"OK":"NA");
}exit(0);}

Measured memory_bytes: 968
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")
    };
}

fn main() {
    input!{
        d: u32,
        n: u32,
    }
    if n != 100 {
        println!("{}", 100u32.pow(d) * n)
    } else {
        println!("{}", 100u32.pow(d) * 101)
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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

void add(ll& a, ll b){a = (a+b) % MOD;}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,t;
    cin>>a>>b>>t;
    int ans=0;
    for(int i=a;i<=t+0.5;i+=a){
        ans+=b;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
# frozen_string_literal: true

n, m = gets.split.map(&:to_i)
ab = m.times.map { gets.split.map(&:to_i) }

h = Array.new(n) { [] }
c = Array.new(n) { -1 }

ab.each do |e|
  a = e[0] - 1
  b = e[1] - 1
  h[a].push b if b.positive?
  h[b].push a if a.positive?
end

q = [0]

loop do
  break if q.empty?

  dd = q.shift
  h[dd].each do |e|
    if c[e].negative?
      c[e] = dd + 1
      q.push e
    end
  end
end

if c[1..-1].all?(&:positive?)
  puts 'Yes'
  puts c[1..-1]
else
  puts 'No'
end


Measured memory_bytes: 53424
s = list(input())

# 2^(文字数 - 1) 通りの数式が作れるので、それぞれの計算結果を足し合わせる
result = 0
for i in range(2 ** (len(s) - 1)):
    # 数字と数字の間を左から順に0, 1, ...番目とし、
    # iをビット列と見なして、(j+1)ビット目(j=0,1,...)が1の場合は j番目の位置に '+' を挿入する
    # e.g.) S = '125' とすると、 1{0}2{1}5, i=0b00~0b11 なので、それぞれ以下の数式に対応する
    # 0b00 → '125'
    # 0b01 → '1' + '25'
    # 0b10 → '12' + '5'
    # 0b11 → '1' + '2' + '5'
    num_str = s[0]
    for j in range(0, len(s) - 1):
        if ((i & (2 ** j)) >> j) == 1:
            # 文字間を '+' で繋ぐ
            num_str += '+'
        num_str += s[j + 1]
    result += eval(num_str)

print(result)


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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

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

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

    int N;
    cin >> N;

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

    vi copy = x;
    sort(all(copy));

    for (int i = 0; i < N; i++) {
        if (x[i] <= copy[(N-1)/2]) cout << copy[N/2] << "\n";
        else cout << copy[(N-1)/2] << "\n";
    }

    return 0;
}



Measured memory_bytes: 3840
#include<iostream>
using namespace std;
int main(){
	int count=0,count2,m,f,r;
	char seiseki[100];
	while(1){
		cin>>m>>f>>r;
		if((m==-1&&f==-1)&&r==-1){break;}
		if((m==-1||f==-1)||(m+f)<30){
			seiseki[count]='F';
			count++;
		}else if((m+f)<50&&r<50){
			seiseki[count]='D';
			count++;
		}else if((m+f)<65||r>=50){
			seiseki[count]='C';
			count++;
		}else if((m+f)<80){
			seiseki[count]='B';
			count++;
		}else{
			seiseki[count]='A';
			count++;
		}
	}
	for(count2=0;count2<count;count2++){
		cout<<seiseki[count2]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef pair<int, int> p;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int Inf = (1<<30);
ll inf = (1LL<<60);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
	int n;
	cin >> n;
	ll a[110000];
	int i;
	a[0] = 0;
	for (i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	ll ans = 0; // a[1]が正でスタート
	ll ans2 = 0; // a[1]が負でスタート
	bool is_natural = true;
	ll hosei = 0;
	for (i = 1; i <= n; i++) {
		ll X = a[i] + hosei;
		if (is_natural) {
			if (X <= 0) {
				ll tmp = 1 - X;
				ans += tmp;
				hosei += tmp;
			}
		}
		else {
			if (X >= 0) {
				ll tmp = X + 1;
				ans += tmp;
				hosei -= tmp;
			}
		}
		is_natural = !is_natural;
	}
	is_natural = false;
	hosei = 0;
	for (i = 1; i <= n; i++) {
		ll X = a[i] + hosei;
		if (is_natural) {
			if (X <= 0) {
				ll tmp = 1 - X;
				ans2 += tmp;
				hosei += tmp;
			}
		}
		else {
			if (X >= 0) {
				int tmp = X + 1;
				ans2 += tmp;
				hosei -= tmp;
			}
		}
		is_natural = !is_natural;
	}
	cout << min(ans, ans2);
	return 0;
}

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

using namespace std;

int n, odd, even;

int main()
{
    //freopen("input","r",stdin);
    //freopen("output","w",stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        if (x&1) odd++; else even++;
    }

    if (odd & 1)
        printf("NO\n");
    else printf("YES\n");

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
using ll = int64_t;

int main() {
  ll n,D;
  cin >> n >> D;
  ll ans = 0;
  for(ll i=0; i<n; i++) {
    ll x,y;
    cin >> x >> y;
    ll d2 = x*x + y*y;
    if(d2 <= D*D) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3628
import java.text.SimpleDateFormat

fun main(args: Array<String>) {
    val df = SimpleDateFormat("yyyy/MM/dd")
    val input = readLine()!!.toString()

    val date = df.parse(input)
    val date2 = df.parse("2019/04/30")

    if (date <= date2) {
        println("Heisei")
    } else {
        println("TBD")
    }
}

Measured memory_bytes: 34184
N, M = map(int, input().split())
X = list(map(int, input().split()))

x = sorted(X)
diff = []
for n in range(1, M):
	diff.append(x[n] - x[n - 1])
diff.sort(reverse=True)

print(x[-1] - x[0] - sum(diff[:N - 1]))


Measured memory_bytes: 13960
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,count=0,mi;
  cin >> N;
  vector<int> num(N);
  for(int i=0;i<N;i++) {
    cin >> num.at(i);
    if(i==0) mi=num.at(i);
    else mi=min(mi,num.at(i));
    if(0<num.at(i)&&num.at(i)<=N&&mi>=num.at(i))count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
const LL mod=1e9+7;
const LL LL_MAX=9223372036854775807;
using namespace std;
char a[Max];
int main()
{
    scanf("%s",a);
    int len = strlen(a);
    int ans=0;
    for(int i=1;i<len;i++){
        if(a[i]==a[i-1]){
            ans++;
            if(a[i-1]=='0')
                a[i]='1';
            else
                a[i]='0';
        }
    }
    printf("%d\n",ans);
    return 0;
}


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

const long double EPS = 1e-10;
const long long INF = 1e18;
const int MOD = (int)1e9 + 7;
const long double PI = acos(-1.0L);

int main() {
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> a(q), b(q), c(q), d(q);
  rep(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
  ll ans = 0;

  int NM = n + m - 1;

  rep(A, 1 << NM) {
    ll sumd = 0;
    rep(qi, q) {
      int ai = a[qi];
      int bi = b[qi];
      int an = 0;
      int am = 1;
      int av = 0;
      int bv = 0;

      for (int i = 1; i <= NM; i++) {
        if (A >> i & 1) {
          am++;
        } else {
          an++;
          if (an == ai) av = am;
          if (an == bi) bv = am;
        }
      }
      if (an == n && c[qi] == bv - av) sumd += d[qi];
    }

    ans = max(ans, sumd);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=998244353;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e9+7;
const long double PI=acos(-1);

int v=0;

void f(ll x){

    for(ll i=2;i*i<=x;i++){
        bool div=0;
        while(x%i==0){
            div=1;
            x/=i;
        }
        if(div==1){
            v++;
        }
    }
    if(x>=2)v++;
}


void solve(int T){
    ll a,b;
    cin>>a>>b;
    ll g=__gcd(a,b);
    f(g);
    int ans=v;
    cout<<ans+1<<"\n";
}

int main() {
    fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3652
<>=~/ (.*) /,${$`}{$1}=$$1{$`}=$' for 2..<>;@s=<>=~$"*$';
map{$d[$_]or$d[$_]=$d[$u]+$$u{$_},push@s,$_}keys%{$u=$_}for@s;
/ /,print$d[$`]+$d[$'],$/for<>

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

using namespace std;

#define ll long long
#define ar array



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

	int t;
	cin >> t;
	int a=0,b=0,c=0,d=0;
	while(t--){
		string s;
		cin >> s;
		if(s=="AC") a++;
		else if(s=="WA") b++;
		else if(s=="TLE") c++;
		else if(s=="RE") d++;
	}
	cout << "AC x "<<a<<"\n";
	cout << "WA x "<<b<<"\n";
	cout << "TLE x "<<c<<"\n";
	cout << "RE x "<<d<<"\n";
	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using pp = pair<int, int>;
const int INF = 1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<string> days{"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string s;
    cin >> s;
    cout << 7 - (find(days.begin(), days.end(), s) - days.begin()) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int m=1000000007;
int n,f[1000005];
int a;
int main(){
    cin>>n;
    while(0){
    	int ggg;
    	cin>>ggg;
    	cin>>ggg;cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
    	cin>>ggg;
	}
    f[n]=n;
    f[n-1]=(long long)n*n%m;
    for(int i=n-2;i>=1;i--){
        a=(a+f[i+3])%m;
        f[i]=f[i+1];
        f[i]=(f[i]+(long long)(n-1)*(n-1)%m)%m;
        f[i]+=a;
        f[i]%=m;
        f[i]+=i+1;
        f[i]%=m;
    }
    cout<<f[1]<<endl;
}

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

long N,n;
vector<long> A;

main(){
    for(cin>>N;cin>>n;)A.push_back(n);
    auto a=A.begin(),t=a+1,d=A.end(),b=t+1;
    partial_sum(a,d,a);
    n=1LL<<50;
    for(--d;t+1!=d;++t){
        while(a+1!=t)
            if(*a<*t-*(a+1))++a;
            else break;
        if(b==t)++b;
        while(b+1!=d)
            if(*b-*t<*d-*(b+1))++b;
            else break;
        n=min(n,max({*a,*t-*a,*b-*t,*d-*b})-min({*a,*t-*a,*b-*t,*d-*b}));
    }
    cout<<n<<" ";
}


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

int main() {
  vector<int> N(9);
  for(auto& i: N) cin >> i;

  vector<int> A(9);
  iota(begin(A), end(A), 1);

  int answer = 0;
  do {
    bool valid = true;
    for(int i = 0; i < 9; ++i) valid &= (N[i] == -1 || N[i] == A[i]);
    if(!valid) continue;
    answer += (A[0] + 10*A[1]+A[2] + 100*A[3]+10*A[4]+A[5] == 100*A[6]+10*A[7]+A[8]);
  } while(next_permutation(begin(A), end(A)));
  cout << answer << endl;
}

Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
char str[1001][1001];
int w, h, sx, sy, gx, gy;
int solve() {
    int x[] = { -1,0,1,0 }, y[] = { 0,-1,0,1 };
    vector<vector<int>>weight(w + 1, vector<int>(h + 1, 0));
    queue<pair<int, int>>que;
    que.push(make_pair(sx, sy));
    while (!que.empty()) {
	int curx = que.front().first, cury = que.front().second;
	que.pop();
	for (int i = 0; i < 4; ++i) {
	    if (curx + x[i] != 0 && curx + x[i] != w + 1 && cury + y[i] != 0 && cury + y[i] != h + 1) {
		if (curx + x[i] == gx && cury + y[i] == gy) return weight[curx][cury] + 1;
		if (str[cury + y[i]][curx + x[i]] == '.'&&weight[curx + x[i]][cury + y[i]] == 0) {
		    que.push(make_pair(curx + x[i], cury + y[i]));
		    weight[curx + x[i]][cury + y[i]] = weight[curx][cury] + 1;
		}
	    }
	}
    }
}
int main() {
    int sum=0,facx[10],facy[10],n;
    cin >> h >> w>>n;
    for (int i = 1; i <= h; ++i) {
	for (int j = 1; j <= w; ++j) {
	    cin >> str[i][j];
	    if (str[i][j] == 'S') {
		sx = j; sy = i;
		str[i][j]='.';
	    }
	    if (str[i][j] >= '1'&&str[i][j]<='9') {
		facx[str[i][j]-'0'] = j; facy[str[i][j]-'0'] = i;
		str[i][j]='.';
            }
	}
    }
    for(int i=1;i<=n;++i){
	gx=facx[i]; gy=facy[i];
	sum+=solve();
	sx=gx; sy=gy;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 7792
def swap(l, i, j):
    tmp = l[i]
    l[i] = l[j]
    l[j] = tmp
    return l

def bubble_sort(l):
    cnt = 0
    for i in range(0, len(l) - 1):
        flag = True
        for j in range(len(l)-1, i, -1):
            if l[j-1] > l[j]:
                l = swap(l, j-1, j)
                cnt += 1
                flag = False
        if flag:
            break

    return l, cnt

if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))

    sl, cnt = bubble_sort(l)
    print(' '.join(map(str, sl)))
    print(cnt)



Measured memory_bytes: 5600