akhauriyash/Code-Regression huggingface dataset:
n = int(input())
l = list(map(int, input().split()))
l.sort()
lt = [n] * (l[n-1] + l[n-2] + 1)
ans = 0
for i in range(l[0]+1):
    lt[i] = 0
length = l[0]
for i in range(1, n):
  if length < l[i]:
    for j in range(length+1, l[i]+1):
      lt[j] = i
    length = l[i]
for i in range(n):
  for j in range(i+1, n):
    right = l[i]+l[j]
    ans += max(0,  lt[right] - (j+1))
print(ans)

Measured memory_bytes: 3188
def prime(m):
  N = range(1,m+2, 2)
  r = int(m**.5)
  h = len(N)
  N[0] = 0
  for i in range(h):
    x = N[i]
    if x>r: break
    if x and i+x<h: N[i+x:h:x]=[0] * ((h-1-i-x)/x+1)
  N[0] = 2
  return filter(None, N)

P = prime(10000)
x = [a for a,b in zip(P[1:],P[:-2]) if a-b==2]
while 1:
  n = input()
  if n==0: break
  for e in x:
    if e>n: break
    a = e
  print a-2,a

Measured memory_bytes: 4628
#include <bits/stdc++.h>
using namespace std;
queue<map<string ,int > >d;

map<string ,int > tag;
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        string a;
        int b;
        for(int i=0;i<n;i++)
        {
            cin>>a>>b;
            map<string ,int > p;
            p[a]=b;
            d.push(p);
        }

        int sum=0;
        map<string ,int > x;
        while(d.size())
        {
            x=d.front();
            for(map<string,int >::iterator i=x.begin();i!=x.end();i++)
            {
                int s=i->second;
                string ss;
                ss=i->first;

                sum+=min(s,m);
                tag[ss]=sum;

                if(s>m)
                {
                    map<string ,int > xx;
                    xx[ss]=s-m;
                    d.push(xx);
                }
                else cout<<i->first<<' '<<sum<<endl;
            }
            d.pop();
           // cout<<x->first<<endl;
            //sum+=min(x.second,m);
        }

    }

}

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

int main() {
    int m, d, ans = 0;
    cin >> m >> d;
    for (int i = 1; i <= m; i++) {
        for (int j = 10; j <= d; j++) {
            if (j % 10 < 2 || j / 10 < 2) continue;
            if (i == (j % 10) * (j / 10)) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
struct edge {
  ll to, cost;
};

// 最大公約数
int gcd(int a, int b) {
  if (a % b == 0) {
    return(b);
  } else {
    return(gcd(b, a % b));
  }
}

int main() {
  int K; cin >> K;
  ll ans = 0;
  REP(i, K) {
    REP(j, K) {
      REP(k, K) {
        ans += gcd((i + 1), gcd((j + 1), (k + 1)));
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3600
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = long.Parse(Console.ReadLine());
        long[] a = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long[] t = new long[n + 2];
        t[0] = 0;
        t[n + 1] = 0;
        for (int i = 1; i < n+1; i++)
        {
            t[i] = a[i - 1];
        }

        long sum = 0;
        for (int i = 0; i < t.Length - 1; i++)
        {
            sum += Math.Abs(t[i + 1] - t[i]);
        }

        long ans = 0;
        for (int i = 1; i < t.Length - 1; i++)
        {
            ans = sum - Math.Abs(t[i] - t[i-1]) - Math.Abs(t[i + 1] - t[i]) + Math.Abs(t[i + 1] - t[i-1]);
            Console.WriteLine(ans);
        }

    }
}


Measured memory_bytes: 27100
#include<stdio.h>
int main(void){
  int n;
  scanf("%d",&n);
  switch(n%10){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      printf("hon");
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      printf("pon");
      break;
    case 3:
      printf("bon");
      break;
  }
  return 0;
}

Measured memory_bytes: 1736
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x:x[1])

now = 0
for i in range(n):
    now += a[i][0]
    if (now > a[i][1]):
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 53600
n, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]
A = [x+y for x, y in zip(X, Y)]
B = [x-y for x, y in zip(X, Y)]
A.sort()
B.sort()
print(max(A[-1] - A[0], B[-1] - B[0]))

Measured memory_bytes: 55028
import bisect

N=int(input())
A=list(map(int,input().split()))

inc=[[A[0],0]]
for i in range(1,N):
    if A[i]>inc[-1][0]:
        inc.append([A[i],i])

n=len(inc)
test=inc[:n-1]
query=[[] for i in range(n)]
for i in range(0,N):
    r=bisect.bisect_left(test,[A[i],i])
    query[r].append(A[i])

ans=[0 for i in range(N)]
count=0
for i in range(n-1,0,-1):
    fr=inc[i][0]
    to=inc[i-1][0]
    val=count*(fr-to)+sum(query[i])-to*len(query[i])
    ans[inc[i][1]]=val
    count+=len(query[i])

fr=inc[0][0]
to=0
val=count*(fr-to)+sum(query[0])-to*len(query[0])
ans[0]=val

for i in range(N):
    print(ans[i])

Measured memory_bytes: 86636
#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=(a); i>=(b); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define CEIL(n, m) ceil(n/pow(10.0, m))*pow(10.0, m)
#define FLOOR(n, m) floor(n/pow(10.0, m))*pow(10.0, m)
#define ROUND(n, m) round(n/pow(10.0, m))*pow(10.0, m)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define llong long long
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve()
{

  int n, k;
  cin >> n >> k;
  vector<int> d(n); REP(i, n) cin >> d[i];

  int ans=n;
  while(1) {
    int tmp=ans;
    bool flg=false;
    while(tmp>0) {
      REP(i, k) {
        if ((tmp%10)==d[i]) {
          flg=true;
          break;
        }
      }
      if (flg) {
        ans++;
        break;
      }
      tmp/=10;
    }
    if (!flg) break;
  }

  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = input().strip()

if N % 2 == 1:
    print("No")
else:
    for i in range(N//2):
        if S[i] != S[i+N//2]:
            print("No")
            sys.exit()
    
    print("Yes")



Measured memory_bytes: 2940
#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 = (s); i < (int)(n); i++)
typedef long long ll;
#define all(x) (x).begin(),(x).end()
int INF = 1000000000;

int main() {
  int A, B, C, D; cin >> A >> B >> C >> D;
  int s = max(A, C);
  int e = min(B, D);
  if (e > s) {
    cout << e - s << endl;
  }
  else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
//Running median
//keeping max heap for first half and min heap for second half
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
# define M_PI           3.14159265358979323846
ll  P=1000000007;
ll M=P;
ll power(ll a, ll b) {
    if(b == 0) return 1;
    ll x = power(a, b / 2);
    x = (x * x)%M;
    if(b%2) x = (x*a)%M;
    return x;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i,j,k,l,m,n,o,p,q,r,s,t;
    cin>>n;
    long double x=(n);
    x=(2*x*M_PI);
    printf("%.20llf\n",x);
    return 0;
}


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

const ll mod = 1000000007;
const int INF = 1001001001;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	ll x, k, d; cin >> x >> k >> d;
	x = abs(x);
	ll cnt = x / d;
	if(cnt >= k) cout << x - d * k << endl;
	else{
		ll now = x - cnt * d;
		ll res = k - cnt;
		cout << (res % 2 ? abs(now - d) : now);
	}
} 

Measured memory_bytes: 3656
#include <stdio.h>
#include <stdlib.h>

// 絶対値を返す関数
int abs(int num) {
  return (num < 0) ? -num : num;
}

// 配列のn番目までの総和を求める関数
int sumArr(int *arr, int n) {
  int sum = 0;
  int i = 0;
  while (i < n) {
    sum += arr[i++];
  }
  return sum;
}

int main() {
  int n;
  scanf("%d", &n);
  int *warr = malloc(sizeof(int) * n);
  if (warr == NULL) {
    return -1;
  }
  int i;
  for (i = 0; i < n; i++) {
    scanf("%d", warr+i);
  }

  int flag = 1;
  int diff = 10000000;
  for (flag = 1; flag < n; flag++)  {
    if (abs(diff) > abs(sumArr(warr, n) - 2*sumArr(warr, flag))) {
      diff = abs(sumArr(warr, n) - 2*sumArr(warr, flag));
    }
  }
  printf("%d\n", diff);


  return 0;
}


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

int main() {
    int k;
    cin >> k;
    queue<long long int> q;
    for (int i = 1; i < 10; i++){
        q.push(i);
    }
    long long int x,x1;
    for (int i = 0; i < k; i++){
        x=q.front();
        x1=x%10;
        q.pop();
        if(x1!=0)q.push(10*x+x1-1);
        q.push(10*x+x1);
        if(x1!=9)q.push(10*x+x1+1);
    }
    cout <<x<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define debug(...) \
  { cerr << "# " << __VA_ARGS__ << "\n"; }
#else
#define debug(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
typedef unsigned long long ui64;
const i64 MOD = 119 << 23 | 1;
struct hashing {
  static constexpr int dimensions = 4;
  static constexpr int mod = (1u << 31) - 1;
  vector<vector<int>> hashes, p;
  static const vector<int> &get_bases() {
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    static vector<int> bases;
    while (bases.size() < dimensions) {
      bases.emplace_back(uniform_int_distribution<int>((int)1e9, mod - 1)(rng));
    }
    return bases;
  }
  hashing(const vector<int> &s) : hashes(dimensions), p(dimensions) {
    int n = s.size();
    const vector<int> &bases = get_bases();
    for (int d = 0; d < dimensions; ++d) {
      hashes[d].resize(n + 1);
      p[d].resize(n + 1);
      p[d][0] = 1;
      long long base = bases[d];
      for (int i = 0; i < n; i++) {
        hashes[d][i + 1] = (hashes[d][i] * base + s[i]) % mod;
        p[d][i + 1] = p[d][i] * base % mod;
      }
    }
  }
  vector<int> get_hash(int i, int len) {
    vector<int> res;
    for (int d = 0; d < dimensions; ++d) {
      int hash = (int)((hashes[d][i + len] + (long long)hashes[d][i] * (mod - p[d][len])) % mod);
      res.emplace_back(hash);
    }
    return res;
  }
};
class {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), sa(n), sb(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) {
      sa[i] = a[i] ^ a[(i + 1) % n];
      sb[i] = b[i] ^ b[(i + 1) % n];
      sa.push_back(sa[i]);
    }
    hashing A(sa), B(sb);
    for (int i = 0; i < n; ++i) {
      if (A.get_hash(i, n - 1) != B.get_hash(0, n - 1))
        continue;
      int v = a[i] ^ b[0];
      cout << i << ' ' << v << '\n';
    }
  }
} NSPACE;
int main() {
  FPEN;
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  NSPACE.solve();
}

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

const int N = 1e6 + 7;

int prime[N];

void f()
{
	memset(prime, 0, sizeof(prime));
	prime[1] = 1;
	for (int i = 2; i < N; i++)
	{
		if (prime[i] == 1)
			continue;
		for (int j = 2; i * j < N; j ++)
			prime[i * j] = 1;
	}
}
int pre_sum[N];
void init()
{
	memset(pre_sum, 0, sizeof(pre_sum));
	for (int i = 3; i < N; i += 2)
		if (!prime[i] && !prime[(i + 1) / 2])
			pre_sum[i] = 1;
	for (int i = 1; i < N; i++)
		pre_sum[i] += pre_sum[i - 1];
}
int main()
{
	f();
	init();
	int n;
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)
		{
			int l, r;
			cin >> l >> r;
			cout << pre_sum[r] - pre_sum[l - 1] << endl;
		}
	}
}

Measured memory_bytes: 8448
#include <iostream>
using namespace std;
int main(void){
    int n, C, d[30][30], ans = 1e9, u[3][30];
    cin >> n >> C;
    for(int i=0;i<C;i++){
        for(int j=0;j<C;j++){
            cin >> d[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int t;
            cin >> t;
            u[(i+j)%3][--t]++;
        }
    }
    for(int i=0;i<C;i++){
        for(int j=0;j<C;j++){
            if(j == i)continue;
            for(int k=0;k<C;k++){
                int v = 0;
                if(k == j || k == i)continue;
                for(int l=0;l<C;l++){
                    v += u[0][l] * d[l][i];
                    v += u[1][l] * d[l][j];
                    v += u[2][l] * d[l][k];
                }
                ans = min(ans, v);
            } 
        }
    }
    cout << ans << endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001;
const int INFLL=1001001001001001001ll;
const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int calc(vint A,vint B){
    if(A.size()==0)return 0;
    vint xs;
    rep(i,A.size())xs.pb(A[i]);
    sort(all(xs));xs.erase(unique(all(xs)),xs.end());

    rep(i,A.size()){
        A[i]=lower_bound(all(xs),A[i])-xs.begin();
        B[i]=lower_bound(all(xs),B[i])-xs.begin();
    }

    UnionFindTree uf(xs.size());
    rep(i,A.size())uf.unite(A[i],B[i]);

    set<int>s;
    rep(i,A.size())s.insert(uf.find(A[i]));
    return A.size()+s.size();
}

signed main(){
    int N;cin>>N;
    vint A(N),B(N);
    rep(i,N)cin>>A[i];
    rep(i,N)cin>>B[i];

    int a=0;
    rep(i,N)a^=A[i];
    int b=0;
    rep(i,N)b^=B[i];

    A.pb(a);B.pb(b);

    vint latte=A,malta=B;
    sort(all(latte));
    sort(all(malta));

    rep(i,N+1)if(latte[i]!=malta[i]){
        puts("-1");
        return 0;
    }

    vint AA,BB;
    int beet=0;
    rep(i,N+1)if(A[i]!=B[i]){
        AA.pb(A[i]);
        BB.pb(B[i]);
        if(A[i]==B[N])beet=2;
    }

    if(beet==2&&A[N]==B[N])beet--;

    printf("%lld\n",calc(AA,BB)-beet);
    return 0;
}


Measured memory_bytes: 11232
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rusha scanf("%d",&n);rep(i,1,n)scanf("%d",&a[i]);
#define rushb scanf("%d",&t);while(t--)
#define debug(x) cout<<" L-B-W-- "<<x<<" --N-B\n"
#define pb push_back
//#define pii pair<int,int>
#define vii vector<int>
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof a)
#define all(x) (x.begin(),x.end())
#define judgef printf("%s\n",f?"Yes":"No")
#define Judgef printf("%s\n",f?"YES":"NO")
#define sz(x) ((int)(x).size())
#define sf(x) (sizeof(x))
using namespace std;
typedef long long ll;
typedef double db;
const double pai = acos(-1.0);
const double eps = 1e-8;
const int mod=998244353;
//const int mod=1e9+7;
const int inf=1e9+7;
//const ll inf=0x7f7f7f7f1234abcd;
const int maxn=1e5+10;
inline ll ksm(ll x,ll y){ ll res=1; while(y){if(y&1) res=res*x%mod;x=x*x%mod; y>>=1;} return res; }
inline ll inv(ll a,ll p){if(a==1)return 1;return (p-p/a)*inv(p%a,p)%p;}
ll lcm(ll a, ll b) { return a * b / __gcd(a, b); }

int t,n,m,k;
char s[2];
bool ff[4];
bool f=0;
int g[maxn];
char str[maxn];
//struct pp{
//    int i,a,b,c;
//    bool operator <(const pp& d){
//        if(i!=d.i) return i<d.i;
//        if(a!=d.a) return a<d.a;
//        if(b!=d.b) return b<d.b;
//        if(c!=d.c) return c<d.c;
//    }
//};
//map<pp,int> ma;
inline void dfs(int i,int a,int b,int c){
    if(a<0||b<0||c<0) return ;
    if(i==n+1) {
        puts("Yes");
        rep(i,1,n) printf("%c\n",str[i]);
        exit(0);
    }
    //if(ma[{i,a,b,c}]==1) return ;
    if(g[i]==0){
        str[i]='B';
        dfs(i+1,a,b+1,c-1);
        str[i]='C';
        dfs(i+1,a,b-1,c+1);
    }
    if(g[i]==1){
        str[i]='A';
        dfs(i+1,a+1,b,c-1);
        str[i]='C';
        dfs(i+1,a-1,b,c+1);
    }
    if(g[i]==2){
        str[i]='B';
        dfs(i+1,a-1,b+1,c);
        str[i]='A';
        dfs(i+1,a+1,b-1,c);
    }
}
int a,b,c;
int main(){
    scanf("%d%d%d%d",&n,&a,&b,&c);
    rep(i,1,n) {scanf("%*c%c%c",&s[0],&s[1]);memset(ff,0,sizeof ff);ff[s[0]-'A']=1;ff[s[1]-'A']=1;rep(j,0,2) if(ff[j]==0) g[i]=j; }
    ///rep(i,1,n) printf("%d\n",g[i]);
    dfs(1,a,b,c);
    judgef;
    return 0;
}


Measured memory_bytes: 12016
#include<stdio.h>

int main()
{
	int a, b, c;
	
	while(scanf("%d %d %d", &a, &b, &c) != EOF)
	{
		if(a == -1 && b == -1 && c == -1)
		{
			break;
		}
		if((a == -1 || b == -1) && c == -1)
		{
			printf("F\n");
		}
		else
		{
			int sum = 0, k = 0;
			if(a >= 0)
			{
				sum += a;
			}
			if(b >= 0)
			{
				sum += b;
			}
			if(sum >= 80)
			{
				printf("A\n");
			}
			else if(sum >= 65 && sum < 80)
			{
				printf("B\n");
			}
			else if((sum >= 50 && sum < 65) || c >= 50)
			{
				printf("C\n");
			}
			else if(sum >= 30 && sum < 50)
			{
				printf("D\n");
			}
			else
			{
				printf("F\n");
			}
		}
	}
	
	return 0;
} 


Measured memory_bytes: 2684
function main()
	N,M,X=map(x->parse(Int,x),split(readline()))
	C=zeros(Int,N)
	A=zeros(Int,N,M)
	for i=1:N
		now=map(x->parse(Int,x),split(readline()))
		for j=1:M+1
			if j==1
				C[i]=now[j]
			else
				A[i,j-1]=now[j]
			end
		end
	end
	ans=10^18
	for i=0:2^N-1
		sum=0
		now=zeros(Int,M)
		for j=1:N
			if (i>>(j-1))%2==1
				sum+=C[j]
				for k=1:M
					now[k]+=A[j,k]
				end
			end
		end
		if all(x->x>=X,now)&&ans>sum
			ans=sum
		end
	end
	println(ans<10^18 ? ans : -1)
end
main()

Measured memory_bytes: 175464
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<set>
#include<algorithm>

using namespace std;

int combi(int n, int k) {
    if (n == k || k == 0)
        return 1;
    else {
        return combi(n - 1, k - 1) + combi(n - 1, k);
    }
}

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

    int sum = 0;
    if (N >= 2)sum += combi(N, 2);
    if (M >= 2)sum += combi(M, 2);
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
require 'prime'
N = gets.chomp.to_i
M = 75

#N!を素因数分解する
hash = Hash.new(0)
(2..N).each do |i|
    Prime.prime_division(i).each do |pr, n|
        hash[pr] += n
    end
end

nums = hash.values
len = nums.length

#Mの約数列挙
divs = []
for i in 1..M do
  if M%i == 0
    divs << i
  end
end


#dp[i][j]：i番目の素因数まで用いてつくるとき，約数がj個となる場合の数
dp = Array.new(len+1){Array.new(M+1, 0)}
dp[0][1] = 1
len.times do |i|
    divs.each do |d1|
        divs.each do |d2|
            next if d1*d2 > M
            if nums[i]+1 >= d2
                dp[i+1][d1*d2] += dp[i][d1]
            end
        end
    end
end

puts dp[len][M]


Measured memory_bytes: 2300
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;

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

  vector<array<int, 3>> a(N);
  rep(i, N) { cin >> a[i][0] >> a[i][1] >> a[i][2]; }

  vector<array<uint64_t, 3>> happy(N+1);
  rep(i, N) {
    rep(j, 3) {
      happy[i + 1][j] =
          max(happy[i][(j + 1) % 3], happy[i][(j + 2) % 3]) + a[i][j];
    }
  }

  uint64_t m = max(happy[N][0], happy[N][1]);
  m = max(m, happy[N][2]);
  cout << m << endl;

  return 0;
}


Measured memory_bytes: 3712
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#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 loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    int h,w; cin>>h>>w;
    vvi ujimatu(101,vi(101,-1));
    vector<string>d(h);
    rep(i,h)cin>>d[i];
    for(int i=0; i<h;i++){
        for(int j=0; j<d[i].size();j++){
            if(d[i][j]=='.')continue;
            for(int k=j; k<d[i].size();k++){
                if(k==j)ujimatu[i][k]=0;
                else ujimatu[i][k]=k-j
                    ;            }
        }
    }
    rep(i,h){rep(j,w)if(j)cout<<" "<<ujimatu[i][j];else cout<<ujimatu[i][j];cout<<endl;}
}

Measured memory_bytes: 3284
import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
				
		Scanner sc = new Scanner(System.in);
         
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            
            int tmp=0;
            if(a>b){tmp=a;a=b;b=tmp;
            }int count=0;
            for(int i=a;i<=b;i++){
            	
            	if(c%i==0) count++;
            }System.out.println(count);
	}
        }

Measured memory_bytes: 17356
/**
     *   created: 03 June 2019  00:25:23
    **/
    #include<bits/stdc++.h>
    using namespace std;
     
    typedef vector<int> vi;
    typedef pair<int , int> pii;
    typedef vector< pair<int , int> > vii;
    typedef long long ll;
    typedef vector<long long> vl;
    typedef pair<long long , long long> pll;
    typedef vector< pair<long long , long long> > vll;
     
    #define PB push_back
    #define PPB pop_back
    #define all(c) c.begin(),c.end()
    #define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
    #define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
    #define INFLL 2000000000000000007
    #define INF 2000000007
    #define MOD 1000000007
     
     
    #define TRACE
     
    #ifdef TRACE
    #define trace1(x)                cerr << #x << ": " << x << endl;
    #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
    #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
    #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
    #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
    #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
     
    #else
     
    #define trace1(x)
    #define trace2(x, y)
    #define trace3(x, y, z)
    #define trace4(a, b, c, d)
    #define trace5(a, b, c, d, e)
    #define trace6(a, b, c, d, e, f)
     
    #endif
     
     
    void optimizeIO()
    {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    }
     
    //                                        //AUTHOR: Kaushalesh Shukla
     
    //=========================================================================================================
     
    int main()
    {
    	optimizeIO();
    	int tt=1;
    	//cin>>tt;
    	while(tt--){
    		ll n,k;
    		cin>>n>>k;
    		vl v(n);
    		rep(i,0,n)
    			cin>>v[i];
    		ll lb=-1;
    		rep(i,0,60){
    			ll temp = (ll)((ll)1<<(ll)i);
    			// trace1(temp);
    			if((k&temp))
    				lb = i;
    		}
    		// cout<<lb<<endl;
    		ll num=0;
    		rrep(i,lb+1,0){
    			ll cnt0=0,cnt1=0;
    			rep(j,0,n){
    				if((v[j]&(1ll<<i)))
    					cnt1++;
    				else
    					cnt0++;
    			}
    			// trace3(cnt0,cnt1,i);
    			if(cnt0>cnt1)
    				if((num|(1ll<<i))<=k)
    					num = (num|(1ll<<i));
    		}
    		// cout<<num<<endl;
    		ll sum=0;
    		rep(i,0,n){
    			sum += (v[i]^num);
    		}
    		cout<<sum;
    	}
    	return 0;
    }

Measured memory_bytes: 1024
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_STR_MAX		10										// 最大文字数
#define D_OPE_PLUS		'+'										// 和
#define D_OPE_NONE		' '										// なし

// 内部変数
static char sc1Str[D_STR_MAX + 5];								// 文字
static int siSCnt;												// 文字数
static char sc1Calc[D_STR_MAX * 2];								// 数式
static long long slSum;											// 合計値

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// 改行カット
// 戻り値：文字数
int
fCutCrLf(
	char *pcpStr				// <I> 文字列
)
{
	int i;

	for (i = 0; pcpStr[i] != '\0'; i++) {
		if (pcpStr[i] == '\n') {
			pcpStr[i] = '\0';
			break;
		}
	}

	return i;
}

// 合計値加算
int
fAddSum(
)
{
	int i;

	// 数式の分解 - 初期化
	char lc2Val[D_STR_MAX][D_STR_MAX + 5];
	memset(lc2Val, 0, sizeof(lc2Val));
	int liVCnt = 0;
	int liNo = 0;

	// 数式の分解 - セット
	for (i = 0; i < siSCnt * 2 - 1; i++) {
		switch (sc1Calc[i]) {
		case D_OPE_PLUS:							// 和
			liVCnt++;
			liNo = 0;
			break;
		case D_OPE_NONE:							// なし
			break;
		default:									// 数字
			lc2Val[liVCnt][liNo] = sc1Calc[i];
			liNo++;
			break;
		}
	}
	liVCnt++;

	// 合計値に加算
	for (i = 0; i < liVCnt; i++) {
		long long llVal;
		sscanf(lc2Val[i], "%lld", &llVal);
		slSum += llVal;
	}

	return 0;
}

// 数式セット
int
fSetCalc(
	int piCnt					// <I> セット数
)
{
	// 終了チェック
	if (piCnt >= siSCnt - 1) {
		fAddSum();								// 合計値加算
		return 0;
	}

	// 数式セット - 和
	sc1Calc[piCnt * 2 + 1] = D_OPE_PLUS;
	fSetCalc(piCnt + 1);					// 下位へ

	// 数式セット - なし
	sc1Calc[piCnt * 2 + 1] = D_OPE_NONE;
	fSetCalc(piCnt + 1);					// 下位へ

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// データ初期化
	slSum = 0;													// 合計値

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 文字取得
#ifdef D_TEST
	fgets(sc1Str, sizeof(sc1Str), szpFpT);
#else
	fgets(sc1Str, sizeof(sc1Str), stdin);
#endif

	// 改行カット・文字数取得
	siSCnt = fCutCrLf(sc1Str);

	// 数式の数字部分セット
	for (i = 0; i < siSCnt; i++) {
		sc1Calc[i * 2] = sc1Str[i];
	}

	// 数式セット
	fSetCalc(0);

	// 結果セット
	sprintf(lc1Out, "%lld\n", slSum);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 128
n,m = map(int,input().split(" "))

x,y = map(int,input().split(" "))
for i in range(m-1):
    l,r = map(int,input().split(" "))
    x = max(x,l)
    y = min(y,r)

if y-x >= 0:
    print(y-x+1)
else:
    print(0)


    

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

using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long

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


Measured memory_bytes: 3572
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<cstring>
#include<string>
using namespace std;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(b-a==c-b)printf("YES\n");
		else printf("NO\n");
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    val Array(a, _) = sc.nextLine.split(" ").map(_.toInt)
    val s: String = sc.nextLine
    if (s.filter(_.toString == "-").length != 1) println("No")
    else {
      if (s.takeWhile(_.toString != "-").length == a) println("Yes")
      else println("No")
    }
  }
}


Measured memory_bytes: 27452
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);const tn=():number=>{const a=input[0];input.shift();return Number(a)};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{const a=input[0];input.shift();return String(a)};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const tc=():string=>{let a=input[0].split('');const b=a[0];a.shift();if(a.length>0){input[0]=a.join('')}else{input.shift()}return String(b)};const tcc=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(tc())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length;i+=2){if(eval(a+op+arr[i]))return arr[i+1];}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const gojo=(a:number,b:number):number=>{if(a%b===0)return b;return gojo(b,a%b)};
const main=()=>{
  let s=ts()
  to(s[0]+(s.length-2)+s[s.length-1])
}
main()


Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	bool n = false, e = false, s = false, w = false;
	string str;
	cin >> str;
	rep(i,str.size()) {
		if (str[i] == 'N')n = true;
		if (str[i] == 'E')e = true;
		if (str[i] == 'S')s = true;
		if (str[i] == 'W')w = true;
	}
	cout<<(((!(n^s)) && (!(e^w))) ? "Yes" : "No") << endl;

}

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

const int INF = 1 << 29;
const long long int Mod = 1000000007;
using ll = long long int;
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; ++i)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)

ll a[100010];

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

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

	int change = 0;
	int ans = 0;
	rep(i, n - 1) {
		if (change == 0) {
			if (a[i] < a[i + 1]) change = 1;
			else if (a[i] > a[i + 1]) change = -1;
		}
		else if (change == 1) {
			if (a[i] > a[i + 1]) {
				++ans;
				change = 0;
			}
		}
		else {
			if (a[i] < a[i + 1]) {
				++ans;
				change = 0;
			}
		}
	}
	if (change == 0) ++ans;
	else if (change == 1) {
		if (a[n - 2] <= a[n - 1]) {
			++ans;
		}
		else {
			ans += 2;
		}
	}
	else {
		if (a[n - 2] >= a[n - 1]) ++ans;
		else ans += 2;
	}

	cout << ans << endl;
}

Measured memory_bytes: 3940
<?php
$n = trim(fgets(STDIN));
$h_arr = explode(" ", trim(fgets(STDIN)));

// カウント
$count = 0;
// カウント配列
$count_arr = array();
// 右となりにいける最大回数
$max_count = 0;

for ($i = 0; $i < count($h_arr); $i++) {
	if (($i+1) == count($h_arr)) {
		$count_arr[] = $count;
		break;
	} elseif ($h_arr[$i] >= $h_arr[$i+1]) {
		$count++;
	} else {
		$count_arr[] = $count;
		$count = 0;
	}
}

$max_count = max($count_arr);
echo $max_count;

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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  ll ans = 0;
  map<int,int> cnt;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    ans += cnt[i-a];
    cnt[i+a]++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 20632
import java.util.Scanner;

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

    while (in.hasNext()) {
      int M = in.nextInt();
      int D = in.nextInt();
      int count = 0;

      for (int m = 1; m <= M; ++m) {
        for (int d = 1; d <= D; ++d) {
          int d1 = d % 10;
          int d10 = d / 10;

          if (d1 >= 2 && d10 >= 2 && d1 * d10 == m) {
            ++count;
          }
        }
      }
      
      System.out.println(count);
    }
  }
}

Measured memory_bytes: 21076
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod=1e9;
static const ll INF=1LL<<50;
using namespace std;

int main() {
	int a,b;
  cin>>a>>b;
  if(a<=5)b=0;
  else if(a>=6&&a<=12)b/=2;
  cout<<b<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<vector>
#include<map>
#include <set>
#include<string>
#include <queue>
#include <stack>
#include <random>
#define INF 1000000001
#include<iostream>
#include<vector>
using ll = long long;

struct  UnionFind
{
public:
    UnionFind(const int n) : par(n){
        for(int i = 0; i < n; ++i){
            par[i] = i;
        }
    }

    int root(const int idx){
        if(par[idx] == idx) return idx;
        return root(par[idx]);
    }

    void unite(const int x, const int y){ 
        const int rx = root(x);
        const int ry = root(y);
        if(rx == ry) return;
        par[ry] = rx;
    }

    bool same_tree(const int x, const int y){
        return (root(x) == root(y));
    }

    bool connected(){
        int parent = root(0);
        for(int i = 1; i < par.size(); ++i){
            if(root(i) != parent) return false;
        }
        return true;
    }


public:
    std::vector<int> par;
};


int main()
{    

    int N, M;
    std::cin >> N >> M;
    std::vector<std::pair<int,int>> edge;
    for(int i =  0; i < M; ++i){
        int from, to;
        std::cin >> from >> to;
        edge.push_back({from - 1, to - 1});
    }

    int ans = 0;
    for(int k = 0; k < M; ++k){
        UnionFind tree(N);
        for(int i= 0; i < M; ++i){
           if(i == k) continue;
           tree.unite(edge[i].first, edge[i].second);
        }

       if(!tree.connected()) ans++;
   }
   
   std::cout << ans << std::endl;
   return 0;
    
}



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

using namespace std;
using ll = long long;

const int N = 200005;

int n;
char str[N];
int p[N];
int s[N];

int main() {
	scanf("%d %s", &n, str + 1);

	for(int i = 1; i <= n; i++) {
		p[i] = p[i - 1];
		if(str[i] == 'W') p[i]++;
	}
	for(int i = n; i >= 1; i--) {
		s[i] = s[i + 1];
		if(str[i] == 'R') s[i]++;
	}

	int ans = min(p[n], s[1]);

	for(int i = 1; i <= n; i++) {
		ans = min(ans, max(p[i], s[i + 1]));
	}

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


Measured memory_bytes: 5524
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        if (a == 1) a = 14;
        if (b == 1) b = 14;

        System.out.println(a == b ? "Draw" : a > b ? "Alice" : "Bob");
    }
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
const int maxn=(int)1e6+5;
typedef long long ll;

struct edge{
    ll to,a,b;
};
struct Data{
    ll v,s,t;
    bool operator < (const Data & a)const{return t>a.t;}
};

const ll  MAXN=50,MAXS=MAXN*50,INF=1e18;
ll dp[MAXN+1][MAXS+1];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n,m,s;cin>>n>>m>>s;
    vector<edge> E[MAXN+1];
    rep(i,1,m){
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        E[u].push_back((edge){v,a,b});
        E[v].push_back((edge){u,a,b});
    }
    vector<int> c(n+1),d(n+1);
    rep(i,1,n){
        cin>>c[i]>>d[i];
    }
    s=min(s,MAXS);
    rep(i,1,n)rep(j,0,MAXS)dp[i][j]=INF;dp[1][s]=0;
    priority_queue<Data> Q;
    Q.push((Data){1,s,0});
    while(!Q.empty()){
        Data dt=Q.top();Q.pop();
        //debug(dt.v),debug(dt.s),debug(dt.t);
        //if(dt.s<0)continue;
        if(dt.t>dp[dt.v][dt.s])continue;
        //change
        ll curt=dp[dt.v][dt.s];
        ll ns=min(dt.s+c[dt.v],MAXS);
        ll nt=curt+d[dt.v];//?dp[dt.v][dt.s]+d[dt.v]
        if(dp[dt.v][ns]>nt){
            dp[dt.v][ns]=nt;
            Q.push((Data){dt.v,ns,nt});
        }
        // trans
       
        for(auto e:E[dt.v]){
            ns=dt.s-e.a;
            nt=curt+e.b;//?dt.t+e.b
            if(ns>=0 and dp[e.to][ns]>nt){
                dp[e.to][ns]=nt;
                Q.push((Data){e.to,ns,nt});
            }
        }
    }
    rep(i,2,n){
        ll ans=INF;
        rep(j,0,MAXS){
            ans=min(ans,dp[i][j]);
            
        }
        cout<<ans<<endl;
    }
}
/* 
dp[i][j] min time takes from 1 to node i, have j coin with me.
dp[i][j]=dp[k][j-cost]
wr: 最后的更新出错, INF太小
Q: 更新时 用当前的状态dt.t or 储存的最优状态dp
 */

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

using namespace std;

const int N = 8;
int l[N], n, A, B, C, pre[1 << N];

int solve() {
	int res = 1e9 + 7;
	int cntSs1 = 0, cnts2 = 0, cnts3 = 0;
	for (int S = 0; S < (1 << n); ++S)
		for (int s1 = 1; s1 < (1 << n); ++s1)
			if ((S | s1) == S) {
				cntSs1++;
				for (int s2 = 1; s2 < (1 << n); ++s2)
					if ((s2 & s1) == 0 && (s2 | S) == S) {
						cnts2++;
						int s3 = S & (~(s1 | s2));
						if (s3 == 0) continue;
						cnts3++;
						int mp = 0, a = 0, b = 0, c = 0, cnt = 0, ja = 0, jb = 0, jc = 0;
						for (int i = 0; i < n; ++i) {
							if (s1 & (1 << i)) a += l[i], cnt++, ja++;
							if (s2 & (1 << i)) b += l[i], cnt++, jb++;
							if (s3 & (1 << i)) c += l[i], cnt++, jc++;
						}
						mp = abs(a - A) + abs(b - B) + abs(c - C) + 10 * (ja + jb + jc - 3);
						res = min(res, mp);
					}
			}
	return res;
}

#define bp __builtin_popcount

int solve1() {
	int res = int(1e9) + 7;
	int ns = 1 << n;
	for (int i = 0; i < ns; ++i) {
		pre[i] = 0;
		for (int j = 0; j < n; ++j)
			if (i & (1 << j))
				pre[i] += l[j];
	}
	for (int S = 1; S < ns; ++S)
		for (int s1 = 1; s1 < ns; ++s1)
			if ((S | s1) == S)
				for (int s2 = 1; s2 < ns; ++s2)
					if ((s1 & s2) == 0 && (s2 | S) == S) {
						int s3 = S & ~(s1 | s2);
						if (s3 == 0) continue;
						res = min(res, abs(A - pre[s1]) + abs(B - pre[s2]) + abs(C - pre[s3]) + 10 * (bp(s1) + bp(s2) + bp(s3) - 3));
					}
	return res;
}

int calc(int i, int a, int b, int c) {
	if (i == n) {
		if (min(a, min(b, c)) == 0) return 1e9 + 7;
		return abs(a - A) + abs(b - B) + abs(c -C) - 30;
	}
	int res = 1e9 + 7;
	res = min(res, calc(i + 1, a, b, c));
	res = min(res, 10 + calc(i + 1, a + l[i], b, c));
	res = min(res, 10 + calc(i + 1, a, b + l[i], c));
	res = min(res, 10 + calc(i + 1, a, b, c + l[i]));
	return res;
}

int main() {
	cin >> n >> A >> B >> C;
	for (int i = 0; i < n; ++i)
		cin >> l[i];
	printf("%d", solve1());
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 50;
int A[MAXN];
string S;
bool check(int a, int b){
    for (int i=a; i<=b; i++){
        if (S[i] != 'A' && S[i] != 'C' && S[i] != 'T' && S[i] != 'G'){
            return 0;
        }
    }
    return 1;
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> S;
    int N = S.length();
    for (int i=N; i>=0; i--){
        bool ispos = 0;
        for (int s = 0; s <= N-i; s++){
            if (check(s, s+i-1)) {
                cout << i;
                exit(0);
            }
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n, a, b;
	cin >> n >> a >> b;
	long long c=a+b;
	long long t=n/c*a;
	if (n%c!=0)
	{
		if (n%c>=a) t+=a;
		else t+=n%c;
	}
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int n, m;
  while(cin>>n>>m,n+m) {
    vector<char> v(n, '#');
    REP(j,m) {
      char c;
      cin >> c;
      if (c=='A') {
        REP(i,n) {
          if (v[i] == '#') {
            v[i] = c;
            break;
          }
        }
      } else if (c=='B') {
        bool f = 0;
        for(int i=n-1;i>=0; --i) {
          if (v[i] == '#') {
            if (i<n-1&&v[i+1]=='A' || i>0&&v[i-1]=='A')
              continue;
            v[i] = c;
            f = 1;
            break;
          }
        }
        if (!f) {
          REP(i,n) {
            if (v[i] == '#') {
              v[i] = c;
              break;
            }
          }
        }
      } else if (c=='C') {
        bool f = 0;
        REP(i,n) {
          if (v[i] != '#') {
            if (i<n-1 && v[i+1]=='#') {
              v[i+1] = c;
              f = 1;
              break;
            }
            
            if (i>0&&v[i-1]=='#') {
              v[i-1] = c;
              f = 1;
              break;
            }
          }
        }
        if (!f) {
          if (n%2)
            v[(n+1)/2-1] = c;
          else
            v[n/2] = c;
        }
      } else {
        vector<int> dst(n,INF);
        REP(i,n) REP(j,n)
          if (v[j] != '#')
            dst[i] = min(dst[i], abs(i-j));
        int ma = 0;
        int p = 0;
        REP(i,n) {
          if (v[i] == '#' &&ma < dst[i]) {
            ma = dst[i];
            p = i;
          }
        }
        v[p] = c;
      }
       // REP(i,n)
       //   cout << v[i];
       // cout << endl;

    }
    REP(i,n)
      cout << v[i];
    cout << endl;
  }
}

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

using namespace std;

typedef long long ll;

int main() {
  ll N;
  cin >> N;
  for (ll h = 1; h <= 3500; h++) {
    for (ll n = 1; n <= 3500; n++) {
      ll num = N * h * n;
      ll den = 4 * h * n - N * n - N * h;
      if (den != 0 && num % den == 0) {
        ll w = num / den;
        if (w > 0 && 4 * w * n * h == N * w * n + N * h * w + N * h * n) {
          cout << h << " " << n << " " << w << endl;
          return 0;
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h> 
int main(){
	long long i,j,k,l,m,n;
    scanf("%lld",&n);	
    if(n%2==0){printf("%d %d %d",n/2,n,n);return 0;} 
	for(i=1;i<=3500;i++)
	 for(j=i;j<=3500;j++)
	 {
	  k=n*i*j;
	  l=4*i*j-n*i-n*j;
	  if(l>0)
	if(k%l==0){m=k/l;
	  if(m<i){l=m;m=i;i=l;l=m;m=j;j=l;}
	  else if(m<j){l=m;m=j;j=l;}
	  printf("%d %d %d",i,j,m);
	  return 0;
	  } 
}
	return 0;
}

Measured memory_bytes: 128
l = list(map(int, input().split()))
l.sort()

max_v = l[2]
mid_v = l[1]
min_v = l[0]

count = max_v - mid_v
mid_v = max_v
min_v = min_v + count
diff = max_v - min_v

if diff == 0:
    count = count
elif diff == 1:
    count += 2  # ope2 and ope1
elif diff > 1 and diff % 2 == 0:
    count += diff / 2
elif diff > 1 and diff % 2 == 1:
    count += int(diff / 2)
    count += 2
else:
    print("Error")
print(int(count))


Measured memory_bytes: 38384
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(l):
	n = len(l)
	

A,B = list(map(int, stdin.readline().rstrip().split()))
curr = 1
f = 1
while(curr < 100000):
	if(floor(curr*0.08) == A and floor(curr*0.1) == B):
		f = 0
		print(curr)
		break
	curr += 1
	# print(curr)

if(f):
	print(-1)








Measured memory_bytes: 5100
#include "bits/stdc++.h"
#include <algorithm>

using namespace std;

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

    long long ans=0;

    for (long long i = 1; i < n; i++)
    {   
        long long temp = (n-i)/i;
        if(temp<i){
            break;
        }
        if(n-temp*i==i){
            if(n%temp==i){
                // cout <<i<<endl;
                ans+=temp;
            }
        }
    }
    
    cout << ans <<endl;
    return(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#define INF (long)1e9
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
using namespace std;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	string ans = "";
	ans += s[0];
	ans += to_string(s.size() - 2);
	ans += s[s.size() - 1];
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256