akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

struct Dijkstra{
  ll INF=1000000000000000009;
  ll MAX_V=1000000;
  ll st = -1;
  struct edge{ll to, cost;};
  typedef pair<ll, ll> p;
  vector<vector<edge>> G;
  vector<ll> pre, d;
  priority_queue<p, vector<p>, greater<p> > que; //class, inner, compair
  Dijkstra(ll s){
    G.resize(s+2);
    pre.resize(s+2, -1);
    d.resize(s+2, INF);
  }
  inline void insert(ll a, ll b, ll c){
    G[a].push_back(edge{b, c});
  }
  void init(){
    for(int i=0;i<d.size();i++) pre[i] = -1, d[i] = INF;
  }
  void dijkstra(int start){
    init();
    st = start;
    d[start]=0;
    que.push(p(0, start));
    while(!que.empty()){
      p p_now=que.top(); que.pop();
      ll v = p_now.second;
      if(d[v]<p_now.first) continue;
      for(int i=0;i<G[v].size();i++){
        edge e = G[v][i];
        if(d[e.to]>d[v]+e.cost){
          d[e.to]=d[v]+e.cost;
          pre[e.to] = v;
          que.push(p(d[e.to], e.to));
        }
      }
    }
  }
  vll get_path(int now){
    vll ret;
    while(now!=-1){
      ret.push_back(now);
      now = pre[now];
    }
    return ret;
  }
};
int main(int argc, char const *argv[]) {
  ll h, w;std::cin >> h >> w;
  vector<string> s(h);

  re(i, h) std::cin >> s[i];
  Dijkstra dj(101*101);

  vvl x{vll{1, 0}, vll{0, 1}};
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      re(k, 2){
        ll l = x[k][0], r = x[k][1];
        if(i+l<0||i+l>=h||j+r<0||j+r>=w) continue;
        ll d = ((s[i][j]=='.'&&s[i+l][j+r]=='#')?1:0);
        dj.insert(i*100+j, (i+l)*100+(j+r), d);
      }
    }
  }

  dj.dijkstra(0);
  std::cout << dj.d[(h-1)*100+(w-1)] + (s[0][0]=='#'?1:0) << '\n';
  return 0;
}


Measured memory_bytes: 1152
import numpy as np

LI = lambda: list(map(int, input().split()))

N = int(input())
A = LI()


def main():
    s = 0
    for a in A[2:]:
        s ^= a
    t = A[0] + A[1]
    f = lambda x: list(map(int, format(x, "050b")[::-1]))
    sb = f(s)
    tb = f(t)
    ab = f(A[0])

    dp = np.full((51, 2, 2), -1, dtype=int)
    dp[0][0][0] = 0
    for i in range(50):
        for j in range(2):
            for k in range(2):
                if dp[i][j][k] == -1:
                    continue
                for na in range(2):
                    for nb in range(2):
                        if na ^ nb != sb[i] or (na + nb + j) % 2 != tb[i]:
                            continue
                        nj = (na + nb + j) // 2
                        if na == ab[i]:
                            nk = k
                        elif na == 1:
                            nk = 1
                        else:
                            nk = 0
                        v = dp[i][j][k] + (2 ** i) * na
                        dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], v)

    if dp[-1][0][0] < 1:
        ans = -1
    else:
        ans = A[0] - dp[-1][0][0]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 27112
N, *A = map(int, open(0).read().split())
ans = 0
for i in range(N):
    minj = i
    for j in range(i, N):
        if A[j] < A[minj]:
            minj = j
    if i != minj:
        A[i], A[minj] = A[minj], A[i]
        ans += 1
print(' '.join(map(str, A)))
print(ans)


Measured memory_bytes: 5600
#%%time
from itertools import accumulate
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def loop1(a):
  #b = [0]*(n+1)
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)

Measured memory_bytes: 122796
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function bsearch(a,x);l,r=0,length(a)+1;while r-l>1;m=(r+l)>>1;if a[m]<x;l=m;else;r=m;end;end;l;end
function main()
	p = 10^9+7
	n,m = readline() |> split |> parseMap
	a = readline() |> split |> parseMap |> sort
	b = readline() |> split |> parseMap |> sort
	ad = Dict{Int,Int}()
	bd = Dict{Int,Int}()
	f = 0
	for i in 1:n
		if haskey(ad,a[i])
			f = 1
		else
			ad[a[i]] = i
		end
	end
	for i in 1:m
		if haskey(bd,b[i])
			f = 1
		else
			bd[b[i]] = i
		end
	end

	k = 1
	for i in n*m:-1:1
		if haskey(ad,i)&&haskey(bd,i)
		elseif haskey(ad,i)
			z = m-bsearch(b,i)
			k = k*z%p
		elseif haskey(bd,i)
			z = n-bsearch(a,i)
			k = k*z%p
		else
			x = m-bsearch(b,i)
			y = n-bsearch(a,i)
			k = k*(x*y-n*m+i)%p
		end
	end
	println(f==0?k:0)
end

main()

Measured memory_bytes: 115360
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define tp tuple<int,int,int>
#define mtp make_tuple
using namespace std;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    set<string>h;
    while(n--)
    {
        string s;
        cin>>s;
        h.insert(s);
    }
    cout<<(int)h.size();
}


Measured memory_bytes: 19252
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.*;

public class Main {

    static int D;
    static int G;
    static int p[];
    static int c[];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        D = scanner.nextInt();
        G = scanner.nextInt();
        p = new int[D];
        c = new int[D];
        for (int n = 0;n < D;++n){
            p[n] = scanner.nextInt();
            c[n] = scanner.nextInt();
        }
        System.out.println(search(0,p));
    }

    public static int search(int s,int p[]){
        int min = Integer.MAX_VALUE;
        for (int i = 0;i < D;++i) {
            if(p[i] == 0)continue;
            int t = (G - s) / ((i + 1) * 100);
            if((G - s) % (i * 100 + 100) != 0)++t;
            if (t <= p[i]){
                if(t < min)min = t;
            }
            else {
                int ns = s + p[i] * (i * 100 + 100) + c[i];
                if(ns >= G){
                    if(p[i] < min)min = p[i];
                }
                else {
                    int[] cp = p.clone();
                    cp[i] = 0;
                    int k = search(ns, cp);
                    if (k + p[i] < min)min = k + p[i];
                }
            }
        }
        return min;
    }
}


Measured memory_bytes: 148052
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 1

typedef long long ll;

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

int main(){
    int n,m;
    cin >> n >> m;
    cout << (n-1) * (m-1) << endl;
    return 0;
}


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

int main(){
    int n, m;
    int a[100][100], b[100];
    
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < m; i++){
        cin >> b[i];
    }
    for (int i = 0; i < n; i++){
        int c = 0;
        for (int j = 0; j < m; j++){
            c += a[i][j] * b[j];
        }
        cout << c << endl;
    }
}


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

int H, W;
const int MAX_H = 50;
vector<string> S(MAX_H);
void solve()
{
	int dire[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, 
			{0, -1}, {0, 0}, {0, 1},
			{1, -1}, {1, 0}, {1, 1}};
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			int cnt = 0;
			if(S[i][j] == '.'){
				for(int k = 0; k < 9; k++){
					int pos_x = j + dire[k][0];
					int pos_y = i + dire[k][1];
						if(0 <= pos_x && pos_x < W && 0 <= pos_y && pos_y < H && S[pos_y][pos_x] == '#')
							cnt++;
				}	
				S[i][j] = cnt + '0';
			}
		}
	}
	for(int i = 0; i < H; i++)
		cout << S[i] << endl;
}
int main()
{
	cin >> H >> W;
	for(int i = 0; i < H; i++){
		cin >> S[i];
	}
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define LFOR(i, a, b) for (long long int i = (a); i <= (b); i++)
#define LRFOR(i, a, b) for (long long int i = (a); i >= (b); i--)
#define MOD 1000000007
#define INF 1000000000           // 2000000000
#define LINF 1000000000000000000 // 9000000000000000000
#define DINF 1000000000000000.0
#define PI 3.14159265358979

//.size()はunsigned int　0-1をするとオーバーフローする

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

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

int main(void) {
    int n;
    string s;

    cin>>n>>s;

    FOR(i,0,s.size()-1){
       s[i]+=n; 
       if(s[i]>'Z'){
           s[i]-=26;
       }
    }
    cout<<s<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
#define intl long long
#define mp make_pair

int main(){
	map<string,int> m;
	int a;
	cin>>a;
	vector <string> v;
	for(int i=0;i<a;i++){
		string b;
		cin>>b;
		if(m.count(b)==0){
			m[b]=1;
		}
		else{
			m[b]++;
		}
		v.push_back(b);
	}
	cin>>a;
	for(int i=0;i<a;i++){
		string b;
		cin>>b;
		if(m.count(b)==1){
			m[b]--;
		}
	}
	int max=0;
	for(int i=0;i<v.size();i++){
		if(m[v[i]]>max){
			max=m[v[i]];
		}
	}
	cout<<max<<endl;
	return 0;

}

Measured memory_bytes: 256
k = int(input())
ans = [i for i in range(1, 10)]


def generate_lunlun(x):
    y = x % 10
    if 0 <= y-1:
        yield 10*x + y-1
    yield 10*x + y
    if y+1 < 10:
        yield 10*x + y+1


idx = 0
while len(ans) < k:
    x = ans[idx]
    for i in generate_lunlun(x):
        ans.append(i)
    idx += 1

print(ans[k-1])

Measured memory_bytes: 7144
#include<bits/stdc++.h>
using namespace std;
map<int,int>M;
int main()
{
	int n,m;
	cin>>n;
	for(int i=0;i<n;i++)
    {
        int x;
        cin>>x,M[x]++;
    }
	cin>>m;
	int f=0;
	for(int i=0;i<m;i++)
	{
		int x;
        cin>>x;
		if(!M[x]) {f=1;break;}
		else M[x]--;
	}
	cout<<(f?"NO\n":"YES\n");
	return 0;
}


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

int N;
map<char, int> S;

void solve() {
  cout << (S.size() == 3 ? "Three" : "Four") << endl;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) {
    char c;
    cin >> c;
    ++S[c];
  }
  solve();
}

Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var e = int.Parse(line[1]);
        var dp = new long[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i == j) dp[i, j] = 0;
                else dp[i, j] = 999999999999;
        for (int i = 0; i < e; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            var s = int.Parse(line2[0]);
            var t = int.Parse(line2[1]);
            var d = int.Parse(line2[2]);
            dp[s, t] = d;
        }
        goWarshall(dp);
        display(dp);
    }
    public static void display(long[,] dp)
    {
        var n = dp.GetLength(0);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i == j && dp[i, j] < 0)
                { Console.WriteLine("NEGATIVE CYCLE"); return; }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (j == n - 1)
                {
                    if (dp[i, j] == 999999999999) Console.WriteLine("INF");
                    else Console.WriteLine(dp[i, j]);
                }
                else if (dp[i, j] == 999999999999) Console.Write("INF ");
                else Console.Write("{0} ", dp[i, j]);
    }
    public static void goWarshall(long[,] dp)
    {
        var n = dp.GetLength(0);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                {
                    if (dp[j, i] != 999999999999 && dp[i, k] != 999999999999)
                        dp[j, k] = Math.Min(dp[j, k], dp[j, i] + dp[i, k]);
                }
    }
}

Measured memory_bytes: 9468
import java.util.Scanner;
class Main{
    public static void main(String[] av){
	Scanner sc=new Scanner(System.in);
	int a=sc.nextInt();
	int b=sc.nextInt();
	if(a>b){
	    System.out.println("a > b");
	}else if(a<b){
	     System.out.println("a < b");
	}else{
	     System.out.println("a == b");
	}
    }
}


Measured memory_bytes: 26348
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 998244353;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); 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; }


int main() {   
    int h1, m1, h2, m2, k; cin >> h1 >> m1 >> h2 >> m2 >> k;
    int h = (h2 - h1)*60;
    int m = m2 - m1;
    int sum = h + m;
    cout << sum - k << ln;
}

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

int main() {
    string st;
    cin >> st;

    string res = "Yes";
    int n = 0, w = 0, s = 0, e = 0;
    for (int i = 0; i < st.size(); i++) {
       switch (st.at(i)) {
           case 'N':
               n++;
               break;
           case 'W':
               w++;
               break;
           case 'S':
               s++;
               break;
           case 'E':
               e++;
               break;
           default:
               break;
       }
    }

    if (!((n == 0 && s == 0) || (n != 0 && s != 0))) res = "No";
    if (!((w == 0 && e == 0) || (w != 0 && e != 0))) res = "No";

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<string>
 
using namespace std;
 
int main() {
	int a, b;
	char c;
	cin >> a >> c >> b;
	if (c == '+')cout << a + b << endl;
	if (c == '-')cout << a - b << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
typedef pair<int , int > pii;
#define MOD 1000000007
#define MOD1 998244353
#define ff first
#define ss second
#define bn cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define sz(a) (a).size()
#define o(a) cout << a
#define MAX6 1000006
#define int ll
#define all(x) x.begin(), x.end()
#define ppii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<ppii>
#define vs vector<string>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define MAX5 300005
#define MAX7 10000007
#define rep(i,a,b)  for (__typeof((b)) i=(a);i<=(b);i++)
#define nrep(i,b,a)  for (__typeof((b)) i=(b);i>=(a);i--)
#define mem(a) memset(a,0,sizeof(a))
#define memneg(a) memset(a,-1,sizeof(a))
//#define se second
#define LN 14
#define LIM 22
#define MAX_ALPHA 26
const long long INF64 = 1e18;
const ll INF = 1e9;
const double PI = acos(-1);
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
inline void max_self(ll &a, ll b)
{
  a = max(a,b);
}
 
inline void min_self(ll &a,ll b)
{
  a = min(a,b);
}
 
inline void add_self(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
 
inline void sub_self(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}
 
inline int mul(int a, int b) {
  return (int) ((long long) a * b % MOD);
}
 
 
ll gcd(ll a,ll b)
{
  if(b == 0)
    return a;
  else 
    return gcd(b, a%b);
}
 
 
int countDigits(int x)
{
  int cnt = 0;
  while(x)
  {
    x /= 10;
    cnt++;
  }
  return cnt;
}
 
 
ll binExpo(ll a,ll b)
{
  ll res = 1;
  while(b)
  {
    if(b&1)
      res = (res * a)%MOD;
    a = (a * a)%MOD;
    b /= 2;
  }
  return res%MOD;
}
 
int sum(int a) {
    int result = 0;
    while (a > 0) {
        result += a % 10;
        a /= 10;
    }
    return result;
}

const int nax = 405;

int dp[nax][nax];

//dp[i][j]   -->    minimum total cost of combining interval [i..j] to one 

void solve(){
    int n;
    cin>>n;
    vector<int > a(n);
    rep(i, 0, n-1)
      cin>>a[i];

    auto sum = [&](int L, int R){
      int s = 0;
      rep(i, L, R)
        s += a[i];
      return s;
    };

    nrep(L, n-1, 0)
    {
      rep(R, L, n-1)
      {
        if(L == R)
          dp[L][R] = 0;
        else{
          dp[L][R] = INF64;
          int s = sum(L, R);
          rep(i, L , R-1){
            dp[L][R] = min(dp[L][R], dp[L][i] + dp[i+1][R] + s);
          }
        }
      }
    }

    cout<<dp[0][n-1]<<endl;
}

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

  int t = 1;
  //cin>>t;
  while(t--) solve();
  return 0;
}















Measured memory_bytes: 1536
/*
やったぜ。　投稿者：変態糞土方 (8月16日（水）07時14分22秒)

昨日の8月15日にいつもの浮浪者のおっさん（60歳）と先日メールくれた汚れ好きの土方のにいちゃん
（45歳）とわし（53歳）の3人で県北にある川の土手の下で盛りあったぜ。
今日は明日が休みなんでコンビニで酒とつまみを買ってから滅多に人が来ない所なんで、
そこでしこたま酒を飲んでからやりはじめたんや。
3人でちんぽ舐めあいながら地下足袋だけになり持って来たいちぢく浣腸を3本ずつ入れあった。
しばらくしたら、けつの穴がひくひくして来るし、糞が出口を求めて腹の中でぐるぐるしている。
浮浪者のおっさんにけつの穴をなめさせながら、兄ちゃんのけつの穴を舐めてたら、
先に兄ちゃんがわしの口に糞をドバーっと出して来た。
それと同時におっさんもわしも糞を出したんや。もう顔中、糞まみれや、
3人で出した糞を手で掬いながらお互いの体にぬりあったり、
糞まみれのちんぽを舐めあって小便で浣腸したりした。ああ～～たまらねえぜ。
しばらくやりまくってから又浣腸をしあうともう気が狂う程気持ちええんじゃ。
浮浪者のおっさんのけつの穴にわしのちんぽを突うずるっ込んでやると
けつの穴が糞と小便でずるずるして気持ちが良い。
にいちゃんもおっさんの口にちんぽ突っ込んで腰をつかって居る。
糞まみれのおっさんのちんぽを掻きながら、思い切り射精したんや。
それからは、もうめちゃくちゃにおっさんと兄ちゃんの糞ちんぽを舐めあい、
糞を塗りあい、二回も男汁を出した。もう一度やりたいぜ。
やはり大勢で糞まみれになると最高やで。こんな、変態親父と糞あそびしないか。
ああ～～早く糞まみれになろうぜ。
岡山の県北であえる奴なら最高や。わしは163*90*53,おっさんは165*75*60、や
糞まみれでやりたいやつ、至急、メールくれや。
土方姿のまま浣腸して、糞だらけでやろうや。
*/

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main m = new Main();
    }
    
    public Main(){
        Scanner s = new Scanner(System.in);
        long N = s.nextLong();
        long M = s.nextLong();
        long reverse = 0;
        if(N >= 3 && M >= 3)
            reverse = N*M - (N+M-2)*2;
        else if(N == 2 || M == 2)
            reverse = 0;
        else if(N == 1 && M == 1)
            reverse = 1;
        else if(N == 1)
            reverse = M - 2;
        else if(M == 1)
            reverse = N - 2;
        System.out.println(reverse);
    }
    
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e9;
using namespace std;

class UnionFind{
	private:
		vector<int> par, depth;
	public:
		UnionFind() {}
		UnionFind(int n){
			init(n);
		}
		void init(int n){
			par = vector<int>(n);
			depth = vector<int>(n);
			rep(i,n){
				par[i] = i;
				depth[i] = 0;
			}
		}
		int find(int x){
			if(par[x] == x){
				return x;
			}else {
				return par[x] = find(par[x]);
			}
		}
		void unite(int x, int y){
			x = find(x);
			y = find(y);
			if(x == y) return;

			if(depth[x] < depth[y]){
				par[x] = y;
			}else{
				par[y] = x;
				if(depth[x] == depth[y]) depth[x]++;
			}
		}
		bool same(int x, int y){
			return find(x) == find(y);
		}
};

struct Edge{
	int u, v, cost, id;
	Edge() {}
	Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}

	bool operator < ( const Edge &right ) const {
		return cost < right.cost ? 1 : (cost == right.cost ? (u < right.u ? 1 : (u == right.u ? (v == right.v) : 0)) : 0);
	}
};

class Kruskal{
	private:
		static const int MAX_E = 50005;
		UnionFind unionFind;
	public:
		int v;
		vector<Edge> edge;
		vector<int> mst; //edge[ mst[i] ] := 最小全域木を構築するi番目の辺
		Kruskal(vector<Edge>& e, int _v){
			v = _v;
			unionFind.init(v);
			edge = e;
			sort(all(edge));
		}
		void reset(int v){
			unionFind.init(v);
		}
		long long solve(vector<bool> sinked){
			long long res = 0;
			rep(i,edge.size()){
				Edge c = edge[i];
				if(not unionFind.same(c.u, c.v) and not sinked[c.u] and not sinked[c.v]){
					unionFind.unite(c.u, c.v);
					res += c.cost;
					mst.emplace_back(i);
				}
			}
			int b = 0;
			rep(i,v){
				if(sinked[i]) continue;
				b = i;
				break;
			}
			rep(i,v){
				if(not unionFind.same(b,i) and not sinked[i]){
					return INF;
				}
			}
			return res;
		}
};

int main(){
	int n, m;
	while(cin >> n >> m, n||m){
		map<int,vector<int>> h;
		rep(i,n){
			int a;
			cin >> a;
			h[a].emplace_back(i);
		}

		vector<Edge> e(m);
		rep(i,m){
			int a, b, c;
			cin >> a >> b >> c;
			e[i] = Edge{a - 1, b - 1, c};
		}

		Kruskal krus(e, n);
		vector<bool> sinked(n,0);
		if(krus.solve(sinked) == INF){
			cout << 0 << endl;
			continue;
		}

		for(auto it = h.begin(); it != h.end(); it++){
			krus.reset(n);
			vector<bool> cp = sinked;
			for(auto p : it->second) cp[p] = true;
			//for(auto i : cp) cout << i << ' '; cout << endl;
			if(krus.solve(cp) == INF){
				break;
			}
			sinked = cp;
		}


		krus.reset(n);
		//for(auto i : sinked) cout << i << ' '; cout << endl;
		long long ans = 0;
		for(auto it = h.rbegin(); it != h.rend(); it++){
			for(auto p : it->second) sinked[p] = false;
		//for(auto i : sinked) cout << i << ' '; cout << endl;
			ans += krus.solve(sinked);
			//show(ans)
			assert(ans <= INF);
		}
		cout << ans << endl;
	}
}



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

int main()
{
	int n;
	cin>>n;
long long a[n],g[n],gg[n];
for(int i=0;i<n;i++)cin>>a[i];
g[0]=a[0];
for(int i=1;i<n;i++)g[i]=__gcd(g[i-1],a[i]);
gg[n-1]=a[n-1];
for(int i=n-2;i>=0;i--)gg[i]=__gcd(gg[i+1],a[i]);


long long an=1;
for(int i=1;i<n-1;i++)
an=max(an,__gcd(g[i-1],gg[i+1]));
an=max({an,gg[0],gg[1],g[n-2]});
cout<<an<<endl;


}



Measured memory_bytes: 5940
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N; i >= 0; i--)
const ll INF = 1000000000000000000;
#define PI 3.1415926535
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
bool seen[100000];
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

//input



//processing
int ans = 1;



//dpTable
//int dp[100050];
int main(){
    int N,K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        ans = min(ans + K,ans * 2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin >> n;
    
    vector<int> a(n), b(n),c(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n; i++) cin >> c[i];
    
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());
    
    long long ans = 0;
    for(int i = 0; i < n; i++){
        long long number_of_lower_parts = lower_bound(a.begin(),a.end(),b[i]) - a.begin();
        long long number_of_upper_parts = c.end() - upper_bound(c.begin(),c.end(),b[i]);
        ans += number_of_lower_parts * number_of_upper_parts;
    }
    cout << ans << endl;
}


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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

int main(){
string s;
cin>>s;

if(s=="ABC")
cout<<"ARC"<<endl;
else
{
  cout<<"ABC"<<endl;
}



  return 0;
}


Measured memory_bytes: 3628
#include <iostream>

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

using namespace std;

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if (A + B > C + D)
        cout << "Left" << endl;
    else if (A + B == C + D)
        cout << "Balanced" << endl;
    else
        cout << "Right" << endl;

    return 0;
}

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

int n,x,y,z,w,sum;

int main(){
	while(scanf("%d",&n)*n){
		sum=0;
		for(;n>0;n--){
			scanf("%d %d %d %d",&x,&y,&z,&w);
			x+=y+z;
			if(x>160 || w>25)sum+=0;
			else if(x>140 || w>20)sum+=1600;
			else if(x>120 || w>15)sum+=1400;
			else if(x>100 || w>10)sum+=1200;
			else if(x>80 || w>5)sum+=1000;
			else if(x>60 || w>2)sum+=800;
			else sum+=600;
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 600
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
using namespace std;

int main(void){
        int i,j;
        long long a,b,n,x;

        scanf("%lld%lld%lld",&a,&b,&n);
        if(b-1<=n){
                n += 1;
                x = (n/b)*b;
                x--;
        } else {
                x = n;
        }
        printf("%lld\n", (a*x)/b - a*(x/b) );
        return 0;
}
        


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << #x << '=' << x << '\n'
const long long MOD=1e9+7;
//const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<class T1,class T2> inline bool chmin(T1 &a,T2 b){
    if (a>b){a=b; return true;} return false;
}
template<class T1,class T2> inline bool chmax(T1 &a,T2 b){
    if (a<b){a=b; return true;} return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S,T; cin >> S >> T;
    int n=S.size();
    cout << (S==T.substr(0,n)?"Yes":"No") << '\n';
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  
  long long sum = 0;
  long long ans1 = 0;
  for (int i = 0; i < n; i++)
  {
    sum+=a[i];
    if(i%2==0){
      if(sum>=0){
        ans1+=sum+1;
        sum=-1;
      }
    }
    else{
      if(sum<=0){
        ans1+=1-sum;
        sum=1;
      }
    }
  }

  sum = 0;
  long long ans2 = 0;
  for (int i = 0; i < n; i++)
  {
    sum+=a[i];
    if(i%2==0){
      if(sum<=0){
        ans2+=1-sum;
        sum=1;
      }
    }
    else{
      if(sum>=0){
        ans2+=sum+1;
        sum=-1;
      }
    }
  }
  cout << min(ans1,ans2) << endl;  
}

Measured memory_bytes: 768
str = str(input())
q = int(input())
for i in range(q):
    order = input().split()
    if order[0] == "print":
        print(str[int(order[1]):int(order[2])+1])
    elif order[0] == "reverse":
        str = str[:int(order[1])] + str[int(order[1]):int(order[2])+1][::-1] + str[int(order[2])+1:]
        # print(str)
    elif order[0] == "replace":
        str = str[:int(order[1])] + order[3] + str[int(order[2])+1:]
        # print(str)
    else:
        pass



Measured memory_bytes: 5616
#include <iostream>
using std::cin ;
using std::cout;

int main(){
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  int N,K,Q; cin>>N>>K>>Q;
  int num = Q-K;
  int* member = new int[N];
  for (int i=0;i<Q;++i){
    int tmp; cin>>tmp;
    ++member[tmp-1];
  }
  for(int i=0;i<N;++i){
    if((member[i])>num){
      cout << "Yes" << std::endl;
    }else{
      cout << "No" << std::endl;
    }
  }
  return 0;
}


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

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    if (s == "ABC")
        cout << "ARC";
    else
        cout << "ABC";

    return 0;
}

Measured memory_bytes: 3652
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#define ll long long
#define oku7 1000000007
using namespace std;


int main() {
	int N;
	vector<int> l,moto;
	cin >> N;
	l.reserve(200000);
	moto.reserve(200000);
	for (int i = 0; i < N; i++) {
		int x;
		//cin >> x;
		scanf("%d", &x);
		l.push_back(x);
		moto.push_back(x);
	}


	sort(l.begin(), l.end());
	
	for (int i = 0; i < N; i++) {
		//int ind = binSearch(l, moto[i]);
		int mid = l[N / 2];
		if (moto[i] < mid) {
			//cout << l[N / 2]<< "\n";
			printf("%d\n", l[N / 2]);
		}
		else {
			//cout << l[N / 2 - 1] << "\n";
			printf("%d\n", l[N / 2-1]);
		}
	}
	

	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
using namespace std;
signed main(){
  int a;
  cin>>a;
  if(a%2==0)
    cout<<a;
  else
    cout<<a*2;
}

Measured memory_bytes: 256
let split_string ?(pattern="") = Str.split @@ Str.regexp pattern
let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n
let a = read_line () |> split_string ~pattern:" " |> List.map int_of_string
let b = read_line () |> split_string ~pattern:" " |> List.map int_of_string

let c = List.map2 (fun a b -> b - a) a b
let (px, mx) = List.fold_left (fun (sp, sm) c -> if c > 0 then (c :: sp, sm) else (sp, c :: sm)) ([], []) c
let sp = List.fold_left (+) 0 px
let sm = List.fold_left (+) 0 mx

let f () = 
  let rec loop i = function
    | (rest, _) when rest <= 0 -> i
    | (_, []) -> failwith ""
    | (rest, x :: xs) -> loop (i + 1) (rest + x, xs)
  in
  let mx = List.sort compare mx in
  List.length px + loop 0 (sp, mx)

let () = 
  if sp + sm > 0 then print_endline "-1"
  else if sp = 0 then print_endline "0" 
  else Printf.printf "%d\n" @@ f ()

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

int main() {
  int a, b;
  cin >> a >> b;

  if (a * b / 2 != (a * b - 1) / 2) {
    cout << "Even" << endl;
  }
  
  else {
    cout << "Odd" << endl;
  }
}

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

int main(){
        int n,ans=0;
        cin >> n;

        int a,b;
        bool flag=1;
        cin >> a;
        for(int i=1; i<n; i++){
                cin >> b;
                if(flag==1 && a==b){
                        ans++;
                        flag=0;
                }
                else flag=1;
                a=b;
        }

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


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

using namespace std;

int main() {
  int N; cin >> N;
  int a[2][N];

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

  int ans = 0;
  for (int i = 0; i < N; i++) {
    int ame = 0;
    for (int j = 0; j < i+1; j++) {
      ame += a[0][j];
    }
    for (int k = i; k < N; k++) {
      ame += a[1][k];
    }
    ans = max(ame, ans);
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, O = 0, P = 0, Q = 0;
  cin >> N;
  vector<int> X(N);
  for (int i = 0; i < N; i++) {
    cin >> X.at(i);
    O += X.at(i);
  }
  O /= N;
  for (int i = 0; i < N; i++) {
    if (O > X.at(i)) {P += (O - X.at(i)) * (O - X.at(i));}
    else {P += (X.at(i) - O) * (X.at(i) - O);}
  }
  for (int i = 0; i < N; i++) {
    if (O + 1 > X.at(i)) {Q += (O + 1 - X.at(i)) * (O + 1 - X.at(i));}
    else {Q += (X.at(i) - O - 1) * (X.at(i) - O - 1);}
  }
  cout << min(P, Q) << endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.20f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;

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

	if (n % 1000 == 0) {
		cout << 0 << endl;
	}
	else {
		cout << 1000 - n % 1000 << endl;
	}

	return 0;
}


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

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

string S;
signed main() {
    cin >> S;
    int m = S.length();
    while (m > 0) {
        if (m < 5) { break; }
        if (S.substr(m - 5, 5) == "erase") {
            m -= 5;
            continue;
        }
        if (S.substr(m - 5, 5) == "dream") {
            m -= 5;
            continue;
        }
        if (m < 6) { break; }
        if (S.substr(m - 6, 6) == "eraser") {
            m -= 6;
            continue;
        }
        if (m < 7) { break; }
        if (S.substr(m - 7, 7) == "dreamer") {
            m -= 7;
            continue;
        }
        fin("NO");
    }
    if (m == 0) { cout << "YES" << endl; }
    else { cout << "NO" << endl; }

}


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

typedef long long int   ll;
#define int             ll
#define PI              3.1415926535897932384626433832795

#define pb              push_back
#define rep0            for(int i=0;i<n;i++)
#define rep1            for(int i=1;i<=n;i++)
#define inputar0(ar)    for(int i=0;i<n;i++)cin>>ar[i]
#define inputar1(ar)    for(int i=1;i<=n;i++)cin>>ar[i]

#define hell            freopen("input.txt","r", stdin);freopen("output.txt", "w", stdout);freopen("error.txt", "w",stderr);
#define fastasF_boi()   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl            "\n"
//#define cerr            if(false)cerr

int mod=1000000007;
int maxn=200001;
int binpow(int a,int b,int mod){int res=1;while(b>0){if(b%2){res=(res*a)%mod;b--;}a=(a*a)%mod;b/=2;}return res%mod;}
int binpow(int a,int b){int res=1;while(b>0){if(b%2){res=(res*a);b--;}a=(a*a);b/=2;}return res;}
bool isPrime(int n){if(n==1)return false;for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}
int mulmod(int a,int b){return ((a%mod)*(b%mod))%mod;}
int addmod(int a,int b){return (((a%mod)+(b%mod))+mod)%mod;}

void solve(){
    int n;cin>>n;
    int ar[n];
    for(int i=0;i<n;i++){
        cin>>ar[i];
    }
    vector<int> ss(n,0);
    ss[n-1]=ar[n-1];
    for(int i=n-2;i>=0;i--){
        ss[i]=addmod(ss[i+1],ar[i]);
    }
    int ans=0;
    for(int i=0;i<n-1;i++){
        ans=addmod(ans,mulmod(ar[i],ss[i+1]));
    }
    cout<<ans<<endl;
}

signed main(){
//    hell;

    fastasF_boi();
    int t=1;
//    cin>>t;
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}



Measured memory_bytes: 6364
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long r = sc.nextLong();
    long g = sc.nextLong();
    long b = sc.nextLong();
    long n = sc.nextLong();
    long cnt = 0;
    for(long i = 0;i <= n;i++)
      for(long j = 0;j <= n;j++)
        if(n-i*r-j*g>=0&&(n-i*r-j*g)%b==0)cnt++;
    System.out.println(cnt);
  }
}


Measured memory_bytes: 22356
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>
#include <set>
#include <map>
#include <type_traits>
#include <cstdint>
#include <queue>
#define _USE_MATH_DEFINES
#include <math.h>
#include <sstream> // std::stringstream
#include <bitset>  // std::bitset<N>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

//素因数分解
void factoring(ll n, map<ll, ll>& mp) {
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			mp[i]++;
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
}

//絶対値
template<class T, class U = std::make_unsigned_t<T>>
U SafeAbs( T x ) {
    return x < 0 ? -static_cast<uintmax_t>(x) : x;
}

//最大・最小
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//xのn乗
ll mod_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
//xの逆元
ll mod_inv(ll x, ll mod) {//O(log(mod))
    return mod_pow(x, mod - 2, mod);
}

//nCr
ll ncr(ll n, ll r, ll mod){
	ll res=1;
	ll num=1,den=1;
	for(ll i=n;i>=n-r+1;i--){
		(den*=i)%=mod;
	}
	for(ll i=1;i<=r;i++){
		(num*=i)%=mod;
	}
	
	res=den*mod_inv(num,mod);

	return res%mod;
}


//二分探索
bool isOk(ll index, ll key,vector<ll> &a){
	
	if(a[index]>key){
		return true;
	}
	
	return false;
}

ll bin_search(ll key, vector<ll> &a){
	
	ll l=-1;
	ll r=a.size();

	while(abs(r-l)>1){
		ll mid = (l+r)/2;
		if(isOk(mid, key, a)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	return r;
}

/*
//深さ優先探索
void dfs(vector<vector<ll>> &gra,vector<bool> &seen, ll v){

	seen[v]=true;

	for(auto next : gra[v]){
		if(seen[next]){
			continue;
		}

		dfs(gra,seen,next);
	}
	
}
*/

const ll MOD=1000000007;

ll min(ll a, ll b){
	if(a>=b){
		return b;
	}
	else{
		return a;
	}
}

bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}


void solve()
{
	ll n;
	cin >> n;
	ll ans = 0;
	for (ll i = 1; i <= n; i+=2)
	{
		ll cnt = 0;
		for (ll j = 1; j <= i;j++){
			if (i % j == 0)
			{
				cnt++;
			}
		}
		if(cnt==8)
		{
			ans++;
		}
	}

	cout << ans << endl;
}

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

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

int main() {
  int N,
      Alice = 0,
      Bob = 0;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  for (int i = 0; i < N; i++) {
    int max = 0,
        max_i;
    for (int j = 0; j < N; j++) {
      if (a.at(j) >= max) {
        max = a.at(j);
        max_i = j;
      }
    }
    a.at(max_i) = 0;
    if (i % 2) {
      Bob += max;
    }
    else {
      Alice += max;
    }
  }
  cout <<  Alice - Bob << endl;
}


Measured memory_bytes: 256
import math

def main():
  A, B, C = map(int, input().split())
  
  if A == B and B != C:
    print('Yes')
  elif A == C and A != B:
    print('Yes')
  elif B == C and B != A:
    print('Yes')
  else:
    print('No')
  
  
main()

Measured memory_bytes: 9076
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main() {
    int n,k,x,y;
    cin>>n>>k>>x>>y;
    if(n<=k){
        cout<<x*n<<endl;
    }else{
        cout<<x*k+y*(n-k)<<endl;
    }
}   



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
 
int main() {
  ll n;
  cin>>n;
  bool b =1;
  vector<int> a(n);
  rep(i,n){
    cin>>a[i];
  }
  rep(i,n){
    if(a[i]%2==0){
      if(a[i]%3==0||a[i]%5==0){
        continue;
      }
      else{
        b=0;
        break;
      }
    }
  }
  if(b){
    cout<<"APPROVED"<<endl;
  }
  else{
    cout<<"DENIED"<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

template<class T> inline void checkmin(T &a,const T &b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,const T &b){if(b>a) a=b;}

const int inf=1e9+10;
const int maxn=2e5+10;

vector <int> g[maxn],v[3],c[2];
int n,ans[maxn];

void dfs(int x,int fa,int col){
	c[col].pb(x);
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to!=fa) dfs(to,x,col^1);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int u,vv;
		scanf("%d%d",&u,&vv);
		u--; vv--;
		g[u].pb(vv);
		g[vv].pb(u);
	}
	dfs(0,-1,0);
	for(int i=1;i<=n;i++) v[i%3].pb(i);
	if(c[0].size()>c[1].size()) swap(c[0],c[1]);
	vector <int> v2,v3;
	if(c[0].size()>=v[2].size()){
		for(int i=0;i<v[2].size();i++)
			v2.pb(v[2][i]);
		for(int i=0;i<v[0].size();i++)
			v2.pb(v[0][i]);
		for(int i=0;i<v[1].size();i++)
			v2.pb(v[1][i]);
	}
	else{
		for(int i=0;i<v[0].size();i++)
			v2.pb(v[0][i]);
		for(int i=0;i<v[1].size();i++)
			v2.pb(v[1][i]);
		for(int i=0;i<v[2].size();i++)
			v2.pb(v[2][i]);
	}
	for(int i=0;i<c[0].size();i++) v3.pb(c[0][i]);
	for(int i=0;i<c[1].size();i++) v3.pb(c[1][i]);
	for(int i=0;i<n;i++)
		ans[v3[i]]=v2[i];
	for(int i=0;i<n;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}


Measured memory_bytes: 21872
#include <iostream>
#define C(a,b)  *(a) == *std::next((a), (b))
#define O(a)    std::cout << (std::distance(T.begin(), itr) + 1) << " " << (std::distance(T.begin(), std::next(itr, (a))) + 1) << std::endl
int main(){std::string T;std::cin>>T;for(auto itr=T.begin();itr!=T.end();++itr){if(C(itr,1)){O(1);return 0;}else if(C(itr,2)){O(2);return 0;}}std::cout<<"-1 -1"<<std::endl;return 0;}

Measured memory_bytes: 512
n, m, q = list(map(lambda x: int(x), input().split(' ')))

e = []

for i in range(q):
  s = list(map(lambda x: int(x), input().split(' ')))
  e.append(s)

def helper(l, tmp, n, all):
  if len(tmp) == n:
    r = tmp.copy()
    all.append(r)
    return

  for i, v in enumerate(l):
    tmp.append(v)
    helper(l[i:], tmp, n, all)
    tmp.pop()

candidates = []
helper(list(range(1, m+1)), [], n, candidates)

max_val = 0

for c in candidates:
  sum = 0

  for j in e:
    if c[j[1] - 1] - c[j[0] - 1] == j[2]:
      sum += j[3]

  max_val = max(max_val, sum)

print(max_val)

Measured memory_bytes: 22912
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m;
	cin>>n>>m;
	cout<<min(n,m-((n-1)%m+1))<<endl;
}











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

int main() {
    int i, j, k;
    string s;
    cin >> s;
    int cnt = 0;
    char a = s[0];
    char b = s[1];
    char c = s[2];
    char d = s[3];
    if (a == b) cnt++;
    if (a == c) cnt++;
    if (a == d) cnt++;
    if (b == c) cnt++;
    if (b == d) cnt++;
    if (c == d) cnt++;
    if (cnt == 2)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
int main(){
    ll a,b,k;
    cin >> a >> b >> k;
    while(1){
        if(k==0)    break;
        if(a%2==1)  a--;
        b+=(a/2);
        a-=(a/2);
        k--;
        if(k==0)    break;
        if(b%2==1)  b--;
        a+=(b/2);
        b-=(b/2);
        k--;
    }
    cout << a << ' ' << b << endl;
    return 0;
}

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

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

const int INF = 1000000007;

int main(void){
	int n;
	int p[10000] = {0};
	cin>>n;
	for(int i=0;i<n;i++) cin>>p[i];

	int maxv=0, tmp=0, ans=0;
	for(int i=0;i<n;i++) {
		tmp = p[i];
		maxv = max(maxv, tmp);
	} 
	for(int i=0;i<n;i++) ans += p[i];
	ans = ans - (maxv / 2);
	
	cout<< ans <<endl;

	return 0;
}

Measured memory_bytes: 256