akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys

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

M = 1000
kabu = 0

cur = A[0]

for i in range(1,N):
    if cur > A[i]:
        # 持ってる株全部売る
        M = M + kabu * cur
        kabu = 0
    if cur < A[i]:
        # 所持金全部株に変える
        if M >= cur:
            kabu = M // cur
            M = M % cur
    cur = A[i]

# print(M)
# print(kabu)
# print(cur)
M = M + kabu * cur
print(M)


Measured memory_bytes: 61724
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(min(b,d) > max(a,c)){
    cout << abs(max(a,c)-min(b,d));
  }else{
    cout << 0;
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
 int w, h, x, y, r;

 scanf("%d", &w);

 scanf("%d", &h);

 scanf("%d", &x);

 scanf("%d", &y);

 scanf("%d", &r);

 if (x + r > w || x - r < 0 || y + r > h || y - r < 0)
  printf("No\n");
 else
  printf("Yes\n");

 return 0;

}



Measured memory_bytes: 2140
N, X = map(int, input().split())
count = 0

for i in range(100):
    if N == 0:
        count += 1
        break
    elif X == 1:
        break
    elif X == 2**(N+1) - 1:
        count += 2**N
        break
    elif X == 2**(N+2) - 3:
        count += 2**(N+1) - 1
        break
    elif 1 < X < 2**(N+1) - 1:
        X -= 1
        N -= 1
    elif 2**(N+1) - 1 < X < 2**(N+2) - 3:
        count += 2**N
        X -= 2**(N+1) - 1
        N -= 1

print(count)

Measured memory_bytes: 3064
import Control.Applicative((<$>))
import Control.Monad
import Data.Map ((!))
import qualified Data.Map as M
-- import Data.IntMap ((!))
-- import qualified Data.IntMap as M
import qualified Data.List as L
import Data.Maybe (catMaybes)
-- import qualified Data.Char as C
-- import qualified Data.IntSet as I
import Debug.Trace
--------------------------------------------
readInt    = read :: String -> Int
getInt     = readInt <$> getLine
getIntList = map readInt . words <$> getLine
int2bin 0 =  []
int2bin n =  n `mod` 2 : int2bin (n `div` 2)
----------------------------------------------

main :: IO ()
main = do
  [a, b] <- getIntList
  let n = b - a
  print $ (1+n) * n `div` 2 - b

Measured memory_bytes: 508
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

int main(){

  int a,b,ans;
  char opr;

  while(1){
  cin >>a >>opr >>b;
    switch(opr){
    case '+': ans=a+b; cout<<ans; break;
    case '-': ans=a-b; cout<<ans; break;
    case '*': ans=a*b; cout<<ans; break;
    case '/': ans=a/b; cout<<ans; break;
    case '?': break;
    }
    if(opr=='?') break;
    cout <<endl;
  }
  return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;

int main(){
    ll A,B,K;
    cin >> A >> B >> K;
    if(A<K){
        K = K - A;
        if(B<K){
            B = 0;
        }else{
            B = B-K;
        }
        A=0;
    }else{
        A = A-K;
    }
    cout << A << " " << B << endl;
    return 0;
}

Measured memory_bytes: 888
def gcd(a,b):
	if b==0:
		return a
	else:
		return gcd(b,a%b)

def lcm(a,b):
	return a*b//gcd(a,b)

n=int(input())
a=[int(i) for i in input().split()]
tmp=1
for i in a:
	tmp=lcm(i,tmp)
mod=1000000007
print(sum(tmp//i for i in a)%mod)

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

int n, m, p[100005], cnt;

int f(int x){
    if (p[x] == x) return x;
    return p[x] = f(p[x]);
}

int main() {
    cin >> n >> m;
    cnt = n;
    for (int i = 1; i <= n; i++){
        p[i] = i;
    }
    for (int i = 0, a, b; i < m; i++){
        cin >> a >> b;
        a = f(a);
        b = f(b);
        if (a != b){
            p[b] = a;
            cnt--;
        }
    }
    cout << cnt-1 << "\n";
}


Measured memory_bytes: 4024
package main

import (
	"fmt"
)

func main() {
	var c string
	fmt.Scan(&c)

	if c == "a" {
		fmt.Println("b")
	} else if c == "b" {
		fmt.Println("c")
	} else if c == "c" {
		fmt.Println("d")
	} else if c == "d" {
		fmt.Println("e")
	} else if c == "e" {
		fmt.Println("f")
	} else if c == "f" {
		fmt.Println("g")
	} else if c == "g" {
		fmt.Println("h")
	} else if c == "h" {
		fmt.Println("i")
	} else if c == "i" {
		fmt.Println("j")
	} else if c == "j" {
		fmt.Println("k")
	} else if c == "k" {
		fmt.Println("l")
	} else if c == "l" {
		fmt.Println("m")
	} else if c == "m" {
		fmt.Println("n")
	} else if c == "n" {
		fmt.Println("o")
	} else if c == "o" {
		fmt.Println("p")
	} else if c == "p" {
		fmt.Println("q")
	} else if c == "q" {
		fmt.Println("r")
	} else if c == "r" {
		fmt.Println("s")
	} else if c == "s" {
		fmt.Println("t")
	} else if c == "t" {
		fmt.Println("u")
	} else if c == "u" {
		fmt.Println("v")
	} else if c == "v" {
		fmt.Println("w")
	} else if c == "w" {
		fmt.Println("x")
	} else if c == "x" {
		fmt.Println("y")
	} else if c == "y" {
		fmt.Println("z")
	}
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
typedef pair<int, int> pii;
struct edge{int u, v, cost;};

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }

  bool is_same(int x, int y){
    return find(x) == find(y);
  }
};

int main(){
    int n; cin >> n;
    vector<pii> v;
    map<pii, int> eid;
    vector<edge> g;
    rep(i,n){
        int x, y; cin >> x >> y;
        v.push_back(make_pair(x, y));
        eid[make_pair(x, y)] = i;
    }

    vector<pii> x_order;
    x_order = v;
    sort(ALL(x_order));
    int from, to; int cost;
    rep(i,n-1){
        from = eid[x_order[i]];
        to = eid[x_order[i+1]];
        cost = min(abs(x_order[i+1].second - x_order[i].second), abs(x_order[i+1].first - x_order[i].first));
        g.push_back((edge){from, to, cost});
    }

    vector<pii> y_order;
    y_order = v;
    rep(i,n) swap(y_order[i].first, y_order[i].second);
    sort(ALL(y_order));
    rep(i,n) swap(y_order[i].first, y_order[i].second);
    rep(i,n-1){
        from = eid[y_order[i]];
        to = eid[y_order[i+1]];
        cost = min(abs(y_order[i+1].second - y_order[i].second), abs(y_order[i+1].first - y_order[i].first));
        g.push_back((edge){from, to, cost});
    }

    sort(ALL(g), comp);
    UnionFind tree(n);
    ll ans = 0;
    rep(i, 2*n-2){
        edge e = g[i];
        if(!tree.is_same(e.u, e.v)){
            tree.unite(e.u, e.v);
            ans += (ll)e.cost;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 13424
#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=5+3*1e+4;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=7+1e+9;

int main() {
	string s;
	int K;
	cin >> s;
	cin >> K;
	REP(i,s.size()){
		if(s[i] == 'a')
			continue;
		
		int c = 'z'- s[i] + 1;
		if(c <= K){
			s[i] = 'a';
			K -= c;
		}
	}
	if(K > 0){
		s[s.size() - 1] += K % 26;
	}
	cout << s << endl;
    return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws java.io.IOException {
		Scanner scan = new Scanner(System.in);
		int i1 =scan.nextInt();
		int i5 =scan.nextInt();
		int i10 =scan.nextInt();
		int i50 =scan.nextInt();
		int i100 =scan.nextInt();
		int i500 =scan.nextInt();
		if(i1 + i5*5 + i10*10 + i50*50 + i100*100 + i500*500 >=1000){
			System.out.println(1);
		}else{
			System.out.println(0);
		}
	}
}

Measured memory_bytes: 17332
#include <iostream>

int main() {
    long a, b, x;
    std::cin >> a >> b >> x;
    if (a == 0) {
        std::cout << b / x + 1 << std::endl;
    } else {
        std::cout<< b / x - (a - 1) / x << std::endl;
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll max3(ll a, ll b, ll c){return max(a, max(b, c));};
ll min3(ll a, ll b, ll c){return min(a, min(b, c));};
ll max4(ll a, ll b, ll c, ll d){return max(max(a, b), min(c, d));};
ll min4(ll a, ll b, ll c, ll d){return min(min(a, b), min(c, d));};
ll max5(ll a, ll b, ll c, ll d, ll e){return max(max(a, b), max3(c, d, e));};
ll min5(ll a, ll b, ll c, ll d, ll e){return min(min(a, b), min3(c, d, e));};

const ll INFL = 1LL << 60;//10^18 = 2^60
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD = 998244353;

vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};


ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

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

ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}

/*
//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}
*/

int main(){
  ll N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  S += '#';
  ll group = 0;
  rep(i, N){
    if(S[i] != S[i+1]) group++;
  }
  group = max(1, group - 2 * K);
  cout << N-group << endl;

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - 48;}
char myitoc(int N) {return '0' + N;}

signed main()
{
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  int suma = 0;
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
    suma += A.at(i);
  }

  vector<int> div;
  for (int i = 1; i * i <= suma; i++)
  {
    if (suma % i == 0)
    {
      div.push_back(i);
      if (i * i != suma) div.push_back(suma / i);
    }
  }
  sort(div.begin(), div.end(), greater<int>());
  
  for (int i = 0; i < div.size(); i++)
  {
    int d = div.at(i);
    vector<int> x(N);
    multiset<int> y;
    int sumx = 0;
    for (int i = 0; i < N; i++)
    {
      x.at(i) = d - A.at(i) % d;
      sumx += x.at(i);
      y.emplace(A.at(i) % d);
    }
    
    int sumy = 0;
    auto itr = y.begin();
    for (int j = 0; j < sumx / d; j++)
    {
      sumy += *itr;
      itr++;
    }
    
    if (sumy <= K)
    {
      cout << d << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
main = getLine >>= putStrLn.show.answer.(read :: String -> Int)

answer n = minimum $ n:map (f 0) (zip [0..n] [0..n]) where
    f v (i,nn) = if i > 0 then f (v+mod i 6) (div i 6,nn) else g v (n-nn)
    g v i = if i > 0 then g (v+mod i 9) (div i 9) else v

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

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

const int mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 11

int h,w,c; 
char f[10][10];


int main()
{
    cin >> h >> w >> c;
    
    rep(i,h) rep(j,w) cin >> f[i][j];
    int ans = 0;
    for(int i = 0; i < (1 << h); i++){
        for(int j = 0; j < (1 << w); j++){
            char tmp[h][w];
            rep(y,h) rep(x,w) tmp[y][x] = f[y][x];
            for(int k = 0; k < h; k++){
                if(i & (1<<k)){
                    rep(x,w) tmp[k][x] = '.'; 
                }
            }
            for(int k = 0; k < w; k++){
                if(j & (1 << k)){
                    rep(y,h) tmp[y][k] = '.';
                }
            }
            int cnt = 0;
            rep(y,h) rep(x,w) if(tmp[y][x] == '#') cnt++;
            if(cnt == c) ans++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 3628
N,Y = map(int,input().split())
for i in range(N+1):
    for n in range(N-i+1):
        if 10000*i+5000*n+1000*(N-i-n) == Y:
            print(i,n,N-i-n)
            break
    else:
        continue
    break
else:
    print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>
#include <math.h>
typedef long long ll;

#define FOR(i,a,b) for(ll i = (a);i < (b);++i)
#define REP(i,n) FOR(i,0,n)

#define debug(x) cout << #x << "=" << x << endl;

using namespace std;

int main(void){

    int X;
    cin >> X;

    int A = sqrt(X);

    int M = 0;
    if(X == 1){
        cout << 1 << endl;
        return 0;
    }
    FOR(i,2,A+1){
        int cnt = 1;
        int tmp = 0;
        while(1){
            if(X >= pow(i,cnt)){
                tmp = pow(i,cnt);
                M = max(tmp,M);
            }else{
                break;
            }
            cnt++;
        }
    }
    cout << M << endl;

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
   
using namespace std;
   
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
   
static const double EPS = 1e-8;
   
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class Duration {
public:
  int from;
  int to;
  Duration(int hour[2],int minute[2]){
    from = hour[0] * 60 + minute[0];
    to = hour[1] * 60 + minute[1];
  }
  
  bool contains(Duration t){
    if(t.from < from || t.to > to) return false;
    return true;
  }
};

int main(){
  int total_lectures;
  while(~scanf("%d",&total_lectures)){
    vector<Duration> lectures;
    for(int lecture_i = 0; lecture_i < total_lectures; lecture_i++){
      int hour[2];
      int minute[2];
      scanf("%d:%d-%d:%d",&hour[0],&minute[0],&hour[1],&minute[1]);
      lectures.push_back(Duration(hour,minute));
    }

    int total_teachers;
    scanf("%d",&total_teachers);
    vector<Duration> teachers[101];
    for(int teacher_i = 0; teacher_i < total_teachers; teacher_i++){
      int num_of_spare_times;
      scanf("%d",&num_of_spare_times);
      for(int spare_i = 0; spare_i < num_of_spare_times; spare_i++){
        int hour[2];
        int minute[2];
        scanf("%d:%d-%d:%d",&hour[0],&minute[0],&hour[1],&minute[1]);
        teachers[teacher_i].push_back(Duration(hour,minute));
      }
    }
    int total_students;
    scanf("%d",&total_students);
    vector<Duration> students[101];
    for(int student_i = 0; student_i < total_students; student_i++){
      int num_of_spare_times;
      scanf("%d",&num_of_spare_times);
      for(int spare_i = 0; spare_i < num_of_spare_times; spare_i++){
        int hour[2];
        int minute[2];
        scanf("%d:%d-%d:%d",&hour[0],&minute[0],&hour[1],&minute[1]);
        students[student_i].push_back(Duration(hour,minute));
      }
    }

    int res = 0;
    for(int lecture_i = 0; lecture_i < total_lectures; lecture_i++){
      
      int teacher_available_count = 0;
      for(int teacher_i = 0; teacher_i < total_teachers; teacher_i++){
        for(int duration_i = 0; duration_i < teachers[teacher_i].size(); duration_i++){
          if(teachers[teacher_i][duration_i].contains(lectures[lecture_i])){
            teacher_available_count++;
          }
        }
      }

      int student_available_count = 0;
      for(int student_i = 0; student_i < total_students; student_i++){
        for(int duration_i = 0; duration_i < students[student_i].size(); duration_i++){
          if(students[student_i][duration_i].contains(lectures[lecture_i])){
            student_available_count++;
          }
        }
      }

      res += min(teacher_available_count,student_available_count);
    }
    printf("%d\n",res);
  }
}

Measured memory_bytes: 1372
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define elif else if
#define lli long long int
#define ld long double
#define vec vector
#define forn(a) for(lli a=0; a<n; a++)
#define all(x) x.begin(), x.end()
#define deb(x) cerr<<#x<<" = "<<x<<endl

using namespace std;

int main(){
  IOS;
  
  string s; cin>>s;
  int n = s.size();
  vec<char> v(n);
  forn(i) v[i]=s[i];
  
  int cont1 = 0;
  forn(i){
    if(i%2){//quiero pintarlo de 1
      if( v[i]=='0') cont1++; 
    }else{//quiero pintarlo de 0
      if( v[i]=='1') cont1++;
    }
  }
  
  int cont2 = 0;
  forn(i){
    if(i%2){//quiero pintarlo de 0
      if( v[i]=='1') cont2++; 
    }else{//quiero pintarlo de 1
      if( v[i]=='0') cont2++;
    }
  }
  
  cout<<min(cont1, cont2)<<endl;
  
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main(void){

    int a, b;
    cin >> a >> b;
    cout << a*b;

    return 0;
}

Measured memory_bytes: 3532
#include<stdio.h>

int main(void){
    int a,b;
    int tap=-1;
    scanf("%d",&a);
    scanf("%d",&b);
    int i;
    for (i = 0; ((a*i)-i+1)-b<0; i++)
    {
        tap=((a*i)-i+1)-b;
        //printf("%d\n",tap);
    }
    printf("%d\n",i);
    
    return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("O3")
/*{{{*/
#include <bits/stdc++.h>
#ifdef LOCAL
int c_ = 0;
#define cout (c_?cerr:cout)
#define debug(...) \
{if(!c_++)cerr<<"\033[96;1m"; \
__VA_ARGS__; \
if(!--c_)cerr<<"\033[0m";}
#else
#define debug(...) {}
#endif
#define assrt(...) debug(\
if (not (__VA_ARGS__)) \
    exit((cerr << __LINE__ << ": " << #__VA_ARGS__ << '\n', 0));\
)
#define st first
#define nd second
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
using namespace std; using ll = long long;
template < typename t > using V = vector< t >;
template < typename t, size_t s > using A = array< t, s >;
void print() {cout << '\n';}
template< typename t, typename... v >
void print(const t& a, const v&... b)
{cout << a << (sizeof...(b)?" ":""); print(b...);}
template< typename t > void print_range(t a, const t& b)
{ while (a != b) cout << (*a++) << ' '; cout << '\n';}
#define dump(...) debug(print(#__VA_ARGS__,'=',__VA_ARGS__))
#define dump_range(...) debug(cerr<<#__VA_ARGS__ << ": "; print_range(__VA_ARGS__))
/*}}}*/

constexpr int nax = 1e5;

int n, tab[nax];

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

    cin >> n;

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

    sort(begin(tab), begin(tab) + n);

    int v = 0;
    ll sum = 0;

    for (int i = 0; i < n; ++i)
    {
        if (sum * 2 < tab[i])
            v = i;
        sum += tab[i];
    }

    print(n - 1 - v + 1);
}

Measured memory_bytes: 640
/* - - - - - - - - - - - - - - -
	User : 		VanishD
	problem :
	Points : 	
- - - - - - - - - - - - - - - */
# include <bits/stdc++.h>
# define 	ll 		long long
using namespace std;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
int read(){
	int tmp = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9'){ if (ch == '-') fh = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9'){ tmp = tmp * 10 + ch - '0'; ch = getchar(); }
	return tmp * fh;
}
const int N = 100010;
int n, num[N], v[N], ans, now[N], hav[N * 2];
bool check(int x){
	ll tot = 1ll * n * (n + 1) / 2, sum = 0;
	memset(hav, 0, sizeof(hav));
	for (int i = 1; i <= n; i++)
		if (num[i] >= x)
			now[i] = 1; else now[i] = -1;
	int delt = 100005, cnt = 0;
	for (int i = 1; i <= n; i++){
		if (now[i] == 1){
			delt--;
			cnt = cnt + hav[delt] + 1;
			hav[delt + 1] += 1;
		}
		else {
			cnt = cnt - hav[delt];
			delt++;
			hav[delt - 1] += 1;
		}
		sum = sum + cnt;
	}
	if (sum >= (tot + 1) / 2)
		return true;
		else return false;
}
int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; i++)
		num[i] = v[i] = read();
	sort(v + 1, v + n + 1);
	int pl = 1, pr = n;
	while (pl <= pr){
		int mid = (pl + pr) / 2;
		if (check(v[mid]) == true)
			ans = v[mid], pl = mid + 1;
			else pr = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

	int ans = 0;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b < c + d)
		cout << "Right" << endl;
	else if (c + d < a + b)
		cout << "Left" << endl;
	else
		cout << "Balanced" << endl;

	return 0;
}

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

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

    int N;
    cin >> N;

    vector<long long> A(N);
    for (int i=0; i<N; ++i) {
        cin >> A[i];
    }

    vector<long long> p(N, 1);
    for (int i=0; i<N; ++i ) {
        for (int j=0; j<N; ++j) {
            p[j] = (p[j] * A[i]) % A[j];
        }
    }

    long long ans = 0;
    for (int i=0; i<N; ++i) {
        p[i] = (p[i] + A[i] - 1) % A[i];
        ans += p[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int main(){
  while(int m = getInt()){
    vector<int> memo(m);
    vector<vector<int> > t(m);
    queue<int> empty;

    REP(i,m) t[i].push_back(memo[i] = i);

    while(true){
      const int a = getInt() - 1;
      const int b = getInt() - 1;

      if(a + b == -2) break;
      if(a == b) continue;

      const int idx = memo[a];
      const int dst = b == -1 ? -1 : memo[b];
      const int h   = find(t[idx].begin(), t[idx].end(), a) - t[idx].begin();
      const int h2  = b == -1 ? -1 : find(t[dst].begin(), t[dst].end(), b) - t[dst].begin();

      if(idx == dst && h > h2) continue;
      if(b == -1 && h == 0) continue;

      for(int i = h + 1; i < (int)t[idx].size(); i++){
	int next = empty.front(); empty.pop();
	memo[t[idx][i]] = next;
	t[next].push_back(t[idx][i]);
      }

      if(h == 0)
	empty.push(idx);

      t[idx].resize(h);

      const int dst2 = b == -1 ? -1 : memo[b];

      if(b == -1){
	int next = empty.front(); empty.pop();
	memo[a] = next;
	t[next].push_back(a);
      }else{
	memo[a] = dst2;
	t[dst2].push_back(a);
      }
      
      //printf("%d %d\n", a + 1, b + 1);
      //REP(i,m) printf("%d ", t[i].size()); puts("");
    }

    vector<int> ans;
    REP(i,m) if(t[i].size()) ans.push_back(t[i].size());
    sort(ans.begin(), ans.end());
    REP(i,ans.size())
      printf("%d\n", ans[i]);
    puts("end");
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e3 + 5;
int d[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n,x,y; cin >> n >> x >> y;
    int cir = y - x + 1;
    for (int i = 1 ; i <= n; i++){
        for (int j = i + 1 ; j <= n ; j++){
            int orr = j - i;
            int now = abs(i - x) + 1 + abs(y - j);
            if(orr > now) d[orr]-- , d[now]++;
        }
    }
    for (int i = 1 ; i <= n - 1 ; i++){
        cout << d[i] + n - i << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define DEBUG(vec) for (auto v : vec) { cout << v << " "; } cout << endl;

using namespace std;

// カウンター
template <typename T>
struct Counter {
  map<T, ull> cnt;
  void add(T key) {
    if (cnt.count(key)) {
      cnt[key]++;
    } else {
      cnt[key] = 1;
    }
  }
  void add(vector<T> keys) {
    for (auto key : keys) {
      add(key);
    }
  }
  ll get(T key) {
    if (cnt.count(key)) {
      return cnt[key];
    } else {
      return 0;
    }
  }
  pair<T, ull> max() {
    T key;
    ull mx = 0;
    for (auto kv : cnt) {
      if (kv.second > mx) {
        mx = kv.second;
        key = kv.first;
      }
    }
    return make_pair(key, mx);
  }
  typename map<T, ll>::iterator begin() {
    return cnt.begin();
  }
  typename map<T, ll>::iterator end() {
    return cnt.end();
  }
  typename map<T, ll>::reverse_iterator rbegin() {
    return cnt.rbegin();
  }
  typename map<T, ll>::reverse_iterator rend() {
    return cnt.rend();
  }
};

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

  ll H, W, N;
  cin >> H >> W >> N;

  Counter<pair<int, int>> c;

  REP(i, N) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    for (int x = -2; x <= 0; x++) {
      for (int y = -2; y <= 0; y++) {
        if (a + x >= 0 && a + x < H - 2 && b + y >= 0 && b + y < W - 2) {
          c.add(make_pair(a + x, b + y));
        }
      }
    }
  }
  ll total = 0;
  ll ans[10] = {};
  for (auto kv : c.cnt) {
    // cout << "p: " << kv.first.first << " " << kv.first.second << " " << kv.second << endl;
    ans[kv.second]++;
    total++;
  }
  cout << (H - 2) * (W - 2) - total << endl;
  for (int i = 1; i <= 9; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 56576
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
const int mod=1e9+7;
 
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
 
void printv(vi& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vll& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  //init(); // mint初期化
  cin.tie( 0 );
  ios::sync_with_stdio( false );
 
  int r;
  cin>>r;
  string ans;
  if(r<1200)ans="ABC";
  else if(r<2800)ans="ARC";
  else ans="AGC";
  cout(ans);
  return 0;
}

Measured memory_bytes: 125568
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;


Int n, x;
Int s[216];

Int fact[1080000];
Int revfact[1080000];
Int rev[1080000];
Int cntx[1080000];
Int dp[1080000];
void init(){
  Int m = MOD;
  fact[0] = 1;
  revfact[0] = 1;
  rev[0] = 0;
  rev[1] = 1;
  for(int i = 1;i < 1080000;i++){
    fact[i] = fact[i-1] * i % m;
    if(i>1)rev[i] = MOD / i * (MOD-rev[MOD % i]) % MOD;
    revfact[i] = revfact[i-1] * rev[i] % MOD;
  }
}

Int nCk(Int n, Int k){
  if(n < k)return 0;
  return fact[n] * revfact[n-k] % MOD * revfact[k] % MOD;
}


int main(){
  init();
  cin >> n >> x;
  for(int i = 0;i < n;i++){
    cin >> s[i];
    cntx[s[i]]++;
  }
  for(int i = 0;i <= 216000;i++)if(i)cntx[i] += cntx[i-1];
  sort(s, s + n);
  Int freedom = n - cntx[x];
  dp[x] = nCk(n, freedom) * fact[freedom] % MOD;
  
  Int ans = 0;
  for(int i = x;i >= 0;i--){
    Int cnt = 0;
    for(int j = n-1;j >= 0;j--){
      if(s[j] > i)continue;
      Int to = i % s[j];
      Int freedom = cntx[i] - cntx[to] -1;
      (dp[to] += dp[i] * nCk(j +cnt,freedom) % MOD * fact[freedom] % MOD) %= MOD;
      cnt++;
    }
    
    //    cout << i << " " << dp[i] << endl;
    if(cnt)dp[i] = 0;
    else (ans+= i * dp[i] % MOD) %= MOD;
  }
  if(ans <0)ans += MOD;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 28928
import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())

def sum_N(N):
	total = 0
	x = N
	while x > 0:
		total += x % 10
		x = x // 10
	return total

ans = 1000000000000
for i in range(1, N):
	ans = min(ans, sum_N(i) + sum_N(N - i))

print(ans)

Measured memory_bytes: 40812
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
lint N, M;
struct edge{lint from, to, cost;};
vector<edge> es;
vector<lint> dist;

bool bellman_ford(int s) {
  for (int i = 0; i < N; i++) dist[i] = INF;
  dist[s] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      edge e = es[j];
      if (dist[e.from] == INF) continue;
      if (dist[e.to] > dist[e.from] + e.cost) {
        dist[e.to] = dist[e.from] + e.cost;
        if (i == N - 1 && e.to == N - 1)
          return true;
      }
    }
  }
  return false;
}

signed main(){
	cin >> N >> M;
	dist.resize(N);
	for(int i = 0; i < M; i++){
		lint a, b, c; cin >> a >> b >> c; 
		es.push_back(edge{a - 1, b - 1, -c}); 
	}
	if(bellman_ford(0)) cout << "inf" << endl;
	else cout << -dist[N - 1] << endl;
}

Measured memory_bytes: 384
#include <cstdio>
using namespace std;
long long x,y,z,p;
int main()
{
	scanf("%lld%lld%lld",&x,&y,&z);p=x;
	x=(x-z)*(y-1);
	if(z)x*=2;
	printf("%.10lf",1.0*x/(p*p));
}

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

int main(){
    int n;
    cin >> n;
    vector<tuple<string,int,int>> p(n);
    for(int i=0;i<n;i++){
        string s;
        int x;
        cin >> s >> x;
        p[i] = make_tuple(s,-x,i+1);
    }
    sort(p.begin(),p.end());
    for(auto x:p){
        cout << get<2>(x) << endl; 
    }
    return 0;
}

Measured memory_bytes: 256
// clang-format off
	#include <bits/stdc++.h>
	using namespace std; using ll = long long; using uint = unsigned int;
	#define SFINAE(x, ...)	template <class, class = void> struct x : false_type {}; template <class T> struct x<T, void_t<__VA_ARGS__>> : true_type {};
	SFINAE(DefaultIO, decltype(cout << declval<T &>()))
	SFINAE(IsTuple, typename tuple_size<T>::type)
	SFINAE(Iterable, decltype(begin(declval<T>())))
	template <class T> constexpr char Space(const T &) { return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' '; }
	template <auto &os> struct Writer {
		template <class T> void Impl(T const &t) const {
			if constexpr (DefaultIO<T>::value) os << t;
			else if constexpr (Iterable<T>::value) { int i = 0; for (auto &&x : t) ((i++) ? (os << Space(x), Impl(x)) : Impl(x)); }
			else if constexpr (IsTuple<T>::value) apply([this](auto const &... args) { int i = 0; (((i++) ? (os << ' ', Impl(args)) : Impl(args)), ...);}, t);
			else static_assert(IsTuple<T>::value, "No matching type for print");
		}
		template <class F, class... Ts> auto &operator()(F const &f, Ts const &... ts) const { return Impl(f), ((os << ' ', Impl(ts)), ...), os << '\n', *this; }
	};
	template <auto &is> struct Reader {
		template <class T> auto& operator()(T &t) const {
			if constexpr (DefaultIO<T>::value) is >> t;
			else if constexpr (Iterable<T>::value) for (auto &x : t) (*this)(x);
			else if constexpr (IsTuple<T>::value) apply([this](auto &... args) { ((*this)(args), ...); }, t);
			else static_assert(IsTuple<T>::value, "No matching type for read");
			return *this;
		}
	};
	#ifdef NARUT_LOCAL
	#define Debug(...) cerr << "\033[0;31m", Writer<cerr>{}(__VA_ARGS__), cerr << "\033[0m\n"
	#else
	#define Debug(...) 0
	#endif
	[[maybe_unused]] constexpr Reader<cin> Cin; [[maybe_unused]] constexpr Writer<cout> Cout;
	#define FOR(i, j, n) for (int i = int(j); i < int(n); ++i)
	#define ROF(i, j, n) for (int i = int(n) - 1; i >= int(j); --i)
// clang-format on





auto Main() {
	int n;
	cin>>n;

	int p = 0;
	while (p*1000 < n) p++;
	cout << p*1000-n;
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
#ifdef NARUT_LOCAL
	assert(freopen("io/test.in", "r", stdin));
	cin.exceptions(cin.badbit | cin.failbit);
	cerr << fixed << setprecision(10);
#endif

	Main();
}


Measured memory_bytes: 3648
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	
	static final Scanner s=new Scanner(System.in);
	
	public static void main(String[] __){
		int
		in[]={s.nextInt(),s.nextInt(),s.nextInt()},
		sum=Arrays.stream(in).sum();
		
		System.out.println(sum%2==0&&Arrays.stream(in).anyMatch(i->i==sum/2)?"Yes":"No");
	}
}


Measured memory_bytes: 28500
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

int main()
{
	int n = 0;
	int sum0 = 0;
	double sum1 = 0;

	string s;
	for (; cin >> s;)
	{
		stringstream ss;
		ss << s;

		int a, b;

		ss >> a;
		ss.ignore();
		ss >> b;


		sum0 += a* b;
		sum1 += b;
		n++;
	}

	cout << sum0 << endl;
	cout << (int)(sum1 / n + 0.5) << endl;
}


Measured memory_bytes: 3160
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


def generate_graph(v_info):
    for info in v_info:
        adj_info = info[2:]
        for each in adj_info:
            adj_matrix[int(info[0]) - 1][int(each) - 1] = 1
    return adj_matrix


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    # assert len(vertex_info) == vertex_num

    ans = generate_graph(vertex_info)
    for v_result in ans:
        print(*v_result)

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  string s, ans;
  cin >> s;
  if(s[0]!='A'){
    cout << "WA" << endl;
    return 0;
  }
  if(isupper(s[1])){
    cout << "WA" << endl;
    return 0;
  }
  bool ok = false;
  for(int i=2; i<s.length()-1; i++){
    if(ok && isupper(s[i])){
      cout << "WA" << endl;
      return 0;
    }
    if(isupper(s[i])){
      if(s[i]=='C') ok = true;
      else{
        cout << "WA" << endl;
        return 0;
      }
    }
  }
  if(!ok){
    cout << "WA" << endl;
    return 0;
  }
  if(isupper(s[s.length()-1])){
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF 1145141919
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)

using namespace std;

int main(void){
  unsigned long long int N,M,sum=0,ans=0;
  cin >> N >> M;
  pair<int,int> drink[N];
  rep(i,N) cin >> drink[i].first >> drink[i].second;
  sort(drink,drink+N);
  while(sum<M){
    rep(i,N){
      while(drink[i].second>0 && sum<M){
        drink[i].second--;
        ans+=drink[i].first;
        sum++;
      }
    }
  }
  cout << ans << endl;
}

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

/* snippet: useful macros and functions */
#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; }
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; }
template<class T> T rng(const T &a, const T &b){ return a < b ? b - a : a - b; }
template<class T> void th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

/* snippet: modint library */
template<class T, int MOD>
class Modint{
	T val;
public:
	Modint(T val = 0) : val(val) {}
	operator T(){ return val; }
	Modint &operator+=(const Modint &a){ val += a.val; if(val >= MOD) val -= MOD; return *this; }
	Modint &operator-=(const Modint &a){ val -= a.val; if(val < 0) val += MOD; return *this; }
	Modint &operator*=(const Modint &a){ val = val * a.val % MOD; return *this; }
	void inverse(){T x[2]={MOD,val},a[2]={0,1};int i;for(i=0;x[!i];i^=1){a[i]-=x[i]/x[!i]*a[!i];x[i]=x[i]%x[!i];}if(!i)a[i]+= MOD;val=a[i];}
	Modint &operator/=(Modint a){ a.inverse(); return *this *= a; }
	friend Modint modpow(Modint a, int n){ Modint ret(1); while(n){ if(n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
	friend Modint operator+(Modint a, const Modint &b){ return a += b; }
	friend Modint operator-(Modint a, const Modint &b){ return a -= b; }
	friend Modint operator*(Modint a, const Modint &b){ return a *= b; }
	friend Modint operator/(Modint a, const Modint &b){ return a /= b; }
	friend std::ostream &operator<<(std::ostream &os, const Modint &a){ return os << a.val; }
};

/* snippet: using declarations */
using Int = long long;
using namespace std;
using Mint = Modint<long long, 1000000007>;

Int n;

int main(){
	Int i;
	Int count = 0;

	cin >> n;

	for(i = 2; i * i <= n; ++i){
		Int tmp = n;
		while(tmp % i == 0) tmp /= i;
		if(tmp % i == 1) ++count;
	}
	--n;
	for(Int j = 1; j * j <= n; ++j){
		if(n % j == 0){
			if(j >= i) ++count;
			if(n / j >= i) ++count;
		}
	}
	cout << ++count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	bool y=true,m=true;
	string s;
	cin>>s;
	if(stoi(s.substr(1,1))>2 && stoi(s.substr(0,1))==1)m=false;
	if(stoi(s.substr(0,1))>1)m=false;
	if(stoi(s.substr(0,1))==0 &&stoi(s.substr(1,1))==0)m=false;
	if(stoi(s.substr(2,1))==0 &&stoi(s.substr(3,1))==0)y=false;
	if(stoi(s.substr(3,1))>2  &&stoi(s.substr(2,1))==1)y=false;
	if(stoi(s.substr(2,1))>1)y=false;
	if(m==true&& y==false){
		cout<<"MMYY"<<endl;
	}else if(y==true&& m==false){
		cout<<"YYMM"<<endl;
	}else if(m==true&& y==true){
		cout<<"AMBIGUOUS"<<endl;
	}else if(m==false&& y==false){
		cout<<"NA"<<endl;
	}


	return 0;
}



Measured memory_bytes: 256
using System;

namespace AOJapps
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] count = new int[26];
            while (true)
            {
                String input = Console.ReadLine();
                if (input == null || input.Length == 0)
                {
                    break;
                }
                Char[] a = input.ToCharArray();
                for (int i = 0; i < a.Length; i++)
                {
                    if ( 'a' <= a[i] && a[i] <= 'z')
                    {
                        count[a[i] - 'a']++;
                    }
                    else if ( 'A' <= a[i] && a[i] <= 'Z')
                    {
                        count[a[i] - 'A']++;
                    }
                }
            }
            for (int i = 0; i < 26; i++)
            {
                Console.WriteLine((char)('a'+i) + " : " + count[i]);
            }
        }
    }
}

Measured memory_bytes: 9068
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define loop(i,n) rep(i,0,n)
using namespace std;
using ll = long long;
int main(){
    int n,z,w;
    cin >> n >> z >> w;
    vector<int> a(n);
    loop(i,n)cin >> a[i];
    //最初に先手が全部取るとスコアは |a[n-2]-w| 点になり、1枚残すと |a[n-2]-a[n-1]| 点なので、スコアはこの2つのmax以上
    //最初に先手が2枚以上残すと、後手は最後から2番目を取って |a[n-2]-a[n-1]| 点にできるので、スコアは |a[n-1]-a[n]| 点以下
    if(n==1)cout << abs(a[0]-w) << endl;
    else cout << max(abs(a[n-1]-w),abs(a[n-1]-a[n-2])) << endl;
    return 0;
}

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


int main()
{
	string s;
	long long k;
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>s)
	{
		string p=s; 
		cin>>k;
		int size = s.size();
		long long tot = 0;
		
		
		int chong=1;
		for(int i=1;i<size;i++)
		{
			if(s[i] == s[0]) chong++;
		}
		if(chong == size)
		{
			cout<<(size*k)/2<<endl;
			continue;
		}
		
		for(int i=0;i<size-1;i++)
		{
			if(s[i]==s[i+1]) 
			{
				int j=i+1;
				s[j] = 'a';
				while(s[j]==s[i]||s[j]==s[j+1]||s[j]==s[0])
				{
					s[j] = s[j] +1;
				}
				tot++;
				i++;
			}
		}
		
		if(s[size-1] == s[0])
		{
			
			long long  tot0 = 0;
			for(int i=1;i<size-1;i++)
			{
				if(p[i]==p[i+1]) 
				{
					int j=i+1;
					p[j] = 'a';
					while(p[j]==p[i]||p[j]==p[j+1]||p[j]==p[0])
					{
						p[j] = p[j] +1;
					}
					tot0++;
					i++;
				}
			}
			cout<<(long long )(tot+k-1+tot0*(k-1))<<endl;
			continue;
		}
		cout<<(long long )k*tot<<endl;
	}
 } 

	

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
ll inf = 1e10;

ll gcd(ll a, ll b){
  return (b != 0) ? gcd(b, a%b) : a;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  ll max1 = 0; ll max2 = 0;
  
  for(int i = n-1; i >= 0; ){
    ll now = a[i];
    if(max1 == 0){
      int cnt = 0;
      while(i >= 0 && now == a[i]){++cnt; --i;}
      if(cnt >= 4){max1 = now; max2 = now; break;}
      else if(cnt >= 2) max1 = now;
    }
    else if(max2 == 0){
      int cnt = 0;
      while(i >= 0 && now == a[i]){++cnt; --i;}
      if(cnt >= 2){ max2 = now; break;}
      
    }
    
  }
  cout << max1*max2 << "\n";
}  

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int x,y;
    while (1){
        cin >>x>>y;
        if(x==0 and y==0)break;
        if (x<=y) cout<<x<<" "<<y<<endl;
        else cout<<y<<" "<<x<<endl;
    }
    return 0;
}


Measured memory_bytes: 3016
A = int(input())
B = int(input())

if A == 1 and B == 2:
  print(3)
elif A == 2 and B == 1:
  print(3)
elif A == 3 and B == 1:
  print(2)
elif A == 1 and B == 3:
  print(2)  
elif A == 2 and B == 3:
  print(1)
elif A == 3 and B == 2:
  print(1)

Measured memory_bytes: 3064
n,m = map(int,input().split())
MOD = 10**9 + 7
FAC = [1]
INV = [1]
for i in range(1,m+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return (FAC[n]*INV[n-r]*INV[r])%MOD

def nPr(n,r):
  return (FAC[n]*INV[n-r])%MOD

# AとBで1個も一致していない組の数を包除原理を使って求める。
#   AとBで0個以上一致している組の数
# - AとBで1個以上一致している組の数
# + AとBで2個以上一致している組の数
# ...
# (-1)**n AとBでn個一致している組の数

# AとBでi個以上一致している組の数
#   nCr(n,i):一致しているi個の位置の選び方の数
# * nPr(m,i):一致しているi個の数の選び方の数
# * nPr(m-i,n-i):残りのn-i個の数の選び方の数(選べる数はm-i個残っている)
#                AとBの2つあるので、2乗する。

ans = 0
for i in range(n+1):
  now = nCr(n,i)
  now *= nPr(m,i)
  now %= MOD
  now *= pow(nPr(m-i,n-i),2,MOD)
  now %= MOD
  now *= pow(-1,i,MOD)
  now %= MOD
  ans += now
  ans %= MOD
print(ans)

Measured memory_bytes: 154784
#include<iostream>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<list>
#include<set>
#include<math.h>
#include<algorithm>
using namespace std;

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

int N,K;

#define INF ( 1 << 30 )
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int main()
{
    // get a integer
    ll A, B, C;
    scanf( "%lld", &A );
    scanf( "%lld", &B );
    scanf( "%lld", &C );
    vector<ll> v;
    v.push_back( A );
    v.push_back( B );
    v.push_back( C );
    sort(v.begin(), v.end(), []( const ll& a, const ll&  b) -> bool { return a < b; });

    /* for (auto&& v_ : v) { */
    /*     cout << v_ << endl; */
    /* } */

    auto it = v.begin();
    if( *it++ == 5 && *it++ == 5 && *it == 7 ) printf( "YES" );
    else printf( "NO" );

    /* printf( "%lld\n", N ); */
    /* printf( "%lld\n", K ); */
}



Measured memory_bytes: 256