akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 10;

struct node{
    int u,v;
    ll w;
}edge[MAXN];

bool cmp(node a,node b){return a.w > b.w;}

int f[MAXN<<1],sz[MAXN<<1];

int find(int x)
{
    int t = x;
    while (x != f[x]) x = f[x];
    while (t != f[t])
    {
        int tmp = f[t];
        f[t] = x;
        t = tmp;
    }
    return x;
}

int main()
{
    int n,h,w;
    scanf("%d%d%d",&n,&h,&w);
    for (int i = 1;i<=n;i++)
    {
        scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w);
    }
    sort(edge+1,edge + n + 1,cmp);
    ll ans = 0;
    for (int i = 1;i<=h+w;i++) f[i] = i,sz[i] = 1;
    for (int i = 1;i<=n;i++)
    {
        int fu = find(edge[i].u),fv = find(edge[i].v + h);;
        if (fu == fv)
        {
            if (sz[fu] > 0)
            {
                ans += edge[i].w;
                sz[fu]--;
            }
        }
        else
        {
            if (sz[fu] + sz[fv] > 0)
            {
                f[fv] = fu;
                sz[fu] += sz[fv] - 1;
                ans += edge[i].w;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <cinttypes>
#include <string.h>
#include <bits/stdc++.h>

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define pi pair<int,int>
#define fi first
#define se second

#define FOR(var, to)          for (register s64 var = 0; var < (s64)to; var++)
#define FROMTO(var, from, to) for (register s64 var = from; var <= (s64)to; var++)

#define INIT(var) FOR(i,countof(var)) var[i] = 0
#define INPUT(var) FOR(i,countof(var)) var[i] = ri()

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)

#define MOD 1000000007
#define INF (1 << 30)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

using namespace std;

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

static inline s64 rs64() {
  s64 a;
  scanf("%" SCNd64, &a);
  return a;
}

static inline void wi(int a) {
  printf("%d", a);
}

static inline void wu64(u64 a) {
  printf("%" PRIu64, a);
}

static inline void ws64(s64 a) {
  printf("%" PRId64, a);
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
  int n = ri();
  int a = (4-(n % 4))%4;
  bool res;
  res = (n >= 7*a);
  printf(res ? "Yes":"No");
  return 0;
}


Measured memory_bytes: 256
import math
n,k= map(int,input().split())
d = list(map(int,input().split()))	
res = n

def f(x):
    c = int(math.log10(x))
    t = []
    for i in range(c+1):
        if x//((10**(c-i)))%10 in d:
            return False
    return True

while not f(res):
    res += 1
print(res)
        


Measured memory_bytes: 3060
def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    S=sum(A)
    c=0
    for i in range(n):
        if 4*m*A[i]>=S:
            c+=1
    if c>=m:
        print("Yes")
    else:
        print("No")
if __name__ == '__main__':
    main()

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
using namespace std;

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

        vi v(n);
        each(&it,v)cin>>it;

        sort(all(v),greater<int>());
        v[0]/=2;

        int ans=0;
        each(it,v)ans+=it;
        cout<<ans<<endl;
}


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

int main()
{
  int a, count = 0;
  cin >> a;

  vector<int> v(a, 0);

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


  for (int i = 0; i < a; i++)
  {
    int tmp = v[i];
    if (i == v[tmp - 1] - 1)
      count++;
  }

  cout << count / 2 << endl;

}


Measured memory_bytes: 640
from math import ceil
N = int(input())

if N == 1:
  print(1)
  exit(0)
  
#1,2,3,4 = 10 = (4)(4+1)//2
for i in range(10001):
  if N <= i * (i+1) // 2:
    break

print(i)
N -= i
for j in range(i-1,0,-1):
  if N >= j:
    print(j)
    N -= j
  

Measured memory_bytes: 3316
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());

		int x=1;

		while(n>=x){
			int w=x;
			int y=0;
			int z=0;
			if(x%3==0){
				System.out.print(" "+x);
			}else{
				while(w>0){
					y=w%10;
					z=w/10;
					if(y==3){
						System.out.print(" "+x);
						break;
					}
					w=z;
				}
			}
			x++;
		}
		System.out.println("");
	}

}



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

int main() {
  int N; cin>>N;
  vector<int> color(8);
  int sugoi=0;
  for(int i=0; i<N; i++){
    int a; cin>>a;
    if(a<400) color.at(0)=1;
    if(a>=400 && a<800) color.at(1)=1;
    if(a>=800 && a<1200) color.at(2)=1;
    if(a>=1200 && a<1600) color.at(3)=1;
    if(a>=1600 && a<2000) color.at(4)=1;
    if(a>=2000 && a<2400) color.at(5)=1;
    if(a>=2400 && a<2800) color.at(6)=1;
    if(a>=2800 && a<3200) color.at(7)=1;
    if(a>=3200) sugoi++;
  }
  int sum1=0;
  int sum2=0;
  for(int i=0; i<8; i++) sum1+=color.at(i); //min
  sum2=sum1+sugoi; //max
  if(sum1==0) cout<<1<<" "<<sum2<<endl;
  else cout<<sum1<<" "<<sum2<<endl;
}


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

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    vector<char> ans(n*2);
    for(int i=0; i<n; i++){
        ans.at(i*2) = s.at(i);
        ans.at(i*2+1) = t.at(i);
    }
    for(int i=0; i<n*2; i++){
    cout << ans.at(i);
    if(i == n*2-1){
        cout << endl;
    }
    }
}


Measured memory_bytes: 256
K = gets.chomp.to_i

lunlun_numbers = []
last_digit_lunlun_numbers = []

MAX_ANSWER = 3234566667
MAX_DIGIT = MAX_ANSWER.to_s.length

1.upto(MAX_DIGIT) do |d|
  if d == 1
    lunlun_numbers = (1..9).to_a
    last_digit_lunlun_numbers = (1..9).to_a
  else
    last_digit_lunlun_numbers = last_digit_lunlun_numbers.map {|last_l|
      last_l_1d = last_l.to_s[-1].to_i

      [last_l_1d - 1, last_l_1d, last_l_1d + 1].map do |num_to_add|
        if 0 <= num_to_add && num_to_add < 10
          new_lunlun = (last_l.to_s + num_to_add.to_s).to_i
          lunlun_numbers << new_lunlun
          new_lunlun
        end
      end
    }.flatten.compact
  end
end

puts lunlun_numbers[K-1]

Measured memory_bytes: 12228
a,b = map(int,input().split())
A = []
B = []

for i in range(1,1263):
    if (100/8)*(a) <= i < (100/8)*(a+1):
        A.append(i)
        
for i in range(1,1011):
    if (100/10)*(b) <= i < (100/10)*(b+1):
        B.append(i)
        
A = set(A)
B = set(B)

C = A&B

if len(C) > 0:
    print(min(C))
else:
    print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    
    int N; cin >> N;
    vector<int> A(N), B(N);
    rep(i, N) {
        cin >> A[i] >> B[i];
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if (N % 2 == 1) {
        int min_med = A[N/2], max_med = B[N/2];
        int ans = max_med - min_med + 1;
        cout << ans << endl;
    } else {
        int min_med = (A[N/2] + A[N/2-1]), max_med = B[N/2] + B[N/2-1];
        int ans = max_med - min_med + 1;
        cout << ans << endl;
    }
    return 0;
}

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

string s[52];

int main(void){
  int h, w;
  cin >> h >> w;
  for(int j=0;j<=w+1;j++) s[0] += '.';
  for(int i=0;i<h;i++){
    cin >> s[i];
    s[i] = '.' + s[i] + '.';
  }
  s[h+1] = s[0];
  
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};
  for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
    if (s[i][j]=='#'){
      bool ok = false;
      for(int k=0;k<4;k++){
        if (s[i+dy[k]][j+dx[k]]=='#') {ok = true; break;}
      }
      if (!ok){
        cout << "No" << endl; return 0;
      }
    }    
  }
  cout << "Yes" << endl; return 0;
}  

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
int judge(int i){
    string s = to_string(i);
    return s.size() % 2;
}
main(){
    int N;
    cin >> N;
    int cnt = 0;
    rep(i,1,N+1){
        cnt += judge(i);
    }
    cout << cnt << endl;
}

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

using namespace std;

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

    string sub = "ABC", fullString;
    int stringLength;

    cin >> stringLength >> fullString;

    vector<size_t> positions; // holds all the positions that sub occurs within str

    size_t pos = fullString.find(sub, 0);
    while(pos != string::npos)
    {
        positions.push_back(pos);
        pos = fullString.find(sub,pos+1);
    }


    cout << positions.size();
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF 1<<30
#define LINF 1LL << 62
 
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	vector<ll> A(N);
	map<ll, ll> bou;
	for (int i = 0; i < N;i++) {
		cin >> A[i];
		bou[A[i]]++;
	}
	ll ans = 0;
	ll tate = 0, yoko = 0;
	for (auto it = bou.rbegin(); it != bou.rend();it++) {
		if (tate == 0) {
			if (it->second >= 4) {
				tate = it->first;
				yoko = it->first;
				break;
			}
			else if (it->second >= 2) {
				tate = it->first;
			}
		}
		else {
			if (it->second >= 2) {
				yoko = it->first;
				break;
			}
		}
	}
	ans = tate* yoko;
	cout << ans << endl;
 
}

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

int DP(int i, int m, int A[], int n){
	if(m == 0){
		return 1;
	}else if(m != 0 && i == n){
		return 0;
	}
	
	int res1 = DP(i+1, m, A, n);
	int res2 = DP(i+1, m-A[i], A, n);
	
	if(res1 == 1 || res2 == 1){
		return 1;
	}else{
		return 0;
	}
}

int main(void){
	int n, A[20]={0}, q, m[200];
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> A[i];
	}
	
	cin >> q;
	for(int i=0; i<q; i++){
		cin >> m[i];
	}
	
	for(int i=0; i<q; i++){
		if(DP(0, m[i], A, n) == 1) cout << "yes\n";
		else cout << "no\n";
	}
	
	return 0;
}


Measured memory_bytes: 3092
import Text.Printf
import Data.List
import Data.Maybe
import Control.Applicative
import Control.Monad

main = do
  n <- readLn :: IO Int
  as <- map read . words <$> getLine :: IO [Int]

  let
    mina = minimum as
    maxa = maximum as

  print $ 2*n-1
  if abs mina < abs maxa then do
    forM_ [1..n] $ \i -> printf "%d %d\n" ((+1) . fromJust . elemIndex maxa $ as) i
    forM_ [1..n-1] $ \i -> printf "%d %d\n" i (i+1)
    else do
    forM_ [1..n] $ \i -> printf "%d %d\n" ((+1) . fromJust . elemIndex mina $ as) i
    forM_ [n,n-1..2] $ \i -> printf "%d %d\n" i (i-1)



Measured memory_bytes: 1020
#include <algorithm>
#include <cstdio>

using namespace std;

int n;
char s[300000 + 10];
int sum[300000 + 10];

int main() {
    while (~scanf("%d", &n)) {
        scanf("%s", s);
        for (int i = 0; i < n; i++) {
            int t = 0;
            if (s[i] == 'E')
                t = 1;
            sum[i + 1] = sum[i] + t;
        }

        int ans = -1;
        for (int i = 0; i < n; i++) {
            int t = 0;
            t = sum[n] - sum[i + 1] + i - sum[i];
            if (ans == -1)
                ans = t;
            else
                ans = min(ans, t);
        }
        printf("%d\n", ans);
    }
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{
	ll N;
	cin >> N;
	vec b(N);
	REP(i, N) {
		cin >> b[i];
		b[i]--;
	}

	vec ans(N, -1);

	IREP(i, N) {
		IREP(j, i + 1) {
			if (b[j] == j) {
				// debug(j);
				b.erase(b.begin() + j);
				ans[i] = j;
				break;
			}
		}
		if (ans[i] == -1) {
			cout << -1 << endl;
			return 0;
		}
	}

	REP(i, N) {
		ans[i]++;
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

const ll mod = 1e9 + 7;


int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
   // cin >> T;
    T = 1;
    for(int cs = 1; cs <= T; cs++)
    {
        ll a,b;
        cin >> a >> b;
        if(a % 4 == 2)  a = 1;
        else if(a % 4 == 0) a = 0;
        else if(a % 4 == 1) a = a - 1;
        if(b % 4 == 1)  b = 1;
        else if(b % 4 == 2) b = b + 1;
        else if(b % 4 == 3) b = 0;
        cout << (a ^ b) << endl;
    }

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int N; scanf("%d",&N);
  int A[200010];
  for(int i = 2;i <= N;i++){
    scanf("%d",&A[i]);
  }

  int count[200010];
  for(int i = 1;i <= N;i++){
    count[i] = 0;
  }
  for(int i = 2;i <= N;i++){
    count[A[i]] += 1;
  }
  for(int i = 1;i <= N;i++){
    printf("%d\n",count[i]);
  }
  return 0;
}


Measured memory_bytes: 3268
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

int INF = INT_MAX / 2;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	vector<vector<bool> > b(32, vector<bool>(32));
	for (int x = 0; x < 32; x++)
		for (int y = 0; y < 32; y++) {
			int z = x & y;
			b[x][y] = (z&-z)==z;
		}
	set<ll> st;
	st.insert(0);
	for (int x = 0; x < 32; x++) {
		if ((x&-x)==x) continue;
		set<ll> _st = st;
		for (ll S: st) {
			int y;
			for (y = 0; y < 32; y++)
				if ((S>>y & 1) && !b[x][y])
					break;
			if (y == 32) _st.insert(S | 1LL<<x);
		}
		st = _st;
	}
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ma = 0;
	for (ll S: st) {
		vector<int> c(n);
		int sum = 0;
		for (int x = 0; x < 1<<n; x++)
			if (S>>x & 1) {
				int cnt = 0;
				for (int i = 0; i < n; i++)
					if (x>>i & 1) {
						c[i]++;
						cnt++;
					}
				sum += cnt - 1;
			}
		bool ok = true;
		for (int i = 0; i < n; i++)
			if (c[i] > a[i])
				ok = false;
		if (!ok) continue;
		ma = max(ma, sum);
	}
	ll ans = -ma;
	for (int i = 0; i < n; i++)
		ans += a[i];
	cout << ans << endl;
}

Measured memory_bytes: 3364
n, y = map(int,input().split())
 
for i in range(0,n+1):
  for j in range(0, n-i+1):
    if y == 10000*i + 5000*j + 1000*(n-i-j):
      print("{0} {1} {2}".format(i, j, n-i-j))
      exit()
print("-1 -1 -1")


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char name[4];
    int i=0,l=0;
    fgets(name,4,stdin);
    if(strcmp(name,"SUN")==0){
        printf("7");
    }    else if(strcmp(name,"SAT")==0){
        printf("1");
    }    else if(strcmp(name,"MON")==0){
        printf("6");
    }    else if(strcmp(name,"TUE")==0){
        printf("5");
    }    else if(strcmp(name,"WED")==0){
        printf("4");
    }   else if(strcmp(name,"THU")==0){
        printf("3");
    }   else if(strcmp(name,"FRI")==0){
        printf("2");
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    int ans = 0;
    if (b > a + w) ans = b - (a + w);
    if (b + w < a) ans = a - (b + w);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define For(i,x,y) for(int i=((int)x);i<=((int)y);i++)
#define Dep(i,y,x) for(int i=((int)y);i>=((int)x);i--)
#define Rep(i,x) for (int y,i=head[x];i;i=E[i].nxt)
using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;

int rd() {
	char c=getchar(); int t=0,f=1;
	while (!isdigit(c)) f=(c=='-')?-1:1,c=getchar();
	while (isdigit(c)) t=t*10+c-48,c=getchar(); return t*f;
}
void wt(int x) {
	if (x<0) putchar('-'),wt(-x);
	else { if (x>9) wt(x/10); putchar(x%10+48); }
}

const int N=100035;

int n,a[N],ans,lst,op;

int main() {
	n=rd(),lst=rd(),ans=1;
	For (i,2,n) {
		a[i]=rd();
		
		if (!op) {
			if (a[i]>lst) op=1;
			else if (a[i]<lst) op=-1;
		}
		else if ((op==1 && a[i]<lst) || (op==-1 && a[i]>lst))
			ans++,op=0;

		lst=a[i];
	}
	printf("%d\n",ans);
	return 0;
}






Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define repd(i,a,b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long int ll;
typedef complex<double> com;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 4e18;



int main() {
	int n, m; cin >> n >> m;
	vector<int> x(n), y(m);
	rep(i, 0, n) cin >> x[i];
	rep(i, 0, m) cin >> y[i];
	ll xsum = 0,ysum=0;
	rep(i, 0, n) {
		xsum = (xsum+1LL*(2LL*i+1-n) * x[i])%mod;
	}
	rep(i, 0, m) {
		ysum = (ysum + 1LL*(2LL * i + 1 - m) * y[i]) % mod;
	}
	printf("%d", (xsum* ysum*1LL) % mod);
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



int main(){

    int x;
    cin >> x;
    int n = x/100;
    x %= 100;

    if(n*5 >= x)P(1);
    else P(0);
    
    return  0;
}


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

// chmax, chmin
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;
}

template <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };

using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T &data, vector<int> &iter)
{
  cout << data << " ";
}
template <typename T>
void dump(const vector<T> &data, vector<int> &iter)
{
  for (auto elem : data)
    dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>> &data, vector<int> &iter)
{
  for (auto elem : iter)
  {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++)
  {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T> &data, int dummy)
{
  for (int i = 0; i < data.size(); i++)
  {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T &data)
{ // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////

const string YES = "Yes";
const string NO = "No";

// up, down, l or r
vector<int> parse(string s)
{
  int cur = 0;
  int minim = 0;
  for (auto c : s)
  {
    if (c == '(')
      cur++;
    else
      cur--;
    chmin(minim, cur);
  }
  if (cur > 0)
  {
    return vector<int>({cur, minim, true});
  }
  return vector<int>({-cur, min(minim - cur, 0), false});
}

bool can_construct(vector<PII> input)
{

  priority_queue<PII> ord;
  for (auto elem : input)
  {
    ord.push(PII(elem.second, elem.first));
  }

  LL cur = 0;
  while (!ord.empty())
  {
    auto val = ord.top();

    if (cur + val.first < 0)
      return false;
    ord.pop();
    cur += val.second;
  }
  return true;
}

bool solve(long long N, std::vector<std::string> S)
{

  vector<PII> left, right;

  LL parity = 0;
  for (auto s : S)
  {
    auto ret = parse(s);
    if (ret[2])
      left.emplace_back(ret[0], ret[1]);
    else
      right.emplace_back(ret[0], ret[1]);
    if (ret[2])
      parity += ret[0];
    else
      parity -= ret[0];
  }
  if (parity != 0)
    return false;

  return can_construct(left) && can_construct(right);
}

int main()
{
  cout << setprecision(10);
  long long N;
  scanf("%lld", &N);
  std::vector<std::string> S(N);
  for (int i = 0; i < N; i++)
  {
    std::cin >> S[i];
  }
  if (solve(N, std::move(S)))
    cout << YES << endl;
  else
    cout << NO << endl;
  return 0;
}


Measured memory_bytes: 81688
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for _ in range(m)]
ans = 0

for i in range(m):
    route = [[] for _ in range(n)]
    for j in range(m):
        if j != i:
            a, b = list_AB[j][0], list_AB[j][1]
            route[a-1].append(b-1)
            route[b-1].append(a-1)

    q = [0]
    l = {0}

    while q:
        x = q.pop(0)
        for p in route[x]:
            if p not in l:
                l.add(p)
                q.append(p)

    if len(list(l)) != n:
        ans += 1

print(ans)

Measured memory_bytes: 9244
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    string s, t;
    int Q;
    cin >> s >> Q;
    int cnt = 0;
    while(Q--) {
        int q;
        cin >> q;
        if(q == 1) {
            cnt++;
        } else {
            int f;
            char c;
            cin >> f >> c;
            f += cnt;
            f %= 2;
            if(f == 1)
                t.push_back(c);
            else
                s.push_back(c);
        }
    }
    if(cnt % 2 == 1) {
        reverse(ALL(s));
        cout << s << t << endl;
    } else {
        reverse(ALL(t));
        cout << t << s << endl;
    }

    return 0;
}

Measured memory_bytes: 980
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int  INF=10e7;

typedef  pair<int,int> P;


int main(){
     int n,k;
     cin>>n>>k;
     int ans=k*(pow(k-1,n-1));
     cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include   <cstring>
#include    <cstdio>
#include    <vector>
using namespace std;

const int MAXN = 300000+9;
int n,A,B;
bool jud;
int ans[MAXN];int top;

void solve(){
	if((n+A-1)/A>B || A+B>n+1){
		puts("-1");
		return;
	}
	if(A==1){
		for(int i=n;i>=1;i--)
			printf("%d ",i);
		return;
	}
	int len=(n-B)/(A-1);
	int r=(n-B)%(A-1);
	reverse(ans+1,ans+B+1);
	int start=B+1;
	for(int i=2;i<=A;i++){
		if(r){
			reverse(ans+start,ans+len+start+1);
			r--;
			start+=len+1;
		}
		else{
			reverse(ans+start,ans+start+len);
			start+=len;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	puts("");
}

int main(){
	scanf("%d%d%d",&n,&A,&B);
	for(int i=1;i<=n;i++)
		ans[i]=i;
	solve();
	return 0;
}

Measured memory_bytes: 3328
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int x = in.nextInt();

		int[] l = new int[n];
		for ( int i = 0; i < n; i++ ) {
			l[i] = in.nextInt();
		}

		int cnt = 1;
		int sum = 0;
		for ( int i = 0; i < n; i++ ) {			
			sum += l[i];
			if ( x < sum ) break;			
			cnt++;
		}

		System.out.println(cnt);
		in.close();
	}
}

Measured memory_bytes: 21844
N = int(input())
S = input()
abc = S.count('R')*S.count('G')*S.count('B')
L = (N-1)//2
for i in range(1,L+1):
  for j in range(N-2*i):
    if S[j]!=S[j+i] and S[j+i]!=S[j+2*i] and S[j]!=S[j+2*i]:
      abc -= 1
print(abc)

Measured memory_bytes: 9132
# Simultaneous Equation

import sys

datas = []

for line in sys.stdin:
	datas.append(map(float, line.split()))

for data in datas:
	a, b, c, d, e, f = data
	y = (c * d - a * f) / (b * d - a * e)
	x = (c - b * y) / a
	print "{0:.3f} {1:.3f}".format(x, y)

Measured memory_bytes: 4232
n,c=map(int,input().split())
chan=[[] for _ in range(c)]
for _ in range(n):
    s,t,sc=map(int,input().split())
    sc-=1
    chan[sc].append((s,t))
for i in range(c):
    chan[i].sort()
#print(chan)
for i in range(c):
    lis=[]
    if len(chan[i])==1:
        lis.append(chan[i][0][0])
        lis.append(chan[i][0][1])
    elif len(chan[i])>=2:
        lis.append(chan[i][0][0])
        for j in range(len(chan[i])-1):
            if chan[i][j][1]!=chan[i][j+1][0]:
                lis.append(chan[i][j][1])
                lis.append(chan[i][j+1][0])
        lis.append(chan[i][j+1][1])
    chan[i]=lis
#print(chan)
accum=[0]*(10**5+2)
for i in range(c):
    for j in range(0,len(chan[i])-1,2):
        accum[chan[i][j]]+=1
        accum[chan[i][j+1]+1]-=1
for i in range(10**5+1):
    accum[i+1]+=accum[i]
#print(accum)
print(max(accum))

Measured memory_bytes: 24712
N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


uf = UnionFind(N)
edge_cnt = 0
MST_cost = 0
i = 0

while edge_cnt < N-1:
    a, b, cost = E[i]
    if not uf.same_check(a, b):
        MST_cost += cost
        uf.union(a, b)
        edge_cnt += 1
    i += 1

print(MST_cost)

Measured memory_bytes: 90192
n = int(raw_input())
a = [int(x) for x in raw_input().split()]

mi = []
l = 0
m = 0

for i in xrange(n):
    if a[i] > m:
        mi.append([i, a[i] - m, a[i], 1, m])
        l += 1
        m = a[i]
    else:
        jl = 0
        ju = l
        while jl < ju:
            mid = (jl + ju) / 2
            if mi[mid][2] < a[i]:
                jl = mid + 1
            else:
                ju = mid
        j = jl
        mi[j][3] += 1
        mi[j][1] += a[i] - mi[j][4]

s = 0
for i in xrange(l - 1, 0, -1):
    s += mi[i][3]
    mi[i - 1][1] += (mi[i - 1][2] - mi[i - 1][4]) * s

j = 0
for i in xrange(n):
    if j >= l:
        print 0
        continue
    ii, d, ai, ni, mim = mi[j]
    if ii == i:
        print d
        j += 1
    else:
        print 0


Measured memory_bytes: 23704
import sys
import itertools
import math
input = sys.stdin.readline


def primes(x):
    if x < 2:
        return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2*p, x, p):
            primes[non_prime] = 0
    return [p for p in primes if p != 0]


def main():
    p = primes(55555)
    ans = []
    for q in p:
        if (q % 5) == 1:
            ans.append(q)
    N = int(input())
    print(*ans[0:N])


if __name__ == '__main__':
    main()


Measured memory_bytes: 5296
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 10 ** 6 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 10 ** 6:
        cnt[i * k] = 0
        k += 1

print(answer)

Measured memory_bytes: 106260
N=int(input())
count_4=0
count_2=0
a_list=list(map(int, input().split()))
for i in range(N):
    if a_list[i]%4==0:
        count_4=count_4+1
    elif a_list[i]%2==0:
        count_2=count_2+1

need_count=N//2

if need_count<=count_4+count_2//2:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 62576
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2

    for k in range(N):
        v = c[A[k]]
        diff = -v*(v-1)//2 + (v-1)*(v-2)//2
        print(ans + diff)


if __name__ == '__main__':
    main()


Measured memory_bytes: 101020
#include<iostream>
#include <bits/stdc++.h>
#include <string>
#include <algorithm>

using namespace std;
int main()
{
  int n;
  cin >> n ;
  int p[n];
  for(int i=0;i<n;i++) cin >> p[i] ;
  
  int ans = 0;
  for(int i=0;i<(n-2);i++){
    if(((p[i+1]>p[i+2])&&(p[i+1]>p[i]))||((p[i+1]<p[i+2])&&(p[i+1]<p[i])))
      continue;
    else
      ans++;
  }
   cout << ans << endl;
  
}


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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define PB push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second

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


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

    ll d,t,s;
    cin>>d>>t>>s;
    if(t*s>=d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}



Measured memory_bytes: 3636
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int nr;
int dfs(vvi &gg,int index,vi &used,int rc,int goal){
	used[index]=1;
	if(index==goal){
		return rc;
	}
	REP(i,nr){
		if(gg[index][i]&&!used[i]){
			if(dfs(gg,i,used,gg[index][i]==2?rc:1-rc,goal)){
				return true;
			}
		}
	}
	return false;
}
int main(){
	int n;
	while(cin>>n,n){
		set<string> roads;
		vector<pair<string,string> > pairs;
		vs vroads;
		REP(i,n){
			string s;
			cin>>s;
			int cur=0;
			string ls;
			string rs;
			REP(i,s.size()){
				if(s[i]=='-'){
					cur++;
				}else if(cur==0){
					ls+=s[i];
				}else{
					rs+=s[i];
				}
			}
			roads.insert(ls);
			roads.insert(rs);
			pairs.push_back(make_pair(ls,rs));
		}
		for(set<string>::iterator it=roads.begin();it!=roads.end();it++){
			vroads.push_back(*it);
		}
		nr=vroads.size();
		vvi g(nr,vi(nr));
		REP(i,pairs.size()){
			int li=find(ALL(vroads),pairs[i].first)-vroads.begin();
			int ri=find(ALL(vroads),pairs[i].second)-vroads.begin();
			g[li][ri]=1;
		}

		vvi gg(g);
		REP(i,nr){
			REP(j,nr){
				bool flag=true;
				bool found=false;
				REP(k,nr){
					if((g[i][k]==1&&g[j][k]==1)||(g[k][i]==1&&g[k][j]==1)){
						found=true;
						break;
					}
				}
				if(!found){
					flag=false;
				}
				found=false;
				REP(k,nr){
					if((g[i][k]==1&&g[k][j]==1)||(g[j][k]==1&&g[k][i]==1)){
						found=true;
						break;
					}
				}
				if(found){
					flag=false;
				}
				if(flag){
					gg[i][j]=2;
					gg[j][i]=2;
				}
			}
		}
	
		cout<<nr<<endl;
		int m;
		cin>>m;
		REP(i,m){
			string s;
			cin>>s;
			int cur=0;
			string ls;
			string rs;
			REP(i,s.size()){
				if(s[i]=='-'){
					cur++;
				}else if(cur==0){
					ls+=s[i];
				}else{
					rs+=s[i];
				}
			}
			string ans;
			int li=find(ALL(vroads),ls)-vroads.begin();
			int ri=find(ALL(vroads),rs)-vroads.begin();
			if(li==vroads.size()||ri==vroads.size()){
				ans="NO";
			}else{
				vi used(nr);
				ans=(dfs(gg,li,used,0,ri)?"YES":"NO");
			}
			cout<<ans<<endl;
		}
	}
}

Measured memory_bytes: 1700
#include <stdio.h>
#include <math.h>

int main (void)
{
    int d, n;

    scanf("%d %d", &d, &n);
    if (n != 100) {
        printf("%d\n", (int)pow((double)100, (double)d) * n);
    } else {
        printf("%d\n", (int)pow((double)100, (double)d) * n + (int)pow((double)100, (double)d));
    }
    
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N= scanner.nextInt();
        int W = scanner.nextInt();
        long[] dp = new long[W+1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for(int i = 0; i < N; i++) {
            int w = scanner.nextInt();
            long v = scanner.nextInt();
            for(int j = W-w; j>=0;j--) {
                if (dp[j]!=-1) dp[j+w] = Math.max(dp[j+w], dp[j] + v);
            }
        }
        long ans = 0;
        for(int i = 0; i <= W; i++) {
            ans = Math.max(dp[i], ans);
        }
        out.println(ans);
        out.flush();
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}


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

const int N = 1e5 + 100, M = 16;

int n, ans, a[N], cnt[M], dp[1 << M];

bool ok(int mask) {
	int res = 0;
	for (int i = 0; i < M; i++)
		if (mask & (1 << i))
			res ^= i;
	return res == 0;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		a[u] ^= w;
		a[v] ^= w;
	}
	for (int i = 0; i < n; i++)
		cnt[a[i]]++;
	for (int i = 1; i < M; i++) {
		ans += (cnt[i] >> 1);
		cnt[i] &= 1;
	}
	int mask = 0;
	for (int i = 1; i < M; i++)
		if (cnt[i])
			mask |= 1 << i;
	ans += __builtin_popcount(mask);
	for (int x = 1; x <= mask; x++) {
		dp[x] = ok(x);
		if ((mask & x) == x)
			for (int y = x; y; y = (--y & x))
				if (y < x && ok(y))
					dp[x] = max(dp[x], dp[y] + dp[x ^ y]);
	}
	ans -= dp[mask];
	cout << ans;
}


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

int n,m;
int a[1001],b[1001],c[1001];
int d[101][101];

int main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)d[i][j]=0;
            else d[i][j]=1e9;
        }
    }
    for(int i=0;i<m;i++){
        d[a[i]][b[i]]=c[i];
        d[b[i]][a[i]]=c[i];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
            }
        }
    }
    int ans=m;
    for(int i=0;i<m;i++){
        bool ok=false;
        for(int j=0;j<n;j++){
            if(d[j][a[i]]+c[i]==d[j][b[i]])ok=true;
        }
        if(ok)ans--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  for ( ; ; )
  {
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    while ( n-- )
    {
      int pm, pe, pj;

      scanf ( "%d%d%d", &pm, &pe, &pj );
      if ( pm == 100 || pe == 100 || pj == 100 )  puts ( "A" );
      else if ( pm + pe >= 180 )                  puts ( "A" );
      else if ( pm + pe + pj >= 240 )             puts ( "A" );
      else if ( pm + pe + pj >= 210 )             puts ( "B" );
      else if ( ( pm + pe + pj >= 150 )
             && ( pm >= 80 || pe >= 80 ) )        puts ( "B" );
      else                                        puts ( "C" );
    }
  }

  return ( 0 );
}

Measured memory_bytes: 0
def main():
    n = int(input())
    v = list(map(int, input().split()))

    ans = 0
    odic = {"0": 0}
    edic = {"0": 0}

    for i in range(int(n/2)):
        if str(v[i*2]) in odic:
            odic[str(v[i*2])] = odic[str(v[i*2])] + 1
        else:
            odic[str(v[i*2])] = 1
        if str(v[i*2 + 1]) in edic:
            edic[str(v[i*2 + 1])] = edic[str(v[i*2 + 1])] + 1
        else:
            edic[str(v[i*2 + 1])] = 1
    
    ols = sorted(odic.values(), reverse=True)
    els = sorted(edic.values(), reverse=True)


    if max(odic, key=odic.get) != max(edic, key=edic.get):
        ans = n - ols[0] - els[0]
    else:
        if ols[0]+els[1] < ols[1]+els[0]:
            ans = n - ols[1] - els[0]
        else:
            ans = n - ols[0] - els[1]

    print(ans)    

if __name__ == "__main__":
    main()


Measured memory_bytes: 20668
import math

n, d = map(int, input().split())
pos = []
dd = float()

for i in range(n):
    x, y = map(int, input().split())
    xy = list()
    xy.append(x)
    xy.append(y)

    dd = math.sqrt(x*x+y*y)

    if dd <= float(d):
        pos.append(xy)

print(len(pos))


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define log_2(a) (log((a)) / log(2))
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 105;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}
int graph[SIZE][SIZE];
void WarshallFloyd(int N) {
    for( int k = 0; k < N; ++k ) {
        for( int i = 0; i < N; ++i ) {
            for( int j = 0; j < N; ++j ) {
                if( graph[i][k] == INF || graph[k][j] == INF ) {
                    continue;

                }
                graph[i][j] = min( graph[i][j], 
                                    graph[i][k] + graph[k][j] );

            }
        }
    }
    return;

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

    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        for(int j = i + 1; j < N; ++j) {
            graph[i][j] = graph[j][i] = INF;
        }
    }

    vector<pair<P, int>> e(M);
    for(int i = 0; i < M; ++i) {
        cin >> e[i].F.F >> e[i].F.S >> e[i].S;
        --e[i].F.F;
        --e[i].F.S;
        graph[e[i].F.F][e[i].F.S] = e[i].S;
        graph[e[i].F.S][e[i].F.F] = e[i].S;
    }

    WarshallFloyd(N);
    int res = 0;
    for(pair<P, int> edge : e) {
        if(graph[edge.F.F][edge.F.S] != edge.S) {
            ++res;
        }
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3700