akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int main(void)
{
	int n;
	int i,len;
	int a,b;
	char w[100][12];
	scanf("%d", &n);
	
	for(i=0;i<n;i++){
		scanf("%s" ,&w[i]);
	}
	for(a=0;a<n;a++){
		for(b=a+1;b<n;b++){
			if(strcmp(w[a],w[b]) == 0){
				printf("No");
				return 0;
			}
		}
	}
	
	for(i=0;i<n-1;i++){
		len = strlen(w[i]) - 1;
		if(w[i][len] != w[i+1][0]){
			printf("No");
			return 0;
			
		}
	}
	printf("Yes");
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
 
int linear_search(int s[], int n,  int key) {
  int i = 0;
  s[n] = key;
  while(s[i] != key)
    i++;
  return i != n;
}
 
int main(void) {
  int n ,q;
  int s[10001];
  int t[500];
  int i;
  int count = 0;
   
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &s[i]);
  scanf("%d", &q);
  for (i = 0; i < q; i++)
    scanf("%d", &t[i]);
 
  for (i = 0; i < q; i++) {
    count += linear_search(s, n, t[i]);
  }
 
  printf("%d\n", count);
   
  return 0;
}


Measured memory_bytes: 2100
// Created by sz
#include <bits/stdc++.h>
using namespace std;

const int maxn = 405;
const long long INF = 1e18;
int N, a[maxn];
long long  s[maxn],dp[maxn][maxn];

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    

    cin>>N;
    for(int i = 0; i<N; i++){
        cin>>a[i];
        if(i==0)s[i] = a[i];
        else s[i] = s[i-1]+a[i];
        
        fill(dp[i], dp[i]+N, INF);
        dp[i][i] = 0;
    }
    
    
    
    for(int l = 2; l<= N; l++){
        for(int i = 0, j = l-1; j < N; i++,j++){
            for(int k = i; k <j; k++){
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
            }
            dp[i][j] += s[j] - (i>0?s[i-1]:0);
        }
    }
    cout<<dp[0][N-1]<<endl;


    
    return 0;
}



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

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int64_t msb(int64_t v){
  v = v | (v >>  1);
  v = v | (v >>  2);
  v = v | (v >>  4);
  v = v | (v >>  8);
  v = v | (v >> 16);
  v = v | (v >> 32);
  return v ^ (v >> 1);
}

int main(){
    int N;
    cin >> N;
    vector<int64_t> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    int64_t ans1 = 0;
    for(int d=0; d<60; d++){
        int num = 0;
        for(int64_t a : A) num += nth_bit(a, d);
        if(num%2){
            ans1 += 1LL<<d;
            for(int64_t& a : A) if(nth_bit(a, d)) a -= 1LL<<d;
        }
    }

    vector<int64_t> V;
    for(int64_t a : A){
        for(int64_t v : V) if(msb(v)&a) a ^= v;
        if(a > 0){
            V.push_back(a);
            sort(V.rbegin(), V.rend());
        }
    }

    int64_t ans2 = 0;
    for(int64_t v : V) if((msb(v)&ans2) == 0) ans2 ^= v;
    int64_t ans = ans1 + 2*ans2;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int main(void){
  string a;
  cin >> a;
  for(int i=0;i < a.size();i++){
    if(a[i] == 'A'){
      printf("X");
    }
    if(a[i] == 'B'){
      printf("Y");
    }
    if(a[i] == 'C'){
      printf("Z");
    }else{
    if(a[i] == 'A' || a[i] == 'B' || a[i] == 'C'){
      continue;
    }else{
    printf("%c",a[i]-3);
    }
   }
  }cout << endl;
}

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

void trace(int A[], int N){
    int i;
    for (i=0; i<N; i++){
        if (i>0) cout << " ";
        cout << A[i];
    }
    cout << "\n";
}

void insertionSort(int A[], int N){
    int j, i, v;
    for (i=1; i<N; i++){
        v = A[i];
        j = i - 1;
        while (j>=0 && A[j]>v){
            A[j + 1] = A[j];
            j--;
        } 
        A[j + 1] = v;
        trace(A, N);
    }
}

int main(){
    int N, i, j;
    int A[100];

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

    trace(A, N);
    insertionSort(A, N);

    return 0;
}


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

#define repo(i,n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
ll saiki(ll x){
    if(x == 1){
        return 1;
    }
    
    return saiki(x/2)*2 + 1;
}

int main(){
    ll H;
    cin >> H;

   cout << saiki(H) << endl; 

    return 0;
}


Measured memory_bytes: 256
n, k, q = map(int, input().split())

#正解者順リスト
al = [int(input()) for i in range(q)]

#このリストのindex+1が参加者ナンバーです
#みんなの持ち点
nl = []
for m in range(n):
    nl.append(k-q)

for y in al:
    nl[y-1] = nl[y-1]+1

for z in nl:
    if z > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 11776
#include<stdio.h>
int main(void)
{
	int w,h,n;
	int i,j;
	int cnt=0;
	int sx,sy,x,y;
	
	scanf("%d %d %d",&w,&h,&n);
	scanf("%d %d",&sx,&sy);
	for(i=0;i<n-1;i++){
		scanf("%d %d",&x,&y);
		if(sx==x){
			if(sy<y){
				cnt+=y-sy;
			}
			else if(y<sy){
				cnt+=sy-y;
			}
		}
		else if(sy==y){
			if(sx<x){
				cnt+=x-sx;
			}
			else if(x<sx){
				cnt+=sx-x;
			}
		}
		else if(x>sx){
			if(y>sy){
				if(x-sx<y-sy){
					cnt+=y-sy;
				}
				else{
					cnt+=x-sx;
				}
			}
			else if(y<sy){
				cnt+=x-sx+sy-y;
			}
		}
		else if(x<sx){
			if(y<sy){
				if(sx-x<sy-y){
					cnt+=sy-y;
				}
				else {
					cnt+=sx-x;
				}
			}
			else if(y>sy){
				cnt+=sx-x+y-sy;
			}
		}
		sx=x;
		sy=y;
	}
	printf("%d\n",cnt);
	return 0;
}

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

int N, M, p[100001];
string S[100001];

void input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> p[i] >> S[i];
    }
}

int main()
{
    input();

    vector<int> wa(N);
    set<int> ac;
    fill(wa.begin(), wa.end(), 0);
    int wa_count = 0;

    for (int i = 0; i < M; i++) {
        if (S[i] == "WA") {
            wa[p[i]] = wa[p[i]] + 1;
        } else if ((!ac.count(p[i])) && S[i] == "AC") {
            wa_count += wa[p[i]];
            ac.insert(p[i]);
        }
    }

    cout << ac.size() << " " << wa_count << "\n";

    return 0;
}


Measured memory_bytes: 11136
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

ll mod(ll a,ll b){
	if(b==0){
		return 1;
	}
	if(b%2){
		return (a*mod(a,b-1))%atcoder_mod;
	}
	return mod((a*a)%atcoder_mod,b/2);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	auto M=in(),N=in();
	auto A=mod(M,N);
	
	out(A);
	return 0;
}


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

bool judge(long long int x,int n){
  if((n-x)%(2*x+1)==0){return true;}
  return false;
}



int main(){
  int count=0;
  int m;
  cin>>m;
  for(int t=0;t<m;t++){


    
  int n;
  cin>>n;
  if(n==0){break;}
  bool j=true;
  for(int x=1;x*x<=n;x++){
    if(judge(x,n)){j=false; break;}
  }
  if(j){count++;}



  }


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


Measured memory_bytes: 3076
#include <iostream>

using namespace std;

int main() {
  int H, W;

  for ( ; ; ) {
    cin >> H >> W;
    if ((H == 0) && (W == 0)) break;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        cout << '#';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
} 



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

int main(){
  string str;
  int q;
  cin >> str;
  cin >> q;
  
  for(int i=0;i<q;i++)
  {
    string s;
    cin >> s;
    if(s == "print"){
      int a, b;
      cin >> a >> b;
      cout << str.substr( a, b - a + 1) << endl;
    } else if(s == "reverse"){
      int a, b;
      cin >> a >> b;
      reverse( str.begin() + a, str.begin() + b + 1);
    } else {
      int a, b;
      string p;
      cin >> a >> b >> p;
      str.replace( a, b - a + 1, p);
    }
  }
}


Measured memory_bytes: 3216
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
for i in range(n-1):
    if a[i] + 1 == a[i + 1]:
        ans += c[a[i] - 1]
print(ans)

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

using namespace std;

typedef vector<int> V;

int main() {
	int n, a, c = 0;
	cin >> n;
	V v(n);
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (i < --a) {
			v[i] = a;
			continue;
		}
		c += v[a] == i;
	}
	cout << c << endl;
}

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

const ll MAX = 1e5 * 2 + 1;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM2(ll n, ll k){
  ll ret = 1;
  for(ll i=1;i<=k;i++){
    ret = ret * (n-i+1) % MOD;
  }
  ret = ret * finv[k] % MOD;

  return ret;
}

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main(void){
  ll n, a, b;
  cin >> n >> a >> b;

  COMinit();

  ll ans = modpow(2,n,MOD) - 1;
  ans = ans - COM2(n,a) - COM2(n,b);
  ans %= MOD;
  if(ans<0)ans += MOD;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
int a[105];
int main(){
	int n;
	scanf("%d", &n);
	int sum = 0;
	int mn = 1e9;
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		sum += a[i];
		if(a[i]%10 != 0) mn = min(mn, a[i]);
	}
	if(sum%10 == 0){
		if(mn == 1e9) printf("0\n");
		else printf("%d\n", sum-mn);
	}
	else printf("%d\n", sum);
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val b = readLine()!!.split(" ").map(String::toInt)

    var sum = 0

    if (n == 2) {
        println(b[0] * 2)
        return
    }

    b.forEachIndexed { i, v ->
        if (i == 0) {
            sum += v
        } else {
            sum += Math.min(b[i - 1], v)
        }
    }

    sum += b[n - 2]
    println(sum)
}

Measured memory_bytes: 37820
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=~-i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Measured memory_bytes: 31908
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll ans = 1;
	for(int i = 1; i <= n; i++)
	{
		ans = (ans * i) % MOD;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a//gcd(a,b)*b
a,b,c,d=[int(i) for i in input().split()]
bac=(b//c)-((a-1)//c)
bad=(b//d)-((a-1)//d)
bacd=(b//lcm(c,d))-((a-1)//lcm(c,d))
print(b+1-a-bac-bad+bacd)

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

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long int
#define ff first
#define ss second
#define S size()
#define mod (ll)(1e9+7)
#define mset(a,k) memset(a,k,sizeof(a));
#define fr(i, x, y) for ( ll i = x; i < y;i++)
#define dr(i, x, y) for ( ll i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define pqueue priority_queue<ll>
#define mapcl map<char,ll>
#define mapll map<ll,ll>
#define mapsl map<string,ll>
#define vi vector<ll>
#define vs vector<string>
#define psi pair<string,ll>
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define vii vector<pii>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
//----------------------------------------FUNCTIONS---------------------------------------------------
ll gcd(ll x, ll y )						{if (y == 0) return x; return gcd(y, x % y);}
ll lcm(ll a, ll b)						{return (a * b) / gcd(a, b);}
ll logx(ll base, ll num)				{int cnt = 0; while (num != 1) {num /= base; ++cnt;} return cnt;}
vi vin(ll n)							{vi a(n); fr(i, 0, n) cin >> a[i]; return a;}
void vout(vi a)							{for (int i = 0; i < (ll)a.S; i++) { cout << a[i] << " "; } cout << endl;}
void in(ll *a, ll n)        			{for (ll i = 0; i < n; i++)cin >> a[i];}
void in1(ll *a, ll n)        			{for (ll i = 1; i <= n; i++)cin >> a[i];}
void out1(ll *a, ll n)					{fr(i, 1, n + 1) {cout << a[i] << " ";} cout << '\n';}
void out(ll *a, ll n)					{fr(i, 0, n) {cout << a[i] << " ";} cout << endl;}
//----------------------------------------START--------------------------------------------------------

bool isprime(ll n)
{
	// Corner cases
	if (n <= 1)  return false;
	if (n <= 3)  return true;

	// This is checked so that we can skip
	// middle five numbers in below loop
	if (n % 2 == 0 || n % 3 == 0) return false;

	for (ll i = 5; i * i <= n; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return false;

	return true;
}
const ll maxN = (ll)(1 * 1e5 + 5 );
int main()
{
#ifndef ONLINE_JUDGE
	freopen ("inp4.txt", "r", stdin);
	freopen ("out4.txt", "w", stdout);
#endif
	fast();
	ll t = 1;
	//cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		ll a[n + 1] = {0};
		fr(i, 1, 101)
		{
			fr(j, 1, 101)
			{
				fr(k, 1, 101)
				{
					ll k1 = i * i + j * j + k * k + i * j + j * k + k * i;
					if (k1 > n)continue;
					a[k1]++;
				}
			}
		}
		fr(i, 1, n + 1)cout << a[i] << '\n';
	}

}


Measured memory_bytes: 3700
#C
import math
n = int(input())
coordinate = []
for _ in range(n):
    x,y = map(int,input().split())
    coordinate.append([x,y])
dist = 0
def culc_dist(x1,y1,x2,y2):
    return (math.sqrt((x1-x2)**2 + (y1-y2)**2))
    
for i in range(n):
    for j in range(n):
        if i != j:
            dist += culc_dist(coordinate[i][0],coordinate[i][1],coordinate[j][0],coordinate[j][1])
dist /= n

print(dist)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};


int main(){
    CIN(N);
    I vec;
    REP(a,N*3){
        CIN(n);
        vec.pb(n);
    }
    sort(ALL(vec));
    reverse(ALL(vec));
    LL ans = 0;
    REP(a,2*N){
        if(a%2==1){
            ans+=vec.at(a);
        }
    }
    COUT(ans);
    rt 0;
}


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

const ll mod = 1e9 + 7;

ll modpow(ll n, ll k) {
    if (k == 0) return 1;
    if (k == 1) return n;

    if (k % 2 == 0) {
        ll root = modpow(n, k / 2);
        return root * root % mod;
    } else {
        return n * modpow(n, k - 1) % mod;
    }
}

ll comb(ll n, ll k) {
    ll mul = 1;
    ll div = 1;

    for (ll i = 0; i < k; i++) {
        mul *= n - i;
        mul %= mod;

        div *= i + 1;
        div %= mod;
    }

    ll ans = mul * modpow(div, mod - 2) % mod;
    return ans;
}

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

    ll ans = modpow(2, n) - 1;
    ans -= comb(n, a);
    if (ans < 0) ans += mod;
    ans -= comb(n, b);

    if (ans < 0) ans += mod;

    cout << ans << endl;
}

Measured memory_bytes: 256
/*
Original problem: https://atcoder.jp/contests/dp/tasks/dp_v
Author: sammochen
*/

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;

#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)

#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef vector<ll> VLL;
typedef vector<int> VI;

ll mod;

namespace SOLVE {
	ll mult(ll a, ll b) {
		return (a * b) % mod;
	}

	vector<VI> E; // E[a] contains all neighbours of a
	vector<VI> pre; // pre[a][i] is mult product of all up to ith a-neighbour - excl. parent
	vector<VI> suf; // suf[a][i] same, but from ith a-neighbour onwards - excl. parent

	VI p; // p[i]: parent of i when tree is rooted at 1

	// these two VI supports O(1) products
	VI subtree; // subtree[i]: how many ways the subtree can be black given that i is black
	VI supertree; // supertree[i]: for supertree, given that i is black.
	int root = 1;
	
	// subtree
	void subdfs(int a, int prev) {
		subtree[a] = 1;
		p[a] = prev;

		for (int b: E[a]) {
			if (b != prev) {
				subdfs(b, a);
				subtree[a] = mult(subtree[a], (1 + subtree[b]));
			}
		}
		
		// works out pre and sub
		pre[a] = E[a];
		suf[a] = E[a];

		REP(i, 0, E[a].size()) {
			if (E[a][i] != prev) {
				pre[a][i] = subtree[E[a][i]] + 1;
				suf[a][i] = subtree[E[a][i]] + 1;
			} else {
				// excludes parent! important
				pre[a][i] = 1;
				suf[a][i] = 1;
			}
		}

		for (int i = 1; i < E[a].size(); i++) {
			pre[a][i] = mult(pre[a][i], pre[a][i - 1]);
		}

		for (int i = E[a].size() - 2; i >= 0; i--) {
			suf[a][i] = mult(suf[a][i], suf[a][i + 1]);
		}

	}

	// supertree
	void superdfs(int a, int prev, int index) { 
		// supertree[i] = supertree[p[i]] * product(p[i]'s other children's subtrees)
		if (prev == -1) {
			supertree[a] = 1;
		} else {
			supertree[a] = supertree[prev];
			if (index != 0) {
				supertree[a] = mult(supertree[a], pre[prev][index - 1]);
			}
			if (index != E[prev].size() - 1) {
				supertree[a] = mult(supertree[a], suf[prev][index + 1]);
			}
			supertree[a]++;
		}

		for (int i = 0; i < E[a].size(); i++) {
			int b = E[a][i];
			if (b != prev) {
				superdfs(b, a, i);
			}
		}
	}

	void main() {
		int n, a, b;
		cin >> n >> mod;

		E.resize(n + 1);
		p.resize(n + 1);
		pre.resize(n + 1);
		suf.resize(n + 1);
		subtree.resize(n + 1);
		supertree.resize(n + 1);
		
		REP(i, 0, n - 1) {
			cin >> a >> b;
			E[a].push_back(b);
			E[b].push_back(a);
		}

		// work out subtree
		subdfs(root, -1);
		// work out supertree
		superdfs(root, -1, -1);
		
		REP(i, 1, n + 1) {
			int ans = mult(subtree[i], supertree[i]); // ans is all combinations of sub and super
			cout << ans << endl;
		}
	}
}


signed main() {
	int t;
	t = 1;
	// cin >> t;
	while (t--) {
		SOLVE::main();
	}

	return 0;
}

Measured memory_bytes: 24192
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
K = int(input())
Xs = list(mapint())

ans = 0
for x in Xs:
    ans += min(abs(x), abs(x-K))*2
print(ans)

Measured memory_bytes: 61932
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define faxd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define f0xd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;
const ld PI = 4*atan((ld)1);

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
	ll a,b; cin >> a >> b;
	cout << max(a+b, max(a-b, a*b));
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll n = 1;
    while (n * 2 <= N)
        n *= 2;
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int inf=INT_MAX;
int main(){
	int n,l;
	vector<int>mp;
	cin>>n>>l;
	int mx=0;
	for (int x=1;x<=n;x++){
		int c=l+x-1;
		mx+=c;
		mp.push_back(c);
	}
	int cmax=inf;
	int final=0;
	for (int x=0;x<n;x++){
		int c=abs(mx-(mx-mp[x]));
		if (c<cmax){
			final=mx-mp[x];
			cmax=c;
		}
	}
	cout<<final<<endl;
} 

Measured memory_bytes: 256
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);
		
		int K = sc.nextInt();
		int X = sc.nextInt();
		
		int start = X - (K - 1);
		int end = X + (K - 1);
		
		for(int i = start; i <= end; i++) {
			System.out.print(i + " ");
		}

	}	
}

Measured memory_bytes: 21716
n = int(input())
*A1, = map(int, input().split())
*A2, = map(int, input().split())
C1 = 0; C2 = sum(A2)
ans = 0
for i in range(n):
    C1 += A1[i]
    ans = max(ans, C1+C2)
    C2 -= A2[i]
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 1e5 + 5;

int n;
int a[N];

int32_t main()
{
	IOS;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int cur = 1e9;
	for(int i = n; i >= 1; i--)
	{
		int x = a[i];
		if(x > cur + 1)
		{
			cout << "No";
			return 0;
		}
		else
			cur = min(cur, x);
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std; // 575

int main() {
	int N, K;
	cin >> N >> K;
	cout << (N + 1 >> 1 >= K ? "YES" : "NO");
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

1, 3, ...
*/

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

// using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

bool IsKai(string s) {
  REP(i,s.size()) {
    if(s[i] != s[s.size()-1-i]) return false;
  }
  return true;
}
/***** MAIN *****/
signed main() {
  string s;
  cin >> s;
  int n = s.size();
  bool flag1 = IsKai(s);
  int half = n/2;
  bool flag2 = IsKai(s.substr(0,half));
  bool flag3 = IsKai(s.substr(n-half, n));
  if(flag1 && flag2 && flag3) {
    cout << "Yes";
  } else {
    cout << "No";
  }
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;


	void doIt() {
		int n = sc.nextInt();
		int even = n / 2;
		System.out.println((n - even) / (double)n);
	}

	public static void main(String[] args) {
		new Main().doIt();
	}
}


Measured memory_bytes: 22228
import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        wf.path(i,j,A[i][j])

wf.build()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i][j] > wf.d[i][j]:
            print(-1)
            exit(0)
        flag = 1
        for k in range(n):
            if i != k != j:
                if wf.d[i][j] == wf.d[i][k] + wf.d[k][j]:
                    flag = 0
                    break
        if flag:
            ans += A[i][j]
print(ans)


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

void out(vector<int> a,int n){
    rep(j,n){
        cout << a[j];
        if(j!=n-1) cout << " ";
    }
    cout << endl;
}

void insertionSort(vector<int> a,int n){
    out(a,n); 
    for(int i=1;i<n;i++){
        int v = a[i];
        int j = i-1;
        while(j>=0 && a[j]>v){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = v;
        out(a,n);
    }
}


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    insertionSort(a,n);
    return 0;
}


Measured memory_bytes: 3084
S = input()

First = S[0:2]
Last  = S[2:4]



First = int(First)
Last = int(Last)

YYMM = False
MMYY = False

if(First>0 and First<13):
	MMYY = True

if(Last>0 and Last<13):
	YYMM = True
	
if(YYMM and MMYY):
	print("AMBIGUOUS")
elif(YYMM):
	print("YYMM")
elif(MMYY):
	print("MMYY")
else:
	print("NA")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
using ll = long long int;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;

	ll ten, nine, eight;
	ten = nine = eight = 1;

	for (int i = 0; i < n; i++) {
		ten = ten * 10 % MOD;
		nine = nine * 9 % MOD;
		eight = eight * 8 % MOD;
	}
	ll res = ((ten + eight) % MOD - 2 * nine % MOD);
	cout << (res < 0 ? res + MOD : res) % MOD << '\n';

	return 0;
}


Measured memory_bytes: 3640
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    ST = S_LIST()
    A, B = MAP()
    U = INPUT()

    if ST[0] == U: A -= 1
    else: B -= 1

    print(A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4212
#include<stdio.h>
int main(){
  int n,i,b[4]={0};
  char t[3];
  while(scanf("%d,%s",&n,t)!=EOF){
    if(t[0]=='A'){
      if(t[1]=='B')   b[2]++;
      else   	      b[0]++;
    }
    else if(t[0]=='B')b[1]++;
    else              b[3]++;
  }
  for(i=0;i<4;i++)printf("%d\n",b[i]);
  return 0;
}
	

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

int main(){

const int MAX_NO=100000;
int m[MAX_NO],f[MAX_NO],r[MAX_NO];
char hyouka[MAX_NO];
int a=0;
int b=0;

for(int i=1;i<MAX_NO;i++){

cin>>m[i]>>f[i]>>r[i];

a++;

for(int j=1;j<20000000;j++){
b++;
b--;
b++;
b--;
}

if(m[i]==-1 && f[i]==-1 && r[i]==-1){
goto aa;
}

if(m[i]==-1 || f[i]==-1){
hyouka[i]='F';
}

else if((m[i]+f[i])>=80){
hyouka[i]='A';
}
else if((m[i]+f[i])>=65){
hyouka[i]='B';
}

else if((m[i]+f[i])>=50){
hyouka[i]='C';
}

else if((m[i]+f[i])>=30 && r[i]<50){
hyouka[i]='D';
}
else if((m[i]+f[i])>=30 && r[i]>=50){
hyouka[i]='C';
}

else if((m[i]+f[i])<30){
hyouka[i]='F';
}

}

aa:;

for(int i=1;i<a;i++){

cout<<hyouka[i]<<endl;

}

return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    if (S.size() < 26) {
        vector<bool> used(26);
        for (char &c : S) {
            used[c - 'a'] = true;
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            if (!used[c - 'a']) {
                S.push_back(c);
                break;
            }
        }
        cout << S << endl;
    } else {
        if (S == "zyxwvutsrqponmlkjihgfedcba") {
            puts("-1");
            return 0;
        }
        
        int N = S.size();
        string T = S;
        set<char> st;
        repr(i, N) {
            st.insert(S[i]);
            T.pop_back();
            for (auto &c : st) {
                string res = T + c;
                if (S < res) {
                    cout << res << endl;
                    return 0;
                }
            }
        }
    }
}

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

using namespace std;

const int MOD = 1e9 + 7;

inline void add (int& a, const int b) { a = (a + b) % MOD; }

int main () {
  int n, m;
  cin >> n >> m;
  vector <string> grid(n);
  for (int i = 0; i < n; i++) cin >> grid[i];
  vector <vector <int>> dp(n, vector <int> (m, 0));
  dp[0][0] = 1;
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < m; c++) {
      if (grid[r][c] == '#') continue;
      if (1 <= c) add(dp[r][c], dp[r][c - 1]);
      if (1 <= r) add(dp[r][c], dp[r - 1][c]);
    }
  }
  cout << dp[n - 1][m - 1] << endl;
  return (0);
}


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

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

    int k , x;
    cin >> k >> x ;

    if(k * 500 >= x) cout << "Yes" << endl ;
    else cout << "No" << endl ;


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	char a;
	char b;
	cin>>a;
	cin>>b;
	if(a=='H'&&b=='H')
	cout<<"H";
	else if(a=='D'&&b=='H')
	cout<<"D";
	else if (a=='D'&&b=='D')
	cout<<"H";
	else if(a=='H'&&b=='D')
	cout<<"D";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{
  public static void main(String args[])
  {
    Scanner sc = new Scanner(System.in);
	int a,b;
    a = sc.nextInt();
    b = sc.nextInt();
 	if(b%a==0)
      System.out.println(a+b);
    else
      System.out.println(b-a);
  }
}


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

const int N = 110000;

int a[N], b[N], X[N];
int ida[N], idb[N];

int root[N];
int find_root(int u) {
	if (u == root[u]) return root[u];
	return root[u] = find_root(root[u]);
}

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
		
	int n; cin >> 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++) ida[i] = i;
	sort(ida, ida + n, [&](int u, int v) {
		return a[u] < a[v];
	});
	for (int i = 0; i < n; i++) idb[i] = i;
	sort(idb, idb + n, [&](int u, int v) {
		return b[u] < b[v];
	});
	
	for (int i = 0; i < n; i++) if (a[ida[i]] > b[idb[i]]) {
		cout << "No\n";
		return 0;
	}
	
	for (int i = 1; i < n; i++) if (a[ida[i]] == a[ida[i - 1]]) {
		cout << "Yes\n";
		return 0;
	}
	for (int i = 0; i < n; i++) X[i] = b[i];
	sort(X, X + n);
	for (int i = 0; i < n; i++) if (n - i != n - (lower_bound(X, X + n, a[ida[i]]) - X)) {
		cout << "Yes\n";
		return 0;
	}
	
	for (int i = 0; i < n; i++) root[i] = i;
	for (int i = 0; i < n; i++) {
		int aa = find_root(ida[i]), bb = find_root(idb[i]);
		if (aa == bb) continue;
		root[aa] = bb;
	}
	
	int cnt = 0;
	for (int i = 0; i < n; i++) cnt += i == root[i];
	if (cnt > 1) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}


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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n;
vll a;
lli ans = LONG_MAX;

int main(){
  cin >> n;
  a = vll(n+2);
  for(lli i = 1;i <= n;i++) cin >> a[i];
  for(lli i = 1;i <= n;i++) a[i] += a[i-1];
  lli r = 1;
  lli l = 3;
  for(lli i = 2;i <= n-2;i++){
    while(abs(a[r]-(a[i]-a[r])) > abs(a[r+1]-(a[i]-a[r+1]))) r++;
    while(abs((a[l]-a[i])-(a[n]-a[l])) > abs((a[l+1]-a[i])-(a[n]-a[l+1]))) l++;
    ans = min(ans, max({a[r], a[i]-a[r], a[l]-a[i], a[n]-a[l]})-min({a[r], a[i]-a[r], a[l]-a[i], a[n]-a[l]}));
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
K, A, B = map(int, input().split())
if B <= A + 2:
    res = K+1
else:
    # はじめA-1回ビスケットを叩く
    K = K - (A-1)
    res = A
    if K%2 == 0:
        res += (K//2) * (B-A)
    else:
        res += ((K-1)//2) * (B-A) + 1
print(res)

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

long long GCD(long long n, long long m) {
    return m ? GCD(m, n % m) : n;
}

int main() {
    long long n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    
    long long g = GCD(n, m);
    long long res = n / g * m;
    n /= g, m /= g;
    bool ok = true;
    for (long long i = 0; i < g; ++i) {
        if (s[i*n] != t[i*m]) ok = false;
    }
    if (ok) cout << res << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int n, m, x, y;
    scanf("%d %d %d %d", &n, &m, &x, &y);
    int xx, yy;
    int maxx = -2000000000, miny = 2000000000;
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &xx);
        if (xx > maxx)
            maxx = xx;
    }
    for (i = 0; i < m; i++)
    {
        scanf("%d", &yy);
        if (yy < miny)
            miny = yy;
    }
    if (maxx<y  && miny>x && maxx < miny)
        printf("No War\n");
    else
        printf("War\n");
    return 0;
}

Measured memory_bytes: 128
// ABC148A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

//#include "pch.h"
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int A, B;
	cin >> A >> B;
	vector<int>ans = { 0,1,2,3 };
	vector<int>check = { 0,0,0,0 };
	check.at(A) = 1;
	check.at(B) = 1;
	for (int  i = 1; i <=3; i++)
	{
		if (check.at(i)==0)
		{
			cout << i << endl;
			break;
		}
	}
}


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

int main() {
  int64_t N,A,B;
  cin >> N >> A >> B;
  const int64_t diff= B-A;

  int64_t ans= (diff%2==0) ? diff/2
                           : diff/2+ min(A-1, N-B)+ 1;

  cout << ans << endl;
}

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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

int main() {
    string s; cin >> s;
    int N = s.length();
    for (int l = 0; l <= N; l++)
        for (int r = l; r <= N; r++) {
            string t = s.substr(0, l) + s.substr(r);
            if (t == "keyence") {
                cout << "YES" << endl;
                return 0;
            }
        }
    cout << "NO" << endl;
}


Measured memory_bytes: 256
// Anve$hi $hukla
#include <bits/stdc++.h>
using namespace std;
struct ${$(){ios_base::sync_with_stdio(false);cin.tie(NULL);}}$;

typedef long long LL;
const int Maxn = 200005;

int main() {
   int k, t;
   cin >> k >> t;
   vector <int> a(t);

   for(int i = 0; i < t; i++) {
      cin >> a[i];
   }
   int x = *max_element(a.begin(), a.end());
   cout << max(0, x - 1 - (k - x)) << endl;

   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<char> cvec;
typedef vector<double> dvec;
typedef pair<ll, ll> LP;
typedef tuple<ll, ll, ll> LT;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
#define fs first
#define sc second
int main()	{
  int ans=0;
  int n;
  cin>>n;
  for(int i=1;i<=n;){
    int cnt=0;
    rep(j,i){
      if(i%j==0)
        cnt++;
    }
    if(cnt==8)
      ans++;
    i+=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3580
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n;
	int c[555]={},s[555]={},f[555]={},t[555]={};
	cin>>n;
	FOR(i,0,n-1){
		cin>>c[i]>>s[i]>>f[i];
	}
	FOR(i,0,n-1){
		int tt=0,tmp;
		FOR(j,i,n-1){
			tmp=max(tt,s[j]);
			tmp+=(f[j]-tmp%f[j])%f[j];
			tmp+=c[j];
			tt=tmp;
		}
		t[i]=tt;
	}
	FOR(i,0,n){
		cout<<t[i]<<endl;
	}
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int[]a =  new int[2];
	while(true){
	a[0] = sc.nextInt();
	a[1] = sc.nextInt();
	if(a[0]==0&&a[1]==0) break;
	Arrays.sort (a);
	System.out.println(a[0]+" "+a[1]);	
	}
}
}

Measured memory_bytes: 27108
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(void){
    int x,a;
    cin >> x >> a;

    if(x>=a){
        cout << 10 << endl;
    }else{
        cout << 0 << endl;
    }
    
    return 0;
}

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

using namespace std;

int n, m, a, b;

int main() {
	scanf("%d%d%d%d", &n, &m, &a, &b);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d", (i < b) ^ (j < a));
		puts("");
	}
}


Measured memory_bytes: 1280
import math

def colon():
    input_value = [int(i) for i in input().split()]
    hour_hand = input_value[0]
    minute_hand = input_value[1]

    hour = input_value[2]
    minute = input_value[3]

    degree = (((hour * 60 + minute) * 360)/720) - ((minute * 360)/60)
    cos = math.cos(math.radians(degree))

    answer = math.sqrt((hour_hand ** 2) + (minute_hand ** 2) - (2 * hour_hand * minute_hand * cos))
    print(answer)

colon()

Measured memory_bytes: 9408
#include<stdio.h>
int main(void){
int W,H,x,y,r;
scanf("%d %d %d %d %d", &W,&H,&x,&y,&r);
if(x - r< 0 || W < x + r || y - r < 0 || H < y + r){
printf("No\n");
}
else{
printf("Yes\n");
}
return 0;
}


Measured memory_bytes: 2104
import java.util.*;

//https://beta.atcoder.jp/contests/abc104/submissions/2961424
//http://betrue12.hateblo.jp/entry/2018/08/05/230358

class Main{
	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		char[]v=s.next().toCharArray();
		int n=v.length,m=1000000007;
		long a=0,ab=0,abc=0,comb=1;
		for(int i=0;i<n;i++){
			if(v[i]=='C') abc+=ab;
			if(v[i]=='B') ab+=a;
			if(v[i]=='A') a+=comb;
			if(v[i]=='?'){
				abc=3*abc+ab;
				ab=3*ab+a;
				a=3*a+comb;
				comb=3*comb;
			}
			a%=m;
			ab%=m;
			abc%=m;
			comb%=m;
//			System.err.println(comb+" "+a+" "+ab+" "+abc);
		}
		System.out.println(abc);
	}
}


Measured memory_bytes: 27476
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int dp[55][55][3000];//dp[i][j][k]:左右1~iまで見て待機がjペア、確定してる交点の個数がk(これから真っ先にj潰して残りは平行でペア作って奇妙さがk)
//main
signed main(){
  int N,K;cin>>N>>K;
  memset(dp,0,sizeof(dp));
  dp[0][0][0]++;
  for(int i=0;i<N;i++){
    for(int j=0;j<=i;j++){
      for(int k=0;k<2500;k++){
        dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k];//二つとも保留
        dp[i+1][j][k+2*j]+=dp[i][j][k]*2*j;//片方保留
        dp[i+1][j-1][k+2*(j-1)]+=dp[i][j][k]*j*j;//両方使う
        dp[i+1][j][k+2*j]+=dp[i][j][k];//その場でペアに

        dp[i+1][j+1][k+2*(j+1)]%=MOD;
        dp[i+1][j][k+2*j]%=MOD;
        dp[i+1][j-1][k]%=MOD;
        dp[i+1][j][k+2*(j-1)]%=MOD;
      }
    }
  }
  cout<<dp[N][0][K]<<endl;
}


Measured memory_bytes: 71168
using static System.Math;
using static System.Console;
class Z
{
	const int INF = 1000000007;
	static void Main() => WriteLine(F(ReadLine()));
	static int F(string S)
	{
		var N = S.Length;
		var bit = new int[N + 1];
		for (var i = 0; i < N; i++) bit[i + 1] = bit[i] ^ (1 << (S[i] - 'a'));
		var s = 0;
		for (var i = 0; i < 26; i++) if ((bit[N] & (1 << i)) != 0) s++;
		if (s <= 1) return 1;
		var dp = new int[N + 1];
		var tb = new int[1 << 26];
		for (var i = 1; i <= N; i++) dp[i] = INF;
		for (var i = 1; i < (1 << 26); i++) tb[i] = INF;
		for (var i = 1; i <= N; i++)
		{
			for (var j = 0; j < 26; j++) dp[i] = Min(dp[i], tb[bit[i] ^ (1 << j)] + 1);
			tb[bit[i]] = Min(tb[bit[i]], dp[i]);
		}
		return dp[N];
	}
}


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

using namespace std ; 

typedef long long ll ; 

int main()
{
    int a, b ; 
    scanf("%d%d", &a, &b) ; 
    if(a <= 0 && 0 <= b)
        return 0*puts("Zero") ; 
    if(0 < a)
        return 0*puts("Positive") ; 
    if(b < 0)
        return 0*puts(1-(b-a)%2 ? "Negative" : "Positive") ; 
    return 0 ; 
}


Measured memory_bytes: 128
use std::io;
use std::io::BufRead;

fn main() {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();

    let n = {
        let mut input = String::new();
        stdin.read_line(&mut input).unwrap();
        let mut input = input.trim().split_whitespace();
        input.next().unwrap().parse::<usize>().unwrap()
    };

    let mut vec = {
        let mut vec: Vec<(String,i32,usize)> = Vec::new();
        for i in 0..n {
            let mut input = String::new();
            stdin.read_line(&mut input).unwrap();
            let mut input = input.trim().split_whitespace();
            
            vec.push((
                input.next().unwrap().to_string(),
                input.next().unwrap().parse::<i32>().unwrap(),
                i+1
            ));
        }
        vec
    };

    vec.sort_by(|a, b| {
        if a.0 == b.0 { b.1.cmp(&a.1) } else { a.0.cmp(&b.0) }
    });

    for x in vec.iter() {
        println!("{}", x.2);
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;

using ll = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;

auto R(int s, int n) {
    return boost::irange(s, n);
}
auto R(int n) {
    return boost::irange(0, n);
}
void show(const auto& v){
    for(auto i:v) cout << i << " ";
    cout << endl;
}

int main() {
    int h,w,n;
    cin>>h>>w>>n;
    VI out{};
    for(ll i:R(n)){
        int j;
        cin>>j;
        for(ll k:R(j)){
            out.push_back(i+1);
        }
    }
    for(ll i:R(h)){
        for(ll j:R(w)){
            if(i%2==0){
                cout<<out.at(i*w+j);
            }else{
                cout<<out.at((i+1)*w-1-j);
            }
            if(j!=w-1) cout<<" ";
            else cout<<endl;
        }
    }
    return 0;
}


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


using namespace std;

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


ll h, w, n, ans[10];
set<pair<ll, ll>> se;
int main() {
	cin >> h >> w >> n;
	ans[0] = (h - 2) * (w - 2);
	REP(l, n) {
		ll a, b;
		cin >> a >> b;
		FOR(i,a - 2,a + 1) {
			FOR(j, b - 2, b + 1) {
				if (i > 0 and j > 0 and i + 2 <= h and j + 2 <= w) {
					ll count = 0;
					FOR(x, i, i + 3) {
						FOR(y, j, j + 3) {
							if (se.find(make_pair(x, y)) != se.end()) count++;
						}
					}
					ans[count]--;
					ans[count + 1]++;
				}
			}
		}
		se.insert(make_pair(a,b));
	}
	REP(i, 10)cout << ans[i] << endl;
}



Measured memory_bytes: 6528
#include <stdio.h>

volatile int stop[40];

int check(int a,int b){
	int i=a*1000+b;
	int j;
	for (j=0;j<40;j++){
		if (i==stop[j]){
			return 1;
		}
	}
	return 0;
}

int saiki(int a,int b){
	if(check(a,b)==1){
		return 0;
	}
	
	if (a==1&&b==1){
		return 1;
	}else if (a==1){
		return saiki(a,b-1);
	}else if(b==1){
		return saiki(a-1,b);
	}else{
		return saiki(a-1,b)+saiki(a,b-1);
	}
}


int main(void){
	for (;;){
		int a,b;
		scanf("%d %d",&a,&b);
		if (a==0&&b==0){
			return 0;
		}
		
		int i;
		for (i=0;i<40;i++){
			stop[i]=0;
		}
		
		int m;
		scanf("%d",&m);
		int s,j,k;
		for (s=0;s<m;s++){
			scanf("%d %d",&j,&k);
			stop[s]=j*1000+k;
		}
		
		printf("%d\n",saiki(a,b));
	}
}

Measured memory_bytes: 600