akhauriyash/Code-Regression huggingface dataset:
/**
 * Title: C - All Green
 * Url: https://atcoder.jp/contests/abc104/tasks/abc104_c
 */
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<numeric>
#include<functional>
#include<sstream>
#include<iomanip>

using namespace std;

#define ll long long
#define INF 1000000000

int main() {
    int D, G; cin >> D >> G;
    vector<int> p(D+1), c(D+1);
    for(int i=1; i<D+1; i++) cin >> p[i] >> c[i];
    int ans = INF;
    for(int bit=0; bit<(1<<D); bit++) {
        int t_ans = 0;
        int g = G;
        // 全問解いたパターンを先に処理
        for(int i=0; i<D; i++) {
            if(bit&(1<<i)) {
                g = g - p[D-i]*100*(D-i) - c[D-i];
                t_ans += p[D-i]; 
            }
        }
        // cout << "(g, t_ans)=(" << g << "," << t_ans << ")" << endl;
        // 0問以上N-1問以下解いた場合
        for(int i=0; i<D; i++) {
            if(g<=0) {
                break;
            }
            if((bit&(1<<i))==0) {
                int q;
                if(g%(100*(D-i))==0) {
                    q = g/(100*(D-i));
                } else {
                    q = g/(100*(D-i))+1;
                }
                if(q > p[D-i]-1) {
                    g = g - (p[D-i]-1)*100*(D-i);
                    t_ans += p[D-i]-1;
                } else {
                    g = 0;
                    t_ans += q;
                }
            }
        }
        if(g<=0) {
            ans = min(ans, t_ans);    
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "fstream"
#include "algorithm"
#include "iomanip"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "map"
#include "set"
#include "list"
#include "deque"
#include "complex"
#include "bitset"
#include "cmath"
#include "unordered_set"
#include "unordered_map"
#include "iterator"
#include <ctime>
#include <cassert>
#include "numeric"
#include <cstdio>

using namespace std;

//#define f(i,n) for(int i=0; i<n;i++) 
//#define rf(i, n) for(int i=n-1;i>=0;i--)
//#define forn(i, j, n) for(int i=j; i<n; i++)
//#define ff(i, j, n) f(i, n)f(j, n)
#define pb push_back
#define maxi(a,b) a = max(a, b);
#define mini(a,b) a = min(a, b);
#define endl '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(x) ((x) * (x))
#define SZ(a) ((int)(a.size()))
#define watch(x) cout << (#x) << " = " << x << endl;
//typedef long long ll;
typedef long double ld;
#define int long long
#define double ld
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<char> vc;

template<class T>
void show(const vector<T> &a)
{
	for (T x : a)
		cout << x << " ";
	cout << endl;
}

const int sze = 3e5 + 50, oo = 1e18 + 500, mod = 1e9 + 7;
const double eps = 1e-9, PI = 2 * acos(0.0);
vi vertices[sze];
vi visit(sze, 0);
vc used(sze, false);
vi arr(sze, 0);
int n, m, k;
int A, B;
int cnt = 0;

int calc[sze];
int dp[sze];
int a[20][20];
bool did[sze];

int rec(int mask)
{
	if (mask == 0)
		return 0;

	if (did[mask])
	{
		return dp[mask];
	}

	did[mask] = true;
	int ans = 0;
	for (int sub = mask; sub; sub = (sub-1)&mask)
	{
		int group = sub;
		int nxt = mask^sub;
		maxi(ans, calc[group] + rec(nxt));
	}

	dp[mask] = ans;
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);
	/*freopen("stars.in", "r", stdin);
	freopen("stars.out", "w", stdout);*/

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

	for (int i = 0; i < 1 << n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int z = j+1; z < n; z++)
			{
				if (((1 << j) & i) && ((1 << z) & i))
				{
					calc[i] += a[j][z];
				}
			}
		}
	}

	cout << rec((1 << n) - 1);
	return 0;
}

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

int main(){
  while(1){
  int h,w;
  cin >> h >> w;
  if(h == 0 && w ==0) break;
  for(int i = 0;i < h;i++){
    for(int j = 0;j < w;j++){
      if((i + j)%2 == 0) cout << "#";
      else cout << ".";
    }
    cout << endl;
  }
  cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3088
#include <iostream>
#include<stdio.h>
#include<stack>

#define MAX 100
#define WHITE 1
#define GRAY 2
#define BLACK 3

using namespace std;

int color[MAX], d[MAX], f[MAX];
int n, A[MAX][MAX];
int tt;

void dfs_visit_1(int u) { //???????????°
    color[u] = GRAY;
    d[u] = ++tt;
    for(int v = 0; v < n; v++) {
        if(A[u][v] == 0) continue;
        if(color[v] == WHITE) dfs_visit_1(v);
    }
    color[u] = BLACK;
    f[u] = ++tt;
}

int next(int u) {
    for(int v = 0; v < n; v++) {
        if(A[u][v] == 1) {
            /*
            if(color[v] == WHITE) return v;
            else if(color[v] == BLACK) return -1;
            else if(color[v] == GRAY) continue;
            */
            return v;
        }
    }
    return -1;
}

void dfs_visit_2(int u) {
    color[u] = GRAY;
    d[u] = ++tt;
    stack<int> S;
    S.push(u);

    while(!S.empty()) {
        int u = S.top();
        int v = next(u);
        if(v != -1) {
            if(color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        }else {
            S.pop();
            color[u] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs_1() { // ???????????°
    for(int i = 0; i < n; i++) {
        color[i] = WHITE;
    }
    tt = 0;
    for(int i = 0; i < n; i++) {
        if(color[i] == WHITE) dfs_visit_2(i);
    }

    for(int i = 0; i < n; i++) {
        printf("%d %d %d\n", i+1, d[i], f[i]);
    }

}
int main()
{
    int u, k, v;
    scanf("%d",&n);
    
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &u, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &v);
            A[u-1][v-1] = 1;
        }
    }

    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("%d", A[i][j]);
            if(j != n-1) printf(" ");
        }
        printf("\n");
    }
    
    //dfs_1();
    
    return 0;
}

Measured memory_bytes: 3220
using System;
using System.Collections.Generic;//list用
using System.Text;//StringBuilder用
using System.Collections;
using System.Linq;
class Program
{
    static List<int> s = new List<int>();
    static decimal result;
static StringBuilder sb = new StringBuilder();
static int N,M,K,A,B,C,D;
  static string a;
    static void Main()
    {
Read3();
      Read5();
      N=s[0];
      A=s[1];
        B=s[2];
        C=s[3];
        D=s[4];
      //D>Cなら先にBを動かせば衝突しない
      if(D>C){for(int i=A-1;i<D;i++){if(a[i]=='#' && a[i+1]=='#'){Console.WriteLine("No");return;}}Console.WriteLine("Yes");return;}
      
      //C>Dなら，追い越し可能ポイントがあるかチェック
      if(C>D){for(int i=A-1;i<C;i++){if(a[i]=='#' && a[i+1]=='#'){Console.WriteLine("No");return;}}
              for(int i=B-2;i<D-1;i++){if(a[i]=='.' && a[i+1]=='.' && a[i+2]=='.'){Console.WriteLine("Yes");return;}}
                                    Console.WriteLine("No");return;
                                    }
             
    }


    static void Read1()//1項
    {
        string tmp = Console.ReadLine();
        N = int.Parse(tmp);
    }
 
    static void Read2()//複数項（項目数Ｎ）
    {
        string[] tmp = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++) { s.Add(int.Parse(tmp[i])); }
    }
    static void Read3()//1行複数項
   {
       string[] tmp = Console.ReadLine().Split(' ');
       for (int i = 0; i < tmp.Length; i++) { s.Add(int.Parse(tmp[i])); }
    }
    static void Read4()//NK１行
    {
        string[] tmp = Console.ReadLine().Split(' ');
       N = int.Parse(tmp[0]);
       K = int.Parse(tmp[1]);
    }
    static void Read5()//N行K項
    {
a= Console.ReadLine();
 
    }


}

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

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if((a==b&&a!=c)||(a==c&&a!=b)||(b==c&&b!=a)){
		cout<<"Yes"<<endl;
	}
	else
		cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
import itertools
S = input()
A = [len(list(v)) for _, v in itertools.groupby(S)]
ans = 0
if S[0] == '>':
    a, A = A[0], A[1:]
    ans += a * (a + 1) // 2
for a, b in zip(A[::2], A[1::2]):
    ans += a * (a + 1) // 2 + b * (b + 1) // 2 - min(a, b)
if S[-1] == '<':
    a = A[-1]
    ans += a * (a + 1) // 2
print(ans)


Measured memory_bytes: 8328
def divisor_num(x):
    num = 0
    for i in range(1,int(x**0.5)+1):
        num += (x%i == 0)*2
    num -= (x**0.5).is_integer()
    return num

n=int(input())
c = 0
for i in range(1,n+1,2):
    c += (divisor_num(i) == 8)
print(c)

Measured memory_bytes: 3068
from sys import stdin
from collections import defaultdict
from collections import deque
 
N = int(stdin.readline().rstrip())
adj = defaultdict(set)
edges = []

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    edges.append((a,b))
    
visited = [False]*(N+1)
color_edges = defaultdict(bool)
visit_p = deque()
visit_p.append((1,0))
 
while visit_p:
    node,color = visit_p.popleft()
    
    if visited[node]:
        continue
        
    visited[node] = True
    
    cnt = 0
    for i in adj[node]:
        if visited[i]:
            continue
        cnt += 1
        if cnt == color:
            cnt += 1
        color_edges[(node,i)] = cnt
        visit_p.append((i,cnt))
print(max(color_edges.values()))
for i in edges:
    if not color_edges[i]:
        print(color_edges[(i[1],i[0])])
    else:
        print(color_edges[i])

Measured memory_bytes: 66408
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

int main(){
    string a;
    cin >> a;
    cout << a[0]+a[1]+a[2]-144 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define for0(i,n) for (int i=0; i<n; i++)
#define forr(i,n) for (int i=n-1; i>=0; i--)
#define fori(i,a,b) for (int i=a; i<=b; i++)
#define iter(c,x) for(x::iterator it=c.begin(); it!=c.end(); it++)
#define vec(x) vector< x >
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define sqr(x) 1LL*(x)*(x)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define size(x) (int)(x).size()
#define read(x) int x; scanf("%d",&x);
#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<size(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif

using namespace std;

typedef long long ll;

const int INF = 999999999;
const long long INFL = 99999999999999999LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

bool win[110][110];

int main()
{
    #ifdef DEBUG
    freopen("B.txt","r",stdin);
    //freopen("","w",stdout);
    #endif

    /*for0(i,2) {
        for0(j,2)
            win[i][j] = 0;
    }

    for (int s=2; s<=100; s++) {
        for (int a=0; a<=s; a++) {
            int b = s-a;
            //pr(a) pr(b) nl
            bool best = 0;
            for (int mv=2; mv<=a; mv+=2) {
                best = best || !win[a-mv][b+mv/2];
            }
            for (int mv=2; mv<=b; mv+=2) {
                best = best || !win[b-mv][a+mv/2];
            }
            win[a][b] = best;
        }
    }
    print2D(win,10,10);*/

    read(a); read(b);
    /*if (a == b) {
        cout<<"Brown"<<endl;
    }
    else if (a%2 == 0 && b==a+1) {
        cout<<"Brown"<<endl;
    }
    else if (a%2 == 1 && b==a-1) {
        cout<<"Brown"<<endl;
    }
    else {
        cout<<"Alice"<<endl;
    }*/

    if (fabs(a-b) <= 1) {
        cout<<"Brown"<<endl;
    }
    else {
        cout<<"Alice"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define tc int t; cin>>t; while(t--)
#define fora(i,n) for(int i=0;i<n;i++)
#define forb(i,a,n) for(int i=a;i<n;i++)
#define mod 1000000007

template<class T> T power(T N,T P){ return (P==0)?  1: N*power(N,P-1);}

int32_t main()
{
    fastio

    string s,t;
    cin>>s>>t;
   int cnt=0;
    fora(i,s.length())
    {
    	cnt+=(s[i]!=t[i]);
    }


    		
cout<<cnt;

    return 0;


}

Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
int main(){

  double a,b,c,d,e,f;

  while(cin >> a){
    cin >> b >> c >> d >> e >> f;
    
    if(c*e==f*b||a*e==d*b) printf("0.000 ");
    else printf("%.3f ",(c*e-f*b)/(a*e-d*b));
    if(c*d==f*a||b*d==e*a) printf("0.000\n");
    else printf("%.3f\n",(c*d-f*a)/(b*d-e*a));
  }

  return (0);
}

Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <random>

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

using namespace std;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

#define INF 1000000

ll evalNow(vector<vector<int>>& s, vector<int>& c, vector<int>& t, int d, vector<int> last) {
    ll ans = 0;
    ans += s[d][t[d]-1];
    last[t[d]-1] = d+1;
    rep(j, 26) {
        ans -= c[j]*(d+1 - last[j]);
    }
    return ans;
}

ll evalAll(vector<vector<int>>& s, vector<int>& c, vector<int>& t, int d) {
    ll ans = 0;
    vector<int> last(26,0);
    rep(i, d) {
        ans += s[i][t[i]-1];
        last[t[i]-1] = i+1;
        rep(j, 26) {
            ans -= c[j]*(i+1 - last[j]);
        }
    }
    return ans;
}

int main(){
    int d; cin >> d;
    vector<int> c(26);
    rep(i, 26) {
        cin >> c[i];
    }
    vector<vector<int>> s(d, vector<int>(26,0));
    rep(i, d) {
        rep(j, 26) {
            cin >> s[i][j];
        }
    }
    vector<int> t(d);
    ll ans = 0;
    vector<int> last(26,0);

    rep(i, d) {
        ll tmpmax = - (1LL << 60);
        ll candidate = -1;
        rep(j, 26) {
            t[i] = j+1;
            if(tmpmax < evalNow(s,c,t,i,last)) {
                tmpmax = evalNow(s,c,t,i,last);
                candidate = j+1;
            }
        }
        last[t[i]-1] = i + 1;
        t[i] = candidate;
    }

    std::random_device rnd;     // 非決定的な乱数生成器を生成
    std::mt19937 mt(rnd());     //  メルセンヌ・ツイスタの32ビット版、引数は初期シード値
    std::uniform_int_distribution<> randd(0, d-1);
    std::uniform_int_distribution<> rand26(0, 25);

    //この時点でtはgreedy
    // rep(x, 1000) {
    //     ll candidate;
    //     int i = randd(mt);
    //     ll tmpmax = evalAll(s,c,t,d);
    //     rep(j, 26) {
    //         t[i] = j+1;
    //         ll tmp = evalAll(s,c,t,d);
    //         if(tmpmax < tmp) {
    //             tmpmax = tmp;
    //             candidate = j+1;
    //         }
    //     }
    //     t[i] = candidate;
    // }

    ll tmpmax = evalAll(s,c,t,d);

    double start,end;
    start = 20000;
    end = 0;

    int loop = 20000;

    rep(x, loop) {
        int i = randd(mt);
        int j = rand26(mt);
        int original = t[i];
        t[i] = j+1;
        ll tmp = evalAll(s,c,t,d);
        if(tmpmax < tmp) {
            tmpmax = tmp;
        } else {
            double temp = start + (end - start)*x/loop;
            double prob = exp((tmpmax-tmp)/temp);
            ll diff = tmpmax - tmp;
            if (prob > (rand()%INF)/(double)INF) {
                t[i] = original;
            }
        }
    }


    rep(i, d) {
        cout << t[i] << endl;
    }
}


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

struct ModInt {
    using M = ModInt;

    static vector<M> fact, finv;
    static long long MOD;
    long long v;

    // normalize: [-MOD, MOD**2] -> [0, MOD)
    ModInt(const long long _v = 0) : v((_v < 0) ? _v % MOD + MOD : _v % MOD) {}

    M operator+(const M& x) const { return M(v + x.v); }
    M operator-(const M& x) const { return M(v - x.v); }
    M operator*(const M& x) const { return M(v * x.v); }
    M operator/(const M& x) const { return M(v * x.inv().v); }
    M& operator+=(const M& x) { return *this = *this + x; }
    M& operator-=(const M& x) { return *this = *this - x; }
    M& operator*=(const M& x) { return *this = *this * x; }
    M& operator/=(const M& x) { return *this = *this / x; }
    bool operator==(const M& x) const { return v == x.v; }
    bool operator!=(const M& x) const { return v != x.v; }
    bool operator<(const M& x) const { return v < x.v; }
    friend istream& operator>>(istream& input, M& x) {
        return input >> x.v, x = M(x), input;
    }
    friend ostream& operator<<(ostream& output, const M& x) {
        return output << x.v;
    }
    inline M pow(long long n) const {
        M x(v), res(1);
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    inline M inv() const { return this->pow(MOD - 2); }
    static void build(int n) {
        fact.assign(n + 1, 1);
        for (int i = 1; i < n + 1; i++) fact[i] = fact[i - 1] * M(i);
        finv.assign(n + 1, fact[n].inv());
        for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * M(i);
    }
    static M comb(int n, int k) {
        if (n < k || k < 0) return M(0);
        return fact[n] * finv[n - k] * finv[k];
    }
    static M extgcd(int a, int b, int& x, int& y) {
        M d(a);
        if (b) {
            d = extgcd(b, a % b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1;
            y = 0;
        }
        return d;
    }
};
vector<ModInt> ModInt::fact = vector<ModInt>();
vector<ModInt> ModInt::finv = vector<ModInt>();
long long ModInt::MOD = 1e9 + 7;

int main() {
    int n, k;
    cin >> n >> k;
    ModInt::build(n);
    vector<ModInt> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(begin(a), end(a));
    ModInt ans = 0;
    for (int i = k - 1; i < n; i++) {
        ans += (a[i] - a[n - i - 1]) * ModInt::comb(i, k - 1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
#include<string.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

ll dp[3000][3000] = {};
ll a[3000];

ll max(ll a,ll b){
	return a>=b?a:b;
}
ll min(ll a,ll b){
	return a<=b?a:b;
}

ll rec(int i, int j){
	if(i>j) return 0;
	if(i==j) return a[i];
	if(i+1==j) return max(a[i],a[j]);
	ll& ans = dp[i][j];
	if(ans!=-1)return ans;

	ans = max(a[i] + min(rec(i+1,j-1),rec(i+2,j)), a[j] + min(rec(i+1,j-1),rec(i,j-2)) );
	return ans;

}


int main(){
	memset(dp,-1,sizeof(dp));
	int n;
	cin >> n;
	ll sum = 0;
	for(int i=0;i < n ; ++i){
		cin >> a[i];
		sum+= a[i];
	}

	ll X = rec(0,n-1);
	ll Y = sum-X;

	cout << X-Y << endl;

}

Measured memory_bytes: 70656
#include <stack>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <iomanip>
using namespace std;
int main(){
    std::stack<int> stack;
    int n;
    cin >> n;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        if(i%3 != 0 && i%5 != 0){
            ans += i;
        }
    }
    cout << ans << endl; 
    return 0;
}
    



Measured memory_bytes: 3632
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let n = read::<i64>();
  let a = read::<i64>();
  let b = read::<i64>();

  println!("{}", if n * a < b { n * a } else { b });
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

    int N; cin >> N; string S; cin >> S;
    int ans = 1;
    rep(i,N-1){
        if(S[i+1] != S[i]) ans++;
    }
    cout << ans << endl;

}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int h, w;
string s[500];

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

void dfs(int y, int x, ll &b_num, ll &w_num)
{
  check[y][x] = true;
  for (int i = 0; i < 4; ++i)
  {
    int ny = y + dy[i], nx = x + dx[i];
    if (0 <= nx && nx < w && 0 <= ny && ny < h && !check[ny][nx] && s[ny][nx] != s[y][x])
    {
      if (s[ny][nx] == '#')
        b_num++;
      else
        w_num++;
      dfs(ny, nx, b_num, w_num);
    }
  }
  return;
}

int main()
{
  cin >> h >> w;
  for (int i = 0; i < h; ++i)
    cin >> s[i];

  ll ans = 0;
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      if (!check[i][j])
      {
        ll b_num = 0, w_num = 0;
        if (s[i][j] == '#')
          b_num++;
        else
          w_num++;
        dfs(i, j, b_num, w_num);
        ans += b_num * w_num;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 20608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int main()
{
    ll a,b,n;
    scanf("%lld%lld%lld",&a,&b,&n);
    cout<<a*min((b-1),n)/b<<endl;
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define EPS (1e-7)
#define INF 1000000009
#define PI (acos(-1))


int main(){
    string s;
    int q;
    cin >> s;
    cin >> q;
    string p="",b="";
    int rev = 0;
    rep(i,q){
        int type;
        cin >> type;
        if (type==2){
            int f;
            char c;
            cin >> f >> c;
            if (f==1){
                if (rev%2==0) p += c;
                else b += c;
            }
            else {
                if (rev%2==0) b += c;
                else p += c;
            }
        }
        else rev += 1;
    }
    reverse(p.begin(),p.end());
    s = p + s + b;
    if (rev%2==1) reverse(s.begin(),s.end());
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 1348
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N = z()
A = zz()
dic = defaultdict(int)
for a in A:
    dic[a] += 1
ans = 0
for key in dic:
    if (dic[key] >= key):
        # kouho.append(dic[key]-key)
        ans += (dic[key]-key)
    else:
        ans += dic[key]
print(ans)


Measured memory_bytes: 39432
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned long;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        ULL a, b; cin >> a >> b;
        cout << (a / b) << " " << (a % b);
        double ad = a, bd = b;
        cout << " " << (ad / bd) << endl;
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}



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

int main() {
    int N, L;
    string ans;

    cin >> N >> L;

    string S[N];
    for (int i = 0; i < N; i++){
        cin >> S[i];
    }
    
    sort(S, S + N);

    for (int i = 0; i < N; i++){
        ans += S[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
type Helix = "A" | "C" | "G" | "T";
const HelixCouple: Helix[] = ["A", "T", "C", "G"];
const getOtherHelix = function(helix: Helix) {
  const index = HelixCouple.indexOf(helix);
  return HelixCouple[index + (index%2 == 0 ? 1 : -1)]
}

const entryPoint = function(args: string[]) {
  console.log(getOtherHelix(args[0] as Helix));
}

const getStandardInput = function() {
  process.stdin.resume();
  process.stdin.setEncoding('utf8');
  let inputString = '';
  process.stdin.on('data', function(chunk) {
      inputString += chunk;
  });
  process.stdin.on('end', () => entryPoint(inputString.split("\n")));
}();

Measured memory_bytes: 7500
a, b, c = [int(x) for x in input().strip().split()]

def f(a, b, c, count):
    if a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
        count += 1
        return f(a/2+b/2, c/2+b/2, a/2+c/2, count)
    else:
        return count

if a == b and b == c and a % 2 == 0:
    print(-1)
else:
    print(f(a, b, c, 0))

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

int main(){
  int q,n,cnt;
  cin >> q;
  while(q--){
    cin >> n;
    cnt = 0;
    for(;;){
      int m = -1, k = 10;
      if(n<10){
	cout << cnt << endl;
	break;
      }
      for(int i=0;i<5;i++){
	m = max(m,(n/k)*(n%k));
	k *= 10;
      }
      n = m; cnt++;
    }
  }
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
vector<pair<int, int>> seg;
int query(int node, int l, int r, int q_l, int q_r)
{
	if (q_l > r || q_r < l)
		return 0;
	if (seg[node].second != 0)
	{
		if (l == r)
		{
			seg[node].first = max(seg[node].first, seg[node].second);
			seg[node].second = 0;
		}
		else
		{
			seg[node].first = max(seg[node].first, seg[node].second);
			seg[node * 2].second = max(seg[node * 2].second, seg[node].second);
			seg[node * 2 + 1].second = max(seg[node * 2 + 1].second, seg[node].second);
			seg[node].second = 0;
		}
	}
	if (l >= q_l && r <= q_r)
		return seg[node].first;
	return max(query(node * 2, l, (l + r) / 2, q_l, q_r), query(node * 2 + 1, (l + r) / 2 + 1, r, q_l, q_r));
}
void update(int node, int l, int r, int q_l, int q_r, int val)
{
	if (q_l > r || q_r < l)
		return;
	if (seg[node].second != 0)
	{
		if (l == r)
		{
			seg[node].first = max(seg[node].first, seg[node].second);
			seg[node].second = 0;
		}
		else
		{
			seg[node].first = max(seg[node].first, seg[node].second);
			seg[node * 2].second = max(seg[node * 2].second, seg[node].second);
			seg[node * 2 + 1].second = max(seg[node * 2 + 1].second, seg[node].second);
			seg[node].second = 0;
		}
	}
	if (l >= q_l && r <= q_r)
	{
		seg[node].first = max(seg[node].first, val);
		if (l != r)
		{
			seg[node * 2].second = max(seg[node * 2].second, seg[node].second);
			seg[node * 2 + 1].second = max(seg[node * 2 + 1].second, seg[node].second);
			seg[node].second = 0;
		}
		return;
	}
	update(2 * node, l, (l + r) / 2, q_l, q_r, val);
	update(2 * node + 1, 1 + (l + r) / 2, r, q_l, q_r, val);
	seg[node].first = max(seg[node * 2].first, seg[node * 2 + 1].first);
	return;
}
void solve()
{
	int n, k;
	cin >> n >> k;
	int maxl = 300000 * 4 + 1;
	vector<int> arr(n);
	for (int c = 0; c < n; c++)
		cin >> arr[c];
	seg.assign(maxl, make_pair(0, 0));
	int ans = 1;
	update(1, 0, 300000, arr[0], arr[0], 1);
	for (int c = 1; c < n; c++)
	{
		int a = query(1, 0, 300000, max(0, arr[c] - k), min(300000, arr[c] + k));
		ans = max(ans, a + 1);
		update(1, 0, 300000, arr[c], arr[c], a + 1);
	}
	cout << ans << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	t = 1;
	for (; t > 0; t--)
		solve();
}

Measured memory_bytes: 13740
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n];
        for(int i = 0; i < n; i++)
        	d[i] = sc.nextInt();

        long hp = 0;

        for(int i = 0; i < n-1; i++) {
        	for(int j = i+1; j < n; j++) {
        		hp += d[i] * d[j];
        	}
        }

        System.out.println(hp);

    }


}

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

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

    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes";
    } else {
        cout << "No";
    }
}

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

signed main()
{   
    int N; cin>>N;
    vector<pair<int,int>> p(N);
    for(int i=0;i<N;i++){
        int x,y; cin>>x>>y;
        p[i]=make_pair(x,y);
    }
    sort(p.begin(),p.end());

    map<pair<int,int>,int> cnt;
    for(int i=0;i<N-1;i++) for(int j=i+1;j<N;j++){
        int dx=p[j].first-p[i].first;
        int dy=p[j].second-p[i].second;
        cnt[make_pair(dx,dy)]++;
    }

    int Max=0;
    for(auto x:cnt){
        //cout<<x.first.first<<' '<<x.first.second<<' '<<x.second<<endl;
        Max=max(Max,x.second);
    }
    cout<<N-Max<<endl;
}


Measured memory_bytes: 384
// AOJ 1068: School of Killifish
// 2017.12.14 bal4u@uu

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

#define INF 0x7fffffff

int pool[8000002];
int **seg;
int h, w;
int r1, c1, r2, c2, g;
char buf[10000000], *p;

int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	p++;
	return n;
}

void update(int r, int c, int x)
{
	int c2, t, a;

	r += h - 1;
	c += w - 1;
	seg[r][c] = x;

	while (r >= 0) {
		c2 = c;
		while (c2) {
			if (!(c2 & 1)) c2--;
			t = c2, c2 >>= 1;
			a = seg[r][t++]; if (a > seg[r][t]) a = seg[r][t];
			seg[r][c2] = a;
		}
		if (r == 0) break;

		if (!(r & 1)) r--;
		t = r, r >>= 1;
		a = seg[t++][c]; if (a > seg[t][c]) a = seg[t][c];
		seg[r][c] = a;
	}
}
 
int query2(int l, int r, int k)
{
	int m, lmin, rmin;

	if (c2 <= l || r <= c1) return INF;
    if (c1 <= l && r <= c2) return seg[g][k];
     
	k <<= 1, m = (l + r) >> 1;
    lmin = query2(l, m, ++k);
    rmin = query2(m, r, ++k);
    if (lmin > rmin) lmin = rmin; 
    return lmin;
}
 
int query(int l, int r, int k)
{
	int m, lmin, rmin;

    if (r2 <= l || r <= r1) return INF;
    if (r1 <= l && r <= r2) { g = k; return query2(0, w, 0); }
    
	k <<= 1, m = (l + r) >> 1;
    lmin = query(l, m, ++k);
    rmin = query(m, r, ++k);
    if (lmin > rmin) lmin = rmin;
    return lmin;
}
 
int main()
{
	int R, C, Q, h2, w2, r, c, i;

    while (fgets(p=buf, 40, stdin) && *p != '0') {
		R = getint(), C = getint(), Q = getint();

		h = w = 1;
		while (h < R) h <<= 1;
		while (w < C) w <<= 1;

		h2 = (h << 1) - 1, w2 = (w << 1) - 1;

//		memset(pool, 0, sizeof(pool));
		seg = malloc(h2 * sizeof(int *));
		for (c = r = 0; r < h2; r++, c += w2) seg[r] = pool + c;

        for (r = 0; r < R; r++) {
			fgets(p=buf, 10000000, stdin);
			for (c = 0; c < C; c++)	update(r, c, getint());
        }

        for (i = 0; i < Q; i++) {
			fgets(p=buf, 100, stdin);
			r1 = getint(), c1 = getint(), r2 = getint()+1, c2 = getint()+1;
            printf("%d\n", query(0, h, 0));
        }

		free(seg);
    }
    return 0;
}

Measured memory_bytes: 27608
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int H, W, K;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> H >> W >> K;
  for (int a=0; a<=W; a++) {
    for (int b=0; b<=H; b++) {
      int x = a*b + (W-a)*(H-b);
      if (x == K) {
        cout << "Yes\n";
        return 0;
      }
    }
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

ll calc(ll x) {
  ll c=1;
  while(x) {
    ll t=__builtin_popcount(x);
    x%=t;
    c++;
  }
  return c;
}

void Main() {
  ll n;
  string s;
  cin >> n >> s;
  reverse(all(s));
  ll c=0;
  rep(i,n) {
    if(s[i]=='1') c++;
  }
  map<ll,ll> m;
  vector<ll> t[2];
  t[0].pb(1);
  t[1].pb(1);
  rep(i,n) {
    if(s[i]=='1') {
      m[c-1]+=t[0].back();
      if(c-1>1) m[c-1]%=c-1;
      m[c+1]+=t[1].back();
      m[c+1]%=c+1;
    }
    if(c-1>1) {
      ll x=t[0].back();
      t[0].pb(x*2%(c-1));
    }
    ll x=t[1].back();
    t[1].pb(x*2%(c+1));
  }
  rrep(i,n) {
    ll d;
    if(s[i]=='1') {
      if(c-1==0) {
        pr(0);
        continue;
      }
      d=m[c-1];
      d=(d-t[0][i]+(c-1))%(c-1);
    } else {
      d=m[c+1];
      d=(d+t[1][i]+(c+1))%(c+1);
    }
    pr(calc(d));
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

int main() {
    int n;
    int ans = 0;
    string s;
    cin >> n >> s;
    map <int, int> m1;
    map <int, int> m2;
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) m1[s[j]]++;    
        for(int j = i; j < n; j++) m2[s[j]]++;
        int tmp = 0;
        for(int j = 0; j < 26; j++) if(m1[j + 'a'] >= 1 && m2[j + 'a'] >= 1) tmp++;            
        ans = max(ans , tmp);
        m1.clear();
        m2.clear();      
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
def main():
    NAB = list(map(int,input().split()))




    # tm = NAB[0] // (NAB[1] + NAB[2]) * NAB[1]
    # amari = NAB[0] % (NAB[1] + NAB[2])
    # tm += min(amari,NAB[1])
    #
    # print(tm)

    # b = 0
    #
    # tm = NAB[0]//(NAB[1]+NAB[2])
    # amari = NAB[0] % (NAB[1]+NAB[2])
    #
    # # print(tm)
    # if NAB[1] < amari:
    #     b = (tm*NAB[1])+ NAB[1]
    # else:
    #     b = (tm*NAB[1])+ amari
    #
    # print(b)


    b = 0
    # if NAB[1] == 0:
    #     b = 0
    # elif NAB[2] == 0:
    #     b = NAB[1]

    if NAB[0] < NAB[1]+NAB[2]:
        if NAB[0] < NAB[1]:
            b = NAB[0]
        else:
            b = NAB[1]

    else:
        tm = NAB[0]//(NAB[1]+NAB[2])
        amari = NAB[0] % (NAB[1]+NAB[2])

        # print(tm)
        if NAB[1] < amari:
            b = (tm*NAB[1])+ NAB[1]
        else:
            b = (tm*NAB[1])+ amari

    print(b)





if __name__ == '__main__':
    main()

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

int main() {
	int H,W,i,j;
	while(1){
	cin >> H >> W;
	if(H == 0 && W == 0)break;
	for(i=0;i<H;i++){
		for(j=0;j<W;j++){
			if(j==0 || j== W-1 || i==0 || i==H-1){
			cout << "#";
			}
			else{
			 cout << ".";
			}
		}
		cout << endl;
	}
	cout << endl;
	}
	return 0;
}

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

int main(){
  string S;
  cin >>S;
  int len = S.size();
  bool TF = true;
  for(int i=0;i<len;i++){
    if ((i%2 ==0)&((S.at(i)!='R')&(S.at(i)!='U')&(S.at(i)!='D'))){
      TF = false;
    }
    if ((i%2 ==1)&((S.at(i)!='L')&(S.at(i)!='U')&(S.at(i)!='D'))){
      TF = false;
    }
  }
  if(TF){
    cout <<"Yes"<<endl;
  }
  else {
    cout <<"No"<<endl;
  }
}


Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))
#print(A)
S = set(A)
#print(len(S))
if len(S) <= K:
  print(0)
else:
  ch = len(S) - K
  INF = 10**7
  X = [INF] * (N + 1)
  for i in range(N):
    if X[A[i]] == INF:
      X[A[i]] = 1
    else:
      X[A[i]] += 1 
  X.sort()
  print(sum(X[:ch]))

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
using ll = long long;
typedef long long ll;

int gcd(int m, int n);
int lcm(int a, int b);

int main(void){
    using namespace  std;
    int A, B, C;
    cin >> A >> B >> C;
    bool isPoor = (A == B && B != C) || (A == C && A != B) || (B == C && A != B);
    cout << (isPoor ? "Yes" : "No" ) << endl;

    return 0;
}

int gcd(int m, int n){
    int r;
    do{
        r = m % n;
        m = n;
        n = r;
    } while (r != 0);

    return m;
}

int lcm(int a, int b){
    long temp = a * b;
    return temp / gcd(a, b);
}


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

void insertionSort(long int A[], long int n, int g, int& count){
  int j,v;
  for(int i=g; i<n; i++){
    j=i-g;
    v = A[i];
    while(1){
      if(A[j] <= v){
        for(int k=i; k>=j+g; k-=g){
          //count++;
          A[k] = A[k-g];
        }
        A[j+g] = v;
        break;
      }
      j -= g;
      count++;
      if(j<0){
        for(int k=i; k>=j+g+g; k-=g){
          A[k] = A[k-g];
        }
        A[j+g] = v;
        break;
      }
    }
  }
}

void shellSort(long int A[], long int n){
  int count =0;
  int n_copy;
  int m = 0;
  int G[100];
  n_copy = n;
  G[0] = 1;
  for(int i=1; i<100; i++){
    G[i] = (G[i-1]*3) +1;
    m++;
    if(G[i] > n){
      break;
    }
  }
  cout <<m << endl;
  for(int i=0; i<m; i++){
    cout << G[m-1-i] << " ";
    insertionSort(A, n_copy, G[m-1-i], count);
  }
  cout << endl;
  cout << count << endl;
}

int main(){
  long int n;
  long int A[1000000];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> A[i];
  }
  shellSort(A, n);
  for(int i=0; i<n; i++){
     cout << A[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 10908
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

def printA(A):
    N = len(A)
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート
# N = N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

def dist(A, B):
    d = 0
    for i in range(len(A)):
        d += (A[i]-B[i])**2            
    d = d**(1/2)
    return d

def get_input():
    N = []
    while True:
        try:
            N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
        except EOFError:
            break
    return N

while True:
    D, W, H = [int(x) for x in input().split()]
    if D==0 and W==0 and H==0:
        break
    N = int(input())

    for i in range(N):
        r = int(input())
        r1 = (D*D+W*W)**(1/2)/2
        r2 = (W*W+H*H)**(1/2)/2
        r3 = (H*H+D*D)**(1/2)/2
        rm = min([r1,r2,r3])
        if r > rm:
            print('OK')
        else:
            print('NA')



Measured memory_bytes: 5728
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(int argc,char** argv){
  int N;
  cin >> N;
  int f = 0;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    f += a;
  }

  cout << f - N << endl;
  return 0;
}


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

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

  vector<int> x(n), y(n), t(n);
  rep(i, n) cin >> x[i] >> y[i];
  rep(i, n) t[i] = i;

  double sum = 0;
  do{
    rep(i, n-1){
      double l = sqrt(pow(x[t[i]]-x[t[i+1]], 2) + pow(y[t[i]]-y[t[i+1]], 2));
      sum += l;
    }
  }while(next_permutation(t.begin(), t.end()));

  int kaijo = 1;
  rep(i, n) kaijo *= i+1;

  cout << fixed << setprecision(10) << sum / kaijo << endl;

}


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

int main() {
  
  int N,T,A;
  cin >> N >> T >> A;
  
  vector<int> H(N);
  for(int i=0; i<N; i++){
    cin >> H.at(i);
  }
  
  int tem = 0;
  int c = 100000000;
  int ans = 0;
  for(int i=0; i<N; i++){
    tem = (T * 1000 - H.at(i) * 6) - A * 1000;
    if(tem < 0){
      tem = -tem;
    }
    
    if(c > tem){
      c = tem;
      ans = i+1;
    }
    
    
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ub upper_bound
#define int long long
#define vbe(sdk) sdk.begin(), sdk.end()
#define pb push_back
#define loop(i, a, b) for (int i = a; i < b; ++i)
#define rloop(i, a, b) for (int i = a; i >= b; --i)
#define mp make_pair
#define mod 1000000007
#define endl '\n'
#define vvll vector<vector<int>>
#define vll vector<int>
#define mint map<int, int>
#define arry(x) (int)x.size()
#define sll set<int>
#define pll pair<int, int>
#define F first
#define S second
#define pi 3.14159265358979323846
using namespace std;
const int MAX = 100001;


void solve()
{
    char c;
    cin>>c;
    if(c >= 'A' && c<='Z')
    {
        cout<<"A\n";
    }
    else
    {
        cout<<"a\n";
    }
    
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #else
    // // online submission
    // #endif


    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define N 500010

// fenwick tree
int f[N];
void init(){for(int i=0;i<=N;i++)f[i]=0;}

void add(int i, int x){for(;i<=N;i+=i&-i)f[i]+=x;}

int sum(int i)
{
    int ret=0;
    for(;i>0;i-=i&-i)ret+=f[i];
    return ret;
}

int rangesum(int l, int r){return sum(r)-sum(l-1);}
// fenwick tree

int c[N];
vector<int> ql[N],qid[N];

int ans[N];

int a[N];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,q;
    cin>>n>>q;

    for(int i=0;i<n;i++)cin>>c[i];

    for(int i=0;i<q;i++)
    {
        int l,r;
        cin>>l>>r;

        ql[r].push_back(l);
        qid[r].push_back(i);
    }

    for(int i=1;i<=n;i++)
    {
        if(a[c[i-1]]>0)add(a[c[i-1]],-1);
        add(i,1);
        a[c[i-1]]=i;

        for(int j=0;j<ql[i].size();j++)
        {
            ans[qid[i][j]]=rangesum(ql[i][j],i);
        }
    }

    for(int i=0;i<q;i++)cout<<ans[i]<<endl;

    return 0;
}



Measured memory_bytes: 52976
moji = "abcdefghi".split("")
numbers = gets.chomp.split.map(&:to_i)
missing = (1..9).to_a
h = {}
unknown = []
moji.zip(numbers){|m, n|
    if n != -1
        h[m] = n
        missing.delete n
    else
        unknown << m
    end
}
answer = 0
missing.permutation(missing.length){|arr|
    unknown.zip(arr){|m, n| h[m] = n}
    answer += 1 if h["a"] + h["c"] + h["f"] + 10 * (h["b"] + h["e"]) + 100 * h["d"] == 100 * h["g"] + 10 * h["h"] + h["i"]
}
puts answer



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

int main() {
  string s;
  bool ans=true;
  cin >> s;
  for(int i=0;i<3;i++){
    if(s[i]==s[i+1]){
      ans=false;
    }
  }
  if(ans){
    cout << "Good" << endl;
  }
  else{
    cout << "Bad" << endl;
  }
      
}


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

using namespace std;

int main()
{
    long long n, a, sum;
    cin >> n;
    cin >> sum;
    for (int i = 1; i < n; i++) {
        cin >> a;
        if (log10(a)+ log10(sum) >= 19 || a * sum > 1000000000000000000) {
            for (int j = i + 1; j < n; j++) {
                cin >> a;
                if (a == 0) {
                    cout << 0 << endl;
                    return 0;
                }
            }
            cout << -1 << endl;
            return 0;
        }
        sum *= a;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3964