akhauriyash/Code-Regression huggingface dataset:
// file creato da gio il 2020-09-14 17:13:19.374937

#include <bits/stdc++.h>

#ifdef FAST
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define MOD 1000000007
#define S second
#define F first
#define PB push_back
#define ll long long 

using namespace std;

#define MN 500001
#define LSB(n) n&-n

ll ftree[MN];
int n;


void update(int p,int v){
    while(p<=n){
        ftree[p]+=v;
        p+=LSB(p); 
    }
}

ll sum(int p){
    ll s=0;
    while(p>0){
        s+=ftree[p];
        p-=LSB(p);
    }
    return s;
}

ll sum(int a,int b){return sum(max(a,b))-sum(min(a,b));}

int main(){
    //freopen("output","w",stdout);
    //freopen("input","r",stdin);
#ifdef FAST
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    int q;
    cin >> n>>q;
    for(int i=0;i<n;i++){
        int t;
        cin >>t;
        update(i+1,t);
    }
    for(int i=0;i<q;i++){
        int a,b,c;
        cin >>a>>b>>c;
        if(a)
            cout <<sum(b,c)<<endl;
        else
            update(b+1,c);

    }

}


Measured memory_bytes: 8212
#line 1 "example/example.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B"
#line 1 "macro/macros.hpp"



/*
@title Macro
@category template
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;

template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;

const double PI = acos(-1.0);

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";


#line 3 "example/example.test.cpp"
/*
@title example(二分探索)
@category example
@brief test用。
*/
int main() {
    int n; cin >> n;
    vector<int> s(n);
    for(int i = 0; i < n;++i){
        cin >> s[i];
    }
    int q; cin >> q;
    int cnt = 0;
    while (q --) {
        int t_i; cin >> t_i;
        cnt += binary_search(s.begin(), s.end(), t_i);
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3420
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

ll choose2(ll n){
    return n*(n-1)/2;
}

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

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

int ans=0;
bool ABC(char X,char Y,char Z){
  return X=='A'&&Y=='B'&&Z=='C'?1:0;
}

int main(){
  int N;string str;cin>>N>>str;
  for(int i=0;i<str.size()-2;i++){
    if(ABC(str.at(i),str.at(i+1),str.at(i+2))){
      ans++;
    }
  }
  cout << ans <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int l, r; cin >> l >> r;
	long long int ans = 2019;
	if(r-l>=2019){
		cout << 0 << endl;
		return 0;
	}else{
		for(long long int i=l;i<=r;i++){
			for(long long int j=i+1;j<=r;j++){
				ans = min(ans, (i*j)%2019);
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
    int N;
    string s[110];

    cin>>N;
    for(int i=1; i<=N;i++){
        cin>>s[i];
        if(i!=1&&s[i][0]!=s[i-1][s[i-1].length()-1]) return puts("No"), 0;
        
        for(int j=1;j<i;j++){
            if(s[i]==s[j]) return puts("No"),0;
        }

    }
    return puts("Yes"),0;
}

Measured memory_bytes: 256
import sys
from math import factorial

MOD = 10 ** 9 + 7


def main():
    # input = sys.stdin.buffer.readline
    n, a, b = map(int, input().split())
    comb_a = 1
    for i in range(a):
        comb_a *= n - i
        comb_a %= MOD
    comb_b = comb_a
    for i in range(a, b):
        comb_b *= n - i
        comb_b %= MOD
    invfact_b = pow(factorial(b), MOD - 2, MOD)
    invfact_a = invfact_b
    for i in range(b, a, -1):
        invfact_a *= i
        invfact_a %= MOD
    comb_a *= invfact_a
    comb_a %= MOD
    comb_b *= invfact_b
    comb_b %= MOD
    print((pow(2, n, MOD) - 1 - comb_a - comb_b) % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 11096
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
    int A, B;
    cin >> A >> B;
    
    if (A >= 13)
        cout << B << endl;
    else if (A >= 6)
        cout << B / 2 << endl;
    else
        cout << 0 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#ifdef DEBUG_MODE
#define DBG(n) n;
#else
#define DBG(n) ;
#endif

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()

typedef long long ll;
typedef pair<ll,ll> P;
#define NODE 100001
#define INF 1000000000
#define LLINF 1000000000000000000LL

//v[i][j]; j番目の辺。iからfirstへの有向辺で、コストはsecond。
vector<vector<pair<ll,ll> > > v(NODE);
ll dist[NODE];
int dijkstra(int start){
  //初期化
  for(int i = 0;i < NODE;i++)dist[i] = LLINF;
  dist[start] = 0;
  //priority_queueの宣言
  //pqに入れているのは(startからtoへの最短距離, to)
  //priority_queueの都合上、vのpairの順番とは逆にしている。
  priority_queue<P,vector<P>,greater<P> > pq;
  pq.push(make_pair(0,start));
  while(!pq.empty()){
    //現在見る者の中で、最もdistが小さいものを取り出す
    P now = pq.top();pq.pop();
    ll d = now.first;
    ll node = now.second;
    //すでに更新されていたりして、現在のが最適でなかったらスルー
    if(dist[node] < d)continue;
    //その点と辺を持つものに対して
    for(int i = 0;i < v[node].size();i++){
      ll opp_n = v[node][i].first;
      ll opp_d = v[node][i].second;
      //もし、distが更新できるならば、更新してpriority_queueに突っ込む
      if(dist[opp_n] > d + opp_d){
        dist[opp_n] = d + opp_d;
        pq.push(make_pair(dist[opp_n],opp_n));
      }
    }
  }
}

int main(){
  int N; cin >> N;
  REP(i, N - 1) {
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    v[a].PB(MP(b,c));
    v[b].PB(MP(a,c));
  }
  int Q, K;
  cin >> Q >> K;
  dijkstra(K - 1);

  REP(i, Q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    cout << (dist[x] + dist[y]) << endl;
  }

  return 0;
}



Measured memory_bytes: 11120
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    set<int> st;
    for(int i = 0; i < q; i++)
    {
        int com, x;
        cin >> com >> x;
        if(com == 0) 
        {
            st.insert(x);
            cout << st.size() << endl;
        }
        else if(com == 1)
        {
            auto itr = st.find(x);
            cout << (itr != st.end() ? 1 : 0) << endl;
        }
    }
    return 0;
}




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

int x[200][200];
int y[200][200];
int n, m, a, b, X, Y;
int dx[6] = { 0,1,1,0,-1,-1 };
int dy[6] = { 1,1,0,-1,-1,0 };

int main() {
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) { break; }
		for (int i = 0; i < 200; i++) {
			for (int j = 0; j < 200; j++) {
				x[i][j] = 0;
				y[i][j] = 1145141919;
			}
		}
		for (int i = 0; i < m; i++) {
			cin >> a >> b;
			x[a + 100][b + 100] = 1;
		}
		cin >> X >> Y;
		y[X + 100][Y + 100] = 0;
		for (int i = 0; i < 50; i++) {
			for (int j = 1; j < 199; j++) {
				for (int k = 1; k < 199; k++) {
					if (y[j][k] < 1145141919) {
						for (int l = 0; l < 6; l++) {
							if (x[dx[l] + j][dy[l] + k] == 0) {
								y[dx[l] + j][dy[l] + k] = min(y[dx[l] + j][dy[l] + k], y[j][k] + 1);
							}
						}
					}
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < 200; i++) {
			for (int j = 0; j < 200; j++) {
				if (y[i][j] <= n) {
					sum++;
				}
			}
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 3332
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var sol = new Solve();
        sol.Exec();
    }
}

class Solve
{
    public void Exec()
    {
        var s = Console.ReadLine().ToCharArray();
        var n = int.Parse(Console.ReadLine());
        
        for (var i = 0; i < s.Length; i++) {
            var diff = (('z'+1)-s[i]);
            //Console.WriteLine(diff);
            if (s[i] != 'a' && diff <= n) {
                n -= diff;
                s[i] = 'a';
            }
        }
        
        var last = s.Length-1;
        var cal = s[last] + n % 26;
        if (cal > 'z') cal -= 26;
        s[last] = (char)cal;
        
        Console.WriteLine(new string(s));
    }
}

public class Util
{
}


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

typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll ans = 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		if( i % 3 != 0 && i % 5 != 0 )
		{
			ans += i;
		}
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3652
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
main(){
	int a,b,c,n,x,y,z,w,i;
	for(;scanf("%d%d%d%d",&a,&b,&c,&n)>3;){
		vector<int>A(a,2);
		vector<int>B(b,2);
		vector<int>C(c,2);
		vector<tuple<int,int,int> >v;
		for(i=0;i<n;i++){
			scanf("%d%d%d%d",&x,&y,&z,&w);
			if(w)A[x-1]=B[y-1-a]=C[z-1-a-b]=1;
			else v.push_back(make_tuple(x-1,y-1-a,z-1-a-b));
		}
		for(i=0;i<v.size();i++){
			if(A[get<0>(v[i])]==1&&B[get<1>(v[i])]==1)C[get<2>(v[i])]=0;
			if(B[get<1>(v[i])]==1&&C[get<2>(v[i])]==1)A[get<0>(v[i])]=0;
			if(C[get<2>(v[i])]==1&&A[get<0>(v[i])]==1)B[get<1>(v[i])]=0;
		}
		for(i=0;i<A.size();i++)printf("%d\n",A[i]);
		for(i=0;i<B.size();i++)printf("%d\n",B[i]);
		for(i=0;i<C.size();i++)printf("%d\n",C[i]);
	}
}

Measured memory_bytes: 1040
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Traveling by Stagecoach
 */
public class Main {

	static final double INF = 4000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		StringTokenizer st;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			//
			int n, m, p, a, b;
			int[] T;
			double[][] G;
			double[][] D;    //[???????????????][?????£?????¬??????]
			boolean[][] V;   //?¨??????????????????????

			st = new StringTokenizer(line);
			n = parseInt(st.nextToken());
			m = parseInt(st.nextToken());
			p = parseInt(st.nextToken());
			a = parseInt(st.nextToken());
			b = parseInt(st.nextToken());
			if ((n | m | p | a | b) == 0) break;

			//
			st = new StringTokenizer(br.readLine());
			T = new int[n];
			for (int i = 0; i < n; i++) T[i] = parseInt(st.nextToken());

			//
			G = new double[m + 1][m + 1];
			for (int i = 0; i <= m; i++) Arrays.fill(G[i], -1);

			for (int i = 0; i < p; i++) {
				st = new StringTokenizer(br.readLine());
				int x, y, z;
				x = parseInt(st.nextToken());
				y = parseInt(st.nextToken());
				z = parseInt(st.nextToken());
				G[x][y] = G[y][x] = (double) z;
			}

			//
			D = new double[m + 1][1 << n];
			V = new boolean[m + 1][1 << n];

			for (int i = 0; i <= m; i++) Arrays.fill(D[i], INF);
			D[a][0] = 0;

			while (true) {

				double min = INF;
				int v = -1, t = -1;

				for (int i = 1; i <= m; i++) {
					for (int j = 0; j < (1 << n); j++) {
						if (!V[i][j] && D[i][j] < min) {
							min = D[i][j];
							v = i; t = j;
						}
					}
				}

				if (v == b || v == -1) break;
				V[v][t] = true;

				for (int u = 1; u <= m; u++) {
					if (G[v][u] != -1) {
						for (int i = 0; i < n; i++) {
							if ((t >> i & 1) == 0) {
								double time = D[v][t] + (G[v][u] / T[i]);
								if (D[u][t | 1 << i] > time) {
									D[u][t | 1 << i] = time;
								}
							}
						}
					}
				}
			}

			double ans = INF;

			for (int i = 0; i < (1 << n); i++) {
				ans = Math.min(ans, D[b][i]);
			}

			System.out.println(ans != INF ? ans : "Impossible");
		}
	}
}

Measured memory_bytes: 50420
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
b = [1 for i in range(n+1)]
for i in a:
  b[i] = 0
for i in range(2,n+1):
  cnt = b[i-1] + b[i-2]
  if b[i] != 0:
    b[i] = cnt
print(b[-1]%1000000007)

Measured memory_bytes: 460056
module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a in
  let acc = Array.make (n + 1) 0 in
  for i = 0 to n - 1 do
    acc.(i + 1) <- as_.(i) + acc.(i)
  done;
  let m =
    Array.fold_left (fun m a ->
      IntMap.add a (1 + try IntMap.find a m with Not_found -> 0) m) IntMap.empty acc in
  Printf.printf "%d\n" @@
  IntMap.fold (fun _ n -> ( + ) @@ n * (n - 1) / 2) m 0


Measured memory_bytes: 16672
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct node{
    int u,v,nxt;
}edge[N*2];
int head[N],mcnt;
void add_edge(int u,int v){
    mcnt++;
    edge[mcnt].u=u;
    edge[mcnt].v=v;
    edge[mcnt].nxt=head[u];
    head[u]=mcnt;
}
int c[N];
int vis[N],tot;
int n,m;
int deep[N];
int q[N],h,t;
int x[N],y[N],z[N];
int maxdeep[N];
void bfs(int s,int depth,int color){
    if(depth<=maxdeep[s])
        return ;
    vis[s]=tot;
    deep[s]=depth;
    maxdeep[s]=depth;
    h=t=1;
    q[1]=s;
    while(h<=t){
        int u=q[h++];
        if(!c[u])
            c[u]=color;
        if(deep[u]==0)
            continue ;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(vis[v]>tot&&maxdeep[v]<deep[u]-1){
                vis[v]=tot;
                deep[v]=deep[u]-1;
                maxdeep[v]=deep[u]-1;
                q[++t]=v;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    int qu;
    scanf("%d",&qu);
    for(int i=1;i<=qu;i++){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    for(int i=1;i<=n;i++)
        vis[i]=qu+1,maxdeep[i]=-1;
    for(tot=qu;tot>=1;tot--){
        bfs(x[tot],y[tot],z[tot]);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",c[i]);
}


Measured memory_bytes: 25472
#include<stdio.h>
#include<stdlib.h>
int main(){
  int i,j,n,k,a[100010],dp[100010];
  scanf("%d %d\n",&n,&k);
  for(i=1;i<=n;i++){
    scanf("%d\n",&a[i]);
  }
  for(i=0;i<=n;i++){
    dp[i]=1200000000;
  }
  dp[1]=0;
  for(i=1;i<=n;i++){
    for(j=i+1;j<=i+k && j<=n;j++){
      if(dp[j]>abs(a[j]-a[i])+dp[i]){
        dp[j]=abs(a[j]-a[i])+dp[i];
      }
    }
  }
  printf("%d\n",dp[n]);
  return 0;
}

Measured memory_bytes: 896
n = int(input())
lst = [list(input().split()) for i in range(n)]
for i in range(n):
    lst[i][0] = float(lst[i][0])

ans = 0
for i in range(n):
    if lst[i][1] == "JPY":
        ans += lst[i][0]
    else:
        ans += lst[i][0] * 380000
print(ans) 

Measured memory_bytes: 3064
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;

    auto ans = new int[][](H, W);
    int p = 0;

    foreach (i; 0..H) {
        foreach (jj; 0..W) {
            int j = jj;
            if (i % 2 == 1) j = W - jj - 1;
            if (A[p] == 0) p++;
            ans[i][j] = p + 1;
            A[p] -= 1;
        }
    }

    foreach (i; 0..H) ans[i].map!(a => a.to!string).join(" ").writeln;
}


Measured memory_bytes: 892
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}


fn main(){
    let line = read_as_vec::<i64>();
    let (n, k) = (line[0], line[1]);

    let mut ans = 0;
    for b in k+1..n+1{
        ans += n/b*(b-k);
        if n%b > 0 && n%b > k-1{
            ans += n%b - cmp::max((k-1), 0);
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void) {
  int N,A,B,C,D;
  scanf("%d %d %d %d %d", &N, &A, &B, &C, &D);

  int num_X = 0;
  int num_Y = 0;
  int num_stick_X = 0;
  int num_stick_Y = 0;
  int money_X,money_Y;

  while(num_stick_X < N){
    num_X = num_X + 1;
    money_X = num_X * B;
    num_stick_X = num_X * A;
  }

  while(num_stick_Y < N){
    num_Y = num_Y + 1;
    money_Y = num_Y * D;
    num_stick_Y = num_Y * C;
  }
  
  int result = money_X;
  if (money_Y < money_X) {
    result = money_Y;
  }

  printf("%d\n", result);
  return 0;
}



Measured memory_bytes: 1968
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);

int N, K;
vector<vector<int>>g;
vector<array<int, 2>>bound;
vector<int>ans;

array<int, 2>dfs1(int pos, int lb, int ub, int prevpos) {
	int nextlb, nextub;
	if (bound[pos][0] == -1) {
		nextlb = lb - 1;
		nextub = ub + 1;
	}
	else {
		int fixnum = bound[pos][0];
		if (fixnum < lb || ub < fixnum || (fixnum - lb) % 2 != 0) {
			return{ intmax,intmax };
		}
		lb = fixnum;
		ub = fixnum;
		nextlb = fixnum - 1;
		nextub = fixnum + 1;
	}

	for (auto x : g[pos])if (x != prevpos) {
		auto re = dfs1(x, nextlb, nextub, pos);
		if (re[0] == intmax)return{ intmax,intmax };
		lb = max(lb, re[0]);
		ub = min(ub, re[1]);
	}
	assert(lb <= ub);
	bound[pos] = { lb,ub };
	return{ lb - 1,ub + 1 };
}

void dfs2(int pos, int lb, int ub, int prevpos) {
	ans[pos] = max(lb, bound[pos][0]);
	for (auto x : g[pos])if (x != prevpos) {
		dfs2(x, ans[pos] - 1, ans[pos] + 1, pos);
	}
}


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

	cin >> N;
	g = vector<vector<int>>(N);
	rep(i, N - 1) {
		int A, B;
		cin >> A >> B;
		A--; B--;
		g[A].push_back(B);
		g[B].push_back(A);
	}
	cin >> K;
	bound = vector<array<int, 2>>(N);
	rep(i, N)bound[i] = { -1,-1 };
	int root = 0;
	rep(i, K) {
		int V, P;
		cin >> V >> P;
		V--;
		bound[V] = { P,P };
		root = V;
	}

	//木のうち高橋君が整数を書き込んだ頂点のどれかを根にしてdfsする。
	auto re = dfs1(root, bound[root][0], bound[root][1], -1);
	if (re[0] == intmax) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;

	ans = vector<int>(N);
	dfs2(root, bound[root][0], bound[root][1], -1);

	rep(i, N) {
		cout << ans[i] << endl;
	}/*

	 vector<int>num(N, -123456789);
	 stack<array<int,3>>dfs;
	 dfs.push({ root,bound[root][0],bound[root][1] });
	 while (!dfs.empty()) {
	 auto a = dfs.top(); dfs.pop();
	 int pos = a[0];
	 int lb = a[1] - 1;
	 int ub = a[2] + 1;
	 if (num[pos] != -123456789)continue;
	 num[pos] = lb;
	 for (auto x : g[pos]) {
	 dfs.push({ x,num[pos]-1,ub });
	 }
	 }*/


	return 0;
}

Measured memory_bytes: 18304
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

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

#define MOD 1000000007

int main(int argc, char **argv)
{
    string S;
    cin >> S;

    int N = S.length();
    ll dp[N + 1][13];

    REP(i, N + 1) REP(j, 13) dp[i][j] = 0;
    dp[0][0] = 1;

    REP(i, N) {
        int c;
        if (S[i] == '?') c = -1;
        else c = S[i] - '0';

        REP(j, 13) {
            if (c == -1) {
                REP(k, 10) {
                    dp[i + 1][((10 * j) + k) % 13] += dp[i][j];
                }
            }
            else {
                dp[i + 1][((10 * j) + c) % 13] += dp[i][j];
            }
        }
        REP(j, 13) dp[i + 1][j] = dp[i + 1][j] % MOD;
    }

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


    return 0;
}


Measured memory_bytes: 10624
#include <stdio.h>

int main(void){
	int a, b;
	int i;
	int output_num=0;
	
	scanf("%d %d", &a, &b);
	
	printf("%d ", a / b);
	printf("%d ", a % b);
	printf("%f\n", (double)a / (double)b);
	
	return 0;
}

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

int main()
{
    vector<int> x(5);
    rep(i, 5) cin >> x[i];
    rep(i, 5) {
        if(x[i] == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 3620
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
//#define int long long
#define double long double

int tree[4100005];
void update(int i,int l,int r,int l1,int r1,int val)
{
    if(l1>r1 || l>r1 || l1>r)
        return;
    if(l1<=l && r<=r1)
    {
        tree[i]=val;
        return;
    }
    int mid=(l+r)/2;
    update(i*2,l,mid,l1,r1,val);
    update(i*2+1,mid+1,r,l1,r1,val);
    tree[i]=max(tree[i*2],tree[i*2+1]);
}
int query(int i,int l,int r,int l1,int r1)
{
    if(l1>r1 || l>r1 || l1>r)
        return 0;
    if(l1<=l && r<=r1)
        return tree[i];
    int mid=(l+r)/2;
    return max(query(i*2,l,mid,l1,r1),query(i*2+1,mid+1,r,l1,r1));
}
int32_t main()
{
    IOS;
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        arr[i]+=k+5;
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int val=arr[i];
        int get=query(1,1,1000005,arr[i]-k,arr[i]+k);
        ans=max(ans,get+1);
        update(1,1,1000005,arr[i],arr[i],get+1);
    }
    cout<<ans;
}

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

class Main{
	  public static void main(String[] args) throws IOException{
		BufferedReader br =
				new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		int num = Integer.parseInt(str);
		String resultLine ="";
		
			
			String[] inputStr = br.readLine().split(" ");
			String[] inputNum = new String[num];
			
			for(int i=0; i<num; i++){
				inputNum[i] = (inputStr[(num-1)-i]);
			}

			for(int j=0; j<num; j++) {
				resultLine = resultLine +inputNum[j] + " ";
			}
			String new_str1 = resultLine.trim();
			System.out.println(new_str1);
	}	
}

Measured memory_bytes: 24252
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    static long[] distance;
    static ArrayList<TreeMap<Integer, Long>> edges;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        distance = new long[n];
        edges = new ArrayList<>();
        for (int i = 0 ; i < n ; i++) {
            edges.add(new TreeMap<Integer, Long>());
        }
        for (int i = 0 ; i < n - 1 ; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            long d = sc.nextLong();
            edges.get(a).put(b, d);
            edges.get(b).put(a, d);
        }
        int q = sc.nextInt();
        dfs(-1, sc.nextInt() - 1, 0);
        int[] l = new int[q];
        int[] r = new int[q];
        for (int i = 0 ; i < q ; i++) {
            l[i] = sc.nextInt() - 1;
            r[i] = sc.nextInt() - 1;
        }
        for (int i = 0 ; i < q ; i++) {
            System.out.println(distance[l[i]] + distance[r[i]]);
        }


    }

    static void dfs(int from, int to, long d) {
        distance[to] = d;
        TreeMap<Integer, Long> m = edges.get(to);
        m.remove(from);
        m.forEach((k, v) -> dfs(to, k, d+v));
    }

}

Measured memory_bytes: 233784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<int,int>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)

int main(){
	ll N,L;
	cin >> N >> L;
	ll a[N];
	FOR(i,0,N)cin >> a[i];
	
	priority_queue<P> pq;
	FOR(i,0,L-1){
		pq.push({-a[i],i});
	}

	FOR(i,L-1,N){
		pq.push({-a[i],i});
		while(pq.top().second<i-L+1){
			pq.pop();
		}
		cout << (i==(L-1)?"":" ") << -pq.top().first;
	}
	cout << endl;
}


Measured memory_bytes: 19032
def lscan; gets.split.map(&:to_i); end
def bye(msg); puts msg.to_s; exit; end
n = gets.to_i

(1..9).each do |x|
  (1..9).each do |y|
    if (x*y == n)
      bye('Yes')
    end
  end
end
bye('No')

Measured memory_bytes: 1916
import sys
#import numpy as np

#sys.setrecursionlimit(10**6)
#readline = sys.stdin.readline

n = int(input())

l = [1,1]

def f(i):
    global l
    if i <= 1:
        return 1
    else:
        return l[i-1] + l[i-2]

for i in range(2,n+1):
    l.append(f(i))

print(l[n])



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

int main(){
    int H, W;
    long long sum = 0;
    cin >> H >> W;
    vector<vector<int>> cost(10, vector<int>(10));
    vector<vector<int>> A(H, vector<int>(W));
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            cin >> cost[i][j];
        }
    }
    for(int k = 0; k < 10; k++){
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> A[i][j];
            if(A[i][j] != -1)sum += cost[A[i][j]][1];
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define c2(n,m) cin>>n>>m
#define c3(n,m,k) cin>>n>>m>>k
#define co(n) cout<<n<<endl
using namespace std;

int main(){
  int a,b;
  c2(a,b);
  char c[a+b+1];
  rep(i,0,a+b+1) c(c[i]);
  int d=0, e;
  
  rep(i,0,a+b+1){
    e=c[i];
    if(i!=a){
      if(48<=e && e<=57) d++;
    }
    else if(c[i]==45) d++;
  }
  if(d==a+b+1) co("Yes");
  else co("No");
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
   /* #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll n,m,count=0;
    cin>>n>>m;
    ll a[m+1];
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        ll k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            ll x;
            cin>>x;
            a[x]++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(a[i]==n)
            count++;

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

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_variables)]

fn main() {
    let w: Vec<char> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().chars().collect()
    };

    let mut cnt = std::collections::HashMap::new();
    for &c in &w {
        *(cnt.entry(c).or_insert(0)) += 1;
    }
    let ans = if cnt.values().all(|x| x % 2 == 0) {
        "Yes"
    } else {
        "No"
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
use std::collections::HashSet;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("Failed to read bytes") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

static mut pos:i32 = -1;

fn main() {
    let n:usize = read();
    let mut g:Vec<Vec<usize>> = vec![vec![]; n];
    for _ in 0..n {
        let mut a:usize = read();
        let mut b:usize = read();
        // 頂点番号が1インデクスで与えられるので0インデクスにする
        a -= 1;
        b -= 1;
        g[a].push(b);
        g[b].push(a);
    }

    let mut seen = vec![false; n];
    let mut finished = vec![false; n];
    let mut hist:Vec<i32> = Vec::new();
    dfs(&g, &mut seen, &mut finished, &mut hist, 0, -1);

    let mut cycle = HashSet::new();
    while !hist.is_empty() {
        let t:i32 = hist.pop().unwrap();
        cycle.insert(t);
        if unsafe { t == pos } {
            break;
        }
    }

    let q:u32 = read();
    for _ in 0..q {
        let mut a:i32 = read();
        let mut b:i32 = read();
        a -= 1;
        b -= 1;
        if cycle.contains(&a) && cycle.contains(&b) {
            println!("2");
        } else {
            println!("1");
        }
    }
}

fn dfs(g: &Vec<Vec<usize>>,seen: &mut Vec<bool>,
    finished:&mut Vec<bool>, hist:&mut Vec<i32>, v:i32, p:i32) {
    let vu = v as usize;
    seen[vu] = true;
    hist.push(v);
    for nv in &g[vu] {
        let nv = *nv;
        let nvi = nv as i32;
        if nvi == p {
            continue;
        }
        if finished[nv] {
            continue;
        }

        if seen[nv] && !finished[nv] {
            unsafe {
                pos = nvi;
            }
            return;
        }

        dfs(g, seen, finished, hist, nvi, v);
        if unsafe {pos != -1 } {
            return;
        }
    }
    hist.pop();
    finished[vu] = true;
}


Measured memory_bytes: 25112
/**
 *  winners never quit
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pp pop_back
#define mp make_pair
#define IO cin.tie(0),cout.tie(0)
#define ISWS ios::sync_with_stdio(0)
typedef long long Long;
void FastIO(){ISWS;IO;}

const int N = 1e5;

int main()
{
  FastIO();
  int tc, ca = 0;
  string s, t;
  cin >> s >> t;
  int ans = INT_MAX;
  for (int i = 0;i <= s.size()-t.size();i++){
    int cnt = 0;
    for (int j = i, k = 0;j < i+t.size();j++, k++){
      if (s[j] != t[k])cnt++;
    }
    ans = min(ans, cnt);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3660
/***

   Author : Md. Jashim Uddin
   From   : RMSTU

 ***/
#include<bits/stdc++.h>
using namespace std;
#define     sf(a)           scanf("%d",&a)
#define     sff(a,b)        scanf("%d %d",&a,&b)
#define     sfff(a,b,c)     scanf("%d %d %d",&a,&b, &c)
#define     pb              push_back
#define     ll              long  long int
#define     fast            ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define     pi              2*acos(0)
#define     sp              fixed<<setprecision
#define     lcm(a,b)        (a*b)/gcd(a,b)
#define     gcd(a,b)        _gcd(a,b)
#define     forn(i,n)       for(int i=1;i<=n;i++)
#define      mx               10001
int main()
{
       string s;
    cin>>s;
    bool b = false;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]==s[i+1])
        {
            b = true;
            break;
        }
    }
    if(b)cout<<"Bad"<<endl;
    else cout<<"Good"<<endl;
   




    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

void main() {
	int[] a = new int[3];
	foreach (i; 0..3) {
		scanf("%d", &a[i]);
	}
	a.sort;
	int ans = 0;
	foreach (i; 0..3) {
		ans += a[2]-a[i];
	}
	if (ans%2 == 1) ans += 3;
	writeln(ans/2);
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
int n,a;
cin >> n;
a=n;
int d[n];
for(int i=0;i<n;i++)
{
cin >> d[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j and d[i]==d[j] and d[j]!=-1)
{
d[j]=-1;
a--;
}}}
cout << a;
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <complex>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")


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

	int n, m, sx, sy, dx, dy, x, y, xx, yy, i, j, k, INF = 1E9, dd;
	int v[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };

	cin >> n >> m >> sx >> sy >> dx >> dy;
	sx--; sy--; dx--; dy--;
	vector<string> s(n);
	for (i = 0; i < n; i++) cin >> s[i];

	vector<vector<int>> d(n, vector<int>(m, INF));
	priority_queue<pair<int, pair<int, int>>> q;
	d[sx][sy] = 0;
	q.push({ 0, {sx, sy} });

	while (!q.empty()) {
		x = q.top().second.first;
		y = q.top().second.second;
		dd = -q.top().first;
		q.pop();

		if (dd != d[x][y]) continue;

		for (k = 0; k < 4; k++) {
			xx = x + v[k][0];
			yy = y + v[k][1];

			if ((xx >= 0) && (xx < n) && (yy >= 0) && (yy < m) && (d[xx][yy] > d[x][y]) && (s[xx][yy] == '.')) {
				d[xx][yy] = d[x][y];
				q.push({ -d[xx][yy], { xx, yy } });
			}
		}

		for (i = -2; i <= 2; i++) {
			for (j = -2; j <= 2; j++) {
				xx = x + i; yy = y + j;

				if ((xx >= 0) && (xx < n) && (yy >= 0) && (yy < m) && (d[xx][yy] > d[x][y] + 1) && (s[xx][yy] == '.')) {
					d[xx][yy] = d[x][y] + 1;
					q.push({ -d[xx][yy], { xx, yy }  });
				}
			}
		}
	}

	if (d[dx][dy] == INF) cout << "-1\n";
	else cout << d[dx][dy] << "\n";

	return 0;
}



Measured memory_bytes: 8700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	string S; cin >> S;
	if(N % 2 == 1) No
	string s1 = S.substr(0,N/2);
	string s2 = S.substr(N/2,N);
	//cout << s1 << " " << s2 << endl;
	if(s1 == s2) Yes
	else No


    return 0;
}

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

using namespace std;

int main()
{
	int n,m;
	char c;
	vector<int> array;
	
	for(;;)
	{
		cin >> n ;
		if(n==0)
			break;
		array.clear();
		cin >> m;
		int flag=-1,flag2=0;
		int save=0;
		
		for(int i=0;i<m;i++)
		{
			cin >> c ;
			if(c=='I')
			{
				if(flag==1)
				{
					array.push_back(save);
					save=1;
					flag2=1;
				
				}
				else
				{
					save++;
					flag=1;
					flag2=0;
				}
			}
			else
			{
				if(flag==0)
				{
					array.push_back(save);
					save=0;
					flag2=1;
				}
				else if(flag==1)
				{
					save++;
					flag=0;
					flag2=0;
				}
			}
		}
		
		if(flag2==0)
			array.push_back(save);
		int  ans=0;
		
		for(int i=0;i<array.size();i++)
		{
			if(array[i]%2==0 && array[i]>3)
				array[i]--;
			if(array[i]>=3+(n-1)*2)
			{
				ans+=(array[i]-(3+(n-1)*2))/2+1;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1272
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

a = iarr()
for i,num in enumerate(a):
    if num==0: print(i+1); break


Measured memory_bytes: 37720
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long INF = 1e9 + 7;
using namespace std;
map<int, int> mp;
int main()
{
	string o, e;
	cin >> o >> e;
	if (o.size() == e.size()) {
		for (int i = 0; i < o.size(); i++) {
			cout << o.at(i) << e.at(i);
		}
	}
	else if (o.size() > e.size()) {
		for (int i = 0; i < e.size(); i++) {
			cout << o.at(i) << e.at(i);
		}
		cout << o.at(o.size() - 1);
	}
	else {
		for (int i = 0; i < o.size(); i++) {
			cout << o.at(i) << e.at(i);
		}
		cout << e.at(e.size() - 1);
	}
	return 0;
}

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

using namespace std;

long long a,b,k;
vector<long long>ans;

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

    if((b-a+1)<=2*k){
        for(int i=a;i<=b;i++){
            cout<<i<<endl;
        }
    }else{
        for(int i=a;i<=a+k-1;i++){
            cout<<i<<endl;
        }
        for(int i=b-k+1;i<=b;i++){
            cout<<i<<endl;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
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>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	ll n,m; cin>>n>>m;
	ll ans=0;
	rep(i,0,n){
		ll a; cin>>a;
		if(a>=m)ans++;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define N 50
#define M 500
using namespace std;
typedef pair<string,int> P;
vector<P> G[N];

string D[M][N];
string dijkstra(int S,int T){
 
  for(int i=0;i<M;i++)
    for(int j=0;j<N;j++) D[i][j]="{";
  
 priority_queue<P,vector<P>,greater<P> > Q;
 Q.push(P("",S));
  D[0][S] = "";
  
  while(!Q.empty()){
    P t = Q.top();Q.pop();
    string cost = t.first;
    int len = cost.size();
    int pos = t.second;
    
    if(len>M-10) return "NO";
    if(pos==T) return cost; 
    if(D[len][pos]<cost) continue;

 
    for(int i=0;i<(int)G[pos].size();i++){
      int npos = G[pos][i].second;
      string ncost = cost+G[pos][i].first;
      int nlen = ncost.size();
      if(D[nlen][npos]<=ncost)continue;
      Q.push(P(ncost,npos));
      D[nlen][npos] = ncost;
    }
  }
  return "NO";
}
 
int main(){
  int cnt=0;
  while(1){
    cnt++;
    int n,m,s,g;
    cin>>n>>m>>s>>g;
    if(!n&&!m&&!s&&!g) return 0;

    
  
  for(int i=0;i<N;i++) G[i].clear();
  int D[N][N];
  for(int i=0;i<N;i++)for(int j=0;j<N;j++) D[i][j]=1;
  
  
  for(int i=0,a,b;i<m;i++){
    string c;
    cin>>a>>b>>c;
    G[a].push_back(P(c,b));
    D[a][b] = 0;
  }

  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	D[i][j] = min(D[i][j],D[i][k]+D[k][j]);
  
  for(int i=0;i<n;i++)if(D[i][g]) G[i].clear();

  cout<<dijkstra(s,g)<<endl;
  }
   
  return 0;
}

Measured memory_bytes: 24708
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut cnts = vec![0; 3];
    for i in 0..3 {
        cnts[i] = read::<usize>();
    }
    let k = read::<usize>();
    let mut seqs = vec![vec![]; 3];
    for i in 0..3 {
        for _j in 0..cnts[i] {
            let v = read::<i64>();
            seqs[i].push(v);
        }
    }
    let mut anss = seqs[0].clone();
    for offset in 1..3 {
        let mut sums = vec![];
        for i in 0..anss.len() {
            for j in 0..cnts[offset] {
                sums.push(anss[i] + seqs[offset][j]);
            }
        }
        let l = sums.len();
        sums.sort();
        sums.reverse();
        sums.resize(std::cmp::min(k, l), 0);
        anss = sums;
    }
    for i in 0..k {
        println!("{}", anss[i]);
    }
}


Measured memory_bytes: 44276
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int MAX = 1000000;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        String line = sc.next().replace("egg", "e").replace("chicken", "c");
        line = line.replace("ee", "e e").replace("ee", "e e")
                .replace("cc", "c c").replace("cc", "c c");
        String strs[] = line.split(" ");
        int max = 0;
        String ans = "";
        for (int i = 0; i < strs.length; i++) {
            if (max < strs[i].length()) {
                max = strs[i].length();
                ans = strs[i].charAt(max - 1) == 'e' ? "egg" : "chicken";
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 12000
import numpy as np
p,q= input().split()
a,b =(int(p), int(q))
ans_list = input().split()
ans_list =np.array(ans_list).astype(float)
#print(ans_list)
ans_list=np.sort(ans_list)[::-1]
#print(ans_list)
if ans_list[b-1] >= sum(ans_list)/4/b:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 27184
#include<stdio.h>
int a, b, sum, i;

int main(void){
  while(scanf("%d %d", &a, &b)!=EOF){
    sum = a + b;
    for(i = 0;sum != 0; i++){
      sum = sum / 10;
    }
    printf("%d\n", i);
  }
  
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 

ll n;

vector <ll> vec[200005];
ll val[200005];

void solve(ll u,ll par)
{
	
	for(ll i=0;i<vec[u].size();++i)
	{
		ll v = vec[u][i];
		if(v!=par)
		{
			val[v]+=val[u];
			solve(v,u);
		}
	}
	
}


int main()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(val,0,sizeof(val));
	ll Q;
	cin>>n>>Q;
	
	for(ll i=0;i<n-1;i++)
	{
		ll a,b;
		cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	
	while(Q--)
	{
		ll p,x;
		cin>>p>>x;
		val[p]+=x;
	}
	
	solve(1,-1);
	
	for(ll i=1;i<=n;i++)cout<<val[i]<<" ";cout<<endl;
	
}





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

int main()
{
    int n,m;
    while(cin >> n && n) {
        vector<int> v(n);
        for(int i = 0; i < n; i++) 
            cin >> v[i];

        cin >> m;
        sort(v.begin(), v.end());

        int lb, ub, cnt;
        lb = 0; ub = v.size() - 1;
        cnt = 0;
        while(lb <= ub) {
            int mb = (lb + ub) / 2;
            cnt++;
            if(v[mb] < m) {
                lb = mb + 1;
            } else if(v[mb] == m) {
                break;
            } else {
                ub = mb - 1;
            }
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 0
N = int(input())
l = list(map(int,input().split()))

d = {}


for i in range(N):
    if l[i] in d:
        d[l[i]] += 1
    else:
        d[l[i]] = 1

max_comb = 0
for v in d.values():
    max_comb += v * max(0, (v-1)) /2

def get_n(x):

    return int(max_comb - d[x] +1)


for e in l:
    print(get_n(e))


Measured memory_bytes: 86988