akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long

ll sum[401][401];
ll dp[401][401];
#define inf (1ll<<60)
ll solve(int i,int j)
{
    if(i==j)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll min_=inf;
    for(int k=i;k<j;k++)
    {
        min_=min(min_,sum[i][j]+solve(i,k)+solve(k+1,j));

    }
    //cout<<min_<<endl;
    return dp[i][j]=min_;


}


int main() {
	//code

//cout<<inf<<endl;
	    int n;
	    cin>>n;
	    ll arr[n+1];
	    for(int i=1;i<=n;i++)
	    {
	        cin>>arr[i];
	    }

	    memset(dp,-1,sizeof(dp));
	    memset(sum,0,sizeof(sum));

	    for(int i=1;i<=n;i++)
	    {
	    for(int j=i;j<=n;j++)
	    {
//cout<<arr[j];
	    sum[i][j]=arr[j]+((i==j)?0:sum[i][j-1]);
	//    cout<<sum[i][j];
	    }
	    }


	    cout<<solve(1,n)<<endl;

	}


Measured memory_bytes: 2816
while 1:
    N = int(input())
    if N == 0:
        break
    P = [list(map(int, input().split())) for i in range(N)]
    P.sort(key=lambda x: (-x[1], x[0]))
    su = sum(w for w, s in P)
    for w, s in P:
        if s < su:
            print("No")
            break
        su -= w
    else:
        print("Yes")



Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head

void solve(){
    int n;
    cin >> n;
    vector<int> l(n);
    ll s = 0;
    for (int i = 0; i < n; i++){
        cin >> l[i];
        s += l[i];
    }
    sort(all(l));
    string ans;
    if (l[n-1] < s-l[n-1]) ans = "Yes\n";
    else ans = "No\n";
    cout << ans; 
}

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

    //int t; cin >> t; while (t--)
        solve();
}


Measured memory_bytes: 3648
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a = list(map(int, input().split()))

n_cnt = [0 for _ in range(2001)]
less = [0 for _ in range(2001)]
ress = [0 for _ in range(n)]
for i in a:
    n_cnt[i] += 1

tmp = 0
for i, c in enumerate(n_cnt):
    less[i] += tmp
    tmp += c

for i in range(n):
    cnt = 0
    tgt = a[i]
    for j in a[i+1::]:
        cnt += 1 if j < tgt else 0
    ress[i] = cnt


cnt = 0
for _a, less_r in zip(a, ress):
    less_all = less[_a]
    cnt +=  ((k*(k-1))//2) * less_all + less_r * k

print(cnt%1000000007)


Measured memory_bytes: 3188
#include<stdio.h>
int main(){
  int h,w,i;
  scanf("%d%d",&h,&w);
  char c[h+1][w+1];
  for(i=0;i<h;i++)
    scanf("%*c%s",c[i]);
  for(i=0;i<h;i++)
    printf("%s\n%s\n",c[i],c[i]);
  return 0;
}

Measured memory_bytes: 1740
#include <bits/stdc++.h>
using namespace std;
int main()
  {int N, X, Y; cin >> N >> X >> Y;
  vector<int> cs(N); for (int i{1}; i < N; ++i) for (int j{i + 1}; j <= N; ++j) ++cs[min({j - i, abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j)})];
  for (int k{1}; k < N; ++k) cout << cs[k] << "\n";}

Measured memory_bytes: 3608
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
 
#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
 
int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
 
    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0,h,w;
    string str;
    cin>>n>>h>>w;
    a=n-h+1;
    b=n-w+1;
    cout<<a*b<<endl;

 
    return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
	public static void main(String[] a){
		long debt = 100000;
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		for(int i = 0;i < n;i++){
			debt *= 1.05f;
			if(debt % 1000 != 0){
				debt = (debt/1000 + 1) * 1000;
			}
		}
		System.out.println(debt);
	}
}

Measured memory_bytes: 25976
#include <stdio.h>
#include <string.h>
#define SIZE 200100

int main() {
	int len, i, ID_s[26], ID_t[26], id_s, id_t, cnt, flg;
	for (i = 0; i < 26; i++) ID_s[i] = ID_t[i] = 0;
	char S[SIZE], T[SIZE], s, t;
	scanf("%s%s", &S, &T);
	len = strlen(S);
	cnt = 0;
	flg = 1;
	for (i = 0; i < len; i++) {
		s = S[i] - 'a'; t = T[i] - 'a';
		id_s = ID_s[s]; id_t = ID_t[t];
		if (id_s == 0 && id_t == 0) {
			cnt++;
			ID_s[s] = ID_t[t] = cnt;
		}
		else if (id_s != id_t) {
			flg = 0;
			break;
		}
	}
	printf(flg ? "Yes" : "No");
	return 0;
}

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

using namespace std;

int main()
{
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0])
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}


Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

a,b,k = inpm()

aa = min(a,k)
bb = max(0,(k-aa))

print(a - aa,max(0,b - bb))

Measured memory_bytes: 30688
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto n = readln.chomp.to!int;
  
  int res;
  foreach (i; iota(1, n+1, 2)) {
    int cnt;
    foreach (j; 1..i+1) {
      if (i % j == 0) {
        cnt++;
      }
    }
    if (cnt == 8) {
      res++;
    }
  }
  res.writeln;
}


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

#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <ull> vu;
typedef vector <vector <int>> vvi;
typedef pair <int, int> pi;
typedef vector <pair <int, int>> vpi;

int a, b;

bool p = 0;

bitset <102> arr[102];

ofstream fout ("out.txt");

void read() {
  cin >> a >> b;
  if (a > b) {
    swap (a, b);
    p = 1;
  }
  if (a == 1 && b == 1) {
    cout << "2 2\n##\n..";
    exit(0);
  }
}

void solve() {
  for(int i = 2; i <= 100 && a > 1; i += 2) {
    for(int j = 1; j <= i && a > 1; ++j) {
      arr[i + 1 - j][j] = 1;
      --a;
      --b;
    }
    ++b;
  }
  for(int i = 100; i >= 1 && b > 1; i -= 2) {
    for(int j = 99; j >= 1 && b > 1; j -= 2) {
      arr[i][j] = arr[i - 1][j] = arr[i - 1][j + 1] = 1;
      --b;
    }
  }
  cout << "100 100\n";
  for(int i = 1; i <= 100; ++i) {
    for(int j = 1; j <= 100; ++j) {
      if (p) {
        if (arr[i][j])
          cout << "#";
        else cout << ".";
      } else {
        if (arr[i][j])
          cout << ".";
        else cout << "#";
      }
    }
    cout << "\n";
  }
}

int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  //cin >> t;           // PLEASE REMOVE IT IF NEEDED
  while(t) {
    --t;
    read();
    solve();
  }
  return 0;
}



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

int gdc(int a, int b)
{
	int	r;

	r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main()
{
	int	n;
	int	x[100000+1];
	int	d[100000];
	int	i, r;

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

	for (i = 0; i <= n; ++i) {
	}

	for (i = 0; i < n; ++i) {
		d[i] = abs(x[i+1] - x[i]);
	}

	r = d[0];
	if (2 <= n) {
		r = gdc(d[0], d[1]);
		for (i = 2; i < n; ++i) {
			r = gdc(r, d[i]);
		}
	}
	printf("%d\n", r);

	return 0;
}


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

  int light[N];
  for(int i = 0; i < N; i++){
    light[i] = 0;
  }
  light[0] = 1;

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

  int next = 1;
  
  for(int i = 0; i < N; i++){
    if(light[next - 1] == 1){
      next = btn[next - 1];
      light[next-1] = 1;
      if(next == 2){
        cout << i + 1<< endl;
        exit(0);
      }
    }else{
      next = btn[next - 1];
      light[next] = 0;
    }
  }
  cout << "-1" << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
char a,b;
int main()
{
	ios::sync_with_stdio(0);
	cin>>a>>b;
    if(a=='A'&&b=='A')cout<<"="<<endl;
    if(a=='A'&&b=='B')cout<<"<"<<endl;
    if(a=='A'&&b=='C')cout<<"<"<<endl;
    if(a=='A'&&b=='D')cout<<"<"<<endl;
    if(a=='A'&&b=='E')cout<<"<"<<endl;
    if(a=='A'&&b=='F')cout<<"<"<<endl;
    if(a=='B'&&b=='A')cout<<">"<<endl;
    if(a=='B'&&b=='B')cout<<"="<<endl;
    if(a=='B'&&b=='C')cout<<"<"<<endl;
    if(a=='B'&&b=='D')cout<<"<"<<endl;
    if(a=='B'&&b=='E')cout<<"<"<<endl;
    if(a=='B'&&b=='F')cout<<"<"<<endl;
    if(a=='C'&&b=='A')cout<<">"<<endl;
    if(a=='C'&&b=='B')cout<<">"<<endl;
    if(a=='C'&&b=='C')cout<<"="<<endl;
    if(a=='C'&&b=='D')cout<<"<"<<endl;
    if(a=='C'&&b=='E')cout<<"<"<<endl;
    if(a=='C'&&b=='F')cout<<"<"<<endl;
    if(a=='D'&&b=='A')cout<<">"<<endl;
    if(a=='D'&&b=='B')cout<<">"<<endl;
    if(a=='D'&&b=='C')cout<<">"<<endl;
    if(a=='D'&&b=='D')cout<<"="<<endl;
    if(a=='D'&&b=='E')cout<<"<"<<endl;
    if(a=='D'&&b=='F')cout<<"<"<<endl;
    if(a=='E'&&b=='A')cout<<">"<<endl;
    if(a=='E'&&b=='B')cout<<">"<<endl;
    if(a=='E'&&b=='C')cout<<">"<<endl;
    if(a=='E'&&b=='D')cout<<">"<<endl;
    if(a=='E'&&b=='E')cout<<"="<<endl;
    if(a=='E'&&b=='F')cout<<"<"<<endl;
    if(a=='F'&&b=='A')cout<<">"<<endl;
    if(a=='F'&&b=='B')cout<<">"<<endl;
    if(a=='F'&&b=='C')cout<<">"<<endl;
    if(a=='F'&&b=='D')cout<<">"<<endl;
    if(a=='F'&&b=='E')cout<<">"<<endl;
    if(a=='F'&&b=='F')cout<<"="<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#define loop(i,a,b) for(int i = a; i < b; i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(), in.end()
#define shosu(x) fixed << setprecision(x)
using namespace std;

typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
const int inf = 1e9;
const ll INF = 2e18;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main(){
	string s;
	int a;
	while(cin>>s>>a,a){
		while(s.size()!=a)s="0"+s;
		map<string,int>ma;
		ma[s]=1;
		int t=1;
		while(1){
			t++;
			sort(all(s));
			string q=s;
			reverse(all(q));
//			cout<<q<<" "<<s<<endl;
			int sa=stoi(q)-stoi(s);
			s=to_string(sa);
//			cout<<s<<endl;
			while(s.size()!=a)s="0"+s;
			if(ma[s]){
				cout<<ma[s]-1<<" "<<sa<<" "<<t-ma[s]<<endl;
				break;
			}
			ma[s]=t;
		}
	}
}

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(ll a = 0;a < n;a++)

static const ll INF = 1e15;
static const ll mod = 1e9+7;

template<typename T>
static inline void chmin(T& ref, const T  value) {
    if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
    if (ref < value) ref = value;
}

int main() {
    ll n, c;
    cin >> n >> c;
    vector<P> events;
    rep(i, n) {
        int s, t, c1;
        cin >> s >> t >> c1;
        events.emplace_back(s-0.5, -c1);
        events.emplace_back(t, c1);
    }
    sort(events.begin(), events.end());
    map<int,int> q;
    int u = 0;
    rep(i, n * 2) {
        auto e = events[i];
        if (e.second < 0) {
            q[-e.second]++;
        }
        else {
            q[e.second]--;
            if (!q[e.second]) {
                q.erase(e.second);
            }
        }
        chmax(u, (int)q.size());
    }
    cout << u << endl;
    return 0;
}


Measured memory_bytes: 7452
import java.util.*;

public class Main {

    static int MOD = 1000000007;
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        String[] a=new String[n];
        String[] b=new String[m];

        for(int i=0;i<n;i++)a[i]=sc.next();
        for(int i=0;i<m;i++)b[i]=sc.next();

        boolean ok = true;
        for(int i=0;i<n-m+1;i++){//Aの縦移動
            System.out.println();
            for(int j=0;j<n-m+1;j++){//Aの横移動
                ok=true;
                for(int k=0;k<m;k++) {//Bの縦移動
                    //System.out.println(a[k+i].substring(j, j + m)+" "+b[k]);
                    if (ok&&!b[k].equals(a[k+i].substring(j, j + m))){
                        ok=false;
                        break;
                    }
                }
                if(ok){
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");

    }

}


Measured memory_bytes: 21972
import java.util.*;
import java.lang.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        while (true) {
            String x = sc.nextLine();
            int l = x.length();
            if (Character.getNumericValue(x.charAt(0)) == 0) {
                break;
            }
            int sum = 0;
            for (int i = 0; i < x.length(); i++) {
                sum += Character.getNumericValue(x.charAt(i));
            }
            System.out.println(sum);
        }
        
    }
}


Measured memory_bytes: 26668
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
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 FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int n;
    cin >> n;
    VL a(n);
    REP(i,n) a[i] = in();
    VL s(n+1);
    REP(i,n) s[i + 1] = s[i] + a[i];
    VVL dp(n + 1, VL(n + 1, 1e18));
    REP(i,n){
        dp[i][i + 1] = 0;
    }

    FOR(len,2,n){
        REP(l,n-len+1){
            int r = l + len;
            FOR(x,l+1,r-1){
                dp[l][r] = min(dp[l][r], dp[l][x] + dp[x][r] + s[r] - s[l]);
            }
        }
    }
    cout << dp[0][n] << endl;
    return 0;
}


Measured memory_bytes: 1536
#include <stdio.h>

int main()
{
	int i, N, d[100001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(d[i]));

	int lb = 100000, ub = 1;
	for (i = 1; i <= N; i++) {
		if (d[i] < lb) lb = d[i];
		if (d[i] > ub) ub = d[i];
	}
	ub++;
	
	int K, easy, hard;
	while (1) {
		if (lb > ub) break;
		K = (lb + ub) / 2;
		easy = 0;
		hard = 0;
		for (i = 1; i <= N; i++) {
			if (d[i] < K) easy++;
			else hard++;
		}
		if (easy == hard) break;
		else if (easy < hard) lb = K + 1;
		else ub = K - 1;
	}
	
	if (lb > ub) printf("0\n");
	else {
		lb = 1;
		ub = 100000;
		for (i = 1; i <= N; i++) {
			if (d[i] < K && d[i] > lb) lb = d[i];
			if (d[i] >= K && d[i] < ub) ub = d[i];
		}
		printf("%d\n", ub - lb);
	}
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 512
import numpy as np


def main():
    N, M = map(int, input().split())
    S = []
    for m in range(M):
        S.append([int(s) for s in input().split()][1:])
    P = [int(p) for p in input().split()]

    def f(l):
        a = []
        for e in l:
            a.append(e + [0])
            a.append(e + [1])
        return a

    a = [[0], [1]]
    for n in range(N-1):
        a = f(a)

    count = 0
    for e in a:
        mat = np.zeros((N, M), dtype=np.int)
        mat += np.array(e)[:, None]
        for i in range(M):
            for j in range(N):
                if j+1 not in S[i]:
                    mat[j, i] = 0
        ans = mat.sum(axis=0) % 2
        all_ok = True
        for i in range(M):
            if ans[i] != P[i]:
                all_ok = False

        if all_ok:
            count += 1

    print(count)


main()


Measured memory_bytes: 21656
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define MAP map<int,int>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;
const ll INF = (ll)1e17;

void ANS(bool flag){
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Ans(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void ans(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

int main() {
	int N, Ma, Mb;
	cin >> N >> Ma >> Mb;
	VI a(N), b(N), c(N);
	REP(i, N) cin >> a[i] >> b[i] >> c[i];
	VVVI dp(N + 1, VVI(401, VI(401, 5000)));
	dp[0][0][0] = 0;
	REP(i,N){
		REP(ca, 391) {
			REP(cb,391){
				dp[i + 1][ca][cb] = min(dp[i + 1][ca][cb] , dp[i][ca][cb]);
				dp[i + 1][ca + a[i]][cb + b[i]] = min(dp[i + 1][ca + a[i]][cb + b[i]], dp[i][ca][cb] + c[i]);
			}
		}
	}
	int cost = 5000;
	REP(i, N + 1) FOR(ca, 1, 401) FOR(cb, 1, 401) if (ca*Mb == cb*Ma) cost = min(cost, dp[i][ca][cb]);
	cout << ((cost == 5000) ? (-1) : cost) << endl;
	//cout << "ok" << endl;
	//cin >> N;


	return 0;
}


Measured memory_bytes: 27264
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse=True)
ans = ''
for i in range(m):
    if a[i] < sum(a)/(4*m):
        ans = 'No'
        break
    else:
        ans = 'Yes'
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define pp pair<int,int>
#define fi first
#define se second
#define maxx 200012
#define ll long long
#define pb push_back
#define mp make_pair
#define lb lower_bound

using namespace std;

int n,a[maxx];

double res;

void input(){
//    freopen("TEST.INP","r",stdin);
//    freopen("TEST.OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        double x;cin>>x;
        res+=1/x;
    }
    cout<<fixed<<setprecision(6)<<1/res;
}

int main()
{
    input();

    return 0;
}


Measured memory_bytes: 256
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
r.sort()
ans = sum(p[:X]) + sum(q[:Y])
flg = 1
lp, lq, lr = X - 1, Y - 1, C - 1
while flg == 1:
    if lr < 0 or (lp < 0 and lq < 0):
        break
    elif lq < 0 or p[lp] < q[lq]:
        if r[lr] > p[lp]:
            ans += r[lr] - p[lp]
            lr -= 1
            lp -= 1
        else: flg = 0
    elif lp < 0 or p[lp] >= q[lq]:
        if r[lr] > q[lq]:
            ans += r[lr] - q[lq]
            lr -= 1
            lq -= 1
        else: flg = 0
    else:
        flg = 0
print(ans)

Measured memory_bytes: 23216
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> Q;
typedef long long ll;
Q p[300000];
P aord[300000];
int ord[300000];
bool used[300000];
int n;
bool calc(int m){
	if(m==0)return true;
	int i;
	ll res=0;
	int count=m-1;
	memset(used,false,sizeof(used));
	for(i=0;i<m;i++)res+=aord[i].first;
	for(i=0;i<n;i++){
		if(res<=(ll)p[i].first.first*(ll)m)return true;
		used[p[i].second]=true;
		if(ord[p[i].second]<=count){
			count++;
			while(count<n&&used[aord[count].second])count++;
			if(count==n)return false;
			res+=aord[count].first-p[i].first.second;
		}
	}
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		p[i]=Q(P(b,a),i);
		aord[i]=P(a,i);
	}
	sort(p,p+n);
	sort(aord,aord+n);
	for(i=0;i<n;i++)ord[aord[i].second]=i;
	int l=0,r=n+1,mid;
	for(i=0;i<20;i++){
		mid=(l+r)/2;
		if(calc(mid))l=mid;
		else r=mid;
	}
	printf("%d\n",mid);
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<tuple<bool, int, int, int>> v(n);
  for (auto &e : v) {
    string s;
    cin >> s;
    int l = 0, r = 0;
    for (auto c : s) {
      if (c == '(') {
        l++;
      } else if (l > 0) {
        l--;
      } else {
        r++;
      }
    }
    e = {l <= r, l <= r ? -l : r, l, r};
  }
  sort(v.begin(), v.end());

  bool valid = true;
  int h = 0;
  for (auto [a, b, l, r] : v) {
    // cerr << a << ' ' << b << ' ' << r << ' ' << l << endl;
    if (h < r) {
      valid = false;
      break;
    }
    h -= r;
    h += l;
  }
  if (h != 0) valid = false;
  cout << (valid ? "Yes" : "No") << endl;
}


Measured memory_bytes: 18660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll maxn = 1e18;

ll dp[65][3][3][2];
int dig[65];

int cmp(int x, int y){
	return x - y + 1;
}

ll solve(ll n){
	int len = 0;
	while(n) dig[++len] = n%2, n/=2;
	dp[0][1][1][0] = 1;
	for(int i = 1; i < 65; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				for(int c = 0; c < 2; c++){
					for(int p = 0; p < 2; p++){
						for(int q = 0; q <= p; q++){
							int t1 = cmp(p^q, dig[i]), t2 = cmp((p+q+c)%2, dig[i]);
							int t3 = (p+q+c)/2;
							if(t1 == 1) t1 = j;
							if(t2 == 1) t2 = k;
							dp[i][t1][t2][t3] += dp[i-1][j][k][c];				 				
							dp[i][t1][t2][t3] %= mod;
						}
					}
				}
			}
		}	
	}
	ll res = 0;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			res += dp[64][i][j][0];
			res %= mod;
		}
	}
	return res;
}

int main(){
	ll N;
	cin >> N;
	cout << solve(N) << endl;
	return 0;	
}

Measured memory_bytes: 256
import heapq

n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
que = []
for _ in a:
  heapq.heappush(que, -1*_)

for _ in range(m):
  maxvalue = -1 * heapq.heappop(que)
  maxvalue /= 2
  heapq.heappush(que, -1*maxvalue)

print(sum([int(-1*_) for _ in que]))
  

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

int main() {
  int N;
  cin >> N;
  int x[1100];
  for (int i = 0; i < N; i++) cin >> x[i];

  int ans = 1000000;
  for (int i = 0; i <= 2000; i++) {
    int time = 0;
    for (int j = 0; j < N; j++) {
      time = max(time, abs(i - x[j]));
    }
    ans = min(ans, time);
  }

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


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
char s[2 * MAXN];
const int ALPHA = 26;
int n;
typedef vector<pair<string, string>> vpss;
vpss gen(int l, int r){
	vpss ret;
	int n = r - l + 1;
	for(int mask = 0; mask < (1 << n); mask++){
		string s1 = "", s2 = "";
		for(int i = 0; i < n; i++){
			if(mask & (1 << i)) s1 += s[l + i];
			else s2 += s[l + i];
		}
		ret.push_back({s1, s2});
	}
	return ret;
}
string rev(string x){
	reverse(x.begin(), x.end());
	return x;
}
int main(){
	scanf("%d", &n);
	scanf("%s", s);
	vpss vp1 = gen(0, n - 1), vp2 = gen(n, 2 * n - 1);
	map<pair<string, string>, int> mp2;
	for(auto ps : vp2) mp2[ps]++;
	long long ans = 0;
	for(auto ps : vp1) ans += mp2[{rev(ps.second), rev(ps.first)}];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 124652
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    ll K;
    cin >> K;
    ll N = 50;
    vector<ll> a(N, N - 1);
    for (int i = 0; i < N; i++) {
        a[i] += K / N;
    }
    for (int i = 0; i < K % 50; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                a[j]--;
            } else {
                a[i] += N;
            }
        }
    }

    cout << N << endl;
    for (int i = 0; i < N; i++) {
        cout << a[i];
        if (i != N - 1) cout << " ";
    }
    cout << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, ans=0;
    cin >> n;
    for(int i=1;i<=n;++i){
        int a;
        cin >> a;
        if(i%2==1 && a%2==1)++ans;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3584
s = input()
maxsum = 0
sum = 0
for i in range(len(s)):
    if s[i] == "A" or s[i] == "C" or s[i] == "G" or s[i] == "T":
        sum += 1
        if sum > maxsum:
            maxsum = sum
    else:
        sum = 0
print(maxsum)

Measured memory_bytes: 3060
#include<stdio.h>
int main(void){
	int n,a,b,x;
	scanf("%d %d %d",&n,&a,&b);
	x=n*a;
	if(x<b){
		printf("%d\n",x);
	}else{
		printf("%d\n",b);
	}
	return 0;
}

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

int main(){
	int a, b, t, T=0, s=0;
	cin >> a >> b >> t;
	while(++T){
		if(T*a>t+0.5) break;
		s += b;
	}
	cout << s;
	return 0;
}

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

const ll INF = 1000000000000000001LL;

ll digit_dp(ll x){
    if (x == 0) return 0;
    string s = to_string(x);
    int n = s.size();
    vector<vector<vector<ll>>> dp1(n + 1, vector<vector<ll>>(2, vector<ll>(15)));
    vector<vector<vector<ll>>> dp2(n + 1, vector<vector<ll>>(2, vector<ll>(15)));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < 2;j++){
            for(int k = 0;k < 15;k++){
                int lim = j ? 9 : s[i] - '0';
                for(int d = 0;d <= lim;d++){
                    bool f = j || d < lim;
                    int v = (k * 10 + d) % 15;
                    dp1[i + 1][f][v] += dp1[i][j][k];
                    dp2[i + 1][f][v] += dp2[i][j][k];
                    if(dp1[i + 1][f][v] > INF) dp1[i + 1][f][v] = INF;
                    if(dp2[i + 1][f][v] > INF) dp2[i + 1][f][v] = INF;
                }
            }
        }
        int lim = i == 0 ? s[0] - '0' : 9;
        for(int d = 1;d <= lim;d++){
            bool f = i != 0 || d < lim;
            dp1[i + 1][f][d] += 1;
            dp2[i + 1][f][d] += n - i;
            if(dp1[i + 1][f][d] > INF) dp1[i + 1][f][d] = INF;
            if(dp2[i + 1][f][d] > INF) dp2[i + 1][f][d] = INF;
        }
    }
    ll res = 0;
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 15;j++){
            if(j == 0){
                res += dp1[n][i][j] * 8;
                if(res > INF) res = INF;
            }
            else if(j % 3 == 0 || j % 5 == 0){
                res += dp1[n][i][j] * 4;
                if(res > INF) res = INF;
            }
            else{
                res += dp2[n][i][j];
                if(res > INF) res = INF;
            }
        }
    }
    return res;
}

string getstr(ll x, ll off){
    string res;
    for(ll i = x;i < x + 20;i++){
        if(i % 15 == 0){
            res += "FizzBuzz";
        }
        else if(i % 3 == 0){
            res += "Fizz";
        }
        else if(i % 5 == 0){
            res += "Buzz";
        }
        else{
            res += to_string(i);
        }
    }
    return res.substr(off, 20);
}

int main()
{
    ll x;
    cin >> x; --x;
    ll lb = 0, ub = x + 1;
    while(ub - lb > 1){
        ll m = (lb + ub) / 2;
        (digit_dp(m) <= x ? lb : ub) = m;
    }
    cout << getstr(lb + 1, x - digit_dp(lb)) << endl;
    return 0;
}



Measured memory_bytes: 3304
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int n = N;
        int ans = 0;
        
        while(n > 0) {
        	 ans += n%10;
        	 n /= 10;
        }
        System.out.println(N%ans == 0 ?"Yes":"No");
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define el "\n"
#define ll long long
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define M 1000000007
#define all(v) v.begin(), v.end()

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    string s;
    unordered_map<string,ll> mp;
    for(int i=0;i<n;i++){
         cin>>s;
         sort(all(s));
         mp[s]++;
    }
    ll ans=0,tmp=0;
    for(auto x:mp){
        tmp=(x.Y)*(x.Y-1);
        tmp/=2;
        ans+=tmp;
    }
    cout<<ans<<el;
    return 0;
}

Measured memory_bytes: 10660
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

int main(void){
  int n, r;
  cin >> n >> r;

  if(n<10){
    cout << r + 100 * (10-n);
  }
  else{
    cout << r << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
N,*as=$<.read.split.map(&:to_i)

arr = [10**9+1]

as.each do |a|
  idx = arr.bsearch_index {|n| a <= n}
  if idx
    if idx-1 < 0
      arr.unshift a
    else
      arr[idx-1] = a
    end
  else
    arr.unshift a
  end
end

ret = arr.length - 1
puts ret


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

void solve(std::string C) { cout << (char)(C[0] + 1) << endl; }

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can
// remove this line by using your custom template)
int main() {
    std::string C;
    std::cin >> C;
    solve(C);
    return 0;
}


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


def solve(N: int, K: int, R: int, S: int, P: int, T: str):
    ans=0
    flag=[False]*N
    for i in range(N):
        if i<K or T[i]!=T[i-K] or (not flag[i-K]):
            ans+=P if T[i]=='r' else S if T[i]=='p' else R
            flag[i]=True
        
    print(ans)

    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 4084
while n = gets.to_i
  break if n == 0
  arr = []
  arr << [0, 1000000001, -1]
  n.times do
    l = gets.split
    cmd = l.shift
    case cmd
    when "W"
      x, s = l.map(&:to_i)
      pos = 0
      loop do
        p, size, y = arr[pos]
        if y == -1
          arr[pos][2] = x
          if size <= s
            s -= size
          else
            arr[pos][1] = s
            arr.insert(pos + 1, [p + s, size - s, -1])
            break
          end
        end
        pos += 1
      end
    when "D"
      x = l[0].to_i
      arr.size.times do |i|
        arr[i][2] = -1 if arr[i][2] == x
      end
    when "R"
      sec = l[0].to_i
      arr.size.times do |i|
        p, size, y = arr[i]
        p y if p <= sec && sec - p < size
      end
    end
  end
  puts
end

Measured memory_bytes: 8948
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
  int a, b, c;
  std::scanf("%d%d%d", &a, &b, &c);
  std::vector<int> tmp = {a, b, c};
  std::printf("%d\n", a + b + c - *std::max_element(tmp.begin(), tmp.end()));

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{       
   public static void main(String[] args){

      Scanner sc = new Scanner(System.in);                                            
  
      Deque<Integer> q = new ArrayDeque<Integer>();
      
      int n = sc.nextInt();
                  
      for(int i = 0;i < n;i++){
          int a = sc.nextInt();
             if(i%2 == 0){
                 q.addLast(a);
             }else{
                 q.addFirst(a);
             }
      }
      

   if(n%2 == 0){
      while(!q.isEmpty()){
          System.out.print(q.poll());
          System.out.print(" ");
      }
   }else{
      while(!q.isEmpty()){
          System.out.print(q.pollLast());
          System.out.print(" ");
      }             
   }
     
      System.out.println();
      
   }
}
        

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"

void Main() {
    int r;
    cin >> r;
    cout << 3 * r * r << "\n";
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
//do not think about past and stay in this moment
//organize and work - Abhinav IIITA
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
#define int long long
#define ld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end() 
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -----------------------------------------------------------------------


// -----------------------------------------------------------------------


void solve(){
	int n;
	cin>>n;
	cout<<n/3;
	
}


// -----------------------------------------------------------------------


int32_t main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); 	
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}


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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 210, M = 110, INF = 0x3f3f3f3f;

int n, m, k;
int g[N][N], r[N];

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			if (i == j) g[i][j] = 0;
			else g[i][j] = INF;
			
	for (int i = 0; i < k; i ++ ) scanf("%d", &r[i]);
	sort(r, r + k);
			
	for (int i = 0; i < m; i ++ )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	
	for (int k = 1; k <= n; k ++ )
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= n; j ++ )
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				
	// for (int i = 1; i <= n; i ++ )
	// {
		// for (int j = 1; j <= n; j ++ )
			// cout << g[i][j] << ' ';
		// puts("");
	// }
				
	int res = INF;	
	do
	{
		// for (int i = 0; i < k; i ++ ) cout << r[i] << ' ';
		// puts("");
		int sum = 0;
		for (int i = 1; i < k; i ++ ) sum += g[r[i]][r[i - 1]];
		res = min(res, sum);
	}while(next_permutation(r, r + k));
	
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF 1LL<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
const int mod = 1e9 + 7;

int main(){
    ll n,a,b,c,d; cin >> n >> a >> b >> c >> d;
    b = b-a;
    double center = (c+d)/(double)2.0;
    double dist = center*2;
    double e = (n-1)*(d-c)/2.0;
    double t = center*(n-1);
    //cout << center << " " << e << " " << t << endl;
    rep(i,n-1){
        //cout << t-e << " " << t+e << endl;
        if(t-e<=b && b<=t+e){
            puts("YES");
            return 0;
        }
        t -= dist;
    }
    puts("NO");
}

Measured memory_bytes: 256
N,A,B,C = map(int, input().split())
ll = [int(input()) for _ in range(N)]
INF = 10**9
# 再帰で全組み合わせのコストを計算する
def dfs(cur,a, b, c):
    # 全部の竹を使ったらコストを返す
    if cur == N:
        return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a,b,c)>0 else INF
    ret0 = dfs(cur+1, a,b,c) # 使わない場合
    ret1 = dfs(cur+1, a+ll[cur],b,c)+10 # Aに使う場合
    ret2 = dfs(cur+1, a,b+ll[cur],c)+10 # Bに使う場合
    ret3 = dfs(cur+1, a,b,c+ll[cur])+10 # Cに使う場合
    return min(ret0,ret1,ret2,ret3)
print(dfs(0,0,0,0))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <complex>

using namespace std;

#define X real()
#define Y imag()

typedef complex<double> P;

bool cmp(const P &a, const P &b) {
	if (a.X != b.X) return a.X < b.X;
	return a.Y < b.Y;
}

vector<P> convex_hull(vector<P> ps){
	sort(ps.begin(), ps.end(), cmp);
	ps.erase(unique(ps.begin(), ps.end()), ps.end());
	int n = ps.size(), k = 0;
	vector<P> ch(2 * n);
	P a;
	for (int i = 0; i < n; ch[k++] = ps[i++]){
		while (k > 1 && imag(conj(ch[k - 1] - ch[k - 2]) * (ps[i] - ch[k - 1])) <= 0) --k;
	}
	for (int i = n - 2, t = k; i >= 0; ch[k++] = ps[i--]){
		while (k > t && imag(conj(ch[k - 1] - ch[k - 2]) * (ps[i] - ch[k - 1])) <= 0) --k;
	}
	ch.resize(k-1);
	return ch;
}

int main(){
	int n;
	while (cin >> n, n){
		vector<P> ps;
		while (n--){
			double x, y;
			char c;
			cin >> x >> c >> y;
			ps.emplace_back(x, y);
		}

		cout << ps.size()-convex_hull(ps).size() << '\n';
	}

	return 0;
}

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

int main(){
  vector<int> v(9, 0);
  for(int i = 0; i < 9; i++){
    cin >> v[i];
  }
  

  int n;
  cin >> n;

  for(int i = 0; i < n; i++){
    int b; cin >> b;
    for(int j = 0; j < 9; j++){
      
        if(v[j] == b){v[j] = 0;}
      }
    
  }

  bool f = false;

  for(int i = 0; i < 3; i++){
    if(v[3*i] == v[3*i +1] && v[3*i] == v[3*i + 2]){f = true;}
  }
  for(int i = 0; i < 3; i++){
    if(v[i] == v[i+3] && v[i] == v[i+6]){f = true;}
  }
  if(v[0] == v[4] && v[0] == v[8]){f = true;}
  if(v[2] == v[4] && v[2] == v[6]){f = true;}
  
  if(f){cout << "Yes" << endl;}
  else{cout << "No" << endl;}

 

}       

Measured memory_bytes: 256
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
#define mp make_pair
typedef pair<int, int> pint;
const int INF = 100000000;

int h, w, n;
char maze[1000][1000];
int i, j;

struct {
	int x, y;
} dir[4] = {
	{1, 0}, // right
	{0, 1}, // down
	{-1, 0}, // left
	{0, -1} // up
};

int dist[1000][1000];

int bfs(int hp) {
	for(int x = 0; x < w; x++) {
		for(int y = 0; y < h; y++) {
			dist[y][x] = INF;
		}
	}
	dist[i][j] = 0;
	queue<pint> q;
	q.push(mp(i, j));
	while(!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		if(maze[y][x] == (char)('0' + hp)) {
			i = y;
			j = x;
			maze[i][j] = '.';
			break;
		}
		for(int k = 0; k < 4; k++) {
			int nx = x + dir[k].x;
			int ny = y + dir[k].y;
			if(0 <= nx && nx < w && 0 <= ny && ny < h && maze[ny][nx] != 'X') {
				if(dist[ny][nx] == INF) { // never searched
					dist[ny][nx] = dist[y][x] + 1;
					q.push(mp(ny, nx));
				}
			}
		}
	}
	int ret = dist[i][j];
	return ret;
}

int main() {
	scanf(" %d %d %d", &h, &w, &n);
	for(int y = 0; y < h; y++) {
		scanf(" %s", maze[y]);
	}
	int ans = 0;
	{
		bool loop = true;
		for(int x = 0; x < w; x++) {
			for(int y = 0; y < h; y++) {
				if(maze[y][x] == 'S') {
					i = y;
					j = x;
					maze[y][x] = '.';
					loop = false;
					break;
				}
			}
			if(!loop) break;
		}
	}
	for(int x = 1; x <= n; x++) {
		ans += bfs(x);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 5668
//#include<cstdio>
//#include<cassert>
//#include<iostream>
//#include<cstring>
//#include<algorithm>
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e6 + 5)
#define MAXL ((ll)1e18 + 5)
#define MAX_X ((ll)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
#define MOD ((int)1e9 + 7)
#define NN ((int)1e6 + 7)
#define N ((int)2e5 + 7)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
#define BUCK 105
#define LEF (idx<<1)
#define RIG ((idx<<1)|1)
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < pair < ll, pair < ll, ll > >,  null_type,  less < pair < ll, pair < ll, ll > > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

int cnt[105];

int main()
{
    fastio;

    int n;

    cin>>n;
    int mxx = 0 , mnn = n;
    for(int i = 1 ; i<=n ; i++){
        int arr;
        cin>>arr;
        mxx = max(mxx,arr);
        mnn = min(mnn,arr);
        cnt[arr]++;
    }

    bool ans = 1;

    if(mnn != (mxx+1)/2) ans = 0;
    else{
        if(mxx&1){
            if(cnt[mnn] != 2) ans = 0;
        }
        else{
            if(cnt[mnn] != 1) ans = 0;
        }

        for(int i = mnn + 1 ; i<=mxx; i++) if(cnt[i] < 2) ans = 0;
    }

    if(ans) cout<<"Possible\n";
    else cout<<"Impossible\n";

    return 0;
}


Measured memory_bytes: 256
//おまじない
//#include <bits/stdc++.h>
//#include <stdio.h>
#include <iostream>
//#include <math.h>
#include<iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
#define pll pair<ll,ll>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 3000;

int h,w;
int ans = 0;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dis[maxn+10][maxn+10]={0};
queue<pair<int,int> > que;

int main(){
    
    cin >> h>>w;
    
    rep(i,h){
        rep(j,w){
            char c;cin >> c;
            if(c=='#'){
                dis[i][j]=0;
                que.push(make_pair(i,j));
            }else{
                dis[i][j]=INF;
            }
        }
    }
    
    while(!que.empty()){
        pair<int,int> p = que.front();que.pop();
        rep(i,4){
            int x = p.second+dx[i],y=p.first + dy[i];
            if(0<=x&&x<w&&0<=y&&y<h&&dis[y][x]==INF){
                dis[y][x]=dis[p.first][p.second]+1;
                ans = max(ans,dis[y][x]);
                que.push(make_pair(y,x));
            }
        }
    }
    
    cout << ans<<endl;
    
    return 0;
}


Measured memory_bytes: 19984
import java.util.ArrayList;
import java.util.Scanner;

 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		ArrayList<Integer> numList = new ArrayList<>();
		int ans = 0;
		
		for(int i = 0; i < N; i++) {
			numList.add(sc.nextInt());
		}
		
		int min = numList.get(0);
		for(int i = 0; i < N; i++) {
			if(numList.get(i) < min) {
				min = numList.get(i);
			}
			
			if(numList.get(i) <= min) {
				ans++;
			}
		}
		
		System.out.println(ans);
		sc.close();
	}
}

Measured memory_bytes: 91252
N = int(input())
v = list(map(int, input().split()))
d0 = {0: 0}
d1 = {0: 0}
for j, i in enumerate(v):
    if j % 2 == 0:
        if i in d0:
            d0[i] += 1
        else:
            d0[i] = 1
    else:
        if i in d1:
            d1[i] += 1
        else:
            d1[i] = 1

l0 = sorted(d0.items(), key=lambda x: -x[1])
l1 = sorted(d1.items(), key=lambda x: -x[1])

if l0[0][0] == l1[0][0]:
    a = min(N - l0[0][1] - l1[1][1], N - l0[1][1] - l1[0][1])
    print(a)
else:
    print(N - l0[0][1] - l1[0][1])


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

using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        int field[n][n];
        for(int i=0; i < n; i++)for(int j=0; j< n; j++) field[i][j] = 0;
        int x = n/2+1, y = n/2;
        field[x][y] = 1;
        for(int i=2; i <= n*n; i++){
            x++; y++;
            if(!(0 <= x && x < n)) x = 0;
            if(!(0 <= y && y < n)) y = 0;
            if(field[x][y] != 0){
                x++; y--;
                if(!(0 <= x && x < n)) x = 0;
                if(!(0 <= y && y < n)) y = n-1;
            }
            field[x][y] = i;
        }
        for(int i=0; i< n; i++){
            for(int j=0; j < n; j++){
                printf("% 4d", field[i][j]);
            }
            cout << endl;
        }
    }
}

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

int main(){
  int n;
  cin>>n;
  string s=to_string(n);
  int x=0;
  for(int i=0;i<s.size();i++)x+=s[i]-'0';
  if(n%x==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }

}


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

int solve(ll &min,ll &max,ll a){
    if(max % a != 0 && min % a != 0 && max/a - min/a == 0)return 0;
    else{
        min = (min+a-1)/a*a;
        max = max/a*a +a-1;
    }
    return 1;
}
int main(){
    int k;
    cin >> k;
    bool judge = true;
    vector<ll> a(k);
    ll max;
    ll min;
    max = 2;
    min = 2;
    for(int i = 0;i < k;i++){
        cin >> a[i];
    }
    reverse(a.begin(),a.end());
    for(int i = 0;i < k;i++){
        judge = solve(min,max,a[i]);
        if(judge == false)break;
    }
    if(judge)cout << min << " " << max << endl;
    else cout << -1 << endl;
    //cin >> k;
}

Measured memory_bytes: 1024