akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 110000;
i64 a[maxn];
vi e[maxn];

bool ok = true;

i64 dfs(int v, int p) {
    if (e[v].size() == 1) return a[v];
    vi lst;
    for (int u: e[v]) {
        if (u == p) continue;
        lst.pb(dfs(u, v));
        if (!ok) return -1;
    }
    sort(all(lst));
    i64 S = accumulate(all(lst), 0LL);
    i64 t = min(S / 2, S - lst.back());
    i64 x = S - a[v];
    if (x < 0 || x > t) {
        ok = false;
        return -1;
    }
    return S - 2 * x;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n;
    cin >> n;
    forn(i, n) cin >> a[i];
    forn(i, n - 1) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        e[x].pb(y);
        e[y].pb(x); 
    }
    if (n == 2) {
        cout << (a[0] == a[1] ? "YES" : "NO") << '\n';
        return 0;
    }
    int v = 0;
    while (e[v].size() == 1) ++v;
    cout << (dfs(v, -1) == 0 ? "YES" : "NO") << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 14720
def insertionSort(A,N):
    print(*A)
    for i in range(1,N):
        v = A[i]
        j = i-1
        while j >= 0 and A[j] > v:
            A[j+1],A[j] = A[j],A[j+1]
            # print(f'i={i} j={j}')
            j -= 1
        print(*A)


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


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
   ll h,w,d;cin >>h>>w>>d;
   ll a[h][w];
   vector<P>p(h*w);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >>a[i][j];
            a[i][j]--;
            p[a[i][j]]={i,j};
        }
    }
    vector<vector<ll>>s(d,vector<ll>());
    for (int i = 0; i < d; ++i) {
        ll j=i;
        while(j<h*w){
            if(j-i==0)s[i].push_back(0);
            else {
                ll cost=abs(p[j].first-p[j-d].first);
                 cost+=abs(p[j].second-p[j-d].second);
                s[i].push_back(cost+s[i][j/d-1]);
            }
            j+=d;
        }
    }
//   vector<vector<ll>>ds(d,vector<ll>(h*w/d,0));
//   vector<vector<ll>>ds(d,vector<ll>(h*w/d,0));
    ll q;cin >>q;
    for (int i = 0; i < q; ++i) {
        ll l,r;cin >>l>>r;
        l--;r--;
        cout <<s[r%d][r/d]-s[l%d][l/d]<<endl;
//        cout <<s[r%d][r/d]<<" "<<s[l%d][l/d]<<endl;
    }
   return 0;
}

Measured memory_bytes: 7424
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t a,b;
    cin >> a >> b;
    cout << (a%3==0||b%3==0||(a+b)%3==0?"Possible":"Impossible") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, to) for (int i = 0; i < (to); ++i)
#define repf(i, from, to) for (int i = (from); i < (to); ++i)
#define unless(cond) if (!(cond))
using namespace std;
using ll = long long;
template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

int main() {
  int n;
  V<int> a;
  map<int, int> count;
  cin >> n;
  a.resize(n);
  rep(i, n) {
    cin >> a[i];

    count[a[i]] = 0;
  }

  // Count
  rep(i, n) {
    count[a[i]]++;
  }
  // Aggregate
  int ans = 0;
  for(auto it = count.begin(); it != count.end(); it++) {
    if(it->second % 2 == 1) {
      ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 8096
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		new Main().start();
	}
	void start(){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = in.nextInt();
		}
		printArray(shellSort(a,n));

		in.close();
	}
	int cnt = 0;
	int[] insertionSort(int[]a, int n, int g){
		for(int i = g; i < n; i++){
			int v = a[i];
			int j = i - g;
			while(j >= 0 && a[j] > v){
				a[j+g] = a[j];
				j -= g;
				cnt++;
			}
			a[j+g] = v;
		}
		return a;
	}
	int[] shellSort(int[] a, int n){
		cnt = 0;
		int m = (int)(Math.log(n) / Math.log(4))+1;
		if(m < 1) m = 1;
		int[] g = new int[m];
		for(int i = 0; i < m; i++){
			g[m-i-1] = (int)Math.pow(4, i);
		}
		for(int i = 0; i < m; i++){
			a = insertionSort(a,n,g[i]);
		}
		System.out.println(m);
		printArray2(g);
		System.out.println(cnt);
		return a;
	}
	void printArray(int[] a){
		for(int x : a){
			System.out.println(x);
		}
	}
	void printArray2(int[] a){
		System.out.print(a[0]);
		for(int i= 1; i < a.length; i++){
			System.out.print(" " + a[i]);
		}
		System.out.println();
	}


}

Measured memory_bytes: 299096
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;

int int_vector_find(std::vector<int> vec, int num) {
	auto itr = std::find(vec.begin(), vec.end(), num);
	int index = std::distance(vec.begin(), itr);

	if (index != vec.size()) {
		return 1;
	}
	else {
		return 0;
	}
}

int main() {
	int n;
	float ans = 0;

	std::cin >> n;
	std::vector<float> vec;
	std::vector<std::string> str;

	for (int i = 0; i < n; ++i) {
		float a;
		std::cin >> a;
		vec.push_back(a);
		std::string s;
		std::cin >> s;
		str.push_back(s);
	}

	for (int i = 0; i < n; ++i) {
		if (str[i] == "BTC") {
			ans += 380000 * vec[i];
		}
		else {
			ans += vec[i];
		}
	}

	std::cout << ans << std::endl;

}

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

int main() {
	int k;
	cin >> k;
	int c=1,a=7%k;
	while(a!=0)
	{
		c++;
		int b=(a*10)+7;
		a=b%k;
		if(c==pow(10,7))
		{
			c=-1;
			break;
		}
	}
	cout << c << endl;
	return 0;
}


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

int main() {
	int n,temp,ans=0;;cin>>n;
  	map<int,int> mp;
  	for(int i=0;i<n;i++){
    	cin>>temp;
      	mp[temp]++;
    }
  	for(auto x:mp){
    	if(x.second%2!=0) ans++;
    }
  	cout<<ans<<endl;
}


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

int main() {
  int S, W;
  cin >> S >> W;
  if (S <= W) {
    cout << "unsafe" << endl;
  }
  else {
    cout << "safe" << endl;
  }
}


Measured memory_bytes: 3600
#include <iostream>

int main() {
    int x1, y1, x2, y2;
    std::cin >> x1 >> y1 >> x2 >> y2;

    auto ay = y1 - y2;
    auto ax = x2 - x1;
    auto x3 = x2 + ay;
    auto y3 = y2 + ax;
    auto x4 = x1 + ay;
    auto y4 = y1 + ax;

    std::cout << " " << x3 << " " << y3 << " " << x4 << " " << y4 << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,t=1,m=0;
	cin>>n;
	int a[n+1];
	for(i=1;i<=n;i++)
	cin>>a[i];
	m=a[1];
	for(i=2;i<=n;i++)
	if(a[i]>=m)
	{
		t++;
		m=a[i];
	}
	cout<<t;
	return 0;
 } 

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] cards = new int[4][13];
        for (int i = 0; i < n; i++) {
             String ma = sc.next();
             int num = sc.nextInt();
             if (ma.equals("S"))
                cards[0][num - 1] = 1;
             else if (ma.equals("H"))
                cards[1][num - 1] = 1;
             else if (ma.equals("C"))
                cards[2][num - 1] = 1;
             else
                cards[3][num - 1] = 1;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                if (cards[i][j] == 0)
                    if (i == 0)
                        System.out.println("S " + (j + 1));
                    else if (i == 1)
                        System.out.println("H " + (j + 1));
                    else if (i == 2)
                        System.out.println("C " + (j + 1));
                    else
                        System.out.println("D " + (j + 1));
            }
        }
    }
}




        


Measured memory_bytes: 26308
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	
	int n=in();
	vector<int> a(n);trav(i,a)i=in();
	int sum=accumulate(all(a),0LL);
	int ans=1e18;
	int cur=0;
	for(int i=0;i<n-1;i++)
	{
		cur+=a[i];
		ans=min(ans,abs(cur-(sum-cur)));
		
	}
	cout<<ans;
}

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

int main(){
  string s;
  cin >> s;
  int count=0;
  int ans=0;
  for(int i=0; i<s.size(); ++i){
    if(s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C'){
      count ++;
      ans=max(ans,count);}
    else
      count=0;
    
  }
  cout << ans << endl;
}   

Measured memory_bytes: 256
N, M = [int(i) for i in input().split(" ")]
A = [int(i) for i in input().split(" ")]

A_sum = sum(A)
flag = 0
A_sorted = sorted(A, reverse=True)
for i in range(M):
    if A_sorted[i]<(A_sum * (1/(4*M))):
        flag = 1
        break
if flag == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<math.h>
using namespace std;
int N,P[101],A,B;
int cnt[3];
int main(void){
    cin >> N >> A >> B;
    for (int i=0;i<N;i++){
        cin >> P[i];
        if (P[i]<=A) cnt[0]++;
        if (P[i]>A && P[i]<=B) cnt[1]++;
        if (P[i]>B) cnt[2]++;
    }

    cout << min( min(cnt[0],cnt[1]), cnt[2]) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int N , K;
    cin >> N >> K;
    int t[N];
    for(int i = 0; i < N; i++){
        t[i] = 0;
    }
    vector <int> d(K);
    for(int i = 0; i < K; i++){
        cin >> d.at(i);
        vector <int> A(d.at(i));
        for(int j = 0; j < d.at(i); j++){
            cin >> A.at(j);
            t[A.at(j) - 1]++;
        }
    }
    int count = 0;
    for(int i = 0; i < N; i++){
        if(t[i] == 0){
            count++;
        }
    }
    cout << count << endl;
}

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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto k = load<int>();
	auto x = load<int>();
	for (auto i=x-(k-1); i<=x+(k-1); ++i)
		cout << i << ' ';
	cout << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<int,string> p1,pair<int,string> p2)
{
	if(p1.first!=p2.first)
	return p1.first>p2.first;
	else
	{
		return p1.second<p2.second;
	}
}
int main()
{
	int i,j,k,l,n,m;
	cin>>m;
	vector<string> v;
	map<string,int> mp;
	for(i=0;i<m;i++)
	{
		string s;
		cin>>s;
		v.push_back(s);
		mp[s]++;
	}
	vector<pair<int,string> > v2;
	for(auto i : mp)
	{
		v2.push_back({i.second,i.first});
	}
	sort(v2.begin(),v2.end(),comp);
	int x=v2[0].first;
    i=0;
	while(v2[i].first==x&&i<v2.size())
	{
		cout<<v2[i].second<<"\n";
		i++;
	 } 
	return 0;
}

Measured memory_bytes: 31088
#include <stdio.h>

int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  if (a<b && a<c) {
    if (b<c)
      printf("%d %d %d\n", a, b, c);
   else
       printf("%d %d %d\n", a, c, b);
} else if (b<a && b<c) {
    if (a<c)
      printf("%d %d %d\n",  b, a, c);
   else
       printf("%d %d %d\n", b, c, a);
} else  {
    if (a<b)
      printf("%d %d %d\n",  c, a, b);
   else
       printf("%d %d %d\n", c, b, a);
  } 
  return 0;
}


Measured memory_bytes: 2128
from collections import deque


def dump_neighbor(val):
    if(val == 0):
        return [val, val+1]
    elif(val == 9):
        return [val-1, val]
    else:
        return [val-1, val, val+1]

def dfs(d, K):
    for i in range(K):
        val = d.popleft()
        neighbors = dump_neighbor(val%10)
        for neighbor in neighbors:
            d.append(val*10 + neighbor)
    print(val)
    

if __name__ == "__main__":
    K = int(input().rstrip())
    d = deque([val for val in range(1,10)])
    dfs(d, K)

Measured memory_bytes: 12396
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int main(){

int A,B;

cin >> A >> B;

int S;
S = A+B;

if(S == 3){
  cout << 3;
  return 0;
}
if(S == 4){
  cout << 2;
  return 0;
}

cout << 1;

return 0;
}


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

int main(){
    int num[3];
    rep(i,3) cin >> num[i];
    
    bool poor = false;

    if(num[0] == num[1] && num[0] != num[2]) poor = true;
    if(num[1] == num[2] && num[1] != num[0]) poor = true;
    if(num[2] == num[0] && num[2] != num[1]) poor = true;

    if(poor) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
s=gets.chop
x,y=gets.split.map(&:to_i)

fs=s.split('T').map(&:length)
xn=fs.shift.to_i
yn=0
xs=fs.select.with_index{ |e,i| i%2==1}.sort.reverse
ys=fs.select.with_index{ |e,i| i%2==0}.sort.reverse

xs.each{ |e|x>xn ? xn+=e:xn-=e}
ys.each{ |e|y>yn ? yn+=e:yn-=e}

puts xn == x && yn == y ? :Yes: :No


Measured memory_bytes: 3836
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<int,int> mp;
int a[200010];
int main(){
	int i,k,n,ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]++;
	sort(a+1,a+n+1);
	for(i=n;i>=1;i--)
		if(mp[a[i]]){
			mp[a[i]]--;
			for(k=30;k>=0;k--)
				if(mp[(1<<k)-a[i]]) ans++,mp[(1<<k)-a[i]]--;
		}
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 300160
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define db double 
#define pll pair<ll,ll>
#define pdb pair<db,db>
#define clr(x) memset(x,0,sizeof(x))
const ll siz=1e6+7;
const ll mod=1e9+7;
ll arr[siz];
ll n,k;
ll solve(ll x)
{
    ll ans=(ll)(ceil((x-1.0)/(k-1.0)));
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    ll ps=-1;
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
        if(arr[i]==1)ps=i;
    }
    if(k==n){cout<<1<<endl;return 0;}
    ll left=max((ll)0,ps-k+1);
    ll lim=min(n,ps+k);
    ll mi=1e18;
    ll ans=0;
    ll cnt=0;
    for(ll i=left;i+k-1<lim;i++)
    {
        //cout<<i<<" "<<endl;
        //cout<<i<<" "<<solve(i+1)<<" "<<solve(n-(i+k-1))<<endl;
        ans=1+solve(i+1)+solve(n-(i+k-1));
        //if(arr[i]==1 or arr[n-(i+k-1)]==1)ans--;
        mi=min(mi,ans);
    }
    cout<<mi<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

long long calc_digit(long long N){
    long long ans = 0;
    while(N>0){
        N /= 10;
        ans++;
    }
    return ans;
}

int main(){
    long long N;
    cin >> N;
    long long ans = INF;
    for(long long A = 1; A*A <= N; A++ ){
        if(N%A!=0)continue;
        long long B = N / A;
        long long res = max(calc_digit(A),calc_digit(B));
        ans = min(ans,res);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3568
# 入力
s = input()

# 処理
left_A  = -1  # 最も左のAの位置
right_Z = -1  # 最も右のZの位置

for i in range(len(s)):
  # left_A < 0 => まだAを見つけていない
  if left_A < 0 and s[i] == "A":
    left_A = i
  if s[i] == "Z":
    right_Z = i

# 答え
print(right_Z - left_A + 1)

Measured memory_bytes: 3516
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<stdio.h>
#include<functional>
#include<queue>

using ll = long long;

using namespace std;

ll mod = 1e9 + 7;
//ll mod = 998244353;

ll n_pow(ll a, ll n) {
	if (n == 0)return 1;
	ll t = n_pow(a, n / 2);
	t *= t;
	//t %= mod;
	if (n % 2 == 1)t *= a;
	return t /*% mod*/;
}

//const int INF = 1001001001;
const ll INF = 1e18;

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

ll cal_gcd(ll a, ll b) {
	ll m = max(a, b);
	ll n = min(a, b);
	while (m%n != 0) {
		ll b = m % n;
		m = n;
		n = b;
	}
	return n;
}

vector<pair<ll, ll>> prime_factorize(ll N) {
	vector<pair<ll, ll>> res;
	for (long long a = 2; a * a <= N; ++a) {
		if (N % a != 0) continue;
		long long ex = 0;
		while (N % a == 0) {
			++ex;
			N /= a;
		}
		res.push_back({ a, ex });
	}
	if (N != 1) res.push_back({ N, 1 });
	return res;
}


int main() {
	int n, x, t;
	cin >> n >> x >> t;
	int c;
	if (n%x == 0) {
		c = n / x;
	}
	else {
		c = n / x + 1;
	}
	cout << t * c << endl;
	return 0;
}

Measured memory_bytes: 3596
#include<iostream>
using namespace std;
int main (void){

    int a, b, c, i;
    int aa, bb;
    int flag = 0;

    cin >> a >> b;


    if(a < b)
    c = b;
    else
    c = a;

    for(i = 0;i < c;i++){
        aa = 0,bb = 0;

        aa = a - i;
        bb = b - i;
        
        if(aa < 0)
            aa *= -1;
        if(bb < 0)
            bb *= -1;

        if(aa == bb){
            flag = 1;
            break;
        }
    }

    if(flag == 1)
    cout << i << endl;
    else
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
//void IO(){
//	#ifndef ONLINE_JUDGE
//	    freopen("input.txt", "r", stdin);
//	    freopen("output.txt", "w", stdout);
//	#endif
//}
// end of Template

int ans,n;
int main(){
	//IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        while(temp%2==0){
            ans++;
            temp/=2;
        }
    }
    cout<<ans<<newl;
}


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

#define MAX 1000000
#define INF (1<<24)
int n[100000],M;

int dp[1000005];
int od[1000005];

int main()
{
	for(M=1; ; M++)
	{
		int v=M*(M+1)*(M+2)/6;
		if(v>MAX) break;
		n[M]=v;
	}



	for(int i=0; i<=MAX; i++)
	{
		dp[i]=INF;
		od[i]=INF;
	}

	dp[0]=od[0]=0;

	for(int i=1; i<M; i++)
	for(int j=0; j<=MAX; j++) 
	{
		if(j+n[i] > MAX) break;
		if(dp[j]!=INF)
		{
			dp[j+n[i]]=min(dp[j+n[i]], dp[j]+1);
		}
		if(od[j]!=INF&&n[i]%2==1)
		{
			od[j+n[i]]=min(od[j+n[i]], od[j]+1);
		}
	}
	int N;
	while(cin >> N, N)
	{

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


}

Measured memory_bytes: 8564
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
const int p = 1000005;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n, x, t;
	cin >> n >> x >> t;
	cout << (n + x - 1) / x * t << endl;
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  
  int cnt = 0;
  while(N > 1){
    N /= 2;
    cnt += 1;
  }
  int ans = pow(2, cnt);
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define deb(x) cout << #x << " = "<< x << "\n"; 
int a[3005];
int dp[3005][3005];
int n, s;
int solve(int idx, int sum)
{
	if(sum == 0) return n - idx + 1;
	if(sum < 0) return 0;
	if(idx >= n) return 0;

	int &res = dp[idx][sum];
	if(res != -1) return res;
	res = solve(idx+1, sum) + solve(idx+1, sum - a[idx]);
	res %= 998244353;
	return res;
}
signed main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	cin >> n >> s;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	int ans = 0;
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < n; i++)
		ans += solve(i, s) ;
	cout << ans % 998244353 << "\n";
	
} 


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

int a;
int b;


int main() {
    cin >> a >> b;
  if(a*b > a+b){
    cout << a*b << endl;
  }
  else if (a-b > a+b){
    cout << a-b << endl;
  } 
  else{
    cout << a+b << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
int cumsum[100002];
int h_d[10];
int h_w[10];
int main(){
  while(true){
    int w;
    int d;
    cin >> w >> d;
    if(w == 0 && d == 0){
      break;
    }

    for(int i = 0; i < w; i++){
      cin >> h_d[i];
    }
    for(int i = 0; i < d; i++){
      cin >> h_w[i];
    }

    sort(h_d, h_d + w);
    reverse(h_d, h_d + w);

    int ans = 0;
    map <int, int> map_hw;
    for(int i = 0; i < d; i++){
      ans += h_w[i];
      if(map_hw.find(h_w[i]) == map_hw.end()){
        map_hw[h_w[i]] = 1;
      } else {
        map_hw[h_w[i]] ++;
      }
    }

    for(int i = 0; i < w; i++){
        if(map_hw.find(h_d[i]) != map_hw.end()){
          map_hw[h_d[i]] --;
          if(map_hw[h_d[i]] == 0){
            map_hw.erase(h_d[i]);
          }
        } else {
          ans += h_d[i];
        }
    }
    cout << ans << endl;

  }
  return 0;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; i--)
#define loop(i, r, n) for (int i = (r); i < (n); i++)
#define FOR(n) for (int _i = 0; _i < (n); _i++)

#define pb push_back
#define all(in) in.begin(),in.end()

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


int main(){
    int n; cin >> n;
    ll ans = -1;
    ll count = 0;
    rep(i,n){
        ll a, b; cin >> a >> b;
        ans += b;
        count += a*b;
    }
    ans += (count-1)/9;
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <functional>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <climits>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <deque>
#include <list>
#include <map>
#include <set>
using namespace std;

/*** typedef ***/
typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ULL;
typedef pair < int , int > ii;
typedef pair < LL  , LL  > ll;
typedef vector <int>  vint;
typedef vector <bool> vbool;
typedef vector <long> vlong;

/*** define ***/
#define sz(x)			((int)x.size())
#define tin(x)			scanf("%d",&x)
#define all(x)			x.begin(),x.end()
#define Set(b,a)		memset(b,a,sizeof b)
#define print1(x)		printf("Case %d:",x++)
#define tin2(x,y)		scanf("%d%d",&x,&y)
#define tin3(x,y,z)		scanf("%d%d%d",&x,&y,&z)
#define loop(i,i0,in)	for(int i=i0 ; i<in ; i++)
#define rep(i,n)		for(int i=0 ; i<(n) ; i++)
#define _rep(i,n)		for(int i=n-1 ; i>=0 ; i--)
#define _loop(i,in,i0)	for(int i=in-1 ; i>=i0 ; i--)
#define Fore(it, x)		for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)

const int       maxn = 100+10;
const long double PI = 3.1415926535897932384626433832795;

int seq[maxn];
     
int main()  
{  
#ifdef Online_Judge
	freopen("a.in","r",stdin);
#endif
	int n;
	cin >> n;
	rep(i,n)
		cin >> seq[i];
	reverse(seq,seq+n);
	cout << seq[0];
	loop(i,1,n)
		cout << " " << seq[i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 1164
/**
*
* Author: Mouhanad
* Lang: GNU C++14
*
**/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ii pair < int , int >
#define LS pair < ll , string >
typedef long long ll;
const int inf = 1<<30;
const int N =100100;
int n , a[N] , q ;

int main ( ){
 cin >> n >> q ;
 for ( int i = 0 ; i < n; i++ ) cin >> a[i] ;
 sort(a,a+n);
  q-- ;
  int j = n-2 ;
  while ( q-- ){
    a[n-1] += a[j--];
  }
 cout << a[n-1];
return 0 ;
}


Measured memory_bytes: 256
D,G = map(int,input().split())
PC = [tuple(map(int,input().split())) for i in range(D)]

ans = 9999
for b in range(1<<D):
    sc = pr = 0
    for i,(p,c) in enumerate(PC):
        if b&(1<<i):
            sc += c + (i+1)*100*p
            pr += p
    if sc >= G:
        ans = min(ans, pr)
        continue
    remsc = G - sc
    for i,(p,_) in reversed(list(enumerate(PC))):
        if b&(1<<i): continue
        for j in range(p):
            remsc -= (i+1)*100
            pr += 1
            if remsc <= 0:
                ans = min(ans, pr)
                break
        else:
            continue
        break
    if remsc <= 0:
        ans = min(ans, pr)
print(ans)

Measured memory_bytes: 9244
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

a = [abs(x[i] - y[i]) for i in range(n)]

for p in range(1, 4):
  ans = 0
  for d in a:
    ans += d ** p
  print('{:.10f}'.format(ans ** (1/p)))
print('{:.10f}'.format(max(a)))



Measured memory_bytes: 5656
N, M = map(int, input().split())
a = []
b = []
count_raw = []
count = 0

for i in range(0, M):
    A, B = list(map(int, input().split()))
    a.append(A)
    b.append(B)

a.extend(b)

for i in range(1, N+1):
    count = 0
    for j in range(0, 2*M):
        if a[j] == i:
            count += 1
    count_raw.append(count)

for i in range(0, N):
    print(count_raw[i])

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>

using namespace std;

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

	int X[N], Y[N];
	for (int i = 0; i < N; ++i) {
		cin >> X[i];
		Y[i] = X[i];
	}

	sort(Y, Y + N, greater<int>());
	int f = N / 2;
	int middlegreat = Y[f-1];
	
	int middlelittle = Y[f];

	for (int i = 0; i < N; ++i) {
		if (middlelittle >= X[i])
			cout << middlegreat << '\n';
		else
			cout << middlelittle << '\n';
		
	}

	return 0;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,b) ROF(i,0,b)

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define MOD(x,m) ((x)%(m)+(m))%(m)

const int maxn = 5e3+10;
int n, m;
int b[maxn], f[maxn][maxn];

int main() {
	cin >> n >> m;
	int mid = n/2;
	F0R(i, mid+1) F0R(j, i+1) b[j]--;
	F0R(i, mid) F0R(j, n-i) b[j]++;
	F0R(i, n) {
		b[i]++;
//		printf("%d ", b[i]); fflush(stdout);
	}
	f[0][0] = 1;
	F0R(i, n-1)
		F0R(j, n)
			for (int k = 0; k*b[i+1]+j <= n; ++k)
				(f[i+1][k*b[i+1]+j] += f[i][j]) %= m;
	long long ans = 0;
	F0R(i, n) {
		(ans += 1ll*f[n-1][i]*(n-i)) %= m;
//		printf("%d\n", f[n-1][i]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 98048
#include <bits/stdc++.h>
using namespace std;
  
int main () {
	int N, A;
  	cin >> N >> A;
  
  	int M = N % 500;
  
  	if (M == 0) {
    	cout << "Yes" << endl;
    }
  	else if (A >= M) {
    	cout << "Yes" << endl;
    }
  	else {
    	cout << "No" << endl;
    }
}

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


using namespace std;

int main(){

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    
    if(S[K-1] == 'A'){
        S[K-1] = 'a';
        
    }else if(S[K-1] == 'B'){
        S[K-1] = 'b';
        
    }else{
        S[K-1] = 'c';
        
    }
    
    
    
    cout << S << endl;
    
    
    
    
    
    return 0;
    
}

Measured memory_bytes: 256
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var n = o.a();
  return n*180-360;
}

Measured memory_bytes: 21956
#include <iostream>
#include <iomanip>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;

int alphabet_number(char x){
  switch(x){
    case 'A':
      return 10;
    case 'B':
      return 11;
    case 'C':
      return 12;
    case 'D':
      return 13;
    case 'E':
      return 14;
    case 'F':
      return 15;
  }
}

int main(int argc, char* argv[]){
  int xnum, ynum;
  char x,y;
  cin >> x;
  cin >> y;
  xnum = alphabet_number(x);
  ynum = alphabet_number(y);

  if(xnum < ynum){
    cout << '<' << endl;
  }else if(xnum == ynum){
    cout << '=' << endl;
  }else{
    cout << '>' << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)
#define ALL(v) (v).begin(), (v).end()
#define CLR(t, v) memset(t, (v), sizeof(t))
template <class T1, class T2>ostream &operator<<(ostream &os, const pair<T1, T2> &a){  return os << "(" << a.first << "," << a.second << ")";}
template <class T>void pv(T a, T b){  for (T i = a; i != b; ++i)    cout << (*i) << " ";  cout << endl;}
template <class T>void chmin(T &a, const T &b){  if (a > b)    a = b;}
template <class T>void chmax(T &a, const T &b){  if (a < b)    a = b;}

int nextInt(){  int x;  scanf("%d", &x);  return x;}

const int INF = 1000000;
const int K = 100;

int D[105][105];
int C[105][105];

struct E {
  int from, to, cost;
};

int main2() {
  int A = nextInt();
  int B = nextInt();
  REP(x, A) REP(y, B) D[x+1][y+1] = nextInt();

  REP(i, K+1) REP(j, K+1) {
    int c = 0;
    for (int x = 1; x <= A; x++) for (int y = 1; y <= B; y++) {
      chmax(c, D[x][y] - i*x - j*y);
    }
    C[i][j] = c;
  }

  bool possible = true;
  for (int x = 1; x <= A; x++) for (int y = 1; y <= B; y++) {
    int d = INF;
    REP(i, K+1) REP(j, K+1) {
      chmin(d, i*x + j*y + C[i][j]);
    }
    if (D[x][y] != d) possible = false;
  }

  if (possible) {
    vector<E> es;
    REP(i, K) es.push_back({i, i+1, -1});
    REP(j, K) es.push_back({299-j-1, 299-j, -2});
    REP(i, K) REP(j, K) {
      es.push_back({i, 299-j, C[i][j]});
    }
    cout << "Possible" << endl;
    cout << 300 << " " << es.size() << endl;
    for (auto e : es) {
      cout << (e.from+1) << " " << (e.to + 1) << " ";
      if      (e.cost == -1) cout << "X";
      else if (e.cost == -2) cout << "Y";
      else                   cout << e.cost;
      cout << endl;
    }
    cout << 1 << " " << 300 << endl;

  } else {
    cout << "Impossible" << endl;
  }
  return 0;
}

int main() {
  for (; !cin.eof(); cin >> ws) main2();
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
vi g[125252];
int dist[125252];
int dx[125252];
int dy[125252];
const int INF = 830252521;

void dfs(int st,int dist[125252]){
  REP(i,n)dist[i] = INF;
  dist[st] = 0;
  stack<int> S;
  S.push(st);
  while(!S.empty()){
    int p = S.top(); S.pop();
    int d = dist[p];
    REP(i,g[p].size()){
      int to = g[p][i];
      if(dist[to]!=INF)continue;
      dist[to] = d+1;
      S.push(to);
    }
  }
}

int main(){
  scanf("%d",&n);
  REP(i,n-1){
    int a,b;
    scanf("%d%d",&a,&b);
    --a;--b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0,dist);
  int x = max_element(dist,dist+n)-dist;
  dfs(x,dx);
  int y = max_element(dx,dx+n)-dx;
  dfs(y,dy);
  REP(i,n){
    int ans = 2*(n-1) - max(dx[i],dy[i]);
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 9052
#include <iostream>
using namespace std;
int main(void){
    int s[10000],t[500];
    int n,q,x=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>t[i];
        for(int j=0;j<n;j++){
            if(t[i]==s[j]){
                x++;
                break;
            }
        }
    }
    cout<<x<<endl;
    return 0;
}

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

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

using namespace std;

typedef long long LL;

typedef vector<float> Point;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "[ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "]";

    return os;
}

void print(const Point &x) {
    cout << x[0] << " " << x[1] << endl;
}

float func1(float p0, float p1) {
    return (2 * p0 + p1) / 3;
}

Point calc_u(const Point &a, const Point &b) {
    float x = (a[0] + b[0] - (b[1] - a[1]) / sqrt(3)) / 2;
    float y = (a[1] + b[1] + (b[0] - a[0]) / sqrt(3)) / 2;

    return {x, y};
}

void rec_koch(const Point &a, const Point &b, int n) {
    if (n == 0) return;

    // get s
    Point s = {func1(a[0], b[0]), func1(a[1], b[1])};
    rec_koch(a, s, n-1);
    print(s);

    // get u
    Point u = calc_u(a, b);
    rec_koch(s, u, n-1);
    print(u);

    // get t
    Point t = {func1(b[0], a[0]), func1(b[1], a[1])};
    rec_koch(u, t, n-1);
    print(t);

    rec_koch(t, b, n-1);

}

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

    int n;
    cin >> n;

    Point p1 = {0, 0}, p2 = {100, 0};

    print(p1);

    rec_koch(p1, p2, n);

    print(p2);
}



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

int h, w, th;
string s[10];

int sub(int t) {
  vector<pair<int, int>> v;
  int prev = 0;
  int ans = __builtin_popcount(t);
  for (int k = 0; k < h; ++k) {
    if (((t >> k) & 1) || k == h - 1) {
      v.push_back(make_pair(prev, k + 1));
      prev = k + 1;
    }
  }
  
  int m = v.size();
  vector<int> curr(m);
  for (int j = 0; j < w; ++j) {
    vector<int> add(m);
    for (int k = 0; k < m; ++k) {
      for (int i = v[k].first; i < v[k].second; ++i) {
        add[k] += s[i][j] == '1';
      }
    }
    
    bool cut = false;
    for (int k = 0; k < m; ++k) {
      if (add[k] > th) return 1e9;
      if (curr[k] + add[k] > th) {
        cut = true;
      }
    }
    
    if (cut) {
      ++ans;
      for (int k = 0; k < m; ++k) {
        curr[k] = add[k];
      }
    } else {
      for (int k = 0; k < m; ++k) {
        curr[k] += add[k];
      }
    }
  }
  return ans;
}

int main() {
  cin >> h >> w >> th;
  for (int i = 0; i < h; ++i) {
    cin >> s[i];
    s[i] += '0';
  }
  ++w;
  
  int mn = 1e9;
  for (int t = 0; t < (1 << (h - 1)); ++t) {
    mn = min(mn, sub(t));
  }
  cout << mn << endl;
}

Measured memory_bytes: 256
isok h [] = True
isok h (a:as) 
  | h >= a = isok h as
  | otherwise = False

ret [] = 0
ret (h:hs) 
  | isok h hs = 1 + ret hs
  | otherwise = ret hs


main = do
  n <- getLine
  hs <- ((map read . words) <$> getLine) :: IO [Int]
  putStrLn $ show $ ret (reverse hs)


Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pa;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mp make_pair
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
int getgcd(int x,int y){return !x?y:getgcd(y%x,x);}
const int maxn=1e3+5,inf=1e9+5;
int n,tot;
int a[maxn];
int head[maxn],des[maxn<<1],nxt[maxn<<1];
int f[maxn][5005],g[maxn][5005];
void adde(int x,int y){
	des[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
int dfs(int x,int fa){
	int leaf=1;
	rep(i,0,5000)f[x][i]=g[x][i]=inf;
	Rep(p,x)if(des[p]!=fa){
		int num=dfs(des[p],x);
		if(num==inf)return inf;
		if(leaf){
			g[x][num]=a[des[p]];
			g[x][a[des[p]]]=num;
		}else{
			per(i,5000,0){
				if(i>=a[des[p]])g[x][i]=min(g[x][i],f[x][i-a[des[p]]]+num);
				if(i>=num)g[x][i]=min(g[x][i],f[x][i-num]+a[des[p]]);
			}
		}
		rep(i,0,5000)f[x][i]=g[x][i],g[x][i]=inf;
		leaf=0;
	}
	if(leaf)return 0;
	int res=inf;
	rep(i,0,a[x])res=min(res,f[x][i]);
	return res;
}
int main(){
	read(n);
	rep(i,2,n){
		int x;read(x);
		adde(x,i);adde(i,x);
	}
	rep(i,1,n)read(a[i]);
	if(dfs(1,0)==inf)puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}

Measured memory_bytes: 39552
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long k;
  cin >> k;
  int n = 50;
  long long d = k / n;
  k -= d * n;
  vector<long long> a(n, n - 1 + d);
  for (int i = 0; i < k; i++) {
    a[i] += n - k + 1;
  }
  for (int i = k; i < n; i++) {
    a[i] -= k;
  }
  cout << n << '\n';
  for (int i = 0; i < n; i++) {
    cout << a[i];
    if (i < n) cout << ' '; else cout << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache

import heapq


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

A,B,N = inputIL()

if N >= B:
  print((A*(B-1))//B)
else:
  print((A*N)//B)
  

Measured memory_bytes: 91952
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;
int main() {
	int L = 0;
	int H = 0;
	int N = 0;
	int A[200] = { 0 };
	int ans = 0;
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
 
	for (int i = 0; i < L; i++) {
		ans += A[N - 1 - i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N, C = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
c = [0]
rc = [0]
uc = [0]
ruc = [0]
sum = 0
out = 0
for x, cal in xy:
    sum += cal
    c.append(max(c[-1], sum-x))
    rc.append(max(rc[-1], sum-2*x))
sum = 0
for x, cal in xy[::-1]:
    sum += cal
    uc.append(max(uc[-1], sum-C+x))
    ruc.append(max(ruc[-1], sum-2*(C-x)))
for w, wr, ww, wwr in zip(c, ruc[::-1], rc, uc[::-1]):
    out = max(out, w + wr, ww + wwr)
print(out)

Measured memory_bytes: 41856
N, K = gets.chomp.split(' ').map(&:to_i)

def solve(n, k)
  result = 0
  if k.even?
    minimum = k / 2
    return result if n < minimum
    a = (n - minimum) / k
    result += (a + 1)**3
  end
  minimum = k
  return result if n < minimum
  a = (n - minimum) / k
  result += (a + 1)**3
  result
end

puts solve(N, K)

Measured memory_bytes: 1916
#include<cstdio>

int solve(int a,int b){
	if(a==0){
		if(0<=b&&b<=9)return 1;
		else return 0;
	}
	int res=0;
	for(int i=0;i<10;i++){
		res+=solve(a-1,b-i);
	}
	return res;
}

int main(){
	int a;
	while(~scanf("%d",&a))	printf("%d\n",solve(3,a));
	return 0;
}

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

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long int ll;
typedef unsigned long long int ull;
#define inf INT_MAX
#define minf INT_MIN
#define watch(x)	cout<<(#x)<<"=>"<<x<<'\n';
#define sz(a) (int)(a).size()

ll ans;
int arr[300009];
vi vr;
void solve()
{
				int n;
				cin>>n;
				int nax = minf;
				for(int i = 0; i < n; ++i){
								cin>>arr[i];
				}
				for(int i = 0; i < n; ++i){
								nax = max(nax,arr[i]);
								ans += nax-arr[i];
				}
				cout<<ans<<'\n';
}

int main()
{
				ios_base::sync_with_stdio(false);
				cin.tie(NULL);
				int testc = 1;
				for(int t = 0; t < testc; ++t)
								solve();
				return 0;
}

		//Sat 22 Aug 2020 05:44:29 PM IST


					/***astrainL3gi0N***/


Measured memory_bytes: 4372
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(true){
			int n = in.nextInt();
			if(n==0)break;
			List<syain> list = new ArrayList<syain>();
			Map<Integer,Integer> map = new HashMap<Integer,Integer>();
			int cnt = 0;
			for(int s=0;s<n;s++){
				int ban = in.nextInt();
				if(!map.containsKey(ban)){
					list.add(new syain(ban));
					map.put(ban,cnt);
					cnt++;
				}
				list.get(map.get(ban)).plus(in.nextLong()*in.nextLong());
			}
			boolean sw = false;
			for(int i=0;i<list.size();i++)if(list.get(i).kin>=1000000){
				System.out.println(list.get(i).ban);
				sw=true;
			}
			if(!sw)System.out.println("NA");
		}
	}
}
class syain implements Comparable<syain>{
	int ban;
	long  kin;
	syain(int ban){
		this.ban=ban;
		kin=0;
	}
	public void plus(long kin){
		this.kin+=kin;
	}
	public int compareTo(syain o) {
		return 0;
	}
}

Measured memory_bytes: 25348
#include <bits/stdc++.h>
#define ll long long
#define pi 3.14159265358979
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

int main(){
    ll n,a,cnt=1;
    cin>>n;
    rep(i,n){
        cin>>a;
        if(a==cnt){
            cnt++;
        }
    }
    if(cnt==1){
        cout<<-1;
    }else{
        cout<<n-cnt+1;
    }
}

Measured memory_bytes: 3680
#include<stdio.h>
//#include<string.h>
//char S[200001],T[200001];
int main()
{
    char S[200001],T[200001];
    scanf("%s %s",&S,&T);
    int i,p=0,length1,length2,j;
    length1=strlen(S);
    length2=strlen(T);
    for(i=0; i<length1; i++)
    {
        if(S[i]!=T[i])
        {
            p++;

        }


    }



    printf("%d\n",p);





    return 0;
}


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

int main(){

  int N;
  cin>>N;
  
  int count=0;
  int k=N/500;
  count+=k*1000;
  
  int k2=(N%500)/5;
  count+=k2*5;
  
  cout<<count<<endl;

}

Measured memory_bytes: 256
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

Measured memory_bytes: 76880