akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())
lange=[1]*(n+1)
for i in range(1,n+1):
  a=i
  b=n-a
  if lange[a]:lange[b]=0
langes=[]
for i in range(1,n):
  if lange[i]:
    if len(langes)%2:langes.append(i)
    else:langes.append(n-i)
langes.sort(reverse=1)
for i in range(m):print(i+1,i+1+langes[i])

Measured memory_bytes: 13816
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    if(n%k==0){
        cout << 0;
    }else{
        cout << 1;
    }
    

    return 0;
}

Measured memory_bytes: 3564
def examA():
    s = sys.stdin.readline().split(",")
    print(" ".join(map(str,s)))

import sys
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examA()

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

int main(){
  int n,m;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++)
  {
    cin >> s[i];
  }

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

  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if(s[i]==s[j]) cnt++;
    }
    for (int k = 0; k < m; k++)
    {
      if(s[i]==t[k]) cnt--;
    }
    ans = max(ans,cnt);
    cnt = 0;
  }
  
  cout << ans << endl;
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	while (cin >> n, n) {
		vector<string> v(n);
		REP(i, n)cin >> v[i];
		vvi g(26);
		bool ok = true;
		REP(i, n - 1) {
			bool done = false;
			REP(j, min(v[i].size(), v[i + 1].size())) {

				if (v[i][j] != v[i + 1][j]) {
					done = true;
					g[v[i][j] - 'a'].push_back(v[i + 1][j] - 'a');
					break;
				}
			}
			if (!done) {
				if (v[i].size() > v[i + 1].size())ok = false;
			}
		}
		REP(i, 26) {
			sort(ALL(g[i]));
			UNIQUE(g[i]);
		}
		vi d(26);
		REP(i, 26) {
			REP(j, g[i].size()) {
				d[g[i][j]]++;
			}
		}
		queue<int> q;
		REP(i, 26)if (d[i] == 0)q.push(i);
		while (!q.empty()) {
			int p = q.front();
			q.pop();
			REP(i, g[p].size()) {
				if (--d[g[p][i]] == 0)q.push(g[p][i]);
			}
		}
		ok &= *max_element(ALL(d)) == 0;
		if (ok)cout << "yes" << endl;
		else cout << "no" << endl;
	}
}


Measured memory_bytes: 3280
n,k=map(int,input().split())
x=[0]*(10**5)#1~10**5
for i in range(n):
    a,b=map(int,input().split())
    x[a-1]+=b
for i in range(10**5):
    k-=x[i]
    if k<=0:
        print(i+1)
        break


Measured memory_bytes: 5748
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <map>
#include <functional>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
  unsigned long int L, N, M;
  while(cin >> L, L){
    int ans = 0;
    unsigned long int sum = 0;
    for(int i = 0; i < 12; i++){
      cin >> M >> N;
      sum += (M - N);
      if(sum >= L && !ans){
        ans = i + 1;
      }
    }
    if(sum < L)cout << "NA" << endl;
    else cout << ans << endl;
  }
}

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

int main()
{
	int n;
	cin >> n;
	
	int tag[n-1];
	for (int i = 0; i < n-1; i++)
	{
		cin >> tag[i];
	}
	
	int sum = 0;
	
	for (int i = 0; i < n-1; i++)
	{
		if (i==0) sum+=tag[i];
		
		else {
			if (tag[i-1]<tag[i]) sum+=tag[i-1];
			else sum+=tag[i];
		}
	}
	sum+=tag[n-2];
	cout << sum << "\n";
}

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(x) cout << x << endl;

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

    bool flag = false;
    int t, f;
    string c;
    rep(i,q){
        cin >> t;
        if(t == 1){
            flag = !flag;
        }else{
            cin >> f >> c;
            // 直前で反転してたらf==2でも先頭に
            if((!flag && f == 1) || (flag && f == 2)){
                s.insert(0,c);
            // 直前で反転してたらf==1でも末尾に
            }else{
                s+=c;
            }
        }
    }
    if(flag) reverse(s.begin(),s.end());
    OP(s);
}


Measured memory_bytes: 900
#include <stdio.h>

int main(){
	int i,j,hit,brow;
	int a[4],b[4];

	while(scanf("%d%d%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&b[0],&b[1],&b[2],&b[3]) != EOF){
		hit = 0;
		brow = 0;

		for(i = 0;i < 4;i++){
			for(j = 0;j < 4;j++){
				if(a[i] == b[j]){
					brow++;
				}
			}
			if(a[i] == b[i]){
				hit++;
			}
		}

		brow -= hit;

		printf("%d %d\n",hit,brow);
	}

	return 0;
}

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

template<int MOD>
struct ModInt {
    long long v;
    ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
    ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
    ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
    ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
    ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
    bool operator == (const ModInt &other) const {return v == other.v;}
    bool operator != (const ModInt &other) const {return v != other.v;}
    friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
    friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
    friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
    friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
    friend ModInt operator - (const ModInt &a) {return 0 - a;}
    friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
    friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
    friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
};
typedef ModInt<1000000007> M;

M dp[2005][2005];

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

    int s;
    cin >> s;

    dp[0][3] = 1;
    for (int i=0; i<=s; i++)
        for (int j=3; j<=s; j++) {
            // add number to seq
            if (i + j <= s)
                dp[i+j][3] += dp[i][j];
            // consider next number
            dp[i][j+1] += dp[i][j];
        }
    cout << dp[s][3] << "\n";

    return 0;
}


Measured memory_bytes: 35048
#include<iostream>
#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
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define ll  long long 
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
#define mod 1000000007
  //vector<ll>to[1000005];
  // ll dp[2000000];
 int gcd(int a, int b)
{
  if (a%b == 0)
{
return(b);
}
else
{
return(gcd(b,a%b));
}
}
  vector<ll>e(200002);
  vector<ll>d(200002);
    vector<vector<ll>>c(1000002);
    vector<vector<ll>>c2(1000002);
int dfs(ll a,ll b){
  ll ans=0;
  if(b!=-1)d[a]+=d[b];
  rep(i,c[a].size()){
    if(c[a][i]==b)continue;
    dfs(c[a][i],a);
  }
  return 0;
}
int main(){
  ll a,b,ans=0,x,y;cin>>a>>b;
  rep(i,a-1){
    cin>>x>>y;
    c[x-1].push_back(y-1);
    c[y-1].push_back(x-1);
  }
  rep(i,b){
   cin>>x>>y;
    d[x-1]+=y;
  }
  e[ans]=d[ans];
  //cout<<ans;
  dfs(0,-1);
  rep(i,a)cout<<d[i]<<" ";
}


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

int main() {
    int64_t X, K, D;
    cin >> X >> K >> D;
    if (X < 0) {
        X = -X;
    }

    //D未満になるまでにかかる回数
    int64_t num = X / D;

    if (num >= K) {
        cout << X - D * K << endl;
        return 0;
    }

    //D未満になったときの値
    int64_t x = X - D * num;

    //残り操作回数
    int64_t rem = K - num;

    if (rem % 2 == 0) {
        cout << x << endl;
    } else {
        cout << D - x << endl;
    }
}

Measured memory_bytes: 3640
# coding:utf-8


def main():
    # N = int(input())
    S = list(input())
    flag = True
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            flag = False
    if flag:
        print('Good')
    else:
        print('Bad')
    # N, M = map(int, input().split())
    # print()


if __name__ == "__main__":
    main()


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin >> n;
  string s;
  cin >> s;

  // left to right
  stack<char> left;
  ll l = 0;
  for(int i = n-1; i >= 0; i--){
    if(')' == s[i])
      l++;
    else if(l != 0)
      l--;

    left.push(s[i]);
  }
  while(l > 0){
    left.push('(');
    l--;
  }

  //right to left
  queue<char> right;
  ll r = 0;
  while(!left.empty()){
    char now = left.top();
    if('(' == now)
      r++;
    else if(r != 0)
      r--;

    right.push(now);
    left.pop();
  }
  while(r > 0){
    right.push(')');
    r--;
  }

  while(!right.empty()){
    cout << right.front();
    right.pop();
  }

  cout << endl;

}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;

void main()
{
    int r=0,d=0;
    foreach(s;stdin.byLine())
    {
        auto m = s.split(",").map!(to!int);
        immutable a=m[0], b=m[1], c=m[2];
        if(a*a+b*b==c*c) ++r;
        if(a==b) ++d;
    }
    writeln(r);
    writeln(d);
}

Measured memory_bytes: 1084
D,G=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(D)]

ans=10000
for i in range(2**D):
    score=0
    cnt=0
    rest=[]
    for j in range(D):
        if (i>>j)&1:
            score+=100*(j+1)*s[j][0]+s[j][1]
            cnt+=s[j][0]
        else:
            rest.append(j)

    if score<G:
        r=rest[-1]
        for _ in range(s[r][0]-1):
            score+=100*(r+1)
            cnt+=1
            if score>=G: break

    if score>=G:
        ans=min(cnt,ans)

print(ans)


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

using namespace std;

typedef long long ll;

int main(int, char**)
{
	ll ans = 0;
	ll sa = 0;
	string str;
	cin >> str;

	bool isCont = false;
	for (int i = 0; i < (str.length() - 1); ++i) {
		if (str[i] == 'A') {
			sa++;
			continue;
		}
		if (str[i] == 'B' && str[i+1] == 'C') {
			ans += sa;
			i++;
		} else {
			isCont = false;
			sa = 0;
		}
	}

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


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long int
#define IOS cin.tie(NULL);cout.tie(NULL)
#define F first
#define S second
#define pb push_back
using namespace std;
ll arr[1001][1001];
int main() {
	IOS;
	int w,h;
	char x;
	ll const num=1000000007;
	cin>>h>>w;
	
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>x;
			
			if(i==1&&j==1&&x!='#'){
				arr[i][j]=1;
			} else if(x=='#')
			arr[i][j]=0;
			else {
				arr[i][j]=(arr[i-1][j]%num+arr[i][j-1]%num)%num;
			}
			
		}
	}
	cout<<arr[h][w];
}


Measured memory_bytes: 8064
#include<stdio.h>
signed main(){
    int n,k,p[99999],i,j,l,m,o=0;
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&p[i]);
    }
    for(i=0;i<n;i++){
        l=i;
        for(j=i+1;j<n;j++){
            if(p[j]<p[l]){
                l=j;
            }
        }
        if(l!=i) {
            m=p[i];
            p[i]=p[l];
            p[l]=m;
        }
    }
    for(i=0;i<k;i++){
        o +=p[i];
    }
    printf("%d\n",o);
    return(0);
}

Measured memory_bytes: 1724
// Training Camp
#include <cmath>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    long long x = 1;
    cin >> N;
    for (int i = 1; i <= N; i++) x = (x * i) % (1000000007);
    cout << x << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var Alist = Console.ReadLine().Split(' ').Select(int.Parse);

            var output = 1 / Alist.Select(A => 1d / A).Sum();
            Console.WriteLine(output);
        }
    }
}


Measured memory_bytes: 13396
from math import gcd
N, M = map(int, input().split())
S = input()
T = input()

L = N // gcd(N, M) * M

ds = L // N
dt = L // M
S = S[0::dt]
T = T[0::ds]

if S == T:
    print(L)
else:
    print(-1)

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

int main(){
    string l;
    cin >> l;
    ll dp[2];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 0; i < l.size(); i++){
        if(l[i] == '1'){
            dp[0] = (dp[0]*3+dp[1])%1000000007;
            dp[1] = (dp[1]*2)%1000000007;
        }
        else{
            dp[0] *= 3;
            dp[0] %= 1000000007;
        }
    }
    cout << (dp[0] + dp[1])%1000000007 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    ll N;
    cin >> N;
    if(N % 2  != 0)cout << 0 << endl;
    else{
    ll ans = N / 10;
    ll m = ans;
    while(m){
        m /= 5;
        ans += m;
    }
    cout << ans << endl;
    }
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	points := make([]point, m)
	for i := 0; i < m; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		points[i] = point{x - 1, y - 1}
	}

	count := 0
	for i := 0; i < m; i++ {
		field := make([][]int, n)
		for j := 0; j < n; j++ {
			field[j] = make([]int, n)
		}
		for j := 0; j < m; j++ {
			if i == j {
				continue
			}
			field[points[j].x][points[j].y] = 1
			field[points[j].y][points[j].x] = 1
		}
		mm := rec(field, make(map[int]int), n, 0)
		if len(mm) != n {
			count++
		}
	}
	fmt.Println(count)
}

type point struct {
	x, y int
}

func rec(field [][]int, m map[int]int, n, x int) map[int]int {
	m[x] = 0
	for y := 0; y < n; y++ {
		if field[x][y] != 0 {
			field[x][y], field[y][x] = 0, 0
			rec(field, m, n, y)
		}
	}
	return m
}

Measured memory_bytes: 1792
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)
#define RALL(x) (x).rbegin(), (x).rend()


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int N, H, a[111111];

  std::cin >> N >> H;

  std::vector<std::pair<int, int>> pairs(N);

  for (int i = 0; i < N; i ++) {
    std::cin >> a[i] >> pairs[i].first;

    pairs[i].second = i;
  }

  std::sort(RALL(pairs));

  int c = 0, b, i, ap = 0;

  for (const auto& pair : pairs) {
    std::tie(b, i) = pair;

    if (ap > b) {
      int cc = (H + ap - 1) / ap;

      H = std::max(H - ap * cc, 0);
      c += cc;
      
      break;
    }

    H = std::max(H - b, 0);
    c ++;

    if (H == 0)
      break;
    
    ap = std::max(a[i], ap);
  }

  if (H)
    c += (H + ap - 1) / ap;

  std::cout << c << std::endl;

  return 0;
}


Measured memory_bytes: 1408
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;	
	cin >> s;
	long long k;
	cin >> k;
	vector<long long> v;
	int n = s.length();
	int last = 1;
	for(int i=1;s[i];i++) {
		if(s[i] == s[i-1]) last++;
		else {
			v.push_back(last);
			last=1;
		}
	}
	v.push_back(last);
	long long ans = 0;
	for(int i=0;i<v.size();i++) ans += (v[i] / 2) * k;
	if(v.size()>=3&&s[n-1]==s[0]) {
		if( v[0]%2==1 && v.back()%2==1 ) ans += (k-1);
	}
	if(v.size()==1) {
		ans = ((long long)s.length()*k)/2;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
        int H,W,N;
        N=0;
        cin >> H >> W ;
        char s[H][W];
        int a[H][W];
        for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                        a[i][j]=0;
                }
        }
        for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                        cin>>s[i][j];
                }
        }
        for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                        if(s[i][j]=='.')a[i][j]=1;
                }
        }
        for(int i=0;i<W-1;i++){
                if(s[H-1][i]=='#'){
                                if(s[H-1][i+1]=='#'){
                                        a[H-1][i]=1;
                                        a[H-1][i+1]=1;
                                }
                }
        }
        for(int i=0;i<H-1;i++){
                if(s[i][W]=='#'){
                                if(s[i+1][W-1]=='#'){
                                        a[i][W-1]=1;
                                        a[i+1][W-1]=1;
                                }
                        }
        }
        for(int i=0;i<H-1;i++){
                for(int j=0;j<W-1;j++){
                        if(s[i][j]=='#'){
                                if(s[i][j+1]=='#'){
                                        a[i][j]=1;
                                        a[i][j+1]=1;
                                }
                                if(s[i+1][j]=='#'){
                                        a[i][j]=1;
                                        a[i+1][j]=1;
                                }
                        }
                }
        }
        for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                        if(a[i][j]==0){
                                N=1;
                                break;
                        }
                }
        }
        if(N==1){

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


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
   int x,y;
   while(1)
         {
          cin>>x>>y;
          if(x==0&&y==0)
                break;
          if(x>y) cout<<y<<" "<<x<<endl;
          else cout<<x<< " "<<y<<endl;
         }
    return 0;
}



Measured memory_bytes: 3016
import fractions
A, B, C, D = map(int, input().split())
divC=B//C-(A-1)//C
divD=B//D-(A-1)//D
CD=int(C*D/fractions.gcd(C, D))
divCD=B//(CD)-(A-1)//(CD)
print(B-A+1-(divC+divD-divCD))

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

using namespace std;

const double PI = acos(-1.0); 
using cd = complex<double>;

void solve() {
    int n; double L;
    cin >> n >> L;
    vector<double> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cd res;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            res += polar(1.0, PI*(a[i]+a[j])/L) * (double)(n-j-1 + i);
            res += polar(1.0, PI*(a[i]+a[j])/L + PI) * (double)(j - i - 1);
        }
    }
    double tot = double(n)*(n-1)*(n-2)/6;
    res /= tot;
    cout << fixed << setprecision(10);
    cout << res.real() << ' ' << res.imag();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 10;
typedef long long ll;
ll n,ans;
int main() {
	scanf("%lld",&n);
	for (ll k = 2; k * k <= n; k++) {
		ll t = k;
		while (t <= n) {
			if (n % t == 0 && (n / t == 1 || (n / t - 1) % k == 0)) {
			//	printf("%lld\n",k);
				ans++;
				break;
			}
			t = t * k;
		}	
	}
	for (ll k = 1; k * k <= n - 1; k++) {
		if ((n - 1) % k == 0) {
			if (k != 1) ans++;
			if ((n - 1) / k != k) ans++;
			//printf("%lld %lld %lld %lld\n",k,(n - 1) / k,n % k,n % ((n - 1) / k));
		}
	}
	printf("%lld\n",ans + 1);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
#include <iomanip>
#include <limits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;

using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

typedef priority_queue<ll> PQ_HIGH;
typedef priority_queue<ll,VL,greater<ll>> PQ_LOW;//昇順

//A 65
//a 97
//pairの比較関数(昇順)
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
//降順
bool compare_by_b_high(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){
  ll n,k;cin>>n>>k;
  vector<pair<int,int>> data;
  REP(i,n){
    int a,b;cin>>a>>b;
    data.push_back({a,b});
  }
  sort(data.begin(),data.end());
  int i=0;
  while(k>0){
    k=k-data[i].second;
    i++;
  }
  i--;
  cout<<data[i].first<<endl;
}

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


typedef struct str_obs str_obs_t;
typedef struct str_obs {
    int id;
    int64_t H;
    int64_t nextcnt;
    vector<str_obs_t *> next;
}str_obs_t;

int search(str_obs_t* cur, int64_t H);
int main(void) {
    int64_t N,M;
    int64_t h;
    int64_t A,B;
    int cnt = 0;

    cin >> N >> M;
    vector<str_obs_t> H(N);
    for(int i=0;i<N;i++) {
        cin >> h;
        H[i].id = i;
        H[i].H = h;
        H[i].nextcnt = 0;
    }

    for(int i=0;i<M;i++) {
        cin >> A >> B;
        H[A-1].nextcnt++;
        H[B-1].nextcnt++;
        H[A-1].next.push_back(&H[B-1]);
        H[B-1].next.push_back(&H[A-1]);
    }

    for(int i=0;i<H.size();i++){
        h = H[i].H;
        // 探索
        if(!search(&H[i], h)) {
            cnt++;
        };
    }

    cout << cnt << "\n";
    return 0;
}

int search(str_obs_t* cur, int64_t H) {
    int ret;

    for(int i=0;i<cur->nextcnt;i++) {
        if(cur->next[i]->H >= H) {
            return -1;
        }
    }

    return 0;
}


Measured memory_bytes: 11444
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		boolean flag = false;
		for(int i = 0; i < S.length(); i++) {
			for(int j = i; j <= S.length(); j++) {
				StringBuilder sb = new StringBuilder(S);
				if(sb.delete(i, j).toString().equals("keyence")) {
					flag = true;
				}
			}
		}
		if(flag) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 24656
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    d = defaultdict(bool)
    for a in A:
        if d[a]:
            d[a] = False
        else:
            d[a] = True

    ans = sum(1 for f in d.values() if f)
    
    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 22436
#include <bits/stdc++.h>
using namespace std;
#define endl "\n";
typedef  long long int lli;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inf (1000*1000*1000+5)
const int NODE =1e4+9;

const int mod=1e9+7;
const lli num=1e5+5;

vector<int>dp;
vector<int>adj[num];
void init(){

}

int dfs(int x){
   if(dp[x]!=-1)return dp[x];
   int tmp=0;
   for(auto c:adj[x]){
      tmp=max(tmp,dfs(c)+1);
   }
   dp[x]=tmp;
   return dp[x];
}


int main()
{
   boost;
   int t=1;
   //cin>>t;
   init();
   while(t--){
      int n,m,a,b;
      cin>>n>>m;
      for(int i=0;i<m;i++){
         cin>>a>>b;
         a--;b--;
         adj[a].push_back(b);
      }
      dp.assign(n,-1);
      int ans=0;
      for(int i=0;i<n;i++){
         ans=max(ans,dfs(i));
      }
      cout<<ans<<endl;
   }
   return 0;
}


Measured memory_bytes: 11016
t=int(input())
from functools import lru_cache####
@lru_cache(maxsize=10000)####
def f(x,a,b,c,d):
    if x==1:
        return d
    
    if x==0:
        return 0
    
    res1,res2=0,0
    if x%2:
        res1 = f(x//2,a,b,c,d)+a+d
        res2 = f(x//2+1,a,b,c,d)+a+d
    else:
        res1=res2=f(x//2,a,b,c,d)+a
    res3,res4=0,0
    if x%3:
        res3 = f(x//3,a,b,c,d)+b+d*(x%3)
        res4 = f(x//3+1,a,b,c,d)+b+d*(3-x%3)
    else:
        res3=res4=f(x//3,a,b,c,d)+b
    if x%5:
        res5 = f(x//5,a,b,c,d)+c+d*(x%5)
        res6 = f(x//5+1,a,b,c,d)+c+d*(5-x%5)
    else:
        res5=res6=f(x//5,a,b,c,d)+c
    return(min(res1,res2,res3,res4,res5,res6,x*d))
for _ in range(t):
    n,a,b,c,d=map(int, input().split( ))
    
    ans=f(n,a,b,c,d)
    print(ans)
        
        
    
    


Measured memory_bytes: 13456
#include "bits/stdc++.h"
using namespace std ;


int a[200005] ;


int main(){
    int N , K ;
    cin >> K  >> N ;
    for( int i = 0 ; i < N ; i++ ){
        cin >> a[i] ;
    }
    int ans = -1 ;
    for( int i = 0 ; i < N -1  ; i++ ){
        ans = max(ans,abs(a[i+1]-a[i])) ;
    }
    ans = max(ans,a[0]+K-a[N-1]) ;
    // cout << ans << endl ;
    cout << K - ans << endl ;



    return 0 ;
}

Measured memory_bytes: 1024
s=list(input())
t=list(input())
sl=len(s)
tl=len(t)
for k in range(sl-tl,-1,-1):
    judge=True
    for i in range(tl):
        if s[i+k]==t[i] or s[i+k]=="?":
            pass
        else:
            judge=False
            break
    if judge:
        for i in range(tl):
            s[i+k]=t[i]
        for i in range(sl):
            if s[i]=="?":
                s[i]="a"
        print("".join(s))
        exit()
print("UNRESTORABLE")



Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007
#define D 100000000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less_equal<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

int main() 
{
    FAST;
    string s,t;
    cin>>s>>t;
    ll n=s.length();
    ll ans=0;
    for(int i=0;i<n;i++)
        if(s[i]!=t[i])
            ans++;
    cout<<ans;
    subt;
    return 0;
}

Measured memory_bytes: 3876
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define F first
#define S second
#define INF 1000000000000000000
#define M 1000000007
void YES(bool o){
    if(o)printf("YES\n");
    else printf("NO\n");
}
void Yes(bool o){
    if(o)printf("Yes\n");
    else printf("No\n");
}
int main(void){
    int n;
    cin>>n;
    if(n==25){
        cout<<"Christmas"<<endl;
    }else if(n==24){
        cout<<"Christmas Eve"<<endl;
    }else if(n==23){
        cout<<"Christmas Eve Eve"<<endl;
    }else{
        cout<<"Christmas Eve Eve Eve"<<endl;
    }
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int mod=1e9+7;
const int INF=1001001001;

int64_t dp[3010][3010][10];
int main() {
  int R,C,K;
  cin>>R>>C>>K;
  vector<int>r(K),c(K),v(K);
  vector<vector<int>>add(R,vector<int>(C));
  for(int i=0;i<K;i++){
    cin>>r[i]>>c[i]>>v[i];
    r[i]--;c[i]--;
    add[r[i]][c[i]]=v[i];
  }

  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      for(int k=2;k>=0;k--){
        chmax(dp[i][j][k+1],dp[i][j][k]+add[i][j]);
      }
      for(int k=0;k<=3;k++){
        chmax(dp[i+1][j][0],dp[i][j][k]); 
        chmax(dp[i][j+1][k],dp[i][j][k]);
      }
    }
  }

  int64_t MAX=0;
  for(int k=0;k<=3;k++){
    chmax(MAX,dp[R-1][C-1][k]);
  }
  cout<<MAX<<endl;
  return 0;  
}

Measured memory_bytes: 746512
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n=0;
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='-') n--;
        else n++;
    }
    cout<<n<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        try (InputReader reader = new InputReader(System.in)) {
            solve(reader);
        }
    }

    private static void solve(InputReader reader) throws IOException {
        int[] input = reader.readIntsSplitByDelimiter(" ");
        int d = input[0];
        int n = input[1];

        if (n == 100) {
            int ans = 101 * (int)Math.pow(100, d);
            System.out.println(ans);
            return;
        }

        int ans = n * (int)Math.pow(100, d);
        System.out.println(ans);
    }
}

class Util {
    static int gcd(int m, int n) {
        int min = Math.min(m, n);
        int max = Math.max(m, n);
        while (min != 0) {
            int tmp = min;
            min = max % tmp;
            max = tmp;
        }

        return max;
    }

    static int lcm(int m, int n) {
        return m / gcd(m, n) * n;
    }
}

class InputReader implements Closeable, AutoCloseable {
    private final BufferedReader br;

    InputReader(InputStream inputStream) {
        this.br = new BufferedReader(new InputStreamReader(inputStream));
    }

    String readLine() throws IOException {
        return this.br.readLine();
    }

    int readInt() throws IOException {
        return Integer.parseInt(this.readLine());
    }

    long readLong() throws IOException {
        return Long.parseLong(this.readLine());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(this.readLine());
    }

    String[] readStringsSplitByDelimiter(String delimiter) throws IOException {
        return this.readLine().split(delimiter);
    }

    int[] readIntsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.readStringsSplitByDelimiter(delimiter);

        int stringsLength = strings.length;
        int[] ints = new int[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            ints[i] = Integer.parseInt(strings[i]);
        }

        return ints;
    }

    long[] readLongsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.readStringsSplitByDelimiter(delimiter);

        int stringsLength = strings.length;
        long[] longs = new long[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            longs[i] = Long.parseLong(strings[i]);
        }

        return longs;
    }

    double[] readDoublesSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.readStringsSplitByDelimiter(delimiter);

        int stringsLength = strings.length;
        double[] doubles = new double[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            doubles[i] = Double.parseDouble(strings[i]);
        }

        return doubles;
    }

    @Override
    public void close() throws IOException {
        this.br.close();
    }
}


Measured memory_bytes: 22868
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	//static int mod = (int) (1e9+7),MAX=(int) (2e5+100);
    static List<Integer>[] edges;
    static long[] ans,dp;
    static int n,m;

	public static void main(String[] args) {
	    n = sc.nextInt();
	    m = sc.nextInt();
	    edges = new ArrayList[n+1];
	    ans = new long[n+1];
	    dp = new long[n+1];
	    
	    for(int i=0;i<edges.length;++i) edges[i] = new ArrayList<>();
	    for(int i=1;i<n;++i) {
	    	int u = sc.nextInt();
	    	int v = sc.nextInt();
	    	edges[u].add(v);
	    	edges[v].add(u);
	    }
	    
	    dfs(1,0);
	    reroot(1,0,1);
	    for(int i=1;i<=n;++i) out.println(ans[i]);
		out.close();
   }

	private static void reroot(int v, int par, long pans) {
		long[] pre=new long[edges[v].size()];
		long[] suf=new long[edges[v].size()];
		
		for (int i=0;i<edges[v].size();++i) {
			int child = edges[v].get(i);
			if (child == par) pre[i] = pans;
			else pre[i] = dp[child]+1;
			if (i > 0) pre[i]*=pre[i-1];
			if (pre[i] >= m) pre[i] %= m;
		}
		for (int i=edges[v].size()-1;i>=0;--i) {
			int child = edges[v].get(i);
			if (child == par) suf[i] = pans;
			else suf[i] = dp[child]+1;
			if (i+1 < edges[v].size()) suf[i]*=suf[i+1];
			if (suf[i] >= m) suf[i]%=m;
		}
		long res = pans;
		for (int i=0;i<edges[v].size();++i) {
			int child = edges[v].get(i);
			if (child == par) continue;
			long tmp = 1;
			if (i>0) tmp = tmp*pre[i-1]%m;
			if (i+1<edges[v].size()) tmp = tmp*suf[i+1]%m;
			reroot(child,v,tmp+1);
			res = res*(dp[child]+1)%m;
		}
		ans[v]= res%m;
		
	}

	private static void dfs(int v, int par) {
		dp[v] = 1;
		for(int child : edges[v]) {
			if(child != par) {
				dfs(child,v);
				dp[v] = mul(dp[v],dp[child]+1);
			}
		}
	}

	private static long mul(long a, long b) {
		return ((a%m) * (b%m))%m;
	}

	
}



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

using namespace std;

int main(){

  int n,m,a;

  while(1){
	cin>>n>>m>>a;

	vector<vector<int>> line;
	int s1,s2,s3;
	int now;

	if(n==0 && m==0 && a==0)
	  break;

	line = vector<vector<int>>(n+5000,vector<int>(n+5000,0)); 
	
	for(int i=0;i<m;++i){
	  cin>>s1>>s2>>s3;
	
	  line[s1][s2]=s3;
	  line[s1][s3]=s2;
	
	}

	now = a;

	for(int i=5000;i>=1;--i){
	  if(line[i][now] != 0){
		now = line[i][now];
	  }
	}
	cout<<now<<endl;
  }

  return 0;
  
}



Measured memory_bytes: 104668
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String N = sc.next();
    char[]n = N.toCharArray();
    
    int all = 0;
    for(int i=0; i<N.length(); i++) {
    	all += n[i]-48;
    }
    int a = Integer.valueOf(N); 
 
    	if(a%all == 0) {
    		System.out.println("Yes");
    	 }else{
    		 System.out.println("No");
      }
    }	 
    }

Measured memory_bytes: 35644
#include<iostream>
#include<string>
#include<utility>
#include<algorithm>

using namespace std;

int w[100000];

bool check(int n, int k, int p) {
	int i=0, tn=0, tw=0;
	for(i=0; i<n && tn<k; i++) {
		if(tw+w[i]>p) {
			tn++;
			tw=w[i];
		} else {
			tw+=w[i];
		}
	}
	return (tn<k);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	int l=0, r=0;
	cin>>n>>k;

	for(int i=0; i<n; i++) {
		cin>>w[i];
		l=max(w[i], l);
		r+=w[i];
	}
	while(l<r) {
		int m=l+(r-l)/2;
		if(check(n, k, m)) r=m;
		else l=m+1;
	}
	cout<<r<<'\n';
	return 0;
}



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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll ;
typedef long double ld ;

const ll MOD = 998244353, INF = 2E18 + 5 ;
const double PI = 2 * acos(0.0) ;
const long double EPS = 1.0E-14 ;


int main()
{
    ll a, b, c, k, val, sum = 0 ;
    cin >> a >> b >> c >> k ;
    val = min(a, k) ;
    a -= val, k -= val ;
    sum += val ;

    val = min(b, k) ;
    b -= val, k -= val ;

    val = min(c, k) ;
    c -= val, k -= val ;

    val = val * -1 ;

    sum += val ;

    cout << sum ;



    return 0 ;
}


Measured memory_bytes: 3636
/*
    mdsaqib
*/

#include <bits/stdc++.h>
#define int long long
#define all(c) (c).begin(),(c).end()
#define endl '\n'
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
using namespace std;

signed main(){
    fast;
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k<a){
        cout << k;
    }
    else if(k<a+b){
        cout << a;
    }
    else cout << a-(k-a-b);
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int n, m, x[N], y[N], tr[N];
pii a[N];

bool cmp(pii a, pii b) {
	return (a.fi != b.fi) ? a.fi < b.fi : a.se > b.se;
}

void init() {
	int cnt = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) scanf("%d", &x[i]);
	for (int i = 1; i <= m; ++i) scanf("%d", &y[i]);
	for (int i = 1; i <= n; ++i) {
		if (x[i] < y[1] || x[i] > y[m]) continue;
		int t = lower_bound(y + 1, y + m + 1, x[i]) - y;
		a[++cnt] = mp(x[i] - y[t - 1], y[t] - x[i]);
	}
	sort(a + 1, a + cnt + 1, cmp);
	n = unique(a + 1, a + cnt + 1) - a - 1;
	m = 0;
	for (int i = 1; i <= n; ++i) y[++m] = a[i].se;
	sort(y + 1, y + m + 1);
	m = unique(y + 1, y + m + 1) - y - 1;
	for (int i = 1; i <= n; ++i)
		a[i].se = lower_bound(y + 1, y + m + 1, a[i].se) - y; 
}

inline void Add(int x, int val) {
	for (++x; x < N; x += x & -x) {
		tr[x] += val;
		if (tr[x] >= mod) tr[x] -= mod;
	}
}

inline int Query(int x) {
	int res = 0;
	for (++x; x; x -= x & -x) {
		res += tr[x];
		if (res >= mod) res -= mod;
	}
	return res;
}

void Solve() {
	int res = 1;
	for (int i = 1; i <= n; ++i) {
		int del = Query(a[i].se - 1) + 1;
		res += del;
		if (res >= mod) res -= mod;
		Add(a[i].se, del);
	}
	cout << res << endl;
}

int main() {
	init();
	Solve();
	return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = k; i < n; i++) {
    if (a[i - k] < a[i])
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3996
#include <cstdio>
#include <cstring>

int N;
char s[100100];

int main()
{
	int i;
	scanf("%s", &s);
	N = strlen(s);
	int g=0, p=0;
	int sc = 0;
	for(i=0; i<N; i++){
		if(p<g){
			if(s[i] == 'g')
				sc ++;
			p ++;
		}
		else{
			if(s[i] == 'p')
				sc --;
			g ++;
		}
	}
	printf("%d\n", sc);
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
hs = sorted([int(input()) for _ in range(N)], reverse=True)
             
ans = 10 ** 10

for i in range(N-K+1):
  tmp = hs[i] - hs[i+K-1]
  ans = min(ans, tmp)
  
print(ans)

Measured memory_bytes: 8280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1e9)
#define MOD (1e9+7)

/////////////////////////////////////////////////////////

void Main(){
  ll N; cin >> N;

  ll sum = 0;
  int cnt = 1;
  while(true){
    sum += cnt;
    if(sum >= N){
      cout << cnt << endl;
      break;
    }
    cnt++;
  }
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
def rot(S, N):
  A = []
  P = []
  for i in range(len(S)):
    A.append(ord(S[i]) - ord('A'))
    A[i] = (A[i] + N) % 26
    P.append(chr(ord('A') + A[i]))
  return P
  
N = int(input())
S = input()
print(''.join(rot(S, N)))

Measured memory_bytes: 3316
"'A', 'C', 'G', 'T' からなる長さNの文字列Sが与えられます
以下のQ個のクエリに答えよ. Sのl文字目からr文字目までにACが何回登場するかを答えよ"

#入力
N, Q = gets.split.map(&:to_i)
str = gets.chomp
l=[]
r=[]
Q.times do |i|
  l[i], r[i] = gets.split.map(&:to_i)
end

# 累積和を配列sに入れてく(ACが続いたら+1)
# i文字目(i=1,,,N)までのACの数はs[i-1]に入ってる
s=[]
s[0] = 0
(N-1).times do |i|
  if str[i]=='A' && str[i+1]=='C'
    s[i+1] = s[i] + 1
  else 
    s[i+1] = s[i]
  end
end

#i文字目からj文字目までのACの数はs[j-1]-s[i-1]
Q.times do |i|
  puts(s[r[i]-1] - s[l[i]-1])
end

Measured memory_bytes: 4984
void main()
{
    long n, l;
    rdVals(n, l);
    long[] a = rdRow;

    long idx;
    bool ok;
    foreach (i; 0.. n-1)
    {
        if (a[i] + a[i+1] >= l)
        {
            idx = i;
            ok = true;
            break;
        }
    }

    if (!ok)
    {
        "Impossible".writeln;
        return;
    }

    "Possible".writeln;
    foreach (i; 0 .. idx)
    {
        writeln(i + 1);
    }
    foreach_reverse (i; idx .. n - 1)
    {
        writeln(i + 1);
    }
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 4988