akhauriyash/Code-Regression huggingface dataset:
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/25 03:46:19 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1e9+7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	int	n;
	cin >> n;
	unordered_map<string, int>	M;

	ll	sum;
	sum = 0;
	rep(i, n)
	{
		string	s;
		cin >> s;

		sort(s.begin(), s.end());
		sum += M[s];
		M.at(s)++;
	}
	cout << sum << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 10660
#! -*- coding:utf-8 -*-
a,b,c,d = map(int,input().split())
if d <= a or b <= c:
    print(0)
elif c <= a and (a <= d and d <= b):
    print(d-a)
elif (a <= c and c <= b) and (a <= d and d <= b):
    print(d-c)
elif (a <= c and c <= b) and b <= d:
    print(b-c)
else:
    print(b-a)


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

int main()
{
    // 入力の受け取り
    string s;
    getline(cin, s);

    // 予測
    string res;
    if(s.at(0) == 'S')          res = "Cloudy";
    else if(s.at(0) == 'C')     res = "Rainy";
    else                        res = "Sunny";
    
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
import Text.Printf
import Control.Monad

main ::IO()
main = do
    s <- getLine
    t <- getLine
    putStrLn $ if checkRoll s t then "Yes" else "No"

checkRolln ::String->String->Int->Bool
checkRolln (s0:sx) t n = do
    if [s0] ++ sx == t then True
    else if n > 0 then checkRolln (sx ++ [s0]) t (n-1)
    else False

checkRoll ::String->String->Bool
checkRoll s t  = do
    checkRolln s t (length s)


Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define  all(x) (x).begin(),(x).end()
typedef long long ll;

int n, k;
vector<int> w;

int check(ll P){
    int i = 0;
    rep(j, k){
        ll s = 0;
        while(s + w[i] <= P){
            s += w[i];
            i++;
            if (i == n)  return n;
        }
    }
    return i;
}

ll solve(){
    ll right = 100000 * 10000, left = 0;
    while( (right - left) > 1){
        ll mid = (right+left) / 2;
        ll v = check(mid);
        if (v == n) right = mid;
        else left = mid;
    }
    return right;
}

int main(){
    cin >> n >> k;
    w = vector<int>(n);
    rep(i, n) cin >> w[i];
    ll ans = solve();
    cout << ans << endl;
}


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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define mod 1000000007;

typedef long long ll; 
typedef pair<int, int> ii; 
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

// Print fn to print array

int main(){
	string s;
	cin >> s;
	bool y = false;
	for(int i=0;i<3;i++){
		if(s[i]=='7') y=true;
	}	
	if(y) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}


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

struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define MOD 1000000007


int main() {
    string S; cin >> S;
    int num = 0;
    int N = S.size();
    rep(i, N) {
        if (S[i] == '0') num++;
    }
    cout << 2 * min(num, N - num) << endl;

}


Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

#define MN 210

int N_;
ll A[MN][MN];
ll B[MN][MN];
ll work[MN][MN];

const ll LIM=LLONG_MAX-(MOD-1)*(MOD-1);

// a := a*b
void matmul(ll a[][MN], ll b[][MN]){
	memset(work,0,sizeof(work));
	rep(i,N_)rep(k,N_)rep(j,N_){
		work[i][j]+=a[i][k]*b[k][j];
		if(work[i][j]>LIM)work[i][j]%=MOD;
	}
	rep(i,N_)rep(j,N_)a[i][j]=work[i][j]%MOD;
}

// a := b*a
void matmulleft(ll a[][MN], ll b[][MN]){
	memset(work,0,sizeof(work));
	rep(i,N_)rep(k,N_)rep(j,N_){
		work[i][j]+=b[i][k]*a[k][j];
		if(work[i][j]>LIM)work[i][j]%=MOD;
	}
	rep(i,N_)rep(j,N_)a[i][j]=work[i][j]%MOD;
}

// a := a^2
void matsq(ll a[][MN]){
	memset(work,0,sizeof(work));
	rep(i,N_)rep(k,N_)rep(j,N_){
		work[i][j]+=a[i][k]*a[k][j];
		if(work[i][j]>LIM)work[i][j]%=MOD;
	}
	rep(i,N_)rep(j,N_)a[i][j]=work[i][j]%MOD;
}

// A := A^n
void matpow(ll a[][MN],ll n){
	memset(B,0,sizeof(B));
	rep(i,N_)B[i][i]=1;
	while(n){
		if(n&1)matmul(B,A);
		matsq(A);
		n>>=1;
	}
	rep(i,N_)rep(j,N_)A[i][j]=B[i][j];
}

ll fib(ll n){
	n+=1;
	N_=2;
	A[0][0]=1;A[0][1]=1;
	A[1][0]=1;A[1][1]=0;
	matpow(A,n);
	return A[1][0];
}

ll N;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>N;
	ll lo=0,hi=INF*2;
	while(lo+1<hi){
		ll mi=lo+hi>>1;
		ll m=(mi+1)/2;
		ll sum=m*(m+1)/2*2;
		if(mi%2){
			sum-=m;
		}
		//cout<<mi<<" "<<sum<<endl;
		if(sum>=N)hi=mi;
		else lo=mi;
	}
	ll M=hi;
	ll m=(M+1)/2;
	ll sum=m*(m+1)/2*2;
	if(M%2){
		sum-=m;
	}
	ll no=m-(sum-N);
	//cout<<M<<" "<<no<<endl;
	ll a;
	if(no <= (m+1)/2) a = no*2-1;
	else{
		if(m%2) a = m-1 - (no-(m+1)/2-1)*2;
		else a = m - (no-m/2-1)*2;
	}
	ll b = M+1-a;
	//cout<<a<<" "<<b<<endl;
	cout<<fib(a)*fib(b)%MOD<<endl;
}

Measured memory_bytes: 1900
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	cin >> a >> b;
	if((a+b)%2==1){
		cout << (a+b)/2+1 << endl;
	}else{
		cout << (a+b)/2 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=3010;

int n, m, k, u, v, x, y, t, a, b, ans;
int dp0[MAXN][MAXN];
int dp1[MAXN][MAXN];

inline void fix(int &x){
	if (x>=mod) x-=mod;
	if (x<0) x+=mod;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=n; i++) dp0[0][i]=1;
	dp1[0][0]=1;
	for (int i=1; i<=m; i++){
		for (int j=0; j<=n; j++){
			if (j>0){
				if (j==1){
					fix(dp1[i][j-1]+=dp0[i-1][j]);
					fix(dp1[i][j-1]+=dp1[i-1][j]);
					
					fix(dp1[i][j]+=dp0[i-1][j]);
					fix(dp1[i][j]+=dp1[i-1][j]);
				}
				else{
					fix(dp0[i][j-1]+=dp0[i-1][j]);
					fix(dp1[i][j-1]+=dp1[i-1][j]);
					
					fix(dp0[i][j]+=dp0[i-1][j]);
					fix(dp1[i][j]+=dp1[i-1][j]);
				}
			}
			if (j<n){
				fix(dp0[i][j+1]+=dp0[i-1][j]);
				fix(dp1[i][j+1]+=dp1[i-1][j]);
				
				fix(dp0[i][j]+=dp0[i-1][j]);
				fix(dp1[i][j]+=dp1[i-1][j]);
			}
		}
	}
	for (int i=0; i<=n; i++) fix(ans+=dp1[m][i]);
	cout<<ans<<"\n";
	
	return 0;
}
/*
2 1

*/

Measured memory_bytes: 74092
#include<stdio.h>
void solve(int n){
	int i,j;
	int d=1;
	for(i=0;i<10;i++){
		if(d<<i&n){
			printf("%d",d<<i);
			for(j=i+1;j<10;j++){
				if(d<<j&n){
					printf(" %d",d<<j);
				}
			}
			puts("");
			break;
		}
	}
}
int main(){
	int n,i;
	while(~scanf("%d",&n)){
		solve(n);
	}
	return 0;
}

Measured memory_bytes: 608
N, T = map(int, input().split())
t = list(map(int, input().split()))

sum_second = 0
for i in range(N):
    if (i == N - 1):
        sum_second += T
        break

    if (t[i + 1] - t[i] <= T):
        sum_second += t[i + 1] - t[i]
    else:
        sum_second += T

    # if T > t[i + 1] - sum_second:
    #     sum_second += t[i + 1] - sum_second
    # elif (T <= t[i + 1] - sum_second):
    #     sum_second += T


print(sum_second)


Measured memory_bytes: 25196
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

    int count = 0;

    for (int i = 0; i < N / v[0] + 1; i++){
        for (int j = 0; j < (N - v[0] * i) / v[1] + 1; j++){
            if ((N - (v[0] * i + v[1] * j)) % v[2] == 0){
                count ++ ;
            }
        }
    }
    
    cout << count << endl;
    
    return 0;
}

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

int main(){
	int a, b;
	cin >> a >> b;
	int arr[a+1][b+1];
	for(int i = 0; i < a; i++){
		for(int j = 0; j < b; j++){
			cin >> arr[i][j];
		}
	}
	for(int i = 0; i < a; i++){
		int sum = 0;
		for(int j = 0; j < b; j++){
			sum += arr[i][j];
		}
		arr[i][b] = sum;
	}
	for(int i = 0; i <= b; i++){
		int sum = 0;
		for(int j = 0; j < a; j++){
			sum += arr[j][i];
		}
		arr[a][i] = sum;
	}
	
	for(int i = 0; i < a+1; i++){
		for(int j = 0; j < b+1; j++){
			cout << arr[i][j];
			if(j != b)
				cout << " ";
		}
		cout << endl;
	}
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long int H, W;
    cin >> H >> W;
    if (H == 1 || W == 1) {
        cout << 1;
    } else if (H * W % 2 != 0) {
        cout << (H * W + 1) / 2;
    } else {
        cout << H * W / 2;
    }
    return 0;
}

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

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

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

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


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

int main()
{
	string S;
	cin >> S;
	int cnt[2]={};
	
	for(int i=0;i<S.size();i++)
		cnt[S[i]-'0']++;
	
	cout << 2*min(cnt[0],cnt[1]) << endl;
	return 0;
}



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

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

    vector<long long int> l(2*n);
    for(int i=0; i<2*n; i++){
        cin >> l[i];
    }
    sort(l.begin(),l.end());

    long long int ans = 0;
    for(int i=0; i<n; i++){
        ans += l[2*i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef complex<double> C;

typedef string::const_iterator State;

bool formula(State& begin, int S);
bool TF(State& begin, int S);

void consume(State& begin, char expected) {
    if (*begin == expected) {
        begin++;
    } else {
        cerr << "Expected '" << expected << "' but got '" << *begin << "'" << endl;
        cerr << "Rest string is '";
        while (*begin) {
            cerr << *begin++;
        }
        cerr << "'" << endl;
        exit(1);
    }
}

bool formula(State& begin, int S) {
    if (*begin == '-') {
        begin++;
        return !formula(begin, S);
    } else if (*begin == '(') {
        consume(begin, '(');
        bool ret = formula(begin, S);
        if (*begin == '*') {
            consume(begin, '*');
            ret &= formula(begin, S);
            consume(begin, ')');
            return ret;
        } else if (*begin == '+') {
            consume(begin, '+');
            ret |= formula(begin, S);
            consume(begin, ')');
            return ret;
        } else {
            consume(begin, '-');
            consume(begin, '>');
            bool tmp = formula(begin, S);
            if (ret == true && tmp == false) ret = false;
            else ret = true;
            consume(begin, ')');
            return ret;
        }
    } else {
        return TF(begin, S);
    }
}

bool TF(State& begin, int S) {
    if (*begin == 'T') {
        consume(begin, 'T');
        return true;
    }
    if (*begin == 'F') {
        consume(begin, 'F');
        return false;
    }
    int tmp = *begin - 'a';
    begin++;
    return ((S>>tmp)&1) == 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (1) {
        bool ng = false;
        string s;
        cin >> s;
        if (s == "#") break;
        for (int i = 0; i < 2048; i++) {
            State begin1 = s.begin(), begin2;
            for (begin2 = s.begin(); ; begin2++) {
                if (*begin2 == '=') {
                    begin2++;
                    break;
                }
            }
            if (formula(begin1, i) != formula(begin2, i)) {
                ng = true;
                break;
            }
        }
        if (ng) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}

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

using namespace std;

int main(){
    ios_base::sync_with_stdio (false);
    int n,x,a[150],i,min=1001,sum=0;
    cin>>n>>x;
    int c=n;
    for(i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        if(min>a[i])
            min=a[i];
    }
    x-=sum;
    while(x>=min){
        x-=min;
        c++;
    }
    cout<<c;
    return 0;
}


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

int main(){
    int h,n;
    cin>>h>>n;
    vector<int>a(n);
    int sum=0;
    for(int i=0; i<n; i++){
        cin>>a.at(i);
        sum+=a.at(i);
    }
    if(h<=sum)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 640
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    print((N + 1) // 2)


if __name__ == '__main__':
    main()


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

long long combi(long long n, long long k) {
  if (n == k || k == 0)
    return 1;
  else {
    return combi(n - 1, k - 1) + combi(n - 1, k);
  }
}

int main(){
  int N, M;
  
  cin >> N >> M ;
  if (N >= 2 && M >=2) {
		cout << combi(N,2) + combi(M,2) << endl;
	}
  if (N >= 2 && M <=1) {
		cout << combi(N,2) << endl;
	}
  if (N <= 1 && M >=2) {
		cout << combi(M,2) << endl;
	}
  if (N <= 1 && M <=1) {
		cout << 0 << endl;
	}
}



Measured memory_bytes: 256
#import<iostream>
#define L %o
using namespace std;long N,M,c,n=1,i,o=1000000007;long m(long a){long g=1,h=2*o-4;while(h/=2){if(h&1)g=g*a L;a=a*a L;}return g;}long C(long b){long r=1,d=1;for(;b;--b){r=r*(N-1+b)L;d=d*b L;}return r*m(d)L;}main(){cin>>N>>M;for(i=2;i*i<=M;++i){c=0;while(!(M%i)){++c;M/=i;}n=n*C(c)L;}cout<<n*(M^1?N:1)L<<endl;}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    k=int(input())
    ans=""
    sx=s[k-1]
    for ss in s:
        if ss!=sx:
            ans+='*'
        else:
            ans+=sx 
    print(ans)

if __name__=='__main__':
    main()

Measured memory_bytes: 3060
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

X = get_int
A = get_int
B = get_int

x = X - A

puts x % B


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

struct Card{char suit, value;};

void bubble(int N, struct Card A[]){
    for(int i=0; i<N-1; i++){
        for(int j=N-1; j>=i+1; j--){
            if(A[j].value < A[j-1].value){
                Card t=A[j]; A[j]=A[j-1]; A[j-1]=t;
            }
        }
    }
}

void selection(int N, struct Card A[]){
    for(int i=0; i<N-1; i++){
        int minj = i;
        for(int j=i; j<N; j++){
            if(A[j].value < A[minj].value) minj=j;
        }
        Card t=A[i]; A[i]=A[minj]; A[minj]=t;
    }
}

void print(int N, struct Card A[]){
    for(int i=0; i<N; i++){
        if(i)cout<<" ";
        cout<<A[i].suit<<A[i].value;
    }
    cout<<endl;
}

bool isStable(int N, struct Card C1[], struct Card C2[]){
    for(int i=0; i<N; i++){
        if(C1[i].suit != C2[i].suit) return false;
    }
    return true;
}

int main(){
    Card C1[100], C2[100];
    int N;
    
    cin>>N;
    for(int i=0; i<N; i++){
        cin>> C1[i].suit>> C1[i].value;
    }
    
    for(int i=0; i<N; i++) C2[i]=C1[i];
    
    bubble(N, C1);
    selection(N, C2);
    
    print(N, C1);
    cout<<"Stable"<<endl;
    
    print(N, C2);
    if(isStable(N, C1, C2)){
        cout<<"Stable";
    }else{
        cout<<"Not stable";
    }
    
    cout<<endl;
    
    return 0;
}



Measured memory_bytes: 3096
N = int(input())
W = [int(x) for x in input().split()]

S1 = 0
S2 = 0
ans = 999
for i in range(N):
    s = abs(sum(W[0:i+1]) - sum(W[i+1:]))
    if ans > s:
        ans = s
print(ans)

Measured memory_bytes: 3060
S = input()

# 中央から同一の数字が何個並ぶかによって解は求まる
N = len(S)
M = N // 2
ans = M + next(
    (
        i
        for i in range(N - M)
        if (
            S[M - i - 1] != S[M] or S[M + i] != S[M] if N % 2 == 0 else
            S[M - i] != S[M] or S[M + i] != S[M]
        )
    ),
    N - M
)

print(ans)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ii pair<int,int>
#define iii pair <int,ii>
#define iil pair<ll,ll>
#define iiil pair<ll,iil>
#define max3(a,b,c) max(a, max(b,c))
#define min3(a,b,c) min(a, min(b,c))
#define s(v) sort(v.begin(),v.end())
#define pf printf
#define sf scanf
#define MIN INT_MIN
#define MAX INT_MAX
#define accepted 0
#define GCD(x,y)  __gcd(x, y)
using namespace std;

int main() {
    //fast
    ll n,x,y,ans;
        cin>>n;
        x = n / 500;
        n%=500;
        y = n / 5;
        ans = (x*1000) + (y*5);
        cout<< ans <<endl;

    return accepted;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	long long n, a, b;	cin >> n >> a >> b;
	if((b-a)%2 == 0){
		cout << (b-a)/2 << endl;
	}
	else{
		cout << min(a-1, n-b) + 1 + (b-a)/2 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
 
public class Main{
	int N;
	int[] A;
	long[] sum;
	public void solve(){
		N = nextInt();
		A = new int[N];
		sum = new long[N + 1];
		for(int i = 0; i < N; i++){
			A[i] = nextInt();
		}
		Arrays.sort(A);
		for(int i = 0; i < N; i++){
			sum[i + 1] = sum[i] + A[i];
		}
		int ans = 1;
		for(int i = N - 1; i >= 1; i--){
			if(sum[i] * 2 >= A[i]){
				ans++;
			}else{
				break;
			}
		}
		out.println(ans);
	}
	

	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

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

#define int long long

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

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int H, W;
  cin >> H >> W;

  int N = H*W;
  const int INF = 1e9;
  int d[N][N];
  fill_n(*d, N*N, INF);
  for ( int i = 0; i < N; i++ ) d[i][i] = 0;

  vector<string> S(H);
  for ( int i = 0; i < H; i++ ) {
    cin >> S[i];
  }

  for ( int i = 0; i < H; i++ ) {
    for ( int j = 0; j < W; j++ ) {
      if ( S[i][j] == '#' ) continue;
      for ( int k = 0; k < 4; k++ ) {
	int nx = j+dx[k], ny = i+dy[k];
	if ( nx < 0 || nx >= W || ny < 0 || ny >= H || S[ny][nx] != '.' ) continue;
	// cout << i << " " << j << endl;
	d[i*W+j][ny*W+nx] = d[ny*W+nx][i*W+j] = 1;	
      }
    }
  }

  int ans = 0;  
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < N; j++ ) {
      for ( int k = 0; k < N; k++ ) {
	d[j][k] = min(d[j][k], d[j][i] + d[i][k]);      
      }
    }
  }
  
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < N; j++ ) {
      // cout << d[i][j] << endl;
      if ( d[i][j] != INF ) ans = max(ans, d[i][j]);
    }
  }

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


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 5100000;
const int MOD = 1e9 + 7;

const double PI=3.14159265358979323846;


long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

std::vector<int> Eratosthenes(int n ){
    std::vector<bool> is_prime( n + 1 );
    for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;
    std::vector<int> P;
    for( int i = 2; i <= n; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= n; j += i ){
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

ll gcd(ll a, ll b){
    if(a < b) swap(a, b);
    if(b == 0) return a;
    if(a%b == 0) return b;
    else return gcd(b, a%b);
}

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



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

    int init = 0;
    int a1 = 0;
    for(int i = 0; i < str.size(); ++i){
        int num = str[i]- '0';
        if(num != init) ++a1;
        init = !init; 
    }
    init = 1;
    int a2 = 0;
    for(int i = 0; i < str.size(); ++i){
        int num = str[i]- '0';
        if(num != init) ++a2;
        init = !init; 
    }
    cout << min(a1,a2);
    return 0;
}

Measured memory_bytes: 512
n = int(input())
R = [int(input()) for i in range(n)]

minv = R[0]
maxv = R[1] - R[0]
for j in range(1, n):
    if (maxv < R[j] - minv):
        maxv = R[j] - minv
    if (R[j] < minv):
        minv = R[j]
print(maxv)


Measured memory_bytes: 13600
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main(){
    char str[110];
    scanf("%100s",str);
    bool yes = true;
    for(int i=1;str[i-1]!='\0';i++){
        if(i%2==0){
            if(str[i-1]=='L' || str[i-1]=='U' ||str[i-1]=='D'){

            }else{
                yes=false;
                break;
            }
        }else{
            if(str[i-1]=='R' || str[i-1]=='U' ||str[i-1]=='D'){

            }else{
                yes=false;
                break;
            }
        }
    }
    if(yes){
        cout << "Yes" << endl;

    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

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

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 long long inf = 1LL << 60;

long long dp[100010];


int main(){
  int n,k,i,j;
  cin >> n >> k;

  vector<int> h(n);

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

  for(i=0;i<100010;i++){
    dp[i]=inf;
  }

  dp[0]=0;

  for(i=1;i<n;++i){
    chmin(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
    if(k>=2){
    for(j=1;j<k;++j){
    if(i>j) {
      chmin(dp[i],dp[i-(j+1)]+abs(h[i]-h[i-(j+1)]));
    }
  }
}

  }

  cout << dp[n-1] << endl;
  return 0;


}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(x) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  LLI I,O,T,J,L,S,Z;
  while(cin >> I >> O >> T >> J >> L >> S >> Z){
    LLI ans = 0;

    ans += O;

    if(I>=1 and J>=1 and L>=1){
      ans += max((I/2)*2 + (J/2)*2 + (L/2)*2, 3 + ((I-1)/2)*2 + ((J-1)/2)*2 + ((L-1)/2)*2);
    }else{
      ans += (I/2)*2 + (J/2)*2 + (L/2)*2;
    }


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


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int maxn = 200005;
const int inf = 1000000007;
int x[maxn],yy[maxn];
char c[maxn];
vector<pair<int,int>>vv1;
vector<int>uu,rr,dd,ll;
int cnt = 0 ;
map<int,int>UL,UR,DL,DR,D,L;
vector<int>GG[5*maxn];
void addnodeUL(int num,int y){if(!UL[num])UL[num]=++cnt;GG[UL[num]].push_back(y);}
void addnodeUR(int num,int y){if(!UR[num])UR[num]=++cnt;GG[UR[num]].push_back(y);}
void addnodeDL(int num,int x){if(!DL[num])DL[num]=++cnt;GG[DL[num]].push_back(x);}
void addnodeDR(int num,int x){if(!DR[num])DR[num]=++cnt;GG[DR[num]].push_back(x);}
void addnodeD(int num,int y){if(!D[num])D[num]=++cnt;GG[D[num]].push_back(y);}
void addnodeL(int num,int x){if(!L[num])L[num]=++cnt;GG[L[num]].push_back(x);}
int query(int num,int num2,int mul){
    int ind=lower_bound(GG[num].begin(),GG[num].end(),num2)-GG[num].begin();
    if(ind!=GG[num].size())
        return mul*(GG[num][ind]-num2);
    return inf;
}
int query2(int num,int num2,int mul){
    int ind=lower_bound(GG[num].begin(),GG[num].end(),num2)-GG[num].begin();
    if(ind-1>=0)
        return mul*(num2-GG[num][ind-1]);
    return inf;
}
int queryUL(int num,int y){
    if(!UL[num])return inf;num=UL[num];
    return query(num,y,10);
}
int queryUR(int num,int y){
    if(!UR[num])return inf;num=UR[num];
    return query(num,y,10);
}
int queryDL(int num,int x){
    if(!DL[num])return inf;num=DL[num];
    //cout << num <<endl;
    return query2(num,x,10);
}
int queryDR(int num,int x){
    if(!DR[num])return inf;num=DR[num];
    return query2(num,x,10);
}
int queryD(int num,int y){
    if(!D[num])return inf;num=D[num];
    return query(num,y,5);
}
int queryL(int num,int x){
    if(!L[num])return inf;num=L[num];
    return query(num,x,5);
}
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x[i] >>yy[i] >> c[i];
        if(c[i]=='R'){
            addnodeUR(x[i]+yy[i],yy[i]);
            addnodeDR(x[i]-yy[i],yy[i]);
        }else if(c[i]=='L'){
            addnodeDL(x[i]+yy[i],yy[i]);
            addnodeUL(x[i]-yy[i],yy[i]);
            addnodeL(yy[i],x[i]);
        }
        else if(c[i]=='D')
            addnodeD(x[i],yy[i]);
    }
    for(int i=1;i<=cnt;i++)
        sort(GG[i].begin(),GG[i].end());
    int point = inf ;
    for(int i=0;i<n;i++){
        if(c[i]=='U'){
            point=min(point,queryUL(x[i]-yy[i],yy[i]));
            point=min(point,queryUR(x[i]+yy[i],yy[i]));
            point=min(point,queryD(x[i],yy[i]));
            //cout << point << endl;
        }
        if(c[i]=='D'){
            point=min(point,queryDL(x[i]+yy[i],yy[i]));
            point=min(point,queryDR(x[i]-yy[i],yy[i]));
        }
        if(c[i]=='R'){
            point=min(point,queryL(yy[i],x[i]));
            //cout << point << endl;
        }
    }
    if(point==inf)
        cout << "SAFE\n" << endl;
    else
        cout << point <<endl;
    return 0;
}


Measured memory_bytes: 62844
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

typedef struct UnionFindTree{
    vector<int> par;

    UnionFindTree(int n): par(n, -1){}

    int find(int x){
        if(par[x] < 0) return x;
        return par[x] = find(par[x]);
    }

    int size(int x){
        return -par[find(x)];
    }

    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

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

template<class T> struct edge{
    int from, to; T cost;
    edge(int f, int t, T c): from(f), to(t), cost(c){}
};

int main(){
    int n, m, K;
    scanf("%d%d%d", &n, &m, &K);
    UF uf(n+K);
    int c[n];
    rep(i, n){
        scanf("%d", &c[i]);
        --c[i];
        if(c[i] >= 0) uf.unite(i, n+c[i]);
    }
    vector<edge<lint>> E;
    rep(i, m){
        int a, b;
        lint w;
        scanf("%d%d%lld", &a, &b, &w);
        --a; --b;
        E.emplace_back(a, b, w);
    }

    int cnt = 0;
    lint sum = 0;
    sort(E.begin(), E.end(), [](const edge<lint> &a, const edge<lint> &b){return a.cost < b.cost;});
    for(auto &e: E)if(cnt < K-1){
        if(uf.unite(e.from, e.to)){
            sum += e.cost;
            ++cnt;
        }
    }
    printf("%lld\n", cnt == K-1 ? sum : -1);
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(vec) vec.begin(), vec.end()
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}

int main(){
  int n; cin >> n;
  ll ans = 0;
  int m = 2e9;
  int ms;
  bool z = true;
  rep(i, n){
  	int x;
  	cin >> x;
  	ans += abs(x);
    if (x < 0) ms++;
    if (abs(x) < m) m = abs(x);
    if (x == 0) z = false;
  }
  if (ms % 2 == 1 && z) ans -= 2 * m;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>                                    
using namespace std;
 
int main() {
  int D, T, S;
  cin >> D >> T >> S;
  if(D < (T * S)){cout << "Yes" << endl;}
  if(D == (T * S)){cout << "Yes" << endl;}
  if(D > (T * S)){cout << "No" << endl;}
} 

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

#define ll long long
#define ld long double
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define ppb pop_back
#define vll vector<ll>
#define vi vector<int>
#define endl "\n"

const ll INF = 1000000007;

/*
const int max_size = 100001;
int parent[max_size];
int Size[max_size];

int root(int x){
	while(x!=parent[x]){
		parent[x] = parent[parent[x]];
		x = parent[x];
	}
	return x;
}

void sunion(int x,int y){
	int rx = root(x);
	int ry = root(y);
	if(rx != ry){
		if(Size[rx] > Size[ry]){
			parent[ry] = parent[rx];
			Size[rx] += Size[ry];
		}
		else{
			parent[rx] = parent[ry];
			Size[ry] += Size[rx];
		}
	}
}
*/

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--){
		int n;
		cin >> n;
		int a[n],b[n],c[n];
		for(int i=0;i<n;i++){
			cin >> a[i] >> b[i] >> c[i];
		}
		int dp[3][n+1];
		dp[0][0] = dp[1][0] = dp[2][0] = 0;
		for(int i=1;i<=n;i++){
			dp[0][i] = a[i-1] + max(dp[1][i-1],dp[2][i-1]);
			dp[1][i] = b[i-1] + max(dp[0][i-1],dp[2][i-1]);
			dp[2][i] = c[i-1] + max(dp[0][i-1],dp[1][i-1]);
		}
		int ans = max(dp[0][n],max(dp[1][n],dp[2][n]));
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 2560
def resolve():
    n, k = map(int, input().split())
    ab = list(list(map(int, input().split())) for _ in range(n))
    ab.sort(key=lambda x: x[0])
    now = 0
    for a, b in ab:
        now += b
        if now >= k:
            print(a)
            break


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 64728
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // A - Can't Wait for Holiday

        Scanner sc = new Scanner(System.in);

        String s = sc.next();

        String yobi[] = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };

        for (int i = 0; i < 7; i++) {
            if (s.equals(yobi[i])) {
                System.out.println(Math.abs(i - 7));
                break;
            }
        }
    }
}

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

int main(void){
    ll n, m, x, y;
    cin >> n >> m >> x >> y;

    ll ma = -10000;
    ll mi = 10000;
    ll a;
    rep(i, n){
        cin >> a;
        ma = max(a, ma);
    }
    rep(i, m){
        cin >> a;
        mi = min(a, mi);
    }

    if(ma > mi){
        cout << "War" << endl;
        return 0;
    }


    for(int i = x+1; i <= y; i++){
        if(ma < i && mi >= i){
            cout << "No War" << endl;
            return 0;
        }
    }

    cout << "War" << endl;
    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
arr = list(map(int, input().split()))

dp = [False] * (k + 1)

for i in range(1, k+1):
    for a in arr:
        if i - a >= 0 and not dp[i - a]:
            dp[i] = True

print("First" if dp[k] else "Second")


Measured memory_bytes: 3828
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	s=list(io())[:-1]
	if len(s)% 2==1:
		center=len(s)//2
		mm=s[center]
		ret=center+1
		la=s[center-1::-1]
		lb=s[center+1:]
		for ca,cb in zip(la,lb):
			#print(ca,cb,mm)
			if ca == mm and cb == mm:
				ret += 1
			else:
				break
	else:
		center=len(s)//2
		ret=center
		mm=-1
		la=s[center-1::-1]
		lb=s[center:]
		for ca, cb in zip(la, lb):
			if (mm == ca or mm == -1) and ca == cb:
				ret+=1
				mm=ca
			else:
				break
				
	if 0:
		print(la)
		print(lb)
		print(mm)
	return ret

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def mod_comb_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
print((2*mod+(pow(2,n,mod)-1)-mod_comb_count(n,a,mod)-mod_comb_count(n,b,mod))%mod)


Measured memory_bytes: 40428
N = int(input())
A = [int(s) for s in input().split(' ')]
A.sort()
print(A[N - 1] + sum([abs(a) for a in A[1:N - 1]]) - A[0])
answer = ''
for i in range(1, len(A) - 1):
    if(A[i] > 0):
        answer += "{} {}\n".format(A[0], A[i])
        A[0] -= A[i]
    else:
        answer += "{} {}\n".format(A[N - 1], A[i])
        A[N - 1] -= A[i]
answer += "{} {}\n".format(A[N - 1], A[0])
print(answer)

Measured memory_bytes: 14788
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n, a, b = inm()
if a == 0:
    print(0)
elif n >= a+b:
    print(n//(a+b) * a + min(a, n % (a+b)))
else:
    print(min(n, a))

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

int main() {
    long long n, m;
    std::cin >> n >> m;
    std::vector<std::map<int, int>> v(n + 1);
    for (int i = 0; i < m; i++) {
        long long y, p;
        std::cin >> p >> y;
        v[p][y] = i;
    }

    std::vector<std::string> ret(m);
    for (int i = 0; i <= n; i++) {
        int cnt = 1;
        for (auto& el : v[i]) {
            auto s = std::to_string(i);
            while (s.size() < 6) s = '0' + s;
            auto t = std::to_string(cnt++);
            while (t.size() < 6) t = '0' + t;
            ret[el.second] = s + t;
        }
    }

    for (auto& ss : ret) std::cout << ss << std::endl;

    return 0;
}

Measured memory_bytes: 16384
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#define ll long long
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pi(n) prllf("%d",n)
#define pl(n) prllf("%d",n)
using namespace std;

int main(){
  ll n,x;
  cin >> n >> x;
  ll arr[n];
  ll s = 0;
  for(ll i=0;i<n;i++){
    cin >> arr[i];
    s+=arr[i];
  }
  ll ans = n;
  if(x-s>0){
      ll k1 = -1;
      ll rem = x-s;
      for(ll i=0;i<n;i++){
        ll temp = floor((rem*1.0)/(arr[i]*1.0));
        k1 = max(k1,temp);
      }
      ans+=k1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;

int main(){
	int A,B;
	while(true){
		int cnt[100]={},r;
		A=B=1;
		while(r = scanf("%d%d",&A,&B),A||B){
			A--; B--;
			if(r==EOF) return 0;
			cnt[A]++; cnt[B]++;
		}
		bool ans=true;
		if((cnt[0]&1)==0 || (cnt[1]&1)==0){
			ans=false;
		}
		else{
			for(int i=2;i<100;i++){
				if((cnt[i]&1)==1){
					ans = false;
				}
			}
		}
		if(ans) puts("OK");
		else puts("NG");
	}
	return 0;
}

Measured memory_bytes: 1168
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def bisearch(f, n):
    l = 0
    r = n
    fl = f(l)
    fr = f(r)
    while l <= r:
        m = (l + r) // 2
        fm = f(m)
        #print l,m,r,fl,fm,fr,n
        if fm == n:
            return m
        elif fm > n:
            r = m - 1
            fr = f(r)
        else:
            l = m + 1
            fl = f(l)


def try_square_root(n2):
    return bisearch(lambda n:n*n, n2)


def main():
    n, d = get_li()
    points = []
    for _ in range(n):
        points.append(get_li())
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            sq_distance = 0
            for k in range(d):
                sq_distance += (points[i][k] - points[j][k]) ** 2
            if try_square_root(sq_distance):
                ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()


Measured memory_bytes: 63412
#include <bits/stdc++.h>
using namespace std;
int n,a,j,i,r;int main(){cin>>n;for(i=1;i<=n;i+=2){r=j=2;for(;j<=i/2;++j)if(i%j==0)++r;a+=r==8;}cout<<a<<'\n';}

Measured memory_bytes: 256