akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt(), m = in.nextInt();

			List<P>[] g = new ArrayList[n];
			g = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);

			for (int i = 0; i < m; i++) {
				int a = in.nextInt()-1;
				int b = in.nextInt()-1;
				long c = in.nextLong();
				g[a].add(new P(b, -c));
			}

			long[] node = new long[n];
			Arrays.fill(node, LINF);

			boolean[] loop = new boolean[n];

			node[0] = 0;

			int i = 0;
			// n 回リピート
			while (i++ < n) {

				// 各辺を1回使用
				for (int from = 0; from < n; from++) {
					for (int j = 0; j < g[from].size(); j++) {
						int to = g[from].get(j).num;
						long c = g[from].get(j).cost;

						if (node[from] + c < node[to]) {
							node[to] = node[from] + c;
							if (i == n) {
								loop[to] = true;
							}
						}
					}
				}
			}

			if (loop[n-1]) {
				out.println("inf");
			} else {
				out.println(-node[n-1]);
			}
		}

		class P {

			int num;
			long cost;

			public P(int num, long cost) {
				super();
				this.num = num;
				this.cost = cost;
			}
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

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

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}


Measured memory_bytes: 28628
from math import tan, degrees, cos, sin, atan
a, b, x = map(int, input().split())
x = x/(a**2)

if x < b/2:
    alpha = degrees(atan((b**2)/(2*a*x)))
elif x > b/2:
    alpha = degrees(atan((2*b - 2*x)/a))
else:
    alpha = degrees(atan(b/a))

print(alpha)


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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 

	string s;
	cin >> s;
	bool ck = s.find("9") != string::npos;
	cout << (ck ? "Yes" : "No");

	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<int> X(M);
	vector<int> d(M);
	for (int i = 0; i < M; i++)
	{
		cin >> X[i];
	}
	sort(X.begin(), X.end());
	for (int i = 1; i < M; i++)
	{
		d[i-1] = X[i]-X[i-1];
	}
	sort(d.begin(), d.end(), greater<int>());
	N--;
	int it = 0;
	for (int i = N; i > 0; i--)
	{
		d[it] = 0;
		it++;
		if(it>=M-1)break;
	}
	
	
	int ans = 0;
	for (int i = 0; i < M-1; i++)
	{
		ans += d[i];
	}
	
	cout << ans << endl;
	 
}



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

void eratos(int n, vector<bool> &isPrime) {
  isPrime.at(0) = false;
  isPrime.at(1) = false;
  for (int i = 2; i <= n; i++) {
    if (isPrime.at(i)) {
      for (int j = i*2; j <= n; j += i) isPrime.at(j) = false;
    }
  }
}

int main() {
  int Q; cin >> Q;
  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; i++) cin >> l.at(i) >> r.at(i);
  vector<bool> isPrime(100001, true);
  eratos(100000, isPrime);
  vector<int> S(100001, 0);
  for (int i = 1; i < 100001; i++) {
    S.at(i) = S.at(i-1);
    if (i % 2 == 0) continue;
    if (isPrime.at(i) && isPrime.at(((i+1)/2))) S.at(i)++;
  }
  for (int i = 0; i < Q; i++) {
    cout << S.at(r.at(i)) - S.at(l.at(i)-1) << endl;
  }
}

Measured memory_bytes: 1792
#include <iostream>
#include <bits/stdc++.h>
#include <iomanip>
#include<math.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
int  main(){
  ios_base::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
    int n,m;
    cin>>n>>m;
    
    if(n<2&&m<2)
      cout<<"0"<<endl;
 	else if(n>=2&&m<2)
      cout<<n*(n-1)/2<<endl;
  	else if(n<2&&m>=2)
      cout<<m*(m-1)/2<<endl;
  	else{
      cout<<n*(n-1)/2+m*(m-1)/2<<endl;
    }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	s, t := scanText(), scanText()

	for i := 0; i < n; i++ {
		fmt.Print(string(s[i]))
		fmt.Print(string(t[i]))
	}
	fmt.Println()
}


Measured memory_bytes: 640
const main = arg => {
  arg = arg.trim().split("\n");
  arg=arg[0].split(" ").map(x=>Number(x));
  let g;
  let count=0;
  for (i = arg[0]; i <=arg[1]; i++) {
   g=i;
   c=g%10;
   g/=10;
   d=Math.floor(g%10);
   g/=100;
   e=Math.floor(g%10);
   g/=10;
   f=Math.floor(g%10);
        if(c==f&&d==e){
       count++;
      }
 
  }
 
  console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
	



Measured memory_bytes: 33288
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
#define ll long long
static const int INF = 1 << 22;
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
/*******source code below********/
#define MAX_V 100
ll N; // 頂点数
pii G[MAX_V][MAX_V];
ll d[MAX_V];
bool used[MAX_V];
void dijkstra(int s) {

	vector<ll> pre(N, -1); 
	pre[s] = s;// 最後にusedにした頂点を保存する
	//すべての頂点の頂点sからのコストをINFで初期化
	//すべての頂点の探索フラッグをfalseで初期化
	for (int i = 0; i < MAX_V; i++) {
		d[i] = INF;
		used[i] = false;
	}

	//頂点ｓから頂点ｓまでの距離は0．
	d[s] = 0;
	//次に最短距離ｄを決定する頂点を見つけてあげる

	while (true) {

		int v = -1;
		//頂点を全探索
		for (int i = 0; i < N; i++) {
			if (!used[i] && (v == -1 || d[i] < d[v])) v = i;
		}
		//一度もｄが更新されなかったら、break;
		if (v == -1) break;
		used[v] = true;

		//頂点vに隣接する頂点の距離を更新していく
		for (int i = 0; i < N; i++) {
			if (d[i] > d[v] + G[v][i].first) {
				d[i] = d[v] + G[v][i].first;
				pre[i] = v;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		int p = i;
		while (p != s) {
			G[p][pre[p]].second = 1;
			G[pre[p]][p].second = 1;
			p = pre[p];
		}
	}


}
int main(void) {

	cin >> N; // 頂点数


	//隣接行列の全要素をINFに初期化する
	for (int i = 0; i < MAX_V; i++) {
		for (int j = 0; j < MAX_V; j++) {
			G[i][j].first = INF;
			G[i][j].second = 0;
		}
	}


	ll M; //辺の数
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		long long a; cin >> a;
		long long b; cin >> b;
		long long c; cin >> c;
		a--; b--;
		G[a][b].first = c;
		G[b][a].first = c;

	}

	for (int i = 0; i < N; i++) {
		dijkstra(i);
	}
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (G[i][j].second == 1) count++;

		}
	}

	cout << M - count << endl;
	return 0;
}

Measured memory_bytes: 384
import math
A, B, X = map(int, input().split())
S = X/A
pi = math.acos(-1)

if S > A*B/2:
    print(math.atan((A*B-S)*2/(A**2))*180/pi)
else:
    print(math.atan(B*B/2/S)*180/pi)


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

int main()
{
  int n,m,x,y,z;
  string ans="War";
  cin>>n>>m>>x>>y;
  vector<int> a(n);
  vector<int> b(m);
  for(int i=0;i<n;i++)
  {
    cin>>a.at(i);
  }
  for(int i=0;i<m;i++)
  {
    cin>>b.at(i);
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  sort(b.begin(),b.end());
  for(int i=x+1;i<=y;i++)
  {
    if((a.at(0)<i)&&(b.at(0)>=i))
    {
      ans="No War";
      break;
    }
  }
  cout<<ans<<endl;
}

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

#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define repm(i, a, n) for (ll i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define mod (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<vector<int>>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()

int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

void print(bool f)
{
    cout << (f ? "Yes" : "No") << endl;
}

void Print(bool f)
{
    cout << (f ? "YES" : "NO") << endl;
}

int main(void)
{
    unsigned long long a, k;
    double b;
    cin >> a >> b;
    if (a != 0 && b != 0)
    {
        k = b * 1000;
        a *= k;
        a /= 1000;
        cout << a << endl;
    }
    else
        cout << 0 << endl;
}

Measured memory_bytes: 3716
#include<bits/stdc++.h>
#define mod ((int)1e9+7)
using namespace std;
typedef pair<int,int> pi;
typedef long long int ll;

const int N = (int)2e5+5;

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

    int n; long double x; string s;
    cin>>n;
    long double ans = 0.0;
    for(int i=0;i<n;i++) {
        cin>>x>>s;
        if (s=="JPY") ans += x;
        else ans += 380000.0*x;
    }
    cout<<fixed<<setprecision(20)<<ans;
}


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

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

    std::unordered_set<std::string> s;
    std::string str;
    for (int i = 0; i < N; ++i) {
        std::cin >> str;
        s.insert(str);
    }

    std::cout << s.size() << std::endl;

    return 0;
}


Measured memory_bytes: 17616
#ABC145-C Average Length
N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
    x[i], y[i] = map(int, input().split()) #空白で区切られたN回の入力。のやり方の一つ。

import math

def root_length(x0, y0, x1, y1):
    return math.sqrt((x1-x0)**2 + (y1-y0)**2)
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += root_length(x[i],y[i],x[j],y[j])
ans *= 2 /N 
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;


int main() {
string S;
cin >> S;
if(S == "Sunny") cout << "Cloudy" <<endl;
if(S == "Cloudy") cout << "Rainy" << endl;
if(S == "Rainy") cout << "Sunny" << endl;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  [a, b, x] <- getIntList
  let nb = b `quot` x + 1
      na = if a > 0 then (a-1) `quot` x + 1 else 0
      ans = nb - na
  print ans

Measured memory_bytes: 3772
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = INT_MAX;
const int MOD = 1000000007;
const long long INF = LLONG_MAX;
const long long MINF = LLONG_MIN;

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

int N;
string S;

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

  int op = 0;
  int cl = 0;
  rep(i, 0, S.size()) {
    char c = S[i];
    if (c == '(') {
      ++op;
    } else {
      if (op) {
        --op;
      } else {
        ++cl;
      }
    }
  }

  rep(i, 0, cl) { cout << '('; }
  cout << S;
  rep(i, 0, op) { cout << ')'; }
}


Measured memory_bytes: 3620
#include<stdio.h>
 int main(){
 int a,b,c,i,ch,k,ca;
ca=0;
 scanf("%d %d %d",&a,&b,&c);

if(b<a) {
ch=a;
a=b;
b=ch;
}

 for(i=a;i<=b;i++){
k=c%i;
if(k==0) ca=ca+1;    
}
 printf("%d\n",ca);
 return 0;
}

Measured memory_bytes: 1804
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  if(s>"2019/04/30"){cout<<"TBD"<<endl;return 0;}
  else cout<<"Heisei";

  return 0;

}


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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int N;
int a[10000];

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

    cin >> N;
    rep(i, N) cin >> a[i];
    int res = 0;
    rep(i, N) {
        while(a[i] % 2 == 0) {
            ++res;
            a[i] /= 2;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
l = []
for i in range(n):
  a,b = map(int,input().split())
  l.append([a,b])
l.sort()
i = 0
count = 0
money = 0
while count < m:
  count += l[i][1]
  money += l[i][0]*l[i][1]
  i += 1
i -= 1
if count > m:
  money -= (count-m)*l[i][0]
print(money)

Measured memory_bytes: 53980
n = int(input())
a = [int(i) for i in input().split()]
s = sum(a)
x = 0
for i in a:
    b = (i * (s - i)) % (10 ** 9 + 7)
    s -= i
    x += b
    x %= (10 ** 9 + 7)
print(x)

Measured memory_bytes: 105132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793;

int main(){
  int n;
  cin >> n;
  ll a[110000];
  ll ans = 1;
  bool flag = false;
  rep(i, n){
    cin >> a[i];
    if(a[i] == 0) flag = true;
  }
  if(flag){
    cout << 0 <<endl;
    return 0;
  }else{
    for(int i = 0; i < n; i++){
      if(1000000000000000000LL / ans < a[i]){
        cout << -1 <<endl;
        return 0;
      }else{
        ans *= a[i];
      }
    }
  }
  cout << ans <<endl;
}

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

int main(){
  int n,m;string s,t;cin>>n>>s;m=n;t=s;
  bool f=1;
  while(f){
    f=0;
    int i=0;
    while(i<m-1){
      if(s.at(i)=='('&&s.at(i+1)==')'){
        s.erase(s.begin()+i);
        s.erase(s.begin()+i);
        f=1;
        m-=2;
      }
      i++;
    }
  }
  int count_r=0,count_l=0;
  REP(i,m) {
    if(s.at(i)==')') count_r++;
    else count_l++;
  }
  REP(i,count_r) cout<<'(';
  cout<<t;
  REP(i,count_l) cout<<')';
}

Measured memory_bytes: 256
import itertools
import math

n = int(input())
word = [[int(i)  for i in input().split()] for j in range(2)]

lis =[i for i in range(1,n+1)]
permutations_lis = itertools.permutations(lis)

count = 0
a = 0
b = 0
for one_case in permutations_lis:
    count += 1
    if(list(one_case) == word[0]):
        a = count
    if(list(one_case) == word[1]):
        b = count

print(abs(a-b))

Measured memory_bytes: 3064
gets
H = gets.strip.split(" ").map(&:to_i)
if H.size == 1
  puts 0
  exit 0
end

ans = 0
cur = 0
i = 0
while i < H.size - 1 do
  if H[i] < H[i + 1]
    ans = cur if cur > ans
    cur = 0
  else
    cur += 1
  end

  i += 1
end

puts [ans, cur].max


Measured memory_bytes: 21728
//============================================================================
// Name        : AOJ.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <stdio.h>
using namespace std;

int main() {
	int n,k;
	int R,L;
	while(1){
		R=0;L=0;
		cin>>n;
		if(n==0) break;
		for(int i=0;i<n;i++){
			cin>>k;
			if(k<=1)R+=1;
			if(k==0)L+=1;
		}
		if(n==R)cout<<"NA"<<endl;
		else cout<<n-L+1<<endl;

	}






	return 0;
}

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

int main(){
    int N ,tmp = 0,count = 1;
    cin >> N ;
    vector<int> d(N);
    for (int i = 0 ; i < N ; i ++){
        cin >> d.at(i);
    }
    for (int i = 0 ; i < N ; i++){
    	for(int j = i+1 ; j < N ; j ++){
        	if(d.at(i) < d.at(j)){
            	tmp = d.at(j);
          	    d.at(j) = d.at(i);
          	    d.at(i) = tmp;
            }
        }
    }

    for (int i = 0; i < N-1; i++){
        if (d.at(i) > d.at(i+1)){
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007


ll n, l;
string s[110];
int main() {
	cin >> n >> l;
	REP(i, n)cin >> s[i];
	sort(s, s + n);
	REP(i, n)cout << s[i];
	cout << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };



int main() {
	int N;
	scanf("%d", &N);

	int ans = 0;

	for (int i = 1; i <= N; i++) {
		int temp = 0;
		for (int j = 1; j <= i; j++) {
			if (i%j == 0)temp++;
		}
		if (i %2 ==1&&temp == 8)ans++;
	}
	
	printf("%d", ans);


}





/*         提出前の確認事項

・デバッグ用の関数は＜＜コメント化＞＞しているか？
・すべての＜＜入力例＞＞は試したか？
・＜＜限界値分析＞＞はしたか？
・＜＜出力の改行＞＞の有無は確認したか？
・文字列の＜＜スペル＞＞は確認したか？
　　　　　　　　↓
	 ＜＜提出先＞＞に注意して提出！！
*/

Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
	int n,i,cnt;
	char s[100001];
	scanf("%d",&n);
	scanf("%s",s);
	cnt=1;
	for(i=0;i<n-1;i++){
		if(!(s[i]==s[i+1])){
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}


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

int main() {
	int a,b,X,Y;
	cin >> a >> b;
	X = a%2;
	Y = b%2;
	if ((X == 0)||(Y == 0)){
		cout << "Even" << endl;
	}
	else {
		cout << "Odd" << endl;
	}
	
}

Measured memory_bytes: 3592
N, K = [int(i) for i in input().split()]

# more than K or K

res = []

for i in range(1, N + 1):
    # when dice is i
    if i >= K:
        res.append(1 / N)
        continue
    else:
        x = 1
        while i < K:
            x = x * 0.5
            i = i * 2
        l = (1/N) * x
        res.append(l)

print(sum(res))

Measured memory_bytes: 6296
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
int N, A, B;
int P[100];
stack<int> c1;
stack<int> c2;
stack<int> c3;

int main()
{
  cin >> N;
  cin >> A >> B;
  for(int i = 0; i< N; i++) {
    cin >> P[i];
    if (P[i] <= A)
      c1.push(P[i]);
    else if (A+1 <= P[i] && P[i] <= B)
      c2.push(P[i]);
    else if (P[i] > B)
      c3.push(P[i]);
  }
  cout << min({c1.size(), c2.size(), c3.size()}) << endl;
  return 0;
}

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

int main()
{
    int D, T, S;
    cin >> D >> T >> S;

    int a, b, c;
    a = D / S;
    b = D / S + 1;
    c = D % S;

    if (a == T && c == 0)
    {
        cout << "Yes" << endl;
    }
    else if (b > T)
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 3632
def main():
    n, k = map(int, input().split())
    n = n - (n // k * k)
    ans = n
    cnt = 0
    while cnt < 10:
        n = abs(n - k)
        if ans > n:
            ans = n
        else:
            cnt += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
program main
Implicit None
	integer(8)::n,k
	character(len = 50)::s
	
	read*,n,k
	read*,s
	
	if(s(k:k) == "A")then
		s(k:k) = "a"
		else if(s(k:k) == "B")then
		s(k:k) = "b"
		else
		s(k:k) = "c"
	endif
	
	print"(a)",trim(s)
end program main

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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


int main(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll d = c - a - b;
    if(d < 0){
        cout << "No" << endl;
        return 0;
    }
    else{
        if(4 * a * b < d * d){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }

    return 0;
    
}


Measured memory_bytes: 256
from itertools import accumulate
N = int(input())
A = [list(map(int,input().split())) for _ in range(2)]
acc1 = list(accumulate(A[0], lambda x,y:x+y))
acc2 = [0]+list(accumulate(A[1], lambda x,y:x+y))
ma = -1
for i in range(N):
    ma = max(ma, acc2[-1]-acc2[i]+acc1[i])
print(ma)

Measured memory_bytes: 9196
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){

	ll k;
	cin >> k;
	
	ll c=1;
	ll num = 7;
	while(num < k){
		num = (num * 10) + 7;
		c++;	
	}

	if(k%2 == 0){
		cout << -1 << "\n";
	}
	else{
		ll rem1 = num%k;

		if(rem1 == 0){
			cout << c << "\n";
		}
		else{
			bool ok = 0;
			ll cnt = 0;
			while(cnt++ <=1e6){
				
				rem1 = (10*rem1 + 7)%k;
				c++;
				if(rem1 == 0){
					ok = 1;					
					break;
				}
			}
			if(ok){	
				
				cout << c << "\n";
			}
			else{
				cout << -1 << "\n";
			}
		}
	}
}

Measured memory_bytes: 3632
n = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i)

def f(x)
  y = Math.log2(x).floor
  while y >= 0 and x % (2 ** y) > 0 do
   y -= 1
  end
  return y
end

puts a.map{|x| f(x)}.reduce(:+).to_s

Measured memory_bytes: 2556
N,M,X = map(int,input().split())
B = [list(map(int,input().split())) for i in range(N)]
ANS = 10**5 * 12 + 1
for i in range(1<<N):
    SCORE=[0]*M
    MONEY=0
    for j in range(N):
        if (1<<j) & i != 0:
            MONEY+=B[j][0]
            for k in range(M):
                SCORE[k]+=B[j][k+1]
    if min(SCORE)>=X:
        ANS=min(ANS,MONEY)
if ANS == 10**5 * 12 + 1:
    print(-1)
else:
    print(ANS)


Measured memory_bytes: 9220
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
const int inf=1e8+20;
vector<int> num;
int mark[3*inf];
int main()
{
   int n;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       int a;
       scanf("%d",&a);
       num.push_back(a+1);
       num.push_back(a+2);
       num.push_back(a);
       mark[a+1]+=1;
       mark[a+2]+=1;
       mark[a]+=1;
   }
 //  int t=1000000000;
//   cout<<t<<endl;
   sort(num.begin(),num.end());;
  // cout<<"***"<<endl;
  //cout<<num[num.size()-1]<<" "<<num
   int maxn=num[num.size()-1];
   int minn=num[0];
   int ans=0;
 //  cout<<minn<<" "<<maxn<<endl;
   for(int i=minn;i<=maxn;i++)
   {
       ans=max(ans,mark[i]);
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 2804
# include <bits/stdc++.h>
# define ll long long
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7, INF = 1e9 + 100; 
int p[N], q[N], c[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, first = 0, second = 0;
	cin >> n;
	for(int i = 0; i < n; i ++)cin >> p[i];
	for(int i = 0; i < n; i ++)cin >> q[i];
	for(int i = 0; i < n; i ++)c[i] = i + 1;
	int cur = 0;
    do {
    	bool ok1 = true, ok2 = true;
    	cur ++;
    	for(int i = 0; i < n; i ++){
    		if(c[i] != p[i])ok1 = false;
    		if(c[i] != q[i])ok2 = false;
		}
		if(ok1 == true)first = cur;
		if(ok2 == true)second = cur;
  	} while (next_permutation(c,c+n));
	cout << abs(first - second) << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
const int N = 1e5+10;
const int M = 1e6+10;
int n,m,k,tot=0,q;
ll ans=0;
int head[N],vis[N],l[N],r[N];
int v[N],d[N],c[N],color[N];
vector<int>edg[N];
void bfs(int v,int d,int c){

    queue<pair<int,int> >q;
    if(vis[v]>=d)return;
    q.push(make_pair(v,d));
    while(!q.empty()){
        int t=q.front().first;
        int dd=q.front().second;
        q.pop();
        
        if(!color[t])color[t]=c;
        vis[t]=max(vis[t],dd);if(dd==0)continue;
        for(int i=0;i<edg[t].size();i++){
            int u=edg[t][i];
            if(vis[u]>=dd-1&&vis[u]!=-1)continue;
            q.push(make_pair(u,dd-1));
        }
    }
}
int main() {
    int T;
    met(vis,-1);
    scanf("%d%d",&n,&m);
    int u,vv;
    while(m--){
        scanf("%d%d",&u,&vv);
        edg[u].push_back(vv);
        edg[vv].push_back(u);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&v[i],&d[i],&c[i]);
    }
    for(int i=q;i>=1;i--){
        bfs(v[i],d[i],c[i]);
    }
    for(int i=1;i<=n;i++)printf("%d\n",color[i]);
    return 0;
}



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

using namespace std;

const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.14159265;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); ++i)
#define RFOR(i,n,r) for(ll i = (ll)(n-1); i >= r; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)
#define ALL(x) x.begin(),x.end()
#define CALL(x) x.cbegin(),x.cend()
#define RALL(x) x.rbegin(),x.rend()
#define CRALL(x) x.crbegin(),x.crend()

#define cout cout << setprecision(12)

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vp = vector<pair<ll, ll>>;
using vs = vector<string>;
using vc = vector<char>;
using lst = list<ll>;
using pq = priority_queue<ll>;

template < typename T >
inline void dbg(T a) { cout << a << ' '; }

ll n, m, k, ans = 0, sum = 0, cnt = 0;
//double d;
string s;
char c;

/*--------------------template--------------------*/

int main() {
    cin >> n;
	int a[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
    cout << a[n-1] << endl;
}


Measured memory_bytes: 256
from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Measured memory_bytes: 133228
#include <stdio.h>
#include <math.h>
#include <string.h>

typedef struct{
	double a,b;
}circles;

int main(void){
	int i,n;
	circles x,y,r;
	double num;
	char str[100];

	fgets(str,sizeof(str),stdin);
	sscanf(str,"%d",&n);
	for(i=0;i<n;i++){
		fgets(str,sizeof(str),stdin);
		sscanf(str,"%lf %lf %lf %lf %lf %lf",&x.a,&y.a,&r.a,&x.b,&y.b,&r.b);
		num=sqrt((x.a-x.b)*(x.a-x.b)+(y.a-y.b)*(y.a-y.b));
		if(r.a+r.b<num)
			printf("0\n");
		else if(num+r.b<r.a)
			printf("2\n");
		else if(num+r.a<r.b)
			printf("-2\n");
		else
			printf("1\n");
	}
	return 0;			
}

Measured memory_bytes: 628
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <math.h>
#include <string.h>

using std::endl;

#define ll long long int
#define LEP(a, n) for(int a = 0; a < n; ++a)
#define INF 1145141919810
#define OUT std::cout
#define IN std::cin
#define itn int
#define fro for
#define sdt std

ll X, Y;

int main()
{
	IN >> X >> Y;


	if (X % Y == 0)
	{
		puts("-1");
		return 0;
	}
	else
	{
		if(Y % X == 0)
			OUT << X + Y << endl;
		else
		{
			OUT << X << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static int buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10;
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
int a[maxn],b[maxn],c[maxn];
int n,k;
int main()
{
	n=read(); k=read();
	if(n<2*k-1){
		puts("-1"); return 0;
	}
	for(int i=0;i<n;i+=2){
		int t=i/2;
		a[i]=t; b[i]=2*n-(n+1)/2+t; c[i]=2*n+i;
	}
	for(int i=1;i<n;i+=2){
		int t=i/2;
		a[i]=(n+1)/2+t; b[i]=n+t; c[i]=2*n+i;
	}
	for(int i=0;i<n;i++)
		writesp(a[i]+k),writesp(b[i]+k),writeln(c[i]+k);
	return 0;
}

Measured memory_bytes: 3328
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define un(x)           x.erase(unique(all(x)), x.end())
#define xx              first
#define yy              second
#define pb              push_back
#define all(v)          v.begin(), v.end()

#define D(x)            cerr << #x " = " << x << '\n'
#define DBG             cerr << "Hi!" << '\n'

#define CLR(a)          memset(a, 0, sizeof(a))
#define SET(a)          memset(a, -1, sizeof(a))

// inline int setBit(int n, int pos) { return n = n | (1 << pos); }
// inline int resetBit(int n, int pos) { return n = n & ~(1 << pos); }
// inline bool checkBit(int n, int pos) { return (bool)(n & (1 << pos)); }

// int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
// int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// unsigned int num = rng();
// shuffle(V.begin(), V.end(), rng);

/******************************************************************************************/

// const int MAX = 500010;
// const int INF = 0x3f3f3f3f;
// const int MOD = 998244353;

// inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
// inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
// inline int mul(int a, int b) { return (a * 1LL * b) % MOD; }


vector <pii> V;

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

    // freopen("in", "r", stdin); 
    // freopen("out", "w", stdout);
    
    int n, u, v;
    cin >> n;
    for(int i=1;i<n;i++) {
        cin >> u >> v;
        V.pb({u, v});
    }
    ll ans = 0;
    for(int i=1,j=n;i<=n;i++,j--) ans += i * 1LL * j;
    for(pii e : V) {
        u = e.xx;
        v = e.yy;
        if(u > v) swap(u, v);
        ans -= (u * 1LL * (n - v + 1));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5312
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <limits.h>
#include <math.h>

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

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
const int INF = INT_MAX;

int rate[10]={0};

int main() {
    // insert code here...    return 0;
    //////
    // input from txt
    /*
     std::ifstream in("input.txt");
     std::cin.rdbuf(in.rdbuf());
     std::ofstream out("output.txt");
     std::cout.rdbuf(out.rdbuf());
     ////
     */
    
    fill(rate,rate+10,0);
    int N;
    cin >> N;
    repeat(i, N){
        int a;
        cin >> a;
        int idx = min(a/400,8);
        rate[idx]++;
    }
    int cnt=0;
    repeat(i, 8){
        if(rate[i]>0)
            cnt++;
    }
    int minn = max(cnt,1);
    int maxn = cnt+rate[8];
    
    cout << minn << " " << maxn << endl;
    return 0;
}



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

int main(){
 char ch[200000];
 gets(ch);
 unsigned a, b;
 for(a = 0; ch[a] != 'A'; a++);
 for(b = strlen(ch); ch[b] != 'Z'; b--);
 printf("%d\n", b - a + 1);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LLI long long int
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int main(){
    int n; cin>>n;
    int a[100001]={},b[100001]={},c[100001]={};
    FOR(i,0,n) cin>>a[i];
    FOR(i,0,n) cin>>b[i];
    FOR(i,0,n) cin>>c[i];
    sort(a,a+n);
    sort(c,c+n);
    LLI ans=0;
    FOR(i,0,n){
        int *ap=lower_bound(a,a+n,b[i]);
        int *cp=upper_bound(c,c+n,b[i]);
        ans+=(LLI)(ap-a)*(n-(LLI)(cp-c));
    }
    co(ans);
}


Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
#define int long long
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
constexpr int INF = (int)1e9;
int d[100000][3];
signed main() {
  int N, M; cin >> N >> M;
  vector<vector<int>> G(N);
  REP(i, M) {
    int u, v; cin >> u >> v;
    u--;
    v--;
    G[u].push_back(v);
  }
  int S, T; cin >> S >> T;
  S--;
  T--;
  REP(i, N) REP(j, 3) d[i][j] = INF;
  queue<pair<int, int>> Q;
  Q.emplace(S, 0);
  d[S][0] = 0;
  while(!Q.empty()) {
    pair<int, int> p = Q.front();
    Q.pop();
    int u = p.first;
    int m = p.second;
    for (int v : G[u]) {
      int m1 = (m + 1) % 3;
      if (d[v][m1] > d[u][m] + 1) {
        d[v][m1] = d[u][m] + 1;
        Q.emplace(v, m1);
      }
    }
  }
  if (d[T][0] == INF) {
    cout << -1 << endl;
  } else {
    cout << d[T][0] / 3 << endl;
  }
}


Measured memory_bytes: 8064
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.container;
import std.datetime;

void main()
{
	auto res = iota(0, 1000001).array;

	foreach_reverse (i; 0..1000001) {
		foreach (y; 2..1001) {
			auto py = y ^^ 2;	
			if (i + py > 1000000) break;
			res[i+py] = res[i] + y;
		}
	}

	foreach_reverse (i; 0..1000001) {
		foreach (z; 2..101) {
			auto pz = z ^^ 3;
			if (i + pz > 1000000) break;
			res[i+pz] = min(res[i+pz], res[i] + z);
		}
	}
	
	while (1) {
		auto n = readln.chomp.to!int;
		if (!n) break;
		res[n].writeln;
	}
}

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

int dp[200010];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	cin >> s;
	int N = s.size();
	for(int i = 0; i < N + 2; i++){
		dp[i] = i;
	}
	int bit = 0;
	map<int, int> m;
	m[0] = 0;
	dp[0] = 0;
	for(int i = 0; i < N; i++){
		//cout << i << endl;
		dp[i + 1] = dp[i] + 1;
		int id = s[i] - 'a';
		// 全部余ってない
		int zero = bit;
		if(m.count(zero)){
			dp[i + 1] = min(dp[i + 1], m[zero] + 1);
		}
		// idが余ってて他余ってない
		int one = bit ^ (1 << id);
		if(m.count(one)){
			dp[i + 1] = min(dp[i + 1], m[one] + 1);
		}
		// idが余ってて他1つ余ってる
		for(int j = 0; j < 26; j++){
			if(j == id) continue;
			one = bit ^ (1 << id) ^ (1 << j);
			if(m.count(one)){
				//cout << char('a' + j) << endl;
				dp[i + 1] = min(dp[i + 1], m[one] + 1);
			}
		}

		if(!m.count(bit)){
			m[bit] = dp[i];
		}
		else{
			m[bit] = min(m[bit], dp[i]);
		}
		bit ^= 1 << id;
	}

	cout << dp[N] << endl;
}


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

#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
#include <stack>
#include <bitset>

//多倍長整数, cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

//#pragma gcc target ("avx2")
//#pragma gcc optimization ("o3")
//#pragma gcc optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a) //少数出力
#define printLdb(a) printf("%.50Lf\n", a) //少数出力
#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str()) //string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2LL) //等差数列の和、初項,末項,項数
#define pb push_back
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)
#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)
#define Please return
#define AC 0
#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */
#define inf numeric_limits<double>::infinity();
#define linf numeric_limits<long double>::infinity()


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1e9+7;
constexpr long double eps = 1e-6;
const long double PI = acosl(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1 && c != ' ') {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

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

ll LSB(ll n) { return (n & (-n)); }

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



int main() {

	int n;
	scanf("%d", &n);
	cpp_int ans = 1, a;
	bool flag = false;
	rep(i, n) {
		cin >> a;
		if (a == 0)ans = 0, flag = false;
		else {
			if (ans * a > 1000000000000000000 or ans == -1 or flag)ans = -1, flag = true;
			else ans *= a;
		}
	}
	if (flag) puts("-1");
	else cout << ans << endl;

	Please AC;
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long int A,B,C,K;
  cin>>A>>B>>C>>K;
  long int ans=0;
  if(K<=A){
    ans+=K;
    cout<<ans<<endl;
    return 0;
  }
  if(K<=A+B){
    ans+=A;
    cout<<ans<<endl;
    return 0;
  }
  else if(K<=A+B+C){
    ans=A-(K-A-B);
    cout<<ans<<endl;
    return 0;
  }
}

Measured memory_bytes: 3624
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


char solve( string s ) {
    if ( s[0] == 'x' && s[s.size()-1] == 'x' ) return 'x';
    return 'o';
}

int main() {
    string s;
    while ( cin >> s ) {
        cout << solve(s) << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; long long int a,b; cin >> n >> a >> b;
  if(n > a*b || n < a + b -1){cout << "-1" << endl; return 0;}
  long long int d = a*b - n;
  vector<int> v;
  for(int i=0;i < b ;i++){
  	if(i==0){
      for(int i=a-1;i>=0;i--) printf("%d ", n-i);
      n -= a;
    }else{
      if(d >= a-1){
       for(int i=0;i>=0;i--) printf("%d ", n-i);
       n -= 1;
       d -= a-1;
      }else if(d == 0){
        for(int i=a-1;i>=0;i--) printf("%d ", n-i);
      	n -= a;
      }else{
      	int r = d % (a-1);
        for(int i=a-1-r;i>=0;i--) printf("%d ", n-i);
      	d -= r;
        n -= a-r;
      }
    }
  }
  printf("\n");
}


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

int n;
int a[1000100];
int ans[100100];

signed main(){
	cin >> n;
	rep(i, n) cin >> a[i];
	ans[0] = 0;
	for(int i = 1; i < n; i++){
		ans[i] = a[i-1] - ans[i-1];
	}
	ans[0] += (a[n-1] - ans[n-1] + ans[0]) / 2;
	cout << (ans[0] * 2) << " ";
	for(int i = 1; i < n; i++){
		ans[i] = a[i-1] - ans[i-1];
		cout << ans[i]*2 << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 2944
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int M; cin >> M&&M;) {
		int N; cin >> N;
		vector<vector<int>> v(N, vector<int>(M));
		rep(i, 0, N) rep(j, 0, M) { cin >> v[i][j]; }
		vector<vector<bool>> f(N, vector<bool>(M));
		static const int di[] = { 1,0,-1,0 };
		static const int dj[] = { 0,1,0,-1 };
		auto inrange = [&](int i, int j) { return i >= 0 && i < N && j >= 0 && j < M; };
		function<int(int, int)> dfs = [&](int i, int j) {
			int ret = 0;
			f[i][j] = true;
			rep(k, 0, 4) {
				int ni = di[k] + i, nj = dj[k] + j;
				if (!inrange(ni, nj))continue;
				if (f[ni][nj])continue;
				if (v[ni][nj] == 0)continue;
				chmax(ret, dfs(ni, nj));
			}
			f[i][j] = false;
			return ret + 1;
		};
		int ans = 0;
		rep(i, 0, N)rep(j, 0, M) {
			if (v[i][j] == 0)continue;
			chmax(ans, dfs(i, j));
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3056
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Can't Wait for Holiday
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int N = 7;
const char wds[N][8] = {
  "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"
};

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  char s[8];
  scanf("%s", s);

  for (int i = 0; i < N; i++)
    if (strcmp(s, wds[i]) == 0) {
      printf("%d\n", 7 - i);
      return 0;
    }
  
  return 0;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())

res = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500 * a + 100 * b + 50 * c == X:
                res += 1

print(res)

Measured memory_bytes: 3060
n,k = map(int,input().split())
sunuke = [0] * (n+1)
sunuke[0] = 1
for i in range(k):
    d = int(input())
    a = list(map(int,input().split()))
    for x in a:
        sunuke[x] += 1
ans = 0
for s in sunuke:
    if s == 0:
        ans += 1
print(ans)

Measured memory_bytes: 67684