akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main(){
    ll x,y;
    cin>>x>>y;
    ll sum=0;
    if(x==1)sum+=300000;
    if(x==2)sum+=200000;
    if(x==3)sum+=100000;
    if(y==1)sum+=300000;
    if(y==2)sum+=200000;
    if(y==3)sum+=100000;
    if(x==1 && y==1)sum+=400000;
    cout<<sum<<endl;
    return 0;
}


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

int main(){
    int s, s1, s2, s3;
    cin >> s;
    s1 = s / 100;
    s2 = (s - s1 * 100) / 10;
    s3 = s - (s1 * 100 + s2 * 10);

    cout << s1 + s2 + s3 << endl;
}



Measured memory_bytes: 256
input = raw_input

n = int(input())

d = {}
times = []
for i in range(n):
    name, time = input().split(" ")
    d[name] = i
    time = int(time)
    times.append(time)

name = input()
i = d[name]
start_i = i+1
if start_i == n:
    print(0)
else:
    out = sum(times[start_i:])
    print(out)

Measured memory_bytes: 28012
#a,b,c = [int(i) for i in input().split()]

import sys
input = sys.stdin.readline

SIZE=200002; 
MOD = 10**9+7
bai= 500000000+4

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



b,w = [int(i) for i in input().split()]

c = min(b,w)
for i in [0]*c:
    print(bai)

ans = bai
p=pow(bai,c+1,MOD)
for i in range(c,b+w):
#    print(p,i-1,i-w,b-1)
    ans += p*(choose(i-1,i-w) - choose(i-1,b-1))
    p= p*bai; p%=MOD
    ans = ans%MOD
    print(ans)



        

Measured memory_bytes: 56924
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <queue>
#include <cstring>
#include <iterator>
#include <list>
#include <set>
#include <map>
#include <bitset>
using namespace std;

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

  int i;
  for (i = 1; X > 0; i++) {
    X -= i;
  }

  cout << i-1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int a,b,c,d,e; cin >> a >> b >> c >> d >> e;
    int h=(60*c+d)-(60*a+b);
    cout << max(0,h-e) << endl;
}

Measured memory_bytes: 3648
#include<stdio.h>

int main()
{
    int maxt,mint;
    int n;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        maxt=-1;
        mint=1001;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&j);
            if(j>maxt) maxt=j;
            if(j<mint) mint=j;
        }
        printf("%d\n",maxt-mint);
    }
    return 0;
}


Measured memory_bytes: 128
n,k=map(int,input().split())
P=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(n):
    dp[i+1]=dp[i]+P[i]
ma=0
for i in range(n-k+1):
    ma=max(ma,dp[i+k]-dp[i])
print((ma+k)/2)


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

using namespace std;

typedef vector<int> VI;

int main ( void )
{
	int n, p;
	while ( cin >> n >> p, n | p ) {
		VI user( n, 0 );
		int size = p,
			turn = 0;

		while ( 1 ) {
			if ( p > 0 ) {
				p--;
				++user[turn];
				if ( p == 0 ) {
					bool end = false;
					for ( int i = 0; i < n; ++i ) {
						end |= user[i] == size;
					}
					if ( end ) {
						break;
					}
				}
			}
			else {
				p += user[turn];
				user[turn] = 0;
			}
			turn = ( turn + 1 ) % n;
		}
		cout << turn << endl;
	}
	return 0;
}

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

int main(){
	int a[5];
	int b[5];
    int c=99,d,time=0;
	for(int i=0; i<5 ;i++){
		cin >> a[i];
    	b[i] = a[i] % 10;
    	if(c>b[i] && b[i]>0){
          c = b[i];
          d = i;
    	}
    }
	for(int i=0; i<5; i++){
		if(i!=d){
          time += a[i];
          if(b[i]!=0) time += 10 - b[i];
        }
      	else time += a[i]; 	 	 
    }
  	
  
	cout << time << endl;
	
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,b,ans=0;
  cin >> n;
  vector<int> a(n),c(n-1);
  for(int i=0;i<n;i++)cin >> a[i];
  for(int i=0;i<n;i++){
    cin >> b;
    ans+=b;
  }
  for(int i=1;i<n;i++)cin >> c[i-1];
  for(int i=1;i<n;i++)if(a[i]==a[i-1]+1)ans+=c[a[i-1]-1];
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const int inf = (int)1.05e9;


int main()
{
	int n;
	i64 x;
	vector<i64> as;

	scanf("%d%lld", &n, &x);
	as.resize(n);
	for(int i = 0; i < n; ++i)
		scanf("%lld", &as[i]);

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

	i64 sum = 0;
	for(int i = 0; i < n; ++i)
		sum += as[i];

	if(sum == x) {
		printf("%d\n", n);
		return 0;
	}

	i64 consumed = 0;
	int ans = 0;

	for(int i = 0; i < n - 1; ++i) {
		if(consumed + as[i] <= x) {
			consumed += as[i];
			ans += 1;
		}
	}

	printf("%d\n", ans);

	return 0;
}

/* waffle */


Measured memory_bytes: 256
"use strict";

function Main(input) {
    input = input.split("\n");
    let tmp = input[0].split(" ");
    let x = parseInt(tmp[0], 10);
    let y = parseInt(tmp[1], 10);

    //出力
    let i = 0;
    while (i <= x) {
        if (2 * i + 4 * (x - i) == y) {
            console.log("Yes");
            return;
        }
        i++;
    }
    console.log("No");
}
//*この行以降は編集しない（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29624
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
char s[233333];
int main()
{
	scanf("%s",s+1); int n=strlen(s+1);
	for(int i=1;i<=n;++i) s[i]-='0';
	for(int i=n+1;i>=1;--i) s[i]^=s[i-1];
	int ans=n;
	for(int i=0;i<=n+1;++i)
		if(s[i]) ans=min(ans,max(i-1,n+1-i));
	printf("%d\n",ans);
}


Measured memory_bytes: 384
dance=input()
char=list(dance)
swt=0
#odd
for i in range((len(dance)+1)//2):
    #print(i)
    if (char[2*i] == "L"):
        swt += 1
#even
for i in range(len(dance)//2):
    #print(i)
    if(char[2*i+1] == "R"):
        swt += 1

if (swt==0):
    print("Yes")
else:
    print("No")

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

int N, M, X;
vector<int> C(N);
vector<vector<int> > A;

ll money = 1e7;
vector<int> skill;


void shopping(int i, ll m, vector<int> s){
	if(i < N){
		shopping(i+1, m, s);

		for(int j = 0; j < M; j++)
			s.at(j) += A.at(i).at(j);
		shopping(i+1, m+C.at(i), s);
	}else{
		bool skilled = true;
		for(int j = 0; j < M; j++)
			if(s.at(j) < X)
				skilled = false;
		if(skilled)
			money = min(m, money);
	}
	return;
}

signed main(){
	cin >> N >> M >> X;
	C = vector<int>(N);
	A = vector<vector<int> > (N, vector<int>(M));
	for(int i = 0; i < N; i++){
		cin >> C.at(i);
		for(int j = 0; j < M; j++)
			cin >> A.at(i).at(j);
	}

	skill = vector<int> (M, 0);
	shopping(0, 0, skill);
	if(money == 1e7)
		money = -1;

	cout << money << endl;

	return 0;	
}

Measured memory_bytes: 3632
#include <algorithm>
#include <climits>
#include <cstring>
#include <cctype>
#include <inttypes.h>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

const int64_t mod = 1e9 + 7;
const int cap = 1e5 + 1;
char d;
int K[cap];
int D;
int dp[cap][100];

void add(int& x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}

int main() {
    int l = 0;
    for (; scanf("%c", &d) && isdigit(d); ++l)
        K[l] = d - '0';
    scanf(" %d", &D);

    fill(&dp[0][0], &dp[0][0] + cap * 100, 0);
    dp[0][0] = 1;
    for (int i = 1; i < l; ++i)
        for (int j = 0; j < D; ++j)
            for (int k = 0; k < 10; ++k)
                add(dp[i][(j + k) % D], dp[i - 1][j]);

//     for (int i = 0; i < l; ++i) {
//         for (int j = 0; j < D; ++j)
//             printf("%d ", dp[i][j]);
//         printf("\n");
//     }

    int ans = dp[l - 1][0] - 1, tot = 0;
    for (int i = 0; i < l; ++i) {
        for (int j = int(i == 0); j < K[i]; ++j) {
            add(ans, dp[l - 1 - i][(2 * D - tot - j) % D]);
        }
        tot = (tot + K[i]) % D;
    }
    add(ans, int(tot == 0));

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





Measured memory_bytes: 39296
#include <stdio.h>
#define FREE 0
#define N_FREE 1
#define Q 2
#define N 8
 
int board[N][N];
int row[N],col[N],dneg[2*N-1],dpos[2*N-1];

void printboard(void);
void putQueen(int);

int main(){
  int k,r,c;
  int i;
  
  
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d",&r);
    scanf("%d",&c);
    board[r][c] = N_FREE;
  }
  
  putQueen(0);
      
  return 0;
}
 
void printboard(){
  int i, j;
  
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(board[i][j] == N_FREE && row[i] != j)
    return;
    }
  }
  
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(row[i] == j)
    printf("Q");
      else
    printf(".");
    }
    printf("\n");
  }
};
 
void putQueen(int i){
  int j;
   
  if(i==N){  
    printboard();
    return;
  }
 
  for(j=0;j<N;j++){
    if(col[j]==N_FREE || dpos[i+j]==N_FREE || dneg[i-j+N-1]==N_FREE){ 
      continue;
    }
 
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = N_FREE; 

    putQueen(i+1);
     
    col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
  }
};
 

Measured memory_bytes: 572
/***************************************************
 * Problem Name : C - Fennec vs Monster.cpp
 * Problem Link :
 * OJ           :
 * Verdict      : Trying
 * Date         : 2020-02-03
 * Problem Type :
 * Author Name  : Saikat Sharma
 * University   : CSE, MBSTU
 ***************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
#include <deque>
#include <stack>
#include <bitset>
#include <cassert>
#include <map>
#include <set>
#include <cassert>
#include <iomanip>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define __FileRead freopen ("input.txt", "r", stdin)
#define __FileWrite freopen ("output.txt", "w", stdout)
#define SET(a,v) memset(a,v,sizeof(a))
#define SZ(v) (int)v.size()
#define pii pair<int,int>
#define pil pair <int, ll>
#define pli pair <ll, int>
#define pll pair <ll, ll>
#define debug cout <<"######\n"
#define debug1(x) cout <<"### " << x << " ###\n"
#define debug2(x,y) cout <<"# " << x <<" : "<< y <<" #\n"
#define nl cout << "\n";
#define sp cout << " ";
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define ss(n) scanf("%s", n)
#define pf(n) scanf("%d", n)
#define pfl(n) scanf("%lld", n)
#define all(v) v.begin(), v.end()
#define rall(v) v.begin(), v.end()
#define srt(v) sort(v.begin(), v.end())
#define r_srt(v) sort(v.rbegin(), v.rend())
#define rev(v) reverse(v.begin(), v.end())
#define Sqr(x) ((x)*(x))
#define Mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define mk make_pair
#define MAX 100005
#define INF 1000000009
#define MOD 1000000007

template<class T>
using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename T>
using ordered_set  = tree<T, null_type, less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

template <typename T> string toString ( T Number ) {
    stringstream ss;
    ss << Number;
    return ss.str();
}
template<typename T> int toInt (T str) {
    stringstream ss;
    ss << str;
    int num;
    ss >> num;
    return num;
}
ll lcm (ll a, ll b) {
    return a * b / __gcd (a, b);
}
/************************************ Code Start Here ******************************************************/
int main () {
    //~ __FastIO;
    //~ cout << setprecision (10);
    //~ cout << fixed;
    int n, k;
    cin >> n >> k;
    vector<int>vec (n);

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

    r_srt (vec);
    ll cnt = 0;

    for (int i = k; i < n; i++) {
        cnt += (ll)vec[i];
    }

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


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <deque>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int main() {
	string a;
	cin >> a;
	if (a == "AAA" || a == "BBB") {
		cout << "No" << endl;
	}
else {
	cout << "Yes" << endl;
}
	return 0;
}

  

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

using namespace std;

int main()
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    int x;
    scanf("%d", &x);
    int st = 1, dr = 45000, rez = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        int s = mij * (mij + 1) / 2;
        if(x <= s)
        {
            dr = mij - 1;
            rez = mij;
        }
        else st = mij + 1;
    }
    printf("%d", rez);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mod 1000000007
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, n;
    cin >> h >> n;
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
    	int x;
    	cin >> x;
    	sum += x;
	}
	if(sum >= h)
	cout << "Yes";
	else
	cout << "No";
    
	return 0;
}



Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.IO.Compression;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        private const long COMDIV = 1000000007;

        static void Main(string[] args)
        {
            var r = Console.ReadLine();
            if (Regex.IsMatch(r,@"[a-z]"))
            {
                Console.WriteLine("a");
            }
            else
            {
                Console.WriteLine("A");
            }
        }
    }
}

Measured memory_bytes: 26780
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int N,K,Q,j;
int A[100010]={0};
int main(void){
	cin>>N>>K>>Q;
	for(int i=0;i<Q;i++){
		cin>>j;
		A[j-1]++;
	}
	for(int i=0;i<N;i++){
		if(Q-K<A[i]){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main()
{
	int K;
	scanf("%d", &K);
	
	int d, i, j, k, digit[16] = {1}, d_sum = 1;
	long long tmp = 1, pow[16];
	for (i = 1, pow[0] = 1; i < 16; i++) pow[i] = pow[i-1] * 10;
	for (k = 1, d = 0; k <= K; k++) {
		printf("%lld\n", tmp);
		
		for (i = d; digit[i] == 9; i++);
		for (tmp += pow[i], digit[i--]++, d_sum++; i >= d; tmp -= pow[i] * 9, digit[i--] = 0, d_sum -= 9);
		while (1) {
			if (digit[d] < 9) {
				if (pow[d] * d_sum >= tmp) break;
				else {
					d_sum += 9 - digit[d];
					tmp += pow[d] * (9 - digit[d]);
					digit[d++] = 9;
				}
			} else break;
		}
	}
	
	fflush(stdout);
	return 0;
}

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

using namespace std ;
typedef long long ll;
typedef string str;
typedef vector<int> vint;
typedef vector<double> vdou ;
typedef vector<ll> vll;
typedef vector<vint> vvint;
typedef vector<str> vstr;
typedef pair<int, int> pii;
typedef vector<pii> vpii ;

#define REP(i, n) for (ll (i) = 0; (i) < (ll)(n); i++) 
#define FOR(i, a, b) for(ll (i) = a; (i) < (ll)b; i++)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (ll)x.size()
#define SP(x)  setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, c, k ;
  cin >> n >> c >> k ;
  vll tim(n) ;
  ll ans = 0 ;
  REP(i,n){
    cin >> tim[i] ;
  }
  sort(ALL(tim)) ;
  
  
  bool f = true ;
  ll end ;
  
  int i=0;
  while(i<n){
    if(f){
      end = tim[i]+k ;
      ans++ ;
    }
    int j = 1 ;
    int ii = i ;
    while(j<c && ii+j<n){
      if(end>=tim[ii+j]){
        i++ ;
      }
      else{
        break ;
      }
      j++ ;
    }
    i++ ;
  }
  cout << ans <<endl ;
      
    
      
      
  return 0 ;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    ll N,K;
    cin >> N >> K;
    ll p[100001];
    memset(p,0,sizeof(p));
    for (int i=0; i<N; i++) {
        ll a,b;
        cin >> a >> b;
        p[a]+=b; 
    }

    // output
    ll total =0;
    int ans =0;
    for (int i=1; i<=100000; i++) {
        total+=p[i];
        if (total >= K ) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
   int n,m;
   cin>>n>>m;
   long long int ans=0;
   if(n>=2)
   {
       ans+=(n*(n-1))/2;
   }
   if(m>=2)
   {
       ans+=(m*(m-1))/2;
   }
   cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int func(int n,int a[],int d){
    int sum=0,i,j;
    for(i=0; i<n; i++){
        j=0;
        while((j*a[i]+1)<=d){
            sum += 1;
            j++;
        }
    }
    return sum;
}

int main(void){
    int n,d,x,i,sum;
    scanf("%d",&n);
    scanf("%d %d",&d,&x);
    int a[n];

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

    sum = func(n,a,d);

    printf("%d\n",sum+x);

    return 0;
}

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

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> d(N);
    for (int i = 0;i < N;i++) {
        cin >> d[i];
    }
    int ans = 0;
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(i != j){
                ans+=d[i]*d[j];
            }
        }
    }
    cout<<ans/2<<endl;
    return 0;
}


Measured memory_bytes: 256
a, b, k = map(int, input().split())
for i in range(k):
    if i % 2 ==0:
        if a % 2 == 0:
            a = a/2
            b = b+a
            
        else:
            a = (a-1)/2
            b = b+a
            
    if i % 2 == 1:
        if b % 2 == 0:
            b = b/2
            a = b+a
            
        else:
            b = (b-1)/2
            a = b+a
            
print(int(a), int(b))

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

int main()
{
  int a[5];
  int ans;
  for(int i=0;i<5;i++)
  {
    cin>>a[i];
    if(a[i]==0)
      ans=i+1;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3616
from sys import stdin
import math
import re
import queue

input = stdin.readline

MOD = 1000000007
INF = 122337203685477580

def solve():
    str = (input().rstrip())
    str = str.replace("hi","")
    if(len(str) == 0):
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()


Measured memory_bytes: 3952
#!/usr/bin/env python3
import sys


def solve(N: int, A: int, B: int):
    print(min(N * A, B))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(N, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>

#define MOD 1000000007

// int max: 2 x 10^9, long long max: 9 x 10^18

using namespace std;

int main()
{
  int n, m;
  cin >> n >> m;
  
  vector<long long> a(n), c(m);
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  
  vector<int> b(m);
  for(int i=0; i<m; i++){
    cin >> b[i] >> c[i];
  }
  
  map<int, int, greater<int> > histo;
  
  for(int i=0; i<n; i++){
    histo[a[i]]++;
  }
  
  for(int i=0; i<m; i++){
    histo[c[i]] += b[i];
  }
  
  int nokori = n;
  long long result = 0;
  for(const auto& p: histo){
    if(nokori > p.second){
      result += p.first * p.second;
      nokori -= p.second;
    }else{
      result += nokori * p.first;
      break;
    }
  }
  
  cout << result;

  return 0;
}

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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

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; }
template<class T>
T GCD(T a, T b) { if (b == 0) return a; else return GCD(b, a % b); }
template<class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

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

Measured memory_bytes: 3572
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int[] p = new int[N];
		for (int i = 0; i < N; i++) {
			p[i] = sc.nextInt();
		}
		int[] sorted = p.clone();
		Arrays.sort(sorted);
		int count = 0;
		for (int i = 0; i < N; i++) {
			if(p[i] != sorted[i]) {
				count++;
			}
		}
		if (count <= 2) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21204
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

intmax_t f(const std::vector<intmax_t>& A, intmax_t X) {
  intmax_t res = 0;
  for (auto ai: A) res += ai ^ X;
  return res;
}

int main() {
  size_t N;
  intmax_t K;
  scanf("%zu %jd", &N, &K);

  std::vector<intmax_t> A(N);
  std::vector<size_t> B(40);
  for (auto& ai: A) {
    scanf("%jd", &ai);
    for (int i = 0; i < 40; ++i)
      if (ai >> i & 1)
        ++B[i];
  }

  intmax_t L = 0;
  for (int i = 0; i < 40; ++i)
    if (B[i] < N-B[i]) L |= 1L << i;

  intmax_t res = f(A, K);
  for (int i = 0; i < 40; ++i) {
    intmax_t mid = 1L << i;
    intmax_t lo = mid-1;
    intmax_t hi = ~(mid | lo);
    intmax_t X = (K & hi) | (L & lo);
    if (X > K) continue;
    res = std::max(res, f(A, X));
  }
  printf("%jd\n", res);
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int N, X;

int main() {
    cin >> N >> X;

    int S = 0, L, ans = 1;
    for (int i = 0; i < N; i++) {
        cin >> L;
        S += L;
        if (S <= X) ans++;
    }

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


Measured memory_bytes: 256
s = int(input())
a = []
a.append(s)
if s == 1 or s == 2 or s == 4:
    print(4)
else:
    while not 1 in a:
        if s % 2 == 0:
            s /= 2
            a.append(round(s))
        else:
            s = 3 * s + 1
            a.append(round(s))
    print(len(a)+1)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = 1e9;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
/*--------------------template--------------------*/

int main() {
    ll A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    double max=-1;
    ll w=0,s=0;
    double maxn=100.0*E/(100+E);
    REP(i,F/(100*A)+2){
        REP(j,F/(100*B)+2){
            REP(k,F/2+2){
                REP(l,F/2+2){
                    ll a=100*A*i+100*B*j;
                    ll b=C*k+D*l;
                    if(a+b>F||a+b==0)continue;
                    double n=100.0*b/(a+b);
                    if(n>max&&n<=maxn){
                        max=n;
                        w=a;
                        s=b;
                    }
                }
            }
        }
    }
    cout<<w+s<<" "<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define p(s) cout<<(s)<<endl
using namespace std;

int main() {
	int x,y;
	cin>>x>>y;
	int ans=0;
	if((x>=0&&y<=0)||(x<0&&y>0)) ans++;
	if((x<0&&x>y)||(y>0&&x>y)) ans+=2;
	ans += abs(abs(x)-abs(y));
	p(ans);
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
 
class Main {
    public static void main(String[] args) throws IOException {
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     String moji=br.readLine();
     int n=Integer.parseInt(br.readLine());
     String str=null; 
     for(int i=0;i<n;i++){
    	 str=br.readLine();
    	
    	 String[] st=str.split(" ");
    	 int start=Integer.parseInt(st[1]);
    	 int end=Integer.parseInt(st[2]);
    	 if(st[0].equals("print"))System.out.println(moji.substring(start,end+1));
    	 else if(st[0].equals("replace")){
    		 if(start==0)moji=st[3]+moji.substring(++end);
    		 else moji=moji.substring(0,start)+st[3]+moji.substring(end+1);
    	 }
    	 else {String kari=moji.substring(start,end+1);
    	 String tmp="";
    	 char[] ch=new char[kari.length()];
    	 for(int j=kari.length()-1;j>=0;j--){
    		 ch[j]=kari.charAt(j);
    		 tmp+=Character.toString(ch[j]);    		 
    	 }
    	 if(start==0)moji=tmp+moji.substring(end+1);
    	 else moji=moji.substring(0,start)+tmp+moji.substring(end+1);
    	 }
    	 
     }
     
    }}

Measured memory_bytes: 40864
Q,H,S,D=map(int,input().split())
N=int(input())

l2=[Q*8,H*4,S*2,D]
l1=[Q*4,H*2,S]
l2min=l2.index(min(l2))
l1min=l1.index(min(l1))

ans,rest=divmod(N,2)
ans=ans*l2[l2min]+rest*l1[l1min]
print(ans)




Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int main(){
    string s;
    cin>>s;
    if(s[0]==s[2]){
       cout<<"Yes"<<endl;
    }else{
       cout<<"No"<<endl;
    }
	return(0);
}

Measured memory_bytes: 256
N,M,C=map(int,input().split())
B=[int(x) for x in input().split()]
ans=0
for i in range(N):
  A=[int(x) for x in input().split()]
  s=0
  for j in range(M):
    s+=A[j]*B[j]
  if s+C>0:
    ans+=1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
    int N;
    cin >> N;
    
    if(N%2==0){
        cout << N << endl;
    }else{
        cout << 2*N << endl;
    }
    
    return 0;
}



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

int main(){
    int n, m;
    cin >> n >> m;
    if (n > m) n = m;
    vector<int> x(m), dist(m-1);
    rep(i, m) cin >> x[i];
    sort(all(x));
    ll ans = 0;
    rep(i, m-1) {
        int tmp = abs(x[i] - x[i+1]);
        dist[i] = tmp;
    }
    sort(all(dist));
    rep(i, (m-1)-(n-1)) {
        ans += dist[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        temp = []
        if n % i == 0:
            temp.append(i)
            temp.append(n//i)
            divisors.append(temp)

    # divisors.sort()
    return divisors

X = make_divisors(N)
ans = 10

for i in X:
    ans = min(ans, max(len(str(i[0])), len(str(i[1]))))

print(ans)



Measured memory_bytes: 3188
import sys

a = []
for i in range(3):
   a.append([int(x) for x in input().split()])

n = int(input())
b = [int(input()) for _ in range(n)]

for i in range(n):
   for j in range(3):
      for k in range(3):
         if (b[i] == a[j][k]):
            a[j][k] = 0

for i in range(3):
   x = 0
   for j in range(3):
      x += a[j][i]
   if (x == 0):
      print('Yes')
      sys.exit()

tmp = [sum(a[i]) for i in range(3)]
if (min(tmp) == 0):
   print('Yes')
elif (a[0][0] + a[1][1] + a[2][2] == 0):
   print('Yes')
elif (a[0][2] + a[1][1] + a[2][0] == 0):
   print('Yes')
else:
   print('No')


Measured memory_bytes: 3064
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //置き換え回数カウント用変数の宣言
        int count = 0;
        //文字列の取得
        String strS= sc.next();
        String strT = sc.next();
        
        for(int i=0; i<strS.length(); ++i){
            //SとTの各文字が一致しないとき、置き換えに必要な回数をカウントする
            if(strS.charAt(i) != strT.charAt(i)){
                ++count;
            }
        }
        System.out.println(count);
    }
}

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

int main() {
    int64_t N;
    cin >> N;
    vector<int64_t> L(N);
    for ( int64_t i = 0; i < N; ++i){
        cin >> L.at(i);
    }
    
    sort(L.begin(),L.end());
    
    int64_t ans = 0;
    for ( int64_t i = 0; i < N; ++i){
        for ( int64_t j = 0; j < N; ++j){
            if ( i == j ) continue;
            int64_t b = L.at(i), c = L.at(j);
            auto itrl = upper_bound(L.begin(),L.end(),abs(b-c)); // 値を"超える"値の最小値のitr
            auto itrh = lower_bound(L.begin(),L.end(),b+c); // 値"以上"の最小値のitr
            int64_t num = itrh - itrl ;
             //cout << "b " << b << " c " << c << " |b-c| " << abs(b-c) << " b+c " << b+c << " " <<  num << endl;
            if ( abs(b-c) < b ) --num;
            if ( abs(b-c) < c ) --num;
            //cout << num << endl;
            if ( num >= 0 ) ans += num;
        }
    }
    
    cout << ans/6 << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 2e4 + 5 ;
const int inf = 0x3f3f3f3f ;
int h , n ;
int a[maxn] , b[maxn] ;
int dp[maxn] ;
int main()
{
	int ans = inf ;
	memset(dp , inf , sizeof(dp)) ;
	dp[0] = 0 ;
	scanf("%d%d" , &h , &n) ;
	for(int i = 1 ; i <= n ; i ++)  
	{
		scanf("%d%d" , &a[i] , &b[i]) ;
		if(a[i] >= h)  ans = min(ans , b[i]) ;
	}
	for(int i = 1 ; i <= n ; i ++)
	  for(int j = a[i] ; j <= 2 * h ; j ++)
	    dp[j] = min(dp[j] , dp[j - a[i]] + b[i]) ;
	for(int i = h ; i <= 2 * h ; i ++)  ans = min(ans , dp[i]) ;
	printf("%d\n" , ans) ;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vvi G(n);
  vi deg(n);
  rep(i, n){
    int a,b; cin >> a >> b;
    a--; b--;
    G[a].pb(b); G[b].pb(a);
    deg[a]++; deg[b]++;
  }

  queue<int> q;
  rep(i, n) if(deg[i] == 1) q.push(i);
  vector<bool> pushed(n, false);

  while (!q.empty()) {
    int v = q.front(); q.pop();
    pushed[v] = true;
    for(auto nv : G[v]){
      deg[nv]--;
      if(deg[nv] == 1) q.push(nv);
    }
  }

  int Q; cin >> Q;
  rep(i, Q){
    int a,b; cin >> a >> b;
    a--; b--;
    if(!pushed[a] && !pushed[b]) std::cout << 2 << '\n';
    else std::cout << 1 << '\n';
  }
}



Measured memory_bytes: 8620
#include <cstdio>
#define LL long long
const int maxn = 4e6 + 5;
const int mo = 1e9 + 7;
using namespace std;
LL f[2005][2005], fac[maxn], inv[maxn];
LL C(int n, int m){
	if (m == 0 || m == n) return 1;
	if (m > n) return 0;
	return fac[n] * inv[n - m] % mo * inv[m] % mo;
}
LL pow(LL x, int t){
	LL res = 1; x %= mo;
	while (t > 0){
		if (t & 1) res = res * x % mo;
		x = x * x % mo;
		t >>= 1;
	}
	return res;
}
int n, k; 
int main(){
	scanf("%d%d", &n, &k);
	if (k == 1){
		puts("1");
		return 0;
	}
	fac[0] = 1; 
	for (int i = 1; i <= n * k; i++) fac[i] = fac[i - 1] * i % mo;
	inv[n * k] = pow(fac[n * k], mo - 2);
	for (int i = n * k - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mo;
	for (int i = 0; i <= n; i++)
		for (int j = i; j <= n; j++){
			if (i == 0 && j == 0) f[i][j] = 1;
			if (j != 0) f[i][j] = (f[i][j] + f[i][j - 1]) % mo;
			if (i != 0) f[i][j] = (f[i][j] + f[i - 1][j] * (n - i + 1) % mo * C(n * k - (i - 1) * (k - 1) - j - 1, k - 2) % mo) % mo;
		}
	printf("%lld\n", f[n][n]);
	return 0;
}

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

int main() 
{
  int n, d;
  cin >> n >> d;
  //d * 2 + 1が何個入るか
  int sum = 0;
  int count = 0;
  while (sum < n) {
    sum += d * 2 + 1;
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let s: String = read(&mut stdin_lock, &mut buf, b'\n');
    let cv: Vec<char> = s.chars().collect();

    let mut ans = 0;
    let mut p = cv[0];
    for i in 1..n {
        if p != cv[i] {
            p = cv[i];
            ans += 1;
        }
    }
    ans += 1;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

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

int N;
int a[1000000];
int cnt;
int m;
vector<int> G;
vector<int> v;

void insertionSort(int g) {
  for(int i = g; i < N; i++) {
    int b = a[i];
    int key = i;
    int j = i - g;
    while(j >= 0 && a[j] > b) {
        a[j+g] = a[j];
        j -= g;
        cnt++;
    }
    a[j+g] = b;
  }
}

void shellSort() {
  int key = 1;
  while(true) {
    v.push_back(key);
    if(1000000000 <= key) break;
    key = key * 3 + 1;
  }
  cnt = 0;
  int ind = (N == 1) ? 0 : upper_bound(v.begin(), v.end(), N-1) - v.begin() - 1;
  m = ind + 1;
  rep(i, m) {
    insertionSort(v[m-1-i]);
  }
}

int main() {
  cin >> N;
  rep(i, N) {
    cin >> a[i];
  }

  shellSort();

  cout << m << endl;
  rep(i, m) {
    cout << v[m-1-i];
    if(i != m-1) cout << " ";
    else cout << endl;
  }
  cout << cnt << endl;
  rep(i, N) {
    cout << a[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 7052
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
const int MOD=1e9+7;
int n;
int a[N];
int b[N];
int main()
{

    cin>>n;
   for(int i=1;i<=n;i++)
   {
   	scanf("%d",&a[i]);
   }
   int m=n;
   int j=1;
   for(int i=n;i>=2;i-=2)
   {
   	b[j]=a[i];
   	b[n-j+1]=a[i-1];
   	j++;
   }
   if(n&1)
   {
   	b[j]=a[1];
   }
   
   for(int i=1;i<=n;i++)
   	printf("%d ",b[i]);
   
    return 0;

}


Measured memory_bytes: 3712
def solve(placed, w1, w2):
  global weight, D
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    if weight > w1:
      D = placed
      weight = w1
    return
   
  for e in x:
    w = W[e]
    if w2 > S[e]: return
    a = w1 + w * n
    if a > weight: return
    b = w2 + w
    solve(placed+[e], a, b)
  return
 
while 1:
  n = input()
  if n==0: break
  D = []
  weight = 1e9
  N = range(n)
  f = lambda x: [int(x[1]),int(x[2]),x[0]]
  x = [f(raw_input().split()) for _ in [0]*n]
  W, S, Name = zip(*sorted(x))
  solve([], 0, 0)
  for e in D[::-1]:
    print Name[e]

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll X[101010];
int M;
ll K;
int A[62][101010];
int B[101010],C[101010];

void doswap(int a[101010],int b[101010],int c[101010]) {
	int i;
	FOR(i,N-1) c[i]=b[a[i]];
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N-1) A[0][i]=B[i]=i;
	cin>>M>>K;
	FOR(i,M) {
		cin>>x;
		swap(A[0][x-2],A[0][x-1]);
	}
	
	for(i=0;i<=60;i++) {
		if(K&(1L<<i)) {
			doswap(B,A[i],C);
			swap(B,C);
		}
		doswap(A[i],A[i],A[i+1]);
	}
	
	ll s=X[0];
	FOR(i,N) {
		cout<<s<<endl;
		s+=X[B[i]+1]-X[B[i]];
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 27264
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)

using ll = long long;

const int INF = 1073741823;
const int MINF = -1073741823;
const ll LINF = ll(4661686018427387903);
const ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

/*-----------------------------------------ここからコード-----------------------------------------*/

int main() {

	int n;
	scanf("%d", &n);
	int ans = 1, a;
	rep(i, n) {
		scanf("%d", &a);
		ans = lcm(ans, a);
	}
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 3212
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int>PA;
using namespace std;
#define MAX  999999
int main (){
    int n; cin >> n;
    rep(k,n){
        string s; string s2;
        cin >> s >> s2;
        vi v(100,0);
        if(s.length()>80 || s2.length() > 80){
            cout << "overflow" << endl;
        }else{
            vi v(100,0); vi v2(100,0);
            vi ans(100,0);
            if(s.length()<s2.length()) swap(s,s2);
            rep(i,s.length())
                v[i] = (int)s[i]-48;
            rep(i,s2.length())
                v2[i] = (int)s2[i]-48;
            int num = (int)max(s2.length(),s.length());
            reverse(v.begin(), v.begin()+s.length());
            reverse(v2.begin(),v2.begin()+ s2.length());
            int ansize = 0;
            rep(i,num){
                ansize++;
                ans[i] += v[i]+v2[i];
                if(ans[i] >= 10){
                    ans[i]-=10;
                    ans[i+1]+=1;
                    if(i == num-1)
                        ansize++;
                }
            }
            if(ansize >80)
                cout <<"overflow" << endl;
            else{
            reverse(ans.begin(), ans.begin()+ansize);
            rep(i,ansize)
            cout << ans[i];
            cout << endl;
            }
        }
        
        }
        return 0;
}

Measured memory_bytes: 3140
# ABC089C - March
from itertools import combinations


def main():
    n = int(input())
    lst = [input().rstrip() for _ in range(n)]
    cond = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
    for i in lst:
        if i[0] in "MARCH":
            cond[i[0]] += 1
    ans = 0
    for x, y, z in combinations("MARCH", 3):
        ans += cond[x] * cond[y] * cond[z]
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 9772
k = list(map(int, input().split()))
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
x10 = k[0]
x2 = Base_10_to_n(x10, k[1])
print(len(x2))

Measured memory_bytes: 3060