akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define int long long
#define endre getchar();getchar();return 0
#define INF 1000000007
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return (y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int n) {
	if (n == 0)return 1;
	return (kai(n - 1)*n) % INF;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int mystoi(string s) {
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		cnt += (int)(s[i] - '0') * pow(10, s.size() - i - 1);
	}
	return cnt;
}
vector<int>vec;
void solve(int n) {
	for (int i = 2; i <= n; i++) {
		int nn = n, cnt = 0;
		if (!prime(i))continue;
		while (nn / i) {
			cnt += nn / i;
			nn /= i;
		}
		vec.push_back(cnt);
	}
}
signed main() {
	int n, cnt = 1;
	cin >> n;
	solve(n);
	for (int i = 0; i < vec.size(); i++) {
		cnt *= vec[i] + 1;
		cnt %= INF;
	}
	cout << cnt << endl;
	endre;
}


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

int main() {
    int N, P;
    cin >> N >> P;

    ll dp[60][2] = {0};

    dp[0][0] = 1;

    rep(i, N) {
        ll a;
        cin >> a;
        if (a % 2 == 0)
            dp[i + 1][0] = dp[i][0] * 2, dp[i + 1][1] = dp[i][1] * 2;
        else
            dp[i + 1][0] = dp[i][0] + dp[i][1],
                   dp[i + 1][1] = dp[i][0] + dp[i][1];
    }

    cout << dp[N][P] << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  string s;
  cin>>s;
  char c = s[0];
  if(c=='A')puts("T");
  if(c=='T')puts("A");
  if(c=='C')puts("G");
  if(c=='G')puts("C");
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  int n;
  cin >> n;

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

  int dp[n + 10] = {};
  for (int i = 0; i < n + 10; i++) {
    dp[i] = INF;
  }
  dp[0] = 0;

  for (int i = 0; i < n; i++) {
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
    dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
  }

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

  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000001

int parent_key(int);
int left_key(int);
int right_key(int);

int *A;
int n;

int main(){
        int i, p, l, r;

        scanf("%d", &n);

        A = malloc(n * sizeof(int) + 1);

        for(i = 1 ; i <= n ; i++){
                scanf("%d", &A[i]);
        }

        for(i = 1 ; i <= n ; i++){
                printf("node %d: key = %d, ", i, A[i]);
                p = parent_key(i);
                if(p != INF)printf("parent key = %d, ", p);
                l = left_key(i);
                if(l != INF)printf("left key = %d, ", l);
                r = right_key(i);
                if(r != INF)printf("right key = %d, ", r);
                printf("\n");
        }

        return 0;
}

int parent_key(int i){
        if(i/2 < 1 || n < i/2)return INF;
        return A[i / 2];
}

int left_key(int i){
        if(n < i*2)return INF;
        return A[2 * i];
}

int right_key(int i){
        if(n < (i*2+1))return INF;
        return A[2 * i + 1];
}



Measured memory_bytes: 2112
#include<iostream>
#include<vector>
#include<string>
#include<tuple>
#include<algorithm>
#include<iomanip>
#include<math.h>
#include<stdio.h>

using namespace std;

int main(){
    double D, N;

    cin >> D >> N;
    double ans = 0;
    if(N == 100)
    {
        ans = pow(100, D)*(N+1);
    }
    else
    {
        ans = pow(100, D)*N;
    }

    printf("%.0f",ans); 
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
  Scanner sc;

  void run() {
    for ( ;; ) {
      int n, m, a;
      n = ni();
      m = ni();
      a = ni();
      if ( n == 0 ) {
        break;
      }

      boolean link[][][] = new boolean[1001][n + 1][n + 1];
      for ( int i = 0; i < m; ++i ) {
        int h, p, q;
        h = ni();
        p = ni();
        q = ni();
        link[ h ][ p ][ q ] = link[ h ][ q ][ p ] = true;
      }

      for ( int i = 1000; 1 <= i; --i ) {
        for ( int j = 1; j <= n; ++j ) {
          if ( !link[ i ][ a ][ j ] )
            continue;
          a = j;
          break;
        }
      }

      System.out.println( a );
    }
  }

  Main() {
    sc = new Scanner( System.in );
  }

  int ni() {
    return sc.nextInt();
  }

  public static void main(String[] args) {
    new Main().run();
  }

  void debug(Object... os) {
    System.err.println( Arrays.deepToString( os ) );
  }

}

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

using namespace std;
int main() {
	int n,sum=0,max=0;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) 
	{
		cin >> h[i];
		if (max <= h[i])
		{
			sum++;
			max = h[i];
		}
	}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
def order_ascend(a, b):
    if  a > b:
        a, b = b, a
    return a, b

if __name__ == "__main__":
    while True:
        a, b =  map(int, input().split())
        if a == b == 0:
            break
        a, b = order_ascend(a, b)
        
        print(f"{a} {b}")
    





Measured memory_bytes: 5624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x)  if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
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;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
pll a[maxn];
int n;
ll d;
int main()
{
#if DEBUG_Switch
    freopen("C:\\code\\input.txt", "r", stdin);
#endif
    //freopen("C:\\code\\output.txt","w",stdout);
    n = readint();
    d = readint();
    repd(i, 1, n)
    {
        a[i].fi = readint();
        a[i].se = readint();
    }
    int cnt = 0;
    repd(i, 1, n)
    {
        if (a[i].fi * a[i].fi + a[i].se * a[i].se <= d * d)
        {
            cnt++;
        }
    }
    printf("%d\n", cnt );
    return 0;
}




Measured memory_bytes: 6884
import copy
from collections import deque
n,m = map(int,input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
joint = [[]for _ in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
    joint[a[i]].append(b[i])
    joint[b[i]].append(a[i])

ans = 0
jointdef = copy.deepcopy(joint)
for i in range(m):
    joint = copy.deepcopy(jointdef)
    joint[a[i]].remove(b[i])
    joint[b[i]].remove(a[i])
    
    looked = [1 for _ in range(n)]
    looked[0] = 0
    queue = deque([0])
    while(queue):
        now = queue.popleft()
        for i in joint[now]:
            if looked[i]:
                queue.append(i)
                looked[i] = 0
    if sum(looked) != 0:
        ans += 1
print(ans)

Measured memory_bytes: 9544
# ＤＦＳ, パターン列挙_各竹の使用パターンを列挙

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]

stack = [[0],[1],[2],[-1]] # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        stack += [w, x, y, z]  # 積む

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)


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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define bb begin()
#define ee end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);
#define eps 1e-9



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;

int power(int a,int b){
    int r=1;
    while(b){
        if(b & 1){
            r=r*a;
            b--;
        }
        a=a*a;
        b>>=1;
    }
    return r;
}

int arr[g_size];



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

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	string s1,s2;

	char s[100000];

	int ara[n_size],ara2[n_size];

	vi v;

	v.pb(1);

	for(i=1;;i++){
        k=power(6,i);
        if(k>100000) break;
        v.pb(k);
	}

	for(i=1;;i++){
        k=power(9,i);
        if(k>100000) break;
        v.pb(k);
	}

	sort(v.bb,v.ee);

//	f(i,0,v.size()-1) cout<<v[i]<<" ";
//	cout<<endl;

	cin>>n;
	k=n;
//    for(i=v.size()-1;i>=0;i--){
//        k=n;
//        count=0;
//        if(k<v[i]) continue;
//        else{
//            j=i;
//            while(k){
//                if(k<v[j]){
//                    j--;
//                    continue;
//                }
//                m=k%v[j];
//                count+=k/v[j];
//                k=m;
//                j--;
//            }
//            mini=min(mini,count);
//            cout<<mini<<endl;
//        }
//    }
    int dp[n_size];
	f(i,1,n){
        dp[i]=mx;
        for(auto x:v){
            if(i-x>=0)dp[i]=min(dp[i],dp[i-x]+1);
        }
	}
	cout<<dp[k]<<endl;

	//cout<<mini<<endl;

}


Measured memory_bytes: 3976
#include<bits/stdc++.h>
#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 MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 1000005
#define M 1000005
#define INF 10000000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-7
using namespace std;
int a[N];
int b[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    while(cin>>n>>m)
    {
        MST(a,0);
        a[1] = 1;
        FOR(i,1,n)b[i] = 1;
        FOR(i,1,m)
        {
            int x,y;
            cin>>x>>y;
            if(a[x])a[y] = 1;
            b[x]--;
            b[y]++;
            if(b[x] == 0)a[x] = 0;
        }
        int ans = 0;
        FOR(i,1,n)if(a[i])ans++;
        cout<<ans<<endl;
    }
    return 0;
}


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

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> C(H);
  for(int i = 0; i < H; ++i) cin >> C[i];
  vector<string> A = C, B = C;
  for(int i = 0; i < H; ++i){
    A[i][0] = '#';
    B[i][W-1] = '#';
  }
  for(int i = 0; i < H; ++i){
    for(int j = 1; j < W; ++j){
      if(i%2) A[i][j-1] = '#';
      else B[i][j] = '#';
    }
  }
  for(int i = 0; i < H; ++i) cout << A[i] << endl;
  cout << endl;
  for(int i = 0; i < H; ++i) cout << B[i] << endl;
  return 0;
}


Measured memory_bytes: 1536
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define zahyoutype double
typedef struct Point{zahyoutype x,y;}P;
typedef struct line{P p1,p2;}L;

P crosspoint(L s,L t){
	zahyoutype x=1;if(x/2==0){puts("type error");exit(0);}
	double deno=(s.p1.x-s.p2.x)*(t.p1.y-t.p2.y)-(t.p1.x-t.p2.x)*(s.p1.y-s.p2.y);
	zahyoutype xnume=  s.p1.x*t.p1.x*(s.p2.y-t.p2.y)-s.p1.x*t.p2.x*(s.p2.y-t.p1.y)-s.p2.x*t.p1.x*(s.p1.y-t.p2.y)+s.p2.x*t.p2.x*(s.p1.y-t.p1.y);
	zahyoutype ynume=-(s.p1.y*t.p1.y*(s.p2.x-t.p2.x)-s.p1.y*t.p2.y*(s.p2.x-t.p1.x)-s.p2.y*t.p1.y*(s.p1.x-t.p2.x)+s.p2.y*t.p2.y*(s.p1.x-t.p1.x));
	P p={xnume/deno,ynume/deno};
	return p;
}
double seglen(L s){return hypot(s.p2.x-s.p1.x,s.p2.y-s.p1.y);}
double distPP(P p,P q){return hypot(p.x-q.x,p.y-q.y);}

void readpoint(P*p){zahyoutype x=1;scanf(x/2?"%lf%lf":"%ld%ld",&p->x,&p->y);}
void printpoint(P p){zahyoutype x=1;printf(x/2?"%.f %.f\n":"%ld %ld\n",p.x,p.y);}

int main(){
	P p1;
	int r1;
	readpoint(&p1);
	scanf("%d",&r1);
	P p2;
	int r2;
	readpoint(&p2);
	scanf("%d",&r2);
	double dist=distPP(p1,p2);
	double theta=acos((r1*r1+dist*dist-r2*r2)/2/r1/dist);
	double arg=atan2(p2.y-p1.y,p2.x-p1.x);
	double x1,y1,x2,y2;
	x1=p1.x+r1*cos(arg+theta);
	y1=p1.y+r1*sin(arg+theta);
	x2=p1.x+r1*cos(arg-theta);
	y2=p1.y+r1*sin(arg-theta);
	if(x2<x1||(x2==x1&&y2<y1)){
		double t=x1;x1=x2;x2=t;
		t=y1;y1=y2;y2=t;
	}
	printf("%.9f %.9f %.9f %.9f\n",x1,y1,x2,y2);
}


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

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

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

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

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

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

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

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

#[allow(dead_code)]
fn practice_1() {
    input! {
    n: i32,
    m: [i32; 2],
    s: chars,
    }
    let s: Vec<char> = s;
    let s: String = s.into_iter().collect();

    println!("{} {}", n + m[0] + m[1], s);
}

#[allow(dead_code)]
fn abc086_a() {
    input! {
    n: [i32; 2],
    }
    let prod: i32 = n[0] * n[1];
    let res = if prod % 2 == 0 {
        "Even"
    } else {
        "Odd"
    };
    println!("{}", res)
}

#[allow(dead_code)]
fn abc081_a() {
    input! {
    s: chars,
    }
    let s: Vec<char> = s;
    let res: u32 = s.into_iter().map(|n| {
        n.to_digit(10).unwrap()
    }).sum();

    println!("{}", res)
}

#[allow(dead_code)]
fn abc081_b() {
    input! {
    n: i32,
    arr: [i32; n],
    }
    let mut arr: Vec<i32> = arr;
    let mut cnt = 0;

    loop {
        let is_end: bool = arr.to_vec().into_iter().any(|v| (v % 2) == 1);
        if is_end { break; }
        arr = arr.to_vec().into_iter()
            .map(|v| v / 2)
            .collect();
        cnt = cnt + 1;
    }

    println!("{}", cnt)
}


fn main() {
    abc081_b()
}



Measured memory_bytes: 4352
#include <cstdio>
typedef long long ll;

int n,C,A[405],B[405];
int f[405][405],p[405][405],sp[405][405];
const int P=1000000007;

int main()
{
    scanf("%d%d",&n,&C),f[0][0]=1;
    for(int i=1;i<=n;++i)scanf("%d",&A[i]);
    for(int i=1;i<=n;++i)scanf("%d",&B[i]);
    for(int i=1;i<=400;++i)
        for(int j=p[i][0]=1;j<=400;++j)
            p[i][j]=(ll)p[i][j-1]*i%P;
    for(int i=1;i<=400;++i)
        for(int j=0;j<=400;++j)
            sp[i][j]=(p[i][j]+sp[i-1][j])%P;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=C;++j)
            for(int k=0;k<=j;++k)
                f[i][j]=(f[i][j]+(ll)f[i-1][j-k]*(sp[B[i]][k]-sp[A[i]-1][k]+P))%P;
    printf("%d\n",f[n][C]);
    return 0;
}

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

int main(void){

	int c, a, n, Q;

	cin >> Q;
	for(int i=0;i<Q;i++){
		int sum = 0;
		cin >> c >> a >> n;
		while(c >= 1 && a >=1 && n >= 1){sum = sum + 1;c = c - 1;a = a - 1;n = n - 1;}
		while(c >= 2 && a >= 1){sum = sum + 1; c = c - 2;a = a - 1;}
		while(c >= 3){sum = sum + 1;c = c - 3;}
		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 1164
#!/bin/env python3

N = int(input())

#t_prev = x_prev = y_prev = 0
for i in range(N):
    t_i, x_i, y_i = map(int, input().split())

    if (x_i+y_i)> t_i:
        print("No")
        exit()
    elif (x_i+y_i) %2 != t_i%2 :
        print("No")
        exit()
    #elif (abs(x_i - x_prev) + abs(y_i - y_prev)) > (t_i - t_prev):
    #    print("No")
    #    exit()

print("Yes")


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int ans = 700;
char ch[3];

int main() {
  scanf("%s", ch);
  if(ch[0] == 'o') ans += 100;
  if(ch[1] == 'o') ans += 100;
  if(ch[2] == 'o') ans += 100;
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
N, x = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
m = 0
ans = 0
flag = True
for i in range(N):
  x -= A[i]
  ans += 1
  if x == 0:
    print(ans)
    flag = False
    break
  elif x < 0:
    print(ans-1)
    flag = False
    break
if flag:
  print(ans-1)

Measured memory_bytes: 3064
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <iostream> 
#include <iomanip>  
#include <string>
#include <sstream>  
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <cstring>
#include <cmath>
#include <cassert>


#define INF              (int)1000000007
#define EPS              1e-9
#define pb               push_back
#define mp               make_pair
#define all(c)           c.begin(), c.end()
#define forall(i,a,b)    for(int i=a;i<(b);++i)
#define trav(a,x)        for(auto & a: x)
#define in(a,b)          ((b).find(a) != (b).end())
#define sz(c)            (int)(c).size()
#define input(a)         for(auto & x : a) cin >> x;

using namespace std;

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

#ifdef DEBUG
#define trace(...)       __f(#__VA_ARGS__, __VA_ARGS__)
#define debug(args...)   {dbg,args; clog<<endl;}
#define print_( a )      for( auto & x : a ) clog << x << ' '; clog << '\n';
#define printPair_( a )  for( auto & x : a ) clog << '(' << x.first << ',' << x.second << ')' << ' '; clog << '\n';
#else
#define trace(...)       
#define debug(args...)            
#define print_( a )               
#define printPair_( a )           
#endif

struct debugger {
  template<typename T> debugger& operator , (const T& x) {    
    clog << x << " ";    return *this;    
  }
}dbg;

template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " | ";
    __f(comma + 1, args...);
}

auto ____ =[]() { std::ios::sync_with_stdio(0); cin.tie(0); return nullptr; }();

int main( int argc, char * argv[] ){
  string str; cin >> str;
  bool flag = true;
  forall(i,0,sz(str)){
    if( i%2 == 0 and str[i] != 'L' ) continue;
    if( i%2 == 1 and str[i] != 'R' ) continue;
    flag = false;
    break;
  }
  if( flag ){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }
  return 0;
}


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

//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx,avx2")

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define dbg(x) cerr<<#x<<" : "<<x<<endl

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
const ll INF = 1e18+1;
const ll MOD = 1000000007L;
clock_t time_p=clock();
void timer(){time_p=clock()-time_p;cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";}

template <typename Arg1> ostream& operator << (ostream& out, const vector<Arg1> &a) {out<<"[ ";for(const auto &x:a)out<<x<<" ";return out<<"]";}


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

    double n;
    cin>>n;
    ll count =0 ;
    for(int i=1; i<=n; i++){
        if(i&1){
            count++;
        }
    }
    cout<<count/n<<endl;
    timer();
    return 0;
}


Measured memory_bytes: 256
// AOJ 2708: ABC Gene
// 2017.11.26 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

char s[2][5002];
int f['C'+1];

int main()
{
	int n, i, k1, k2, n2;
	char x, *p, *q;

	fgets(p=s[0], 5002, stdin);
	while (*p > ' ') f[*p++]++;
	n = p - s[0];

	for (i = 'A'; i <= 'C'; i++) if (!f[i]) break;
	if (i <= 'C') goto no;
	for (k1 = 0, k2 = 1; n > 3; k1 = k2, k2 = !k2) {
		p = s[k1], q = s[k1]+n-3;
		if      (*p == 'A' && *(p+1) == 'B' && *(p+2) == 'C') x = 'A';
		else if (*q == 'A' && *(q+1) == 'B' && *(q+2) == 'C') x = 'C';
		else x = 'B';

		q = s[k2]; while (*p > ' ') {
			if (*p == 'A' && *(p+1) == 'B' && *(p+2) == 'C') *q++ = x, p+=3;
			else *q++ = *p++;
		}
		*q = 0;
		n2 = q-s[k2];
//printf("n %d -- %s\n", n2, s[k2]);
		if (n - n2 < 2) goto no;
		n = n2;

		p = s[k2], q = s[k1]; while (*p > ' ') {
			if (*p == x) {
				if (*q != 'A' || *(q+1) != 'B' || *(q+2) != 'C') goto no;
				q += 2;
			} else if (*q != *p) goto no;
			p++, q++;
		}
	}

	if (n == 3) {
		for (i = 0; i < 3; i++) if (s[k1][i] != i+'A') break;
		if (i == 3) { puts("Yes"); return 0; }
	}
no: puts("No");
	return 0;
}

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

#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  double l;
  cin >> l;

  double x = l/3;
  printf("%.6f\n", x*x*x);
  return 0;
}


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

using namespace std;
using ll = long long;

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

    ll T = 0, w = 0;
    for (ll i = 0; i < S.size(); ++i) {
        if (S[i] == 'W') {
            T += i;
            ++w;
        }
    }

    ll sum = w * (w - 1) / 2;
    // 最終状態におけるT

    cout << T - sum << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
  int n; cin >> n;
  static double x[100], a[100], y;
  int i;

  for( i = 0; i < n; i++ ) cin >> x[i];
  for( i = 0; i < n; i++ ) cin >> y, a[ i ] = abs( x[i] - y );

  static double p1, p2, p3, p4;
  for( i = 0; i < n; i++ ) {
    p1 += a[ i ];
    p2 += a[ i ] * a[ i ];
    p3 += a[ i ] * a[ i ] * a[ i ];
    p4  = p4 < a[ i ]?a[ i ] : p4;
  }
  p2 = sqrt( p2 );
  p3 = cbrt( p3 );
  cout  << fixed << p1 << endl << p2 << endl << p3 << endl << p4 << endl;
  return 0;
}

Measured memory_bytes: 3464
/*
	Name: Harshit Jain
	Institution: IIIT Vadodara
*/
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <list>
#include <stack>
#include <cstring>
#include <map>
#include <queue>
#include <ctime>
#include <iomanip>
#include <set>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <climits>

#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define pb push_back
#define mp make_pair
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ull unsigned long long
#define rep(i,a,b) for(ll i = a; i < b; ++i)
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(typeofa((c).begin() i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end()) 
#define p(a) cout << a << "\n";
#define p1(a) cout << a << " ";

#define PI 3.141592653589793
#define MOD (ll)(1e9 + 7)
#define m(a) ((a)%MOD)

using namespace std;
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
//=======================

void solve()
{
	set<int> s;
	int n;
	cin >> n;
	rep(i,0,n)
	{
		int a;
		cin >> a;
		s.insert(a);
	}
	int si = s.size();
	p(si)
}

//=======================
int main()
{
	bool testing = false;
	IOS
	if(testing)
	{
		freopen("test.txt","rt",stdin);
		int start = clock();
		solve();
		int end = clock();
		cout << "time: " << (end - start)/(double)(CLOCKS_PER_SEC)*1000 << " milliseconds\n";
	}
	else
	{
		solve();
	}
} 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;

ll euclid(ll a, ll b){
  while (b>1){
    a = a % b;
    swap(a,b);
  }
  return a;
}

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

  ll H, W, N;
  cin >> H >> W >> N;
  vector<P> ab(N);
  vector<ll> ans(10, 0);

  REP(i, N) {
    ll a, b;
    cin >> a >> b;
    ab[i] = P(a-1, b-1);
  }

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

  for (P p : ab){
    ll y = p.first;
    ll x = p.second;
    REP3(sy, max((ll)0,y-2), min(y+1,H-2)){
      REP3(sx, max((ll)0,x-2), min(x+1,W-2)){
        ll cnt=0;
        REP3(i,sy,sy+3){
          REP3(j,sx,sx+3){
            if (*lower_bound(ab.begin(), ab.end(), P(i,j)) == P(i,j)){
              cnt++;
            }
          }
        }
        if (cnt>0){
          ans[cnt]++;
        }
      }
    }
  }

  REP3(i,1,10){ ans[i] /= i; }
  ans[0] = (H-2)*(W-2) - accumulate(ans.begin(), ans.end(), 0);
  REP(i,10){ cout << ans[i] << "\n"; }
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <limits.h>
 
#define MAX 200000
#define INF INT_MAX
typedef long long ll;
ll ans; 
int n;
int a[MAX];
 
void merge(int *a, int left, int mid, int right){
  int n1 = mid - left, n2 = right - mid;
  int L[n1+1], R[n2+1], i, j, k;
  
  for(i = 0 ; i < n1 ; i++){
    L[i] = a[left + i];
  }
  
  for(i = 0 ; i < n2 ; i++){
    R[i] = a[mid + i];
  }
  
  L[n1] = R[n2] = INF;
  
  for(i = 0, j = 0, k = left ; k < right ; k++){
    if(i < n1 && (j == n2 || L[i] <= R[j])){
      a[k] = L[i++];
    }else{
      ans += (n1 + n2) / 2 - i;
      a[k] = R[j++];
    }
  }
}
  
void mergesort(int *a, int left, int right){
  int mid;
  
  if(left + 1 < right){
    mid = (left + right) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid, right);
    merge(a, left, mid, right);
  }
}

int main(){
  int i;
 
  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,a + i);
  }
  mergesort(a,0,n);
  printf("%lld\n" ,ans);
 
  return 0;
}

Measured memory_bytes: 2156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    string s;
    int x, y;
    cin >> s >> x >> y;
    int sl = s.length();
    int fcnt = 0, tcnt = 0, ftmp = 0;
    vector<int> f;
    set<pair<int, int>> pos;
    set<int> xpos, ypos;
    bool xfind = false, yfind = false, ans = false;
    rep(i, sl) {
        if (s[i] == 'F') {
            fcnt++;
            ftmp++;
            if (i == (sl - 1)) f.push_back(ftmp);
        }
        else if (s[i] == 'T') {
            tcnt++;
            f.push_back(ftmp);
            ftmp = 0;
        }
    }
    if (sz(f) == 1) {
        if ((x == f[0]) && (y == 0)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    rep(i, (sz(f) + 1) / 2) {
        if (xpos.empty()) {
            xpos.emplace(f[i * 2]);
            continue;
        }
        set<int> add;
        for(auto p : xpos) {
            add.emplace(p + f[i * 2]);
            add.emplace(p - f[i * 2]);
        }
        xpos.clear();
        for(auto p : add) xpos.emplace(p);
    }
    rep(i, sz(f) / 2) {
        if (ypos.empty()) {
            ypos.emplace(f[i * 2 + 1]);
            ypos.emplace(-1 * f[i * 2 + 1]);
            continue;
        }
        set<int> add;
        for(auto p : ypos) {
            add.emplace(p + f[i * 2 + 1]);
            add.emplace(p - f[i * 2 + 1]);
        }
        ypos.clear();
        for(auto p : add) ypos.emplace(p);
    }
    for (auto p : xpos) {
        if (p == x) xfind = true;
    }
    for (auto p : ypos) {
        if (p == y) yfind = true;
    }
    ans = (xfind && yfind);
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;





int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  
    int a,b; cin>>a>>b;
    out(a*b);
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
int main(){
	int H,W,i,j;

	while(1){
		std::cin >> H >> W;
		if(H==0 && W==0)break;
		for(i=0;i<H;i++){
			for(j=0;j<W;j++){
				std::cout<<"#";
				if(j==W-1)
				std::cout<<"\n";					
				}
			if(i==H-1)
			std::cout<<"\n";	
			}
		
		}
	return 0;
}

Measured memory_bytes: 1124
#include <bits/stdc++.h>
#define repeat(i, n) for(int (i) = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const double EPS = numeric_limits<double>::epsilon();
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
	int N, M;
	cin >> N >> M;
	string result = "";
	vector<P> list(M);

	repeat(i, M) {
		cin >> list[i].first >> list[i].second;
	}

	repeat(i, 1000) {
		string str = to_string(i);
		bool is_exist = true;
		result = "-1";

		// 桁数と合っていなければ次の数値へ
		if (str.length() != N) continue;

		repeat(j, M) {
			// s桁目の数値とcの値を比較する
			string s = str.substr(list[j].first - 1, 1);
			string x = to_string(list[j].second);
			if (s != x) is_exist = false;
		}

		// 存在していれば結果を更新
		if (is_exist) {
			result = str;
			break;
		}
	}

	if (N == 1 && M == 0) result = "0";

	cout << result << endl;
	return 0;
}


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

int main()
{
	int N;
	cin >> N;
	vector<ll> A(N), sum(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum[i + 1] = sum[i] + A[i];
	}
	vector<ll> dl(N + 2);
	ll s = A[0], l = 0, tmp = 0;
	for (int i = 1; i < N; i++) {
		s += A[i];
		while (l + 1 <= i && abs((s - tmp) - tmp) > abs((s - (tmp + A[l])) - (tmp + A[l]))) tmp += A[l++];
		dl[i + 1] = l;
	}
	vector<ll> dr(N);
	s = A[N - 1];
	int r = N;
	tmp = 0;
	for (int i = N - 2; i >= 0; i--) {
		s += A[i];
		while (r - 1 > i && abs((s - tmp) - tmp) > abs((s - (tmp + A[r - 1])) - (tmp + A[r - 1]))) tmp += A[--r];
		dr[i] = r;
	}
	ll res = 1e18;
	for (int i = 2; i <= N - 2; i++) {
		vector<ll> v = { sum[N] - sum[dr[i]], sum[dr[i]] - sum[i], sum[i] - sum[dl[i]], sum[dl[i]] - sum[0] };
		res = min(res, (ll)(*max_element(v.begin(), v.end()) - *min_element(v.begin(), v.end())));
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 6528
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
int arive[101][101];
int main(void){
  int n,m;
  while(cin>>n>>m){
    if(n==0) break;
    int ans = 0;
    vector<pair<int,PII> > route;
    REP(i,n)REP(j,n)arive[i][j] = 1;
    REP(i,m){
      int a,b,l;
      scanf("%d,%d,%d",&a,&b,&l);
      l = (l-1)/100;
      route.push_back(pair<int,PII>(l,PII(a,b)));
    }
    sort(route.begin(),route.end());
    REP(i,route.size()){
      int a = route[i].second.first;
      int b = route[i].second.second;
      if(arive[a][b]){
        arive[a][b] = arive[b][a] = 0;
        REP(i2,n)REP(j,n) arive[i2][j] = min(arive[i2][j]
            ,arive[i2][a] + arive[a][j]);
        REP(i2,n)REP(j,n) arive[i2][j] = min(arive[i2][j]
            ,arive[i2][b] + arive[b][j]);
        ans += route[i].first;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#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 SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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;


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

int n;
cin >> n;
vi a(n);
rep(i,n) cin >> a[i];

ll res = 1000;
int cur = INF;
rep(i,n) {
    if(cur < a[i]) {
        ll st = res/cur;
        res += st*(a[i] - cur);
        cur = a[i];
    } else {
        cur = a[i];
    }
}
cout << res << endl;
return 0;
}

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

int main(){
    long long x; cin >> x;
    bool ok = false;
    for(long long i = 0; i <= 150; i++){
        for(long long j = -150; j <= 150; j++){
            if(i * i * i * i * i - j * j * j * j * j == x){
                cout << i << " " << j << endl;
                ok = true;
                break;
            }
        }
        if(ok) break;
    }
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int n, k;
vector<double> mem;

int main()
{
	cin >> n >> k;
	mem.resize(n);
	rep(i,n) cin >> mem[i]; 

	vector<double> sum;
	sum.resize(n);
 	for(int i = 0; i < n; i++){
		if(i==0) sum[i] = mem[i];
		else sum[i] = sum[i-1]+mem[i];
	}

	//rep(i,n) cout << mem[i] << " "; cout << endl;
	//rep(i,n) cout << sum[i] << " "; cout << endl;

	double E = 0;
	for(int i = k-1; i < n; i++){
		double total;
		if(i==k-1) total = sum[i];
		else  total = sum[i] - sum[i-k];
		double res = (total+k) / 2;
		//cout << total << endl;
		E = max(res, E);
	}
	printf("%.12lf\n", E);
}

Measured memory_bytes: 3328
/* Stay hungry, stay foolish. */
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<sstream>
#include<stack>
#include<ctime>
#include<cmath>
#include<cctype>
#include<climits>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
using namespace std;
template <class T> inline void read(T &x) {
	int t; bool flag=false;
	while((t=getchar())!='-'&&(t<'0'||t>'9')) ;
	if(t=='-') flag=true,t=getchar(); x=t-'0';
	while((t=getchar())>='0'&&t<='9') x=x*10+t-'0';
	if(flag) x=-x;
}
typedef long long LL;
const int maxn=100010;
int n;
LL a[maxn],v[maxn];
#define mod(i) ((i%n+n)%n)
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	v[1]=a[1]-a[n];
	LL mv=v[1];
	for(int i=2;i<=n;++i) {
		v[i]=a[i]-a[i-1];
		if(mod(v[i])!=mod(v[i-1])) {
			puts("NO");
			return 0;
		}
		mv=max(mv,v[i]);
	}
	LL cnt=0;
	for(int i=1;i<=n;++i) {
		if(i==1) cnt+=(mv-v[i])/n;
		else cnt+=(mv-v[i])/n*(n+2-i);
	}
	if(cnt>a[1]) {
		puts("NO");
	} else {
		LL tmp=((LL)n*(n+1))>>1;
		if((a[1]-cnt)%tmp==0) puts("YES");
		else puts("NO");
	}
	return 0;
}


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    char c;
    cin >> c;
    if ('a' <= c && c <= 'z') cout << 'a' << '\n';
    else cout << 'A' << '\n';
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3636
P_Sum = 0
N_Sum = 0
Kazu = 0
while True:
    try:
        pri,num = map(int,input().split(","))
        P_Sum += num * pri
        N_Sum += num
        Kazu += 1
    except(EOFError,ValueError):
        print(P_Sum)
        print(int((N_Sum / Kazu)+ 0.5))
        break

Measured memory_bytes: 7584
#include<iostream>
using namespace std;
int main(){
  char a,b;
  cin>>a>>b;
  if(a=='H'){
    if(a==b){
      cout<<'H'<<endl;
    }
    else{
      cout<<'D'<<endl;
    }
  }
  else{
    if(a==b){
      cout<<'H'<<endl;
    }
    else{
      cout<<'D'<<endl;
    }
  }
  return 0;
}

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

int main()
{
    int n;
    int i,j,k;
    int build[4][3][10]={{{}}};
    cin>>n;
    int b,f,r,v;
    for(i=0;i<n;i++){
        cin>>b>>f>>r>>v;
        build[b-1][f-1][r-1]+=v;
    }
    for(i=0;i<4;i++){
        for(j=0;j<3;j++){
            for(k=0;k<10;k++){
                cout<<" ";
                cout<<build[i][j][k];
            }
            cout<<endl;
        }
        if(i<3)cout<<"####################"<<endl;
    }
}


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

const int MAX_N = 110;
const int MAX_V = 100100;

int n;

long long w, weight[MAX_N], value[MAX_N];

long long dp[MAX_N][MAX_V];


int main(){
  
  //入力受け取り
  cin >> n >> w;
  
  rep(i,n) cin >> weight[i] >> value[i];
  
  //DPを初期化
  rep(i, MAX_N)rep(j,MAX_V) dp[i][j] = INF;
  
  //初期条件
  dp[0][0] = 0;
  
  for(int i = 0; i < n; i++){
    for(int sum_v = 0; sum_v < MAX_V; sum_v++){
      //i番目を使うとき
      if(sum_v - value[i] >= 0){
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
      }
      //i番目を使わないとき
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v]);
    }
  }
  
  int ans = 0;
  for(int sum_v = 0; sum_v < MAX_V; sum_v++){
    if(dp[n][sum_v] <= w){
      ans = sum_v;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 86272
#include <cstdio>
#include <algorithm>
int a[101], N, D;
int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", a + i);
	D = *std::max_element(a + 1, a + N + 1);
	if (*std::min_element(a + 1, a + N + 1) << 1 < D)
	{
		puts("Impossible");
		return 0;
	}
	if (D % 2 == 0 ? std::count(a + 1, a + N + 1, D >> 1) != 1 : std::count(a + 1, a + N + 1, D + 1 >> 1) != 2)
	{
		puts("Impossible");
		return 0;
	}
	for (int i = (D >> 1) + 1; i <= D; i++)
		if (std::count(a + 1, a + N + 1, i) < 2)
		{
			puts("Impossible");
			return 0;
		}
	puts("Possible");
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <valarray>

#define rep(i, n) for(int i = 0; i < n; ++i)

using namespace std;

int n;
valarray<long long> a;

int main(){
	scanf("%d", &n);
	a.resize(n);
	rep(i, n){
		scanf("%lld", &a[i]);
	}
	printf("%lld %lld %lld\n", a.min(), a.max(), a.sum());
	return 0;
}

Measured memory_bytes: 1108
import sys; input = sys.stdin.readline
n = int(input())
lis = list(map(int, input().split()))
ans = 0
for i in range(n):
	for j in range(i+1, n):
		for k in range(j+1, n):
			if lis[i] == lis[j] or lis[j] == lis[k] or lis[i] == lis[k]: continue
			s = sorted([lis[i], lis[j], lis[k]])
			if s[2] < s[1] + s[0]: ans += 1
print(ans)

Measured memory_bytes: 68748