akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>

long long PRIME = 1e9 + 7;
using namespace std;

vector<vector<int>> E;


int main(){ 
    int W, H, x, y;
    cin >> W >> H >> x >> y;
    cout << fixed;

    cout << double(W) * double(H) * 0.5 << " ";

    if(x * 2 == W && y * 2 == H){
        cout << 1;
    }
    else{
        cout << 0;
    }
}



Measured memory_bytes: 256
/*
g++ -std=c++14 -o2 -Wall ABC.cpp -o .\ABC.out
.\ABC.out
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int h[100005];

int main(){
  int n,k;
  cin >> n >> k;
  int ans = 0;
  for (int i=0;i<n;++i) {
    cin>>h[i];
    if(h[i]>=k)++ans;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 640
import sys
from bisect import bisect_left

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


def main():
    A, B, Q = map(int, readline().split())
    S = [int(readline()) for _ in range(A)]
    T = [int(readline()) for _ in range(B)]
    X = [int(readline()) for _ in range(Q)]

    ans = [0] * Q
    vs = [0] * 2
    vt = [0] * 2
    for i, x in enumerate(X):
        idx_s = bisect_left(S, x)
        idx_t = bisect_left(T, x)

        vs[0] = S[idx_s - 1] if idx_s > 0 else -INF
        vt[0] = T[idx_t - 1] if idx_t > 0 else -INF
        vs[1] = S[idx_s] if idx_s < A else INF
        vt[1] = T[idx_t] if idx_t < B else INF

        ans[i] = min(
            abs(x - vs[0]) + abs(vs[0] - vt[0]),
            abs(x - vt[0]) + abs(vt[0] - vs[0]),
            abs(x - vs[0]) + abs(vs[0] - vt[1]),
            abs(x - vt[0]) + abs(vt[0] - vs[1]),
            abs(x - vs[1]) + abs(vs[1] - vt[1]),
            abs(x - vt[1]) + abs(vt[1] - vs[1]),
            abs(x - vs[1]) + abs(vs[1] - vt[0]),
            abs(x - vt[1]) + abs(vt[1] - vs[0]),
        )

    print('\n'.join(map(str, ans)))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 93080
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<string,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())

using namespace std;
int main() {
  ll N,R;
  cin>>N>>R;
  if(N>=10) {
    cout<<R<<endl;
  }
  if(N<10) {
    cout<<R+100*(10-N)<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

#define MAX_N 200005
vector<int> pre_G[MAX_N];
vector<int> G[MAX_N];
int par_[MAX_N];
int flag_netsukigi[MAX_N];
void make_netsukigi(int r){
    queue<int> que;
    que.push(r);
    flag_netsukigi[r] = 1;
    par_[r] = -1;

    while(que.size() > 0){
        int x = que.front();
        que.pop();
        flag_netsukigi[x] = 1;
        rep(i,pre_G[x].size()){
            if(flag_netsukigi[pre_G[x][i]] == 0){
                par_[pre_G[x][i]] = x;
                G[x].push_back(pre_G[x][i]);
                que.push(pre_G[x][i]);
            }
        }
    }
}

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

    rep(i,n-1){
        int a, b;
        scanf("%d%d", &a, &b);
        a--; b--; // 0-indexにするため.
        pre_G[a].push_back(b);
        pre_G[b].push_back(a);
    }

    make_netsukigi(0);

    int f[n];
    rep(i,n)f[i] = -1;

    int now1 = 1;
    int now2 = 2;
    int now3 = 3;

    int cnt1 = 0;
    int cnt2 = 0;

    queue<P> que;
    que.push(P(0,1));

    while(que.size()){
        P p = que.front();
        int x = p.first;
        int y = p.second;
        que.pop();
        if(y == 1){
            f[x] = 1;
            cnt1++;
        }else{
            f[x] = 0;
            cnt2++;
        }
        y = (y + 1) % 2;
        rep(i,G[x].size()){
            que.push(P(G[x][i], y));
        }
    }

    

    

    if(cnt1 < cnt2){
        rep(i,n)f[i] = (f[i] + 1) % 2;
        swap(cnt1, cnt2);
    }

    if(cnt2 <= n / 3){
        rep(i,n){
            if(f[i] == 0){
                f[i] = now3;
                now3 += 3;
            }
        }
        rep(i,n){
            if(f[i] == 1){
                if(now1 <= n){
                    f[i] = now1;
                    now1 += 3;
                }else if(now2 <= n){
                    f[i] = now2;
                    now2 += 3;
                }else{
                    f[i] = now3;
                    now3 += 3;
                }
            }
        }
    }else{
        rep(i,n){
            if(f[i] == 1){
                if(now1 <= n){
                    f[i] = now1;
                    now1 += 3;
                }else{
                    f[i] = now3;
                    now3 += 3;
                }
            }else{
                if(now2 <= n){
                    f[i] = now2;
                    now2 += 3;

                }else{
                    f[i] = now3;
                    now3 += 3;
                }
            }
        }
    }


    

    rep(i,n)cout << f[i] << ' ';
    cout << endl;

    return 0;
}

Measured memory_bytes: 23296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int dp[41][420][420];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int inf = 1e9;
    int N,X,Y;
    cin >> N >> X >> Y;
    vec<int> A(N),B(N),C(N);
    for(int i=0;i<N;i++) cin >> A[i] >> B[i] >> C[i];
    for(int i=0;i<=N;i++) for(int j=0;j<=410;j++) for(int k=0;k<=410;k++) dp[i][j][k] = inf;
    dp[0][0][0] = 0;
    for(int i=0;i<N;i++) for(int j=0;j<400;j++) for(int k=0;k<400;k++){
        int nj = j+A[i],nk = k+B[i];
        dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][k]);
        dp[i+1][nj][nk] = min(dp[i+1][nj][nk],dp[i][j][k]+C[i]);
    }
    int ans = inf;
    for(int j=0;j<410;j++) for(int k=0;k<410;k++){
        if(!j || !k) continue;
        if(j*Y==k*X) ans = min(ans,dp[N][j][k]);
    }
    cout << (ans!=inf? ans:-1) << "\n";
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 305;
const int MAX_M = 305;

int N, M;
int dp[MAX_N][MAX_N][MAX_N];

class Strict {
public:
  int l, x;
};

vector<Strict> S[MAX_N];

signed main()
{
  cin >> N >> M;
  REP(i,M) {
    Strict s;
    int r; cin >> s.l >> r >> s.x;
    S[r].push_back(s);
  }

  memset(dp,0,sizeof(dp));

  dp[0][0][0] = 1;

  REP(r,N+1) {
    REP(g,N+1) {
      REP(b,N+1) {
        if(dp[r][g][b] == 0) {
          continue;
        }
        
        int p = max(r, max(g, b));

        for(const auto& s : S[p]) {
          int cnt = (s.l <= r) + (s.l <= g) + (s.l <= b);
          if(cnt != s.x) {
            dp[r][g][b] = 0;
            break;
          }
        }

				dp[p + 1][g][b] = (dp[p + 1][g][b] + dp[r][g][b]) % MOD;
				dp[r][p + 1][b] = (dp[r][p + 1][b] + dp[r][g][b]) % MOD;
				dp[r][g][p + 1] = (dp[r][g][p + 1] + dp[r][g][b]) % MOD;
      }
    }
  }

  int ans = 0;
  REP(i,N) {
    REP(j,N) {
      ans += dp[N][i][j] + dp[i][N][j] + dp[i][j][N];
      ans %= MOD;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 221952
#include<stdio.h>
int main(){
  int a, b, i, n, data[3000];
  char op;
  for(i=0;;i++){
    scanf("%d %c %d", &a, &op, &b);
    if(op=='+'){
      data[i] = a+b;
    }else if(op=='-'){
      data[i] =  a-b;
    }else if(op=='*'){
      data[i] = a*b;
    }else if(op=='/'){
      data[i] = a/b;
    }else if(op=='?'){
      break;
    }
  }
  n=i;
  for(i=0;i<n;i++){
    printf("%d\n", data[i]);
  }
  return 0;
}

Measured memory_bytes: 1796
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

ll calcNumOfCombination(ll n, ll r){
	ll num = 1;
	for(ll i = 1; i <= r; i++){
		num = num * (n - i + 1) / i;
	}
	return num;
}

int main(){
	int n;
	cin >> n;
	map<char, ll> m;
	rep(i, n){
		string s;
		cin >> s;
		char c = s[0];
		m[c]++;
	}

	ll ans = 0;
	char cho[] = {'M', 'A' ,'R', 'C' ,'H'};
	rep(i, 3){
		ll addi = m[cho[i]];
		rep2(j, i+1, 4){
			ll addj = m[cho[j]];
			rep2(k, j+1, 5){
				ll addk = m[cho[k]];
				ll add = addi * addj * addk;
				ans += add;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    int n;
    int s[14] = {}, h[14] = {}, c[14] = {}, d[14] = {};

    cin >> n;

    int a;
    char ch;
    for (int i = 0; i < n; i++) {
        cin >> ch >> a;
        switch (ch) {
            case 'S' : s[a]++; break;
            case 'H' : h[a]++; break;
            case 'C' : c[a]++; break;
            case 'D' : d[a]++; break;
            default : break;
        }
    }

    for (int i = 1; i < 14; i++) if (!s[i]) cout << "S " << i << endl;
    for (int i = 1; i < 14; i++) if (!h[i]) cout << "H " << i << endl;
    for (int i = 1; i < 14; i++) if (!c[i]) cout << "C " << i << endl;
    for (int i = 1; i < 14; i++) if (!d[i]) cout << "D " << i << endl;

    return 0;
}

Measured memory_bytes: 3008
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int CNT[200001];

int main()
{
	int N, K; cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		CNT[a]++;
	}

	vector<int>kind;
	for (int i = 0; i < 200001; i++) {
		if (CNT[i])kind.push_back(CNT[i]);
	}

	sort(kind.begin(), kind.end());

	int ans = 0;
	int i = 0;
	while (kind.size()-i > K) {
		ans += kind[i++];
	}
	cout << ans << endl;

    return 0;
}



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

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

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

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

    long long ans = 0;

    reps(i,k){
        reps(j,k){
            reps(l,k){
                ans+=gcd(gcd(i,j),l);
            }
        }
    }

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

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

lint gcd(lint x, lint y) {
  if(x == 0) { return y; }
  else { return gcd(y%x,x); }
}

lint lcm(lint x, lint y) { return x/gcd(x,y)*y; }

lint C(lint n, lint k) {
  if(n == k) { return 1; }
  else if(n < k) { return 0; }
  else if(k == 0) { return 1; }
  else if(k == 1) { return n; }
  else return C(n-1,k-1) + C(n-1,k);
}

lint P(lint n, lint k) {
  if(k == 1) { return n; }
  return (n*(P(n-1,k-1)%1000000007)%1000000007);
}


int main() {
  lint n,k; cin >> n >> k;
  /*
  if(k >= n) { cout << P(k,n) << endl; }
  else { printf("%lld\n",k*(lint)pow(k-1,n-1)); }
  */
  printf("%lld\n",k*(lint)pow(k-1,n-1));
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>

using IV = std::vector<int>;
IV ToFixedIntArray(std::istream& is, int n) {
	IV ret(n);
	auto* dst = ret.data();
	while(n > 0) {
		--n;
		is >> *dst++;
	}
	return ret;
}

#define _For(idx, from, to, inc, cmp) \
	for(auto idx=(from) ; idx cmp (to) ; inc idx)
#define ForLE(idx, from, to) \
	_For(idx, from, to, ++, <=)
#define ForGE(idx, from, to) \
	_For(idx, from, to, --, >=)
#define ForLT(idx, from, to) \
	_For(idx, from, to, ++, <)
#define ForGT(idx, from, to) \
	_For(idx, from, to, --, >)
#define For(idx, from, to) \
	_For(idx, from, to, ++, <)
#define Assert(expr) if(!(expr)) {__builtin_trap();}

void DisableIOSync() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios::sync_with_stdio(false);
}
struct Node {
	using Link = std::vector<std::pair<Node*, int>>;
	Link	link;
	uint64_t toKCost;
};

#include <unordered_set>
std::unordered_set<Node*> Used;
void CalcCost(Node* node, const uint64_t cost) {
	if(Used.count(node) != 0)
		return;
	Used.emplace(node);
	node->toKCost = cost;
	for(auto& nd : node->link) {
		CalcCost(nd.first, cost + nd.second);
	}
}
int main() {
	DisableIOSync();

	const int N = ToFixedIntArray(std::cin, 1)[0];
	std::vector<Node> node(N);
	For(i, 0, N-1) {
		const auto inp = ToFixedIntArray(std::cin, 3);
		const int i0 = inp[0]-1,
				i1 = inp[1]-1;
		const int cost = inp[2];
		node[i0].link.emplace_back(&node[i1], cost);
		node[i1].link.emplace_back(&node[i0], cost);
	}
	const auto qk = ToFixedIntArray(std::cin, 2);
	const auto Q = qk[0],
				K = qk[1]-1;

	CalcCost(&node[K], 0);
	For(i, 0, Q) {
		const auto query = ToFixedIntArray(std::cin, 2);
		std::cout << node[query[0]-1].toKCost + node[query[1]-1].toKCost << "\n";
	}
	std::cout.flush();
	return 0;
}


Measured memory_bytes: 18468
#include <bits/stdc++.h>
using namespace std;
int sum_of_dig(int x){
    int sum=0;
    while(x>0){
        sum+=x%10;
        x/=10;
    }
    return sum;
}
int main(){
    int n,a,b;
    cin >> n >> a >> b;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a<=sum_of_dig(i)&&sum_of_dig(i)<=b) ans+=i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  	string s,p;
  	cin>>s>>p;
  	if(s.size()+1!=p.size()) {cout<<"No"; return 0;}
  int j =0;
  	for(char i:s){
    	if(i!=p[j]) {cout<<"No"; return 0;}
      ++j;
    }
  	cout<<"Yes";
	return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
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; }
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;
ll const MOD = 1000000007;


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

vector<string> s(2),t(2);
cin >> s[0] >> s[1];

t[0] = s[1],t[1] = s[0];
reverse(all(t[0])),reverse(all(t[1]));

if(s[0] == t[0] && s[1] == t[1]) cout << "YES" << endl;
else cout << "NO" << endl;

return 0;
}

Measured memory_bytes: 256
N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

ans=0
for i in range(N):
    a=A[N-1-i]+ans 
    b=B[N-1-i]
    if a%b==0:
        continue
    else:
        c=a//b
        d=c+1
        e=b*d
        f=e-a
        ans+=f
print(ans)

Measured memory_bytes: 57048
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

	int X; cin >> X;

	cout << (X == 3 || X == 5 || X == 7 ? "YES" : "NO") << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
// #include <ctime>

using namespace std;

typedef long long ull;
const ull MOD = 1000000007;
const int MAX_N = 100000;
ull fact[MAX_N + 1];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ull ans;
//	clock_t wholetime = 0;
	// 都合上、0! = 0とする
	fact[0] = 0;
	fact[1] = 1;
	ull fs = 1;
	for (int i = 2; i < MAX_N + 1; i++){
		fs = (fs*i) % MOD;
		fact[i] = (fact[i-1] + fs) % MOD;
	}

	while (1){
		int N, R;
		cin >> N;
		if (N == 0) break;

		vector<int> word(N);
		for (int i = 0; i < N; i++) word[i] = i;
		word.push_back(0);
		ans = 0;
		cin >> R;

		vector<int> s(2*R+2, 0);
		s[2 * R + 1] = N;
		for (int i = 0; i < R; i++){
			cin >> s[i] >> s[i+R];
			s[i]--; s[i+R]--;

			s.push_back(s[i] + 1);
			s.push_back(s[i+R] + 1);

			// xor swap
			word[s[i]] ^= word[s[i+R]];
			word[s[i+R]] ^= word[s[i]];
			word[s[i]] ^= word[s[i+R]];
		}

//		clock_t st = clock();
		sort(s.begin(), s.end());
		s.erase(unique(s.begin(), s.end()), s.end());

		for (int i = 0, R = s.size() - 1; i < R; i++){

			ull tmp = fact[N - s[i] - 1] - fact[N - s[i+1] - 1];
			tmp = (tmp * word[s[i]]) % MOD;
			ans =(ans + tmp) % MOD;
//			cout << ans << ",";
			// 値を詰める
			int dif = s[i+1] - s[i];
			for (int j = i + 1; j < R; j++){
				word[s[j]] -= (word[s[j]] > word[s[i]] ? dif : 0);
			}
		}
//		clock_t ed = clock();
//		wholetime += (ed - st);
		cout << (ans + MOD) % MOD << endl;
	}

//	cout << (double)wholetime / CLOCKS_PER_SEC << endl;
	return 0;
}

Measured memory_bytes: 2792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();
		double S = r * r * Math.PI;
		double C = 2 * r * Math.PI;
		System.out.println(String.format("%.6f", S) 
					+ " " + String.format("%.6f", C));
		sc.close();

	}
}


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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A, B = [0]*N, [0]*N
for i in range(N):
    A[i], B[i] = MAP()

# 自分より前の添字に加算される値を保持しておく
added = 0
for i in range(N-1, -1, -1):
    # Biの倍数でなければ、必要な値を追加
    if (A[i]+added) % B[i] != 0:
        added += B[i] - (A[i]+added) % B[i]
print(added)


Measured memory_bytes: 13092
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int n;
    cin >> n;
    vector<int> alpha(26, 0);
    vector<string> S(n);
    rep(i, n) {
        cin >> S[i];
    }

    rep(i, S[0].size()) {
        alpha[S[0][i] - 'a']++;
    }

    repd(i, 1, n) {
        rep(j, 26) {
            if (alpha[j] == 0) continue;
            char ct = (char)('a' + j);
            int cnt = 0;
            rep(k, S[i].size()) {
                if (S[i][k] == ct) cnt++;
            }
            chmin(alpha[j], cnt);
        }
    }

    rep(i, 26) {
        rep(j, alpha[i]) {
            cout << (char)('a' + i);
        }
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
module mod_quick_sort
  implicit none
  integer, private, parameter :: intkind = 8
contains
  logical function less(a, b) result(res)
    integer(intkind), intent(in) :: a, b
    res = a >= b
  end
  subroutine swap(a, b)
    integer(intkind), intent(inout) :: a, b
    a = xor(a, b)
    b = xor(a, b)
    a = xor(a, b)
  end
  recursive subroutine quick_sort(a)
    integer(intkind), intent(inout) :: a(:)
    integer(intkind) :: p
    integer :: n, l, r, m
    n = size(a)
    l = 1
    r = n
    m = (n + 1) / 2
    p = a(l) + a(m) + a(r) - min(a(l), a(m), a(r)) - max(a(l), a(m), a(r))
    do
      do while (.not.less(p, a(l)))
        l = l + 1
      end do
      do while (.not.less(a(r), p))
        r = r - 1
      end do
      if (l >= r) exit
      call swap(a(l), a(r))
      l = l + 1
      r = r - 1
    end do
    if (1 < l - 1) call quick_sort(a(1:l - 1))
    if (r + 1 < n) call quick_sort(a(r + 1:n))
  end
end module mod_quick_sort
program change_a_little_bit
  use mod_quick_sort
  implicit none
  integer(8), parameter :: modu = 1000000007
  integer :: n, i
  integer(8) :: c(200000) = 0, x = 0
  read(*,*) n
  read(*,*) c(1:n)
  call quick_sort(c(1:n))
  do i = 1, n
    x = x + mod(c(i) * (i + 1), modu)
  end do
  x = mod(x, modu)
  write(*,'(i0)') mod(pow(4_8, n - 1) * x, modu)
contains
  pure elemental integer(8) function pow(a, n) result(res)
    integer(8), intent(in) :: a
    integer, intent(in) :: n
    integer(8) :: b
    integer :: m
    res = 1
    b = a
    m = n
    do while (m > 0)
      if (btest(m, 0)) res = mod(res * b, modu)
      b = mod(b * b, modu)
      m = rshift(m, 1)
    end do
  end
end program change_a_little_bit

Measured memory_bytes: 4640
open Printf
let input_int_array n =
	Array.init n (fun _ -> Scanf.scanf " %d" (fun v -> v))

let get_int () = Scanf.scanf " %d" (fun v -> v)
let get_2_ints () = Scanf.scanf " %d %d" (fun u v -> u,v)
let get_3_ints () = Scanf.scanf " %d %d %d" (fun u v w -> u,v,w)
let get_4_ints () = Scanf.scanf " %d %d %d %d" (fun u v w x -> u,v,w,x)
let get_5_ints () = Scanf.scanf " %d %d %d %d %d" (fun u v w x y -> u,v,w,x,y)

let () =
	let n = get_int ()
	in let a = 
		Array.init n (fun _ -> Scanf.scanf " %c" (fun v -> v))
	in let b = Array.make n 0
	in
	let f,i,e = ref true,ref 0,[|0,0;0,1;1,1;1,0|] in
	while !f && !i<4 do
		let e0,e1 = e.(!i) in
		b.(0) <- e0; b.(1) <- e1;
		for j=2 to n-1 do
			b.(j) <- match b.(j-1),a.(j-1) with
				| 0,'o' | 1,'x' -> b.(j-2)
				| 0,'x' | 1,'o' -> 1-b.(j-2)
				| _ -> failwith ""
		done;
		f := not (
			b.(0) = (
				match b.(n-1),a.(n-1) with
				| 0,'o' | 1,'x' -> b.(n-2)
				| 0,'x' | 1,'o' -> 1-b.(n-2)
				| _ -> failwith ""
			)
			&&
			b.(1) = match b.(0),a.(0) with
			| 0,'o' | 1,'x' -> b.(n-1)
			| 0,'x' | 1,'o' -> 1-b.(n-1)
			| _ -> failwith ""
		);
;		i := !i+1;
	done;
	if not !f then (
		Array.iter (fun v -> print_string @@ if v=0 then "S" else "W") b; print_newline ()
	) else printf "-1\n"

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

int main() {
	int n;
	cin >> n;
	set<int> a;
	rep(i, n) {
		int tmp;
		cin >> tmp;
		a.insert(tmp);
	}
	string ans = "NO";
	if(n == a.size()) ans = "YES";
	cout << ans << endl;
	return 0;
}

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

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

using namespace std;

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

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> inline T bis(T ok, T ng, function<bool(T)> f, T eps = 1) { while (abs(ok - ng) > eps) { T mi = (ok + ng) / 2; (f(mi) ? ok : ng) = mi; } return ok; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  i64 a, b, k;
  cin >> a >> b >> k;
  if (a >= k) {
    a -= k;
  } else {
    k = k - a;
    a = 0;
    b = max(0ll, b - k);
  }
  cout << a << " " << b << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            // 文字の入力 
            string s = Console.ReadLine();
            if(s.Length == 2)
            {
                Console.WriteLine(s);
            }
            else if(s.Length == 3)
            {
                string s1 = s.Substring(2,1);
                string s2 = s.Substring(1,1);
                string s3 = s.Substring(0,1);
                Debug.WriteLine(s1 + s2 + s3);
                Console.WriteLine(s1+s2+s3);
            }


            /*
            int a = int.Parse(Console.ReadLine());
            // スペース区切りの整数の入力
            string[] input = Console.ReadLine().Split(' ');
            int b = int.Parse(input[0]);
            int c = int.Parse(input[1]);
            // 文字列の入力
            string s = Console.ReadLine();
            //出力
            Console.WriteLine((a + b + c) + " " + s);
            */
        }
    }
}


Measured memory_bytes: 11092
K = int(input())


def ns(n):
    ret, tmp = 0, n

    while tmp > 0:
        #        tmp, r = divmod(tmp, 10)
        r = tmp % 10
        tmp //= 10
        ret += r

    return ret


ans, base = 0, 1
for _ in range(K):
    ans += base
    print(ans)

    if (ans + base) / ns(ans + base) > (ans + 10 * base) / ns(ans + 10 * base):
        base *= 10

Measured memory_bytes: 38512
n = int( input() )
h = list( map( int, input().split() ) )

dp = [0]*n
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    if dp[i-1]+abs(h[i]-h[i-1]) < dp[i-2]+abs(h[i]-h[i-2]):
        dp[i] = dp[i-1] + abs(h[i]-h[i-1])
    else:
        dp[i] = dp[i-2] + abs(h[i]-h[i-2])

print(dp[n-1])

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


int main() {
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i] >> B[i];
  }
  
  vector<ll> dp(N, 0);
  for (int i = N - 1; 0 <= i; --i) {
    ll div;
    if (i == N - 1) {
      div = (A[i] + (B[i] - 1)) / B[i];
      dp[i] = B[i] * div - A[i];
    } else {
      div = (A[i] + dp[i + 1] + (B[i] - 1)) / B[i];
      dp[i] = B[i] * div - A[i];
    }
  }
  cout << dp[0] << endl;
}

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

typedef long long ll;
int main()
{
    string N;
    cin >> N;
    for (int i = 0; i < 3; ++i)
    {
        if (N[i] == '7')
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <cmath>
using namespace std;
long long nr,n,mini,x,i,s[200005];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        s[i]=s[i-1]+x;
    }
    mini=s[n];
    for(i=1;i<n;i++)
    {
        nr = abs(s[n]-s[i]-s[i]);
        mini = min(mini, nr);
    }
    cout<<mini;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;

int n,k,ans=0;

int get_sum(int l,int r)
{
	return (((l+r)*(r-l+1))/2ll)%mod;
}

signed main()
{
	cin>>n>>k;
	for (int i=k;i<=n+1;i++)  ans=(ans+((get_sum(n-i+1,n)-get_sum(0,i-1)+1)%mod+mod)%mod)%mod;
	cout<<ans%mod<<endl;
	
	return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import java.math.*;

class Main{
	static int field[][];
	static BigInteger val[][];
	static int a,b;
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);

		while(true){
			b=s.nextInt();
			a=s.nextInt();
			if(a==0)System.exit(0);
			
			field=new int[a][b];
			val=new BigInteger[a][b];
			for(int i=0;i<a;i++){
				String line=s.next();
				for(int j=0;j<b;j++){
					if(line.charAt(j)>='A')field[i][j]=-1;
					else field[i][j]=(int)line.charAt(j)-'0';
					val[i][j]=new BigInteger("-1");
				}
			}
		
			BigInteger ans=new BigInteger("0");
			for(int i=0;i<a;i++)
				for(int j=0;j<b;j++){
					ans=ans.max(solve(i,j));
				}
			
			System.out.println(ans.toString());
		}
	}
	
	static BigInteger solve(int m,int n){
		BigInteger shita=new BigInteger("0");
		BigInteger migi=new BigInteger("0");
		
		if(!val[m][n].equals(new BigInteger("-1")))return val[m][n];
		if(field[m][n]==-1)return new BigInteger("-1");
		if(m>0&&field[m-1][n]!=-1)migi=solve(m-1,n);
		if(n>0&&field[m][n-1]!=-1)shita=solve(m,n-1);
		BigInteger ret=shita.max(migi).multiply(BigInteger.TEN).add(new BigInteger(String.valueOf(field[m][n])));
		if(ret.equals(BigInteger.ZERO))ret=new BigInteger(String.valueOf(field[m][n]));
		val[m][n]=ret;
		//System.out.println(ret.toString());
		return ret;
	}
}

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

int main(){
   int a,b,c,d,e,f,r = 0;
   cin >> a >> b;
   for(int i = a;i <= b;i++){
      c = i % 10,d = i / 10000 % 10;
      e = i /1000 % 10,f = i /10 % 10;
      if(c == d && e == f)r++;
   }
   cout << r << endl;
}

Measured memory_bytes: 256
module Main where

import           Control.Monad
import           Data.List
import           Data.List.Split
import           Data.Array.IO
import qualified Data.Vector.Unboxed           as V
import           Text.Printf

main :: IO ()
main = do
  [x, y, z, k] <- map read . words <$> getLine
  [as, bs, cs] <- replicateM 3 $ map read . words <$> getLine
  mapM_ print $ f as bs cs k

f as bs cs k =
  let ab = take k . sortBy (flip compare) $ [ a + b | a <- as, b <- bs ]
  in  take k . sortBy (flip compare) $ [ a + c | a <- ab, c <- cs ]


Measured memory_bytes: 419196
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll N;
ll arr[100005][5];
ll dp[100005][5];

ll rec(ll x, ll id) {
	if(x >= N) {
		return 0;
	}
	ll &ans = dp[x][id];
	if(ans != -1) {
		return ans;
	}
	for(int i = 0; i < 3; i++) {
		if(i != id) {
			ans = max(ans, arr[x][i] + rec(x + 1, i));
		}
	}
	return ans;
}

int main() {
	scanf("%lld", &N);
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 3; j++) {
			scanf("%lld", &arr[i][j]);
		}
	}
	ll maxVal = arr[0][0];
	ll maxInd = 0;
	ll tempInd = 1;
	for(int i = 0; i < 3; i++) {
		if(maxVal < arr[0][i]) {
			maxVal = arr[0][i];
			maxInd = i;
		}
		else {
			tempInd = i;
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << rec(0, tempInd);
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 15872
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

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

		int N = Integer.parseInt(sc.next());
		String stmp;
		int idx;
		HashMap<String, Long> sMap = new HashMap<String, Long>();

		Long num = 0L;
		String s;

		for (idx = 0; idx < N; idx++) {
			stmp = sc.next();
			char[] c1 = stmp.toCharArray();
			Arrays.sort(c1);
			s = String.valueOf(c1);

			num = sMap.get(s);
			if (num == null) {
				sMap.put(s, 1L);
			} else {
				sMap.put(s, num + 1);
			}
		}

		long match = 0;
		ArrayList<Long> numList = new ArrayList<>(sMap.values());
		for (Long nums : numList) {
			if (nums > 1) {
				match += (nums * (nums-1L)) / 2L;
			}
		}

		System.out.println(match);

	}

}


Measured memory_bytes: 54600
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
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; }


int main(){ 
    int a, b; cin >> a >> b;
    if(a > 8 || b > 8) cout << ":(" << ln;
    else cout << "Yay!" << ln;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
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 main() {
    int N;
    cin >> N;
    ll ans = 0;

    for (int i = 1; i < N + 1; i++) {
        if (i % 3 != 0 && i % 5 != 0) ans += i;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3636
//atcode abc135_c
#include <iostream>
using namespace std;
int main(){
	int n,b[100002],a[100002];
	cin>>n;
	for(int i=0;i<=n;++i) cin>>a[i];
	for(int i=0;i<n;++i) cin>>b[i];
	
	int kills,nokills=a[0];
	long long sKills=0;
	//杀怪数，前英雄留下的怪物数，总杀怪数 
	for(int i=0;i<n;++i){
		if(nokills+a[i+1]<=b[i]){// 英雄很牛
		//前英雄留下的怪物数+当前城市怪物数 不够杀 
		 	kills=nokills+a[i+1];
			nokills=0;
		}else{
			kills=b[i];
			if(nokills>b[i])//英雄太弱
			 //前英雄留下的怪物数都杀不完；
			 //只能将当前城市怪物留给下个英雄 
				nokills=a[i+1];
			else
				nokills=nokills+a[i+1]-b[i];
		}
		sKills+=kills;	
	}
	cout<< sKills;
	return 0;
}
  

Measured memory_bytes: 1024
#include<stdio.h>

int main()

{

int W,H,x,y,r;

scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

if(W<r+x || H<r+y || y-r<0 || x-r<0)

{

printf("No\n");

}

else

{
printf("Yes\n");
}

return 0;

}

Measured memory_bytes: 1012
#include <bits/stdc++.h>
        using namespace std;
         
        int main(){
          int N;
          cin >> N;
          
          string s;
         
          
          for(int i = 0; i < N; i++){
            cin >> s;
            if(s == "Y"){
              cout << "Four" << endl;
              return 0;
            }
          }
          cout << "Three" << endl;
        }

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int N;
double V[55];
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	scanf("%lf",&V[i]);
	sort(V+1,V+N+1);
	for(int i=2;i<=N;i++)
	V[i]=(V[i-1]+V[i])/2.0;
	printf("%lf",V[N]);
	return 0;
} 

Measured memory_bytes: 128
#set
h,w = gets.chomp.split(" ").map(&:to_i)
line = Array.new(h)
squares = Array.new(h) {Array.new(w, 0)}
answer = "Yes"

(0 .. h - 1).each do |i|
    line[i] = gets.chomp
    (0 .. w - 1).each do |j|
        squares[i][j] = line[i].split("")[j]
    end
end

#main
(0 .. h - 1).each do |i|
    (0 .. w - 1).each do |j|
        # p squares[i][j]
        if squares[i][j] == "#" then
            chk_flag = 0
            (i - 1 .. i + 1).each do |x|
                (j - 1 .. j + 1).each do |y|
                    if ( x == i || y == j ) && ( x >= 0 && x < h ) && ( y >= 0 && y < w ) then
                        if x == i && y == j then
                            next
                        else
                            if squares[x][y] == "#" then
                                chk_flag += 1
                            end
                        end
                    end
                end
            end
            
            if chk_flag == 0 then
                answer = "No"
                print ("#{answer}\n")
                exit
            end
        end
    end
end

print ("#{answer}\n")

Measured memory_bytes: 2428
L,R = map(int,input().split())

# L <= i,j <== R の中で、i*j mod 2019の最小値を求めよ

# L,R は 0 ~ 2*10^9

# (i*j) mod 2019 = (i mod 2019) * (j mod 2019) %2019

# =============================================================================
# for i in range(2019):
#     for j in range(i,2019):
#         a = (i*j) % 2019
#         b = (i % 2019)*(j % 2019) % 2019
#         if a != b:
#             print(i,a,b)
# =============================================================================

# 全探索: 2019*2019が最大

dist = (R - L)
if dist >= 2019:
    print("0")
else:
    ans = 999999
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = min(ans,(i*j) % 2019)
    print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<climits>
#include<cmath>
#include<stdio.h>
using namespace std;

int ar[10002];

int main(){
    int n;
    while(cin>>n,n){;
        for(int i=0;i<n;i++){
            cin>>ar[i];
        }
        int ans=INT_MAX;
        for(int i=0;i<n;i++){
            int cur=ar[i];
            for(int j=1;j<=3;j++){
                ar[i]=j;
                int l=i,r=i;
                while(1){
                    int dl=0;
                    int dr=0;
                    while(l-dl>0&&ar[l-dl-1]==ar[r]){
                        dl++;
                    }
                    while(r+dr<n-1&&ar[r+dr+1]==ar[l]){
                        dr++;
                    }
                    if(l>=0&&r<=n-1&&dl+dr+1+(l!=r)>3){
                        l-=dl+1;r+=dr+1;
                    } else {
                        break;
                    }
                }
                ans=min(l+1+n-r,ans);
            }
            ar[i]=cur;
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define fWrite          freopen ("out.txt","w",stdout);
#define TC              int t;cin >> t;FOR(tc,1,t)
#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

int main()
{
    Fast
    LL a,b;
  cin >> a >> b;
  cout << a*b;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(ll i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
#define INF 1000000000000000LL
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

signed main(){
	IO_STREAM;
	int N,K;
	cin>>N>>K;
	vi A(N);
	rep(i,0,N){
		cin>>A[i];
	}
	rep(cnt,0,K){
		vi B(N+1);
		rep(i,0,N){
			int st,ed;
			st=max((int)(i-A[i]),0);
			ed=min((int)(i+A[i]+1),N);
			B[st]++;
			B[ed]--;
		}
		rep(i,0,N){
			B[i+1]+=B[i];
		}
		if(A==B) break;
		A=B;
		B[N]=0;
	}
	rep(i,0,N){
		cout<<A[i]<<' ';
	}
	return 0;
}


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

int main() {
    int n,m,pt[100]={INT_MIN},sid=0;
    string s[100], tmp;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>tmp;
        for(int j=0;j<sid;j++){
            if(s[j] == tmp){
                pt[j]++;
                goto L_break1;
            }
        }
        s[sid]=tmp;
        pt[sid++]=1;
L_break1:;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>tmp;
        for(int j=0;j<sid;j++){
            if(s[j] == tmp){
                pt[j]--;
                break;
            }
        }
    }
    sort(&pt[0], &pt[sid+1]);
    cout<< max(pt[sid],0) <<"\n";
}

Measured memory_bytes: 256
#include<iostream>

int main(){
  int N;
  std::cin >> N;
  
  int A[100];
  for(int i=0;i<N;++i){
    std::cin >> A[i];
  }
  
  int not_sort = 1,change=0;
  while(not_sort){
    not_sort = 0;
    for(int i=0;i<N-1;++i){
      if(A[i]>A[i+1]){
        int tmp;
        tmp = A[i];
        A[i] = A[i+1];
        A[i+1] =tmp;
        not_sort = 1;
        change++;
      }
    }
    
  }
  
  for(int i=0;i<N;++i){
    std::cout << A[i];
    if(i!=N-1){
      std::cout << " ";
    }else{
      std::cout << std::endl;
    }
    
  }
  
  std::cout << change << std::endl;
  
  return 0;
}

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

int main(){
    int m,f,b;
    cin >> m >> f >> b;
    if(m>=b)
     cout << 0 << endl;
    else if(m+f<b)
     cout << "NA" <<endl;
    else 
     cout << b-m << endl;
     return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
ll dp[2020];
void solve(){
	int n; 
	cin>>n; 
	dp[0] = 1;
	for(int i=3;i<=n;i++){
		for(int j=0;j<=i-3;j++){
			dp[i]+=dp[j];
			dp[i]%=mod;
		}
	}
	cout<<dp[n]<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3604
n=int(input())
pt=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    pt[a-1].append(b-1)
    pt[b-1].append(a-1)

def dfs(v):
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d

ans=0
for i,j in zip(dfs(0),dfs(n-1)):
    if i<=j:ans+=1
if ans<=n/2:print('Snuke')
else:print('Fennec')

Measured memory_bytes: 28980
f = lambda x, y: len(str(max(x, y)))

if __name__ == '__main__':
    n = int(input())
    a = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            a.append((i, n // i))
            if i != n // i:
                a.append((n//i, n // (n // i)))
    k = [f(e[0], e[1]) for e in a]
    print(min(set(k)))

Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;

//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

using namespace std;
int main(void){

    ll n;
    cin >> n;
    ll a[n];
    REP(i,n){
      cin >> a[i];
    }
    int next = 1;
    int count = 0;
    REP(i,n){
      next = a[next-1];
      count++;
      if( next == 2){
        cout << count << endl;
        return 0;
      }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 4408
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    int n, t; cin >> n >> t;
    vector<int> v(n);
    rep(i,n) cin >> v[i];
    ll ans = 0;
    for(int i = 1; i < n; i++){
        if(v[i-1]+t>v[i]){
            ans += v[i]-v[i-1];
        }else ans += t;
    }
    ans += t;
    cout << ans << endl;

    return 0;
}

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

int main()
{
	string S;
	cin >> S;
	int OK = 1;

	if (S.length() == 0 || S[0] != 'A') OK = 0;
	

	int Cfukumu = 0;
	int Cichi = 0;
	for (int i = 2; i < S.length() - 1; i++) {
		if (S[i] == 'C') {
			Cfukumu++;
			Cichi = i;
		}
	}
	if (Cfukumu != 1) OK = 0;


	repeat(i, S.length()) {
		if (i != 0 && i != Cichi && toupper(S[i]) == S[i]) OK = 0;
	}


	if (OK == 1) cout << "AC" << endl;
	else cout << "WA" << endl;


	return 0;
}

Measured memory_bytes: 256