akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let n: i64 = read();
    let m: i64 = read();
    if m == 10 {
        println!("{}", n.to_string().len());
        return;
    }

    let mut cnt = 0;
    let mut mm = 1;
    loop {
        mm *= m;
        cnt += 1;
        if mm > n {
            break;
        }
    }
    println!("{}", cnt);
}

use std::io::stdin;
use std::io::Read;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let token: String = cin
        .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")
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

int main() {
	int N;
	
	cin >> N;
	int X = N,sum = 0;

	while (N > 0) {
		sum += N % 10;
		N /= 10;
	}

	if (X % sum == 0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int height[maxn];
long long dp[maxn];

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++)
        scanf("%d", &height[i]);
    dp[1] = 0;
    for (int i = 2; i <= n;i++){
        dp[i] = inf;
        for (int j = 1; j <= k;j++){
            if(i-j<1)
                break;
            dp[i] = min(dp[i], dp[i - j] + abs(height[i] - height[i - j]));
        }
    }
    printf("%lld", dp[n]);
    return 0;
}

Measured memory_bytes: 4928
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	string s;
	cin >> s;

	rep(i, s.size())
	{
		if (s[i] == '1')
		{
			cout << 9;
		}
		else
		{
			cout << 1;
		}
	}

	cout << endl;
	
	return 0;
}


Measured memory_bytes: 764
#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    char buf[1000] =  "  ";
    char * const word = buf + 2;
        scanf("%s", word);
        char *tail = word + strlen(word) - 1;
        if (strchr("s", *tail) != NULL){
            strcpy(tail + 1, "es");
        } else {
            strcpy(tail + 1, "s");
        }
        printf("%s\n", word);
}

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

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

    if (s.size() != (a + b + 1)) {
        cout << "No" << endl;
        return 0;
    }

    int count = 0;
    bool dash = false;
    for (int i = 0; i < s.size(); i++) {
        if (i == a) {
            if (s[i] == '-') dash = true;
        } else {
            if (s[i] != '-') count++;
        }
    }

    cout << (count == a + b && dash ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		while (sc.hasNext()) {
			int n = sc.nextInt();
			if (n>36) {System.out.println(0);}
			else if (n==36) {System.out.println(1);}
			else {
				int count = 0;
				for (int i=0; i<=9; i++) {
					for (int j=0; j<=9; j++) {
						for (int k=0; k<=9; k++) {
							for (int m=0; m<=9; m++) {
								if (i+j+k+m==n) {count++;}
							}
						}
					}
				}
				System.out.println(count);
			}
		}
	}
}


Measured memory_bytes: 26644
import sys
input = sys.stdin.readline
N = int(input())
X = input().strip()

def solve(N,X):
    if not '1' in X:
        for i in range(N):
            print(1)
        exit()

    def popcount(n):
        t = 0
        while n > 0:
            k = bin(n).count('1')
            n %= k
            t += 1
        return t

    X1 = X.count('1')

    Rp1 = []
    Rm1 = []
    Bp1 = []
    Bm1 = []

    for i, x in enumerate(list(X[::-1])):
        tp1 = pow(2,i,X1+1)
        if X1-1 > 0:
            tm1 = pow(2,i,X1-1)
        else:
            tm1 = 0
        Bp1.append(tp1)
        Bm1.append(tm1)
        if x == '1':
            Rp1.append(tp1)
            Rm1.append(tm1)
        else:
            Rp1.append(0)
            Rm1.append(0)

    basep1 = sum(Rp1) % (X1+1)
    if X1-1 > 0:
        basem1 = sum(Rm1) % (X1-1)
    else:
        basem1 = 0
    Rp1 = Rp1[::-1]
    Rm1 = Rm1[::-1]
    Bp1 = Bp1[::-1]
    Bm1 = Bm1[::-1]

    #print("base",basep1)
    #print("base",basem1)
    for bp1,bm1,x in zip(Bp1,Bm1,X):
        if x == '1':
            t = basem1 - bm1
            MOD = X1 - 1
            if MOD <= 0:
                print(0)
                continue
        else:
            t = basep1 + bp1
            MOD = X1 + 1
        #print("x",x,"t",t)
        #print(t % MOD,MOD)
        print(popcount(t % MOD) + 1)

solve(N,X)



Measured memory_bytes: 29720
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

ll P = 1000000007;
int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  string s;std::cin >> s;
  // dp[i][j] := i個見て、最後のもの未満で選べるものがj個ある
  vvl dp = VV(n+1, n+1, 0, ll);
  for(int i=0;i<n;i++) dp[0][i] = 1;//始めがi

  //貰う
  vll accum(n, 0);
  for(int i=1;i<n;i++){
    //accumの初期化
    for(int j=0;j<n;j++) accum[j] = ((j==0?0:accum[j-1]) + dp[i-1][j])%P;

    for(int j=0;j<n-i;j++){
      if(s[i-1]=='<'){
        //0~jから到達できる
        dp[i][j] = accum[j];
      }else{
        //j+1~maxから到達できる
        dp[i][j] = (accum[n-i] - accum[j] + P)%P;
      }
    }

  }
  std::cout << dp[n-1][0] << '\n';
  return 0;
}


Measured memory_bytes: 73672
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] values = new int[N+1];
      
        int min = 0;
        int Max = 0;
      
      for (int i=1; i<=N; i++) {
        values[i] = sc.nextInt();

        if (min == 0 || values[i] < min) {
          min = values[i];
        }  
        
        if (Max == 0 || Max < values[i]) {
          Max = values[i];
        }  

      }
                   
        System.out.println(Max - min);
    }
}

Measured memory_bytes: 23764
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;

int main() {
	int N, L, a = 0, ans, b = INT_MAX;
	cin >> N >> L;
	for (int i = 1; i <= N; ++i) a += L - 1 + i;
	for (int i = 1; i <= N; ++i) {
		int c = 0;
		for (int j = 1; j <= N; ++j) {
			if (i == j) continue;
			c += L - 1 + j;
		}
		if (abs(c - a) < b) {
			ans = c;
			b = abs(c - a);
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int N, K;
  int ans, h;

  ans = 0;

  cin >> N >> K;

  for(int i=0 ;i<N; i++) {
    cin >> h;
    ans += h >= K;
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;
int main()
{
	int n; cin >> n;
	int mx = 1;
	for (int i = 2; i * i <= n; ++i) {
		int sqr = i;
	//	cout << "i   "<<i << endl;
		while (sqr * i <= n)

		{
			sqr *= i;
		}
		mx = max(sqr, mx);
		//cout << mx << endl;
	}
	cout << mx;
	
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define set_bits(a) __builtin_popcount(a)
#define pb push_back
#define pf push_front
#define mod 1000000007
#define M 998244353
#define fi first
#define se second
#define endl '\n'
#define INF 1e18
#define PI 3.14159265358979323846
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    char x;
    cin>>x;

    if(isupper(x))
    {
        cout<<"A";
    }
    else
    {
        cout<<"a";
    }
}


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

using namespace std;

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

	int left_a = s.length(), right_z = 0;
	for (int i = 0; i < s.length(); i++) {
		if(s[i] == 'A') {
			left_a = min(i, left_a);
		}
		if(s[i] == 'Z') {
			right_z = max(i, right_z);
		}
	}
	cout << right_z - left_a + 1 << endl;

}

Measured memory_bytes: 640
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=50;

struct T {
	int n;
	vector<int> adj[MAXN];
	bool have(int a,int b) { REPSZ(i,adj[a]) if(adj[a][i]==b) return true; return false; }
	void move(int a,int b) {
		assert(SZ(adj[a])==1);
		int to=adj[a][0]; adj[a].clear(); REPSZ(i,adj[to]) if(adj[to][i]==a) { adj[to].erase(adj[to].begin()+i); break; }
		adj[a].PB(b),adj[b].PB(a);
	}

};

int n;
T A,B;

int solve(T &t,int root) {
	vector<bool> fixed(n,false);
	queue<int> q;
	fixed[root]=true; q.push(root);
	while(!q.empty()) { int at=q.front(); q.pop(); REPSZ(i,t.adj[at]) { int to=t.adj[at][i]; if(!fixed[to]&&B.have(at,to)) { fixed[to]=true; q.push(to); } } }
	//printf("\torig:"); REP(i,n) if(fixed[i]) printf(" %d",i+1); puts("");
	int ret=0;
	vector<vector<int>> after(n);
	REP(at,n) if(!fixed[at]&&SZ(t.adj[at])==1) REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) q.push(at); else after[to].PB(at); }
	while(!q.empty()){ 
		int at=q.front(); q.pop();
		//printf("\tmoving %d\n",at+1);
		assert(!fixed[at]&&SZ(t.adj[at])==1);
		int dst=-1; REPSZ(i,B.adj[at]) { int to=B.adj[at][i]; if(fixed[to]) { assert(dst==-1); dst=to; } } assert(dst!=-1);
		int oth=t.adj[at][0];
		t.move(at,dst); ++ret;
		if(!fixed[oth]&&SZ(t.adj[oth])==1) REPSZ(i,B.adj[oth]) { int to=B.adj[oth][i]; if(fixed[to]) q.push(oth); else after[to].PB(oth); }
		fixed[at]=true; REPSZ(i,after[at]) { int to=after[at][i]; if(!fixed[to]) q.push(to); }
	}
	REP(i,n) if(!fixed[i]) return INT_MAX;
	return ret;
}

int solve() {
	int ret=INT_MAX;
	REP(i,n) { // keep i
		T t=A;
		int cur=solve(t,i);
		ret=min(ret,cur);
	}
	REP(i,n) REP(j,n) if(i!=j) { // first move i to j
		if(SZ(A.adj[i])!=1) continue;
		//printf("moving %d to %d\n",i+1,j+1);
		T t=A; t.move(i,j);
		int cur=solve(t,i);
		if(cur!=INT_MAX) ++cur;
		ret=min(ret,cur);
	}
	return ret==INT_MAX?-1:ret;
}


void run() {
	scanf("%d",&n); A.n=B.n=n;
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; A.adj[u].PB(v),A.adj[v].PB(u); }
	REP(i,n-1) { int u,v; scanf("%d%d",&u,&v); --u,--v; B.adj[u].PB(v),B.adj[v].PB(u); }
	printf("%d\n",solve());
	REP(i,n) A.adj[i].clear(),B.adj[i].clear();
}

int main() {
	int n; scanf("%d",&n); FORE(i,1,n) run();
	return 0;
}


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

using namespace std;
const long long MOD=1e9+7;

int main(){
  long long n, a[300009], cnt[62];
  cin >> n;
  for(int i=0;i<n;i++)cin >> a[i];
  for(int i=0;i<n;i++){
    for(int j=0;j<60;j++){
      if((a[i]>>j)&1)cnt[j]++;
    }
  }
  long long base=1;
  long long ans = 0;
  for(int i=0;i<60;i++){
    long long value=0;
    value+=base*cnt[i];
    value%=MOD;
    value *= n-cnt[i];
    value%=MOD;
    ans += value;
    ans %= MOD;
    base = (base * 2) % MOD;
  }
  cout << ans << endl;
}



Measured memory_bytes: 2560
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(x) cout << fixed << setprecision(x);
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll k,a,b; cin >> k >> a >> b;
  if(a+1 > k) cout << k+1 << endl;
  else if(b <= a+2) cout << k+1 << endl;
  else{
    if((k-a+1) % 2 == 1) cout << (k-a)*(b-a)/2 + 1 + a << endl;
    else cout << (k-a+1)*(b-a)/2 + a << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
 
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int R,G;
    cin>>R>>G;
    cout<<2*G-R<<endl;
	return 0;
}


Measured memory_bytes: 256
fn input_one<T: std::str::FromStr> () -> Result<T, T::Err> {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    n.trim().parse()
}

fn main() {
    let n: usize = input_one().unwrap();
    fn solve(n: usize) -> bool {
        for i in 1..10 {
            if n / i < 10 && n % i == 0 {
                return true
            }
        }
        false
    }
    println!("{}", if solve(n) { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-10;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vvi g;
vl F;
vvl DP,dp[3];

int dfs(int v){
	int S=1;
	dp[0][v][0]++;
	vp b;
	for(int i=0;i<g[v].size();i++){
		int u=g[v][i];
		b.push_back({dfs(u),u});
	}
	sort(b.rbegin(),b.rend());
	for(int i=0;i<b.size();i++){
		int T=b[i].first,u=b[i].second;
		S+=T;
		vl a[3];
		a[0]=a[1]=a[2]=vl(n);
		a[0][0]++;
		if(!i){
			a[0]=DP[u];
			for(int j=1;j<S;j++) a[1][j]=(dp[0][u][j-1]*2+dp[1][u][j-1])%mod;
		}
		else{
			for(int j=0;j<3;j++) for(int k=1;k<S;k++) for(int l=max(0,k-T);l<=k;l++){
				(a[j][k]+=dp[j][v][l]*DP[u][k-l])%=mod;
				if(j&&l<k) (a[j][k]+=dp[j-1][v][l]*(dp[0][u][k-l-1]*(3-j)+dp[1][u][k-l-1]*(j==1?1:mod/2+1)%mod))%=mod;
			}
		}
		dp[0][v]=a[0];
		dp[1][v]=a[1];
		dp[2][v]=a[2];
	}
	for(int i=0;i<3;i++) for(int j=0;j<S;j++) (DP[v][j]+=dp[i][v][j])%=mod;
	return S;
}

int main(){
	cin>>n;
	g=vvi(n);
	F=vl(n+1,1);
	DP=dp[0]=dp[1]=dp[2]=vvl(n,vl(n));
	for(int i=1;i<n;i++){
		int v;
		cin>>v;
		g[v-1].push_back(i);
	}
	dfs(0);
	ll res=0;
	for(int i=1;i<=n;i++) F[i]=F[i-1]*i%mod;
	for(int i=0;i<n;i++){
		ll tmp=F[n-i]*DP[0][i]%mod;
		if(i%2==1) tmp=(mod-tmp)%mod;
		(res+=tmp)%=mod;
	}
	cout<<res<<endl;
}

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

class UnionFind {
public:
    vector<int> d;
    UnionFind(int n=0) : d(n, -1) {}
    // 経路縮約を行いながら根を探す
    int find(int x) {
        if(d[x] < 0){
            return x;
        }
        return d[x] = find(d[x]); //メモ化再帰
    }
    // 小さいほうにくっつける
    bool unite(int x, int y) {
        x = find(x); 
        y = find(y);
        if(x == y){
            return false;
        }
        if(size(x) < size(y)){
            swap(x,y);
        } 
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { 
        return find(x) == find(y);
    }
    int size(int x) { 
        return -d[find(x)];
    }
};

int main() {

    int n, m, k;
    cin >> n >> m >> k;
    UnionFind uf(n);
    vector<int> fri(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        uf.unite(a, b);
        fri[a]++;
        fri[b]++;
    }
    vector<vector<int>> block(n);
    rep(i, k){
        int c, d;
        cin >> c >> d;
        --c;
        --d;
        block[c].push_back(d);
        block[d].push_back(c);
    }

    rep(i, n){
                //    全部　-　友達　―　自分
        int ans = uf.size(i) - fri[i] - 1;
        for(auto v : block[i]){
            if(uf.same(i, v)){
                --ans;
            }
        }
        cout << ans << " ";
    }

    return 0;
}

Measured memory_bytes: 6784
#include<iostream>

using namespace std;

int main() {
	int N;
	string S;
	cin >> N;
	cin >> S;
	int count = 0;
	for (int i = 0;i < N-2;i++) {
		if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char maze[10][10];
int main() {
    int h,w,k;
    cin >> h >> w >> k;
    for (int i = 0; i < h; i++) cin >> maze[i];
    int ans = 0;
    for (int hh = 0; hh < (1 << h); hh++) {
        for (int ww = 0; ww < (1 << w); ww++) {
            int cnt = 0;
            for (int th = 0; th < h; th++) {
                for (int tw = 0; tw < w; tw++) {
                    if ((hh >> th) & 1) continue;
                    if ((ww >> tw) & 1) continue;
                    if (maze[th][tw] == '.') continue;
                    cnt++;
                }
            }
            if (cnt == k) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <array>
#include <cmath>

using namespace std;

using ll = long long int;

// GCDを計算します
template <typename NumType>
NumType calcGCD(NumType a, NumType b) {
    if (a < b) {
        NumType tmp = a;
        a = b;
        b = tmp; 
    }

    NumType r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

// 約数を数えます
template <typename NumType>
NumType cntDivisor(const NumType & num) {
    NumType cnt = 0;
    for(NumType i = 1; i * i <= num; ++i) {
        if(num % i == 0) {
            cnt++;
            if(i * i != num) cnt++;
        }
    }

    return cnt;
}

// [beg, end)の範囲を，添え字indexでループするfor文に置換します
#define FOR_RANGE(index, beg, end)     for (ll index = beg; index < N; ++index)

#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

int main() {
    int N;
    int d[(int)1e5];

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

    std::sort(&d[0], &d[N], std::less<int>());

    cout << d[N/2] - d[N/2-1];

    return 0;
}



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

int main() {
  int n, q;
  cin >> n >> q;
  fenwick_tree<ll> fw(n);
  rep(i,n) {
    int a;
    cin >> a;
    fw.add(i,a);
  }
  rep(i,q) {
    int t;
    cin >> t;
    if(t) {
      int l, r;
      cin >> l >> r;
      cout << fw.sum(l,r) << endl;
    } else {
      int p, x;
      cin >> p >> x;
      fw.add(p,x);
    }
  }
  return 0;
}

Measured memory_bytes: 8220
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

set<pii> st;
set<pii> used;
int main(){
	int h, w, n;
	cin>>h>>w>>n;
	pii p;
	rep(i, n){
		cin>>p.fi>>p.se;
		st.insert(p);
	}
	vector<ll> ans(10, 0LL);
	for(auto& q : st){
		for(int i = q.fi-2; i <= q.fi; i++){
			if(i <= 0 || i+2 > h) continue;
			for(int j = q.se-2; j <= q.se; j++){
				if(j <= 0 || j+2 > w) continue;
				if(used.count({i, j})) continue;
				used.insert({i, j});
				int t = 0;
				for(int k = 0; k < 3; k++){
					for(int l = 0; l < 3; l++){
						if(st.count({i+k,j+l})) t++;
					}
				}
				ans[t]++;
			}
		}
	}
	ans[0] = ((ll)h-2LL)*((ll)w-2LL);
	for(int i = 1; i < 10; i++){
		ans[0] -= ans[i];
	}
	rep(i, 10) cout<<ans[i]<<endl;
}

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

int N,M;
vector<int> path[100001];
int pathed[100001] = {0};

void dfs(int now){
      //cout << now << endl;
  pathed[now] = 1;
  for (int i(0);i<path[now].size();i++){
    int next = path[now][i]; 
    if (pathed[next] == 0) dfs(next);
  }
}

int main(){
  cin>>N>>M;
  for (int i(0);i<M;i++){
    int x,y,z;
    cin>>x>>y>>z;
    path[x].push_back(y);
    path[y].push_back(x);
  }
  ll ans(0);
  for (int i(1);i<=N;i++){
    if (pathed[i] == 0){
      dfs(i);
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

struct Node {
  int value = -1;
  Node *parent = NULL;
  Node *left = NULL;
  Node *right = NULL;
};

Node* tree;

int find(Node* node, int p) {
  if (node == NULL) {
    return 0;
  } else if (node->value == p) {
    return 1;
  } else if (node->value < p) {
    return find(node->right, p);
  } else {
    return find(node->left, p);
  }
}

void insert(int p) {
  Node* z = new Node();
  z->value = p;
  
  if (tree == NULL) {
    tree = z;
    return;
  }

  Node* y = NULL;
  Node* x = tree;
  
  while (x != NULL) {
    y = x;
    if (z->value < x->value) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;
  
  if (y == NULL) {
    tree = z;
  } else if (z->value < y->value) {
    y->left = z;
  } else {
    y->right = z;
  }
}

void inorder(Node* node) {
  if (node == NULL) return;
  inorder(node->left);
  cout << " " << node->value;
  inorder(node->right);
}

void print_inorder(Node* node) {
  inorder(node);
  cout << endl;
}

void preorder(Node* node) {
  if (node == NULL) return;
  cout << " " << node->value;
  preorder(node->left);
  preorder(node->right);
}

void print_preorder(Node* node) {
  preorder(node);
  cout << endl;
}

int main() {
  int N; cin >> N;
  string queue;
  int p;

  for (int i = 0; i < N; i++) {
    cin >> queue;
    if (queue == "insert") {
      cin >> p;
      insert(p);
    } else if (queue == "find") {
      cin >> p;
      cout << (find(tree, p) ? "yes" : "no") << endl;
    } else {
      print_inorder(tree);
      print_preorder(tree);
    }
  } 
}




Measured memory_bytes: 21932
const log = console.log;

// ----

function Main(input: string): void {
  const characters = input
    .trim()
    .split("")
    .sort();

  const len = characters.length;
  let previousCode = "a".charCodeAt(0) - 1;

  for (let i = 0; i < len; i++) {
    const currentCode = characters[i].charCodeAt(0);

    if (currentCode - previousCode > 1) {
      log(String.fromCharCode(previousCode + 1));

      return;
    }

    previousCode = currentCode;
  }

  const lastCharCode = characters[len - 1];
  log(
    lastCharCode === "z"
      ? "None"
      : String.fromCharCode(lastCharCode.charCodeAt(0) + 1)
  );
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 9528
N = int(input())
H = list(map(int, input().split()))

count, count_m = 0, 0
for i in range(1, N):
    if H[i-1] >= H[i]:
        count += 1
        count_m = max(count_m, count)
    else:
        count = 0
print(count_m)


Measured memory_bytes: 14252
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

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

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void judgement(int a){
  if(a){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

int main(){
  ll i,N,cnt=1,ans=0;
  string s;cin>>s;
  vec v;
  if(s[0]!='<'){
    v.pb(1);
  }
  rep1(i,s.size()){
    if(s[i]!=s[i-1]){
      v.pb(cnt);
      cnt=1;
    }else{
      cnt++;
    }
  }
  v.pb(cnt);
  if(s[s.size()-1]!='>')v.pb(1);
  rep(i,v.size()){
    ans+=v[i]*(v[i]-1)/2;
    ans+=v[i+1]*(v[i+1]-1)/2;
    N=max(v[i],v[i+1]);
    ans+=N;
    i++;
  }
  cout<<ans<<endl;
  return 0;
}

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

#define sd(mark) scanf("%d",&mark)
#define s2d(mark,marx) scanf("%d%d",&mark,&marx)
#define s3d(mark,marx,marz) scanf("%d%d%d",&mark,&marx,&marz)
#define sf(mark) scanf("%f",&mark)
#define slf(mark) scanf("%lf",&mark)
#define sst(mark) scanf("%s",&mark)
#define sld(mark) scanf("%lld",&mark)
#define s2ld(mark,marx) scanf("%lld%lld",&mark,&marx)
#define s3ld(mark,marx,marz) scanf("%lld%lld%lld",&mark,&marx,&marz)
#define sline(mline) scanf("%[^\n]%*c",&mline)

#define pi(n) printf("%d\n",n)
#define pf(n) printf("%f\n",n)
#define plf(n) printf("%lf\n",n)
#define pst(n) printf("%s\n",n)
#define pl(n) printf("%lld\n",n)

#define pis(n) printf("%d ",n)
#define pfs(n) printf("%f ",n)
#define plfs(n) printf("%lf ",n)
#define pss(n) printf("%s ",n)
#define pls(n) printf("%lld ",n)

#define sff fflush(stdout)
#define decimal(n) cout.precision(n)
#define fix cout<<fixed
#define debug(mark) printf("check%d\n",mark)
#define in(a) cin>>a
#define out(a) cout<<a<<'\n'
#define clr(mark) memset(mark,0,sizeof(mark))
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long int
#define mod 1000000007ll
#define llu unsigned long long int
#define endl '\n'
#define INF 1123456789
#define eps 1e-9
#define fo(i,a,b) for(int i=a;i<b;++i)
#define foll(i,a,b) for(ll i=a;i<b;++i)
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)

#define UL 100000		//5
#define MAXN 1000000	//6
#define MAXL 10000000	//7

typedef vector< vector<int> > vvi;
typedef vector< vector<ll> > vvl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< pair<ll,ll> > vll;
typedef pair<char,char> pcc;
typedef vector< pair<int, int> > vii;


// bool mark[MAXN+5];

// int sieve()
// {
// 	int ULL = MAXN;
// 	for(int i=0;i<=ULL;i++) mark[i]=true;
// 	for(int i=2;i*i<=ULL;i++) if(mark[i]) for(int j=i*i;j<=ULL;j+=i) mark[j]=false;
// 	for(int i=2;i<=ULL;i++) if(mark[i]) p.pb(i);
// 	return p.size();
// }


ll gcd(ll a, ll b) {if(!b) return a; return gcd(b,a%b);}

ll modexp(ll a,ll b)
{
	if(b==0) return 1;
	if(b==1) return a;
	ll temp = modexp(a,(b>>1));
	temp = (temp*temp);
	return (temp*modexp(a,b&1));
}

ll modexp(ll a,ll b, ll m)
{
	if(b==0) return 1;
	if(b==1) return a%m;
	ll temp = modexp(a,(b>>1),m);
	temp = (temp*temp)%m;
	return (temp*modexp(a,b&1,m))%m;
}

ll modinv(ll a, ll p)
{
	return modexp(a,p-2,p);
}

int main()
{
	int L; sd(L); int n;
	if(L==2) 
	{
		cout<<"2 2\n1 2 0\n1 2 1\n";
		return 0;
	}
	fo(i,0,25)
	{
		if((modexp(2ll,i) <= (L-1))&&(modexp(2,i+1)>(L-1))) { n = i+1; break;}
	}
	int k = 2*(n-1);
	vii xd;
	int ii = n-1;
	while(ii)
	{
		if((L-modexp(2,ii-1))>=modexp(2,n-1)) 
		{
			xd.pb(mp(ii,L-modexp(2,ii-1)));
			L-=modexp(2,ii-1);
		}
		else ii--;
	}
	k += int(xd.size());
	cout<<n<<" "<<k<<'\n';
	fo(i,1,n) cout<<i<<" "<<i+1<<" "<<0<<'\n';
	fo(i,1,n) cout<<i<<" "<<i+1<<" "<<int(1<<(i-1))<<'\n';
	fo(i,0,xd.size()) cout<<xd[i].ff<<" "<<n<<" "<<xd[i].ss<<'\n';	
}

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

tasks = []
for _ in range(n):
    ni, ti = input().split()
    tasks.append((ni, int(ti)))

t = 0
while len(tasks) > 0:
    ni, ti = tasks.pop(0)
    if ti <= q:
        t += ti
        print(f'{ni} {t}')
    else:
        tasks.append((ni, ti - q))
        t += q



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

using namespace std;

const int size = 1e5 + 7;
string grid[size];
int dp[1007][1007];

const int mod = 1e9 + 7;

int main(){
	int h, w;
	
	cin>>h>>w;
	for(int x=0;x<h;x++){
		string a;
		cin>>a;

		grid[x] = a;
	}

	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for(int x=0;x<h;x++){
		for(int i=0;i<w;i++){
			if(grid[x][i] == '#') continue;
			if(x>0 && grid[x-1][i] != '#') dp[x][i] = dp[x-1][i]%mod;
			if(i>0 && grid[x][i-1] != '#') dp[x][i] += dp[x][i-1]%mod;

			dp[x][i]%=mod;
		}
	}
	cout<<dp[h-1][w-1];
	return 0;
}

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

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


Measured memory_bytes: 3132
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>
#include <queue>
#include <stack>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < k; i++) {
		int d;
		cin >> d;
		for (int j = 0; j < d; j++) {
			int a;
			cin >> a;
			if (v[a - 1] == 0)v[a - 1] = 1;

		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] == 0)ans++;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <ios>
#include <iomanip>
#include <cmath>
#include <regex>
using namespace std;

int main(){
  int x, a, b;
  cin >> x >> a >> b;
  cout << (x-a)%b << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m = scan.nextInt();
		int n = scan.nextInt();

		int[][] a;
		a = new int[m][n];

		int[] b;
		b = new int[n];

		for (int i = 0; i < m; i++) {

			for (int j = 0; j < n; j++) {

				a[i][j] = scan.nextInt();

			}

		}

		for (int j = 0; j < n; j++) {

			b[j] = scan.nextInt();

		}

		for (int i = 0; i < m; i++) {
			int c = 0;

			for (int j = 0; j < n; j++) {

				c = c + a[i][j] * b[j];

			}
			System.out.println(c);
		}

	}

}

Measured memory_bytes: 40476
#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int main()
{
    n=read();m=log2(n);
    if((1<<m)==n)   return puts("No"),0;
    puts("Yes");
    printf("%d %d\n",1,2);
    printf("%d %d\n",2,3);
    printf("%d %d\n",3,n+1);
    printf("%d %d\n",n+1,n+2);
    printf("%d %d\n",n+2,n+3);
    for(int i=2;2*i+1<=n;i++)
    {
        printf("%d %d\n",1,2*i);
        printf("%d %d\n",1,2*i+1);
        printf("%d %d\n",2*i,2*i+n+1);
        printf("%d %d\n",2*i+1,2*i+n);
    }
    if(!(n&1))
    {
        for(int i=2;i<=n;i++)
        {
            if(i==3)  continue;
            int y=(i^1^n);
            if(y==3||y>n)  continue;
            printf("%d %d\n",n,i);
            printf("%d %d\n",2*n,y);
            break;
        } 
    }
    return 0;
}

Measured memory_bytes: 2304
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    int a,b;
    cin >> a >> b;
    string ans = "x";
    if(a + b == 15){
        ans = "+";
    }
    if(a * b == 15){
        ans = "*";
    }
    cout << ans << endl;
}


Measured memory_bytes: 3028
n=int(input())
a=[99,111,222,333,444,555,666,777,888,999,1000]
for i in range(len(a)-1):
    if n==a[i]:
        print(n)
        break
    if a[i]<n<a[i+1]:
        print(a[i+1])
        break

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

using i64 = long long;

const int N = 1e5 + 5;

vector<int> g[N];
int siz[N];
bool f[N], col[N];

i64 mono, ant, col1, col2; 
int n, m;

bool dfs(int u, int far = -1) {
	bool flag = false;

	siz[u] = 1;
	f[u] = true;

	for (auto v: g[u]) if (v != far) {
		if (!f[v]) {
			col[v] = !col[u];
			flag|= dfs(v, u);
			siz[u]+= siz[v]; }
		else
			flag|= col[u] == col[v]; }

	return flag; }

int main() {
#ifdef HOME
	freopen("agc11c.in", "r", stdin);
	freopen("agc11c.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int a, b, i = 0; i < m; ++i) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a); }

	for (int i = 1; i <= n; ++i) if (!f[i]) {
		if (dfs(i))
			++col1;
		else
			++col2;
		if (siz[i] == 1) {
			++mono;
			--col2; } }

	ant+= mono * mono;
	ant+= mono * (n - mono) * 2;
	ant+= col1 * col1;
	ant+= col1 * col2 * 2;
	ant+= col2 * col2 * 2;

	cout << ant << endl;

	return 0; }


Measured memory_bytes: 12032
#include<iostream>
using namespace std;
int main(){
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++){
	   cin>>a[i];
	}
	int m=0;
	int mx=0;
	for(int i=0;i<n-1;i++){
		if(a[i+1]<=a[i])m++;
		else{ mx= max(m,mx);
			   m=0;
		}
    }
    cout<<max(mx,m)<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int MAXN=200010;
long long n,k;
long long c[MAXN];
long long c2[MAXN];
void ext_gcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	ext_gcd(b,a%b,y,x);
	y-=x*(a/b);
	return;
}
inline long long inverse(long long a)
{
	long long x,y;
	ext_gcd(a,mod,x,y);
	if(x<0) x+=mod;
	return x;
}
long long ans=0;
int main()
{
	cin>>n>>k;
	k=min(k,n-1);
	c[0]=c2[0]=1;
	for(int i=1;i<=n;i++)
	c[i]=c[i-1]*inverse((long long)i),c[i]%=mod,c[i]*=(n-i+1),c[i]%=mod;
	for(int i=1;i<=n;i++)
	c2[i]=c2[i-1]*inverse((long long)i),c2[i]%=mod,c2[i]*=(n-i),c2[i]%=mod;
	for(int i=0;i<=k;i++) ans+=c[i]*c2[n-i-1],ans%=mod;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <queue>
#define N 100
using namespace std;

int color[N], d[N];
int M[N][N];


void bfs(int n) {
	queue<int> Q;
	d[0] = 0;
	for (int i = 1;i < n;i++) d[i] = -1;
	Q.push(0);
	color[0] = 1;
	while (!Q.empty()) {
	  for (int i = 0;i < n;i++)
		  if (M[Q.front()][i] == 1) {
			  if (color[i] == 0) {
				  d[i] = d[Q.front()] + 1;
				  color[i] = 1;
				  Q.push(i);
			  }
		  }
		  Q.pop();
	}
	for (int i = 0;i < n;i++)
		cout << i + 1 << " " << d[i] << endl;
}


int main() {
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		int u; cin >> u;
		int k; cin >> k;
		for (int j = 0;j < k;j++) {
			int v; cin >> v;
			M[u-1][v-1] = 1;
		}
	}

	bfs(n);

}

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

int main(){
    long long n, h;
    cin >> n >> h;
    vector<long long> swing(n);
    vector<long long> throwing(n);

    for(long long i = 0; i < n; i++) cin >> swing[i] >> throwing[i];

    sort(swing.begin(), swing.end(), greater<long long>());
    sort(throwing.begin(), throwing.end(), greater<long long>());

    long long cnt = 0;
    long long throwing_index = 0;

    while(throwing_index < n and h > 0 and throwing[throwing_index] > swing[0]){
        h -= throwing[throwing_index];
        cnt++;
        throwing_index++;
    }

    if(h <= 0){
        printf("%lld\n", cnt);
        return 0;
    }

    cnt += (h + swing[0] - 1) /swing[0];
    
    printf("%lld\n", cnt);
    return 0;
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(int i = 0; i <= 9; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            for(int k = 0; k <= 9; k++)
            {
                //check if ijk is possible
                bool check = false;
                bool flag = false;
                bool flag2 = false;
                bool flag3 = false;
                for(int cur = 0; cur < n; cur++)
                {
                    if(!flag && s[cur] - '0' == i)
                    {
                        flag = true;
                        continue;
                    }
                    if(flag)
                    {
                        if(!flag2 && s[cur] - '0' == j)
                        {
                            flag2 = true;
                            continue;
                        }
                        if(flag2)
                        {
                            if(!flag3 && s[cur] - '0' == k)
                            {
                                check = true;
                            }
                        }
                    }
                }
                if(check) ans++;
            }
        }
    }
    cout << ans << endl;
}


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

int main() {
	int n, m, a, b;
	vector<pair<ll, ll>> p;
	int count = 0;

	cin >> n >> m;

	vector<ll> v(n, 0);

	for(int i=0; i<m; i++){
		cin >> a >> b;

		p.push_back({ a, b });
	}

	sort(p.begin(), p.end());

	p.push_back({ -1, -1 });

	for (int i = 0; i < m; i++) {
		v[p[i].first - 1]++;
		v[p[i].second - 1]++;
	}

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}
}


Measured memory_bytes: 256
s=input()
ans=0
u=0
l=[0]*2019
l[0]=1
for i,n in enumerate(map(int,s)):
  u=(u+n*pow(10,len(s)-i,2019))%2019
  l[u]+=1
for i in l:
  ans+=i*(i-1)//2
print(ans)

Measured memory_bytes: 9196
#!/usr/bin/env python3
import sys


def check(N, M, ans):
    p = list(range(1, N+1))
    s = set()
    for _ in range(N):
        for a, b in ans:
            s.add((min(p.index(a), p.index(b)), max(p.index(a), p.index(b))))
        p = [p[-1]] + p[:-1]
    assert len(s) == N * M


def solve(N: int, M: int):
    ans = []
    i, j = 0, N + 1
    diffs = set()
    for _ in range(M):
        i += 1
        j -= 1
        while j - i == i + N - j or j - i in diffs or i + N - j in diffs:
            j -= 1
        diffs.add(j - i)
        diffs.add(i + N - j)
        ans.append((i, j))
    for a, b in ans:
        print(a, b)
    # check(N, M, ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


Measured memory_bytes: 102748
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vpii vector<pair<int,int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string> 
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g; }
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

int main()
{
	int n, m; cin >> n >> m;
	vi submit(n, 0);
	vb solved(n,false);
	rep(i, m)
	{
		int p;
		string s;
		cin >> p >> s;
		p--;
		if (s == "AC")solved[p] = true;
		if (s == "WA" && !solved[p])submit[p]++;
	}
	int ra = 0, pen = 0;
	rep(i,n)
	{
		if (solved[i])
		{
			ra++;
			pen += submit[i];
		}
	}
	co(ra << " " << pen);
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int X = in.nextInt();   // 整数
        int N = in.nextInt();   // 長さ
        int p[] = new int[N];
        for(int i=0; i<N; i++)
            p[i] = in.nextInt();
        int tmp = 0;

        for(int i=0; tmp==0; i++){
            tmp = 1;
            for(int j=0; j<N; j++){
                if( X-i == p[j]){
                    tmp = 0;
                }
            }
            if(tmp == 1){
                System.out.println(X-i);
                break;
            }
            tmp = 1;
            for(int j=0; j<N; j++){
                if( X+i == p[j]){
                    tmp = 0;
                }
            }
            if(tmp == 1){
                System.out.println(X+i);
                break;
            }
        }
    }
}

Measured memory_bytes: 35952
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007

//read question carefully!

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int ans = 0;
        if (n < 600)
        {
            ans = 8;
        }
        else if (n < 800)
        {
            ans = 7;
        }
        else if (n < 1000)
        {
            ans = 6;
        }
        else if (n < 1200)
        {
            ans = 5;
        }
        else if (n < 1400)
        {
            ans = 4;
        }
        else if (n < 1600)
        {
            ans = 3;
        }
        else if (n < 1800)
        {
            ans = 2;
        }
        else
            ans = 1;
        cout << ans << "\n";
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 2e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    LL n,k;
    cin>>n>>k;
    LL a[n];
    loop(i,0,n) cin>>a[i];

    LL b = 1, e = MX, mid, ans = -1, k1;
    while(b <= e)
    {
        mid = (b + e)/2;
        k1 = 0;
        loop(i,0,n)
        {
            k1 += (a[i]/mid);
            if(a[i] % mid == 0) --k1;
        }

        //watch(mid); watch(k1);

        if(k1 <= k) {ans = mid; e = mid - 1;}
        else b = mid + 1;
    }

    cout<<ans<<'\n';

    /*
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[n];
        loop(i,0,n)
        {
            cin>>a[i];
        }
    }
    */

    /*
    int n;
    cin>>n;
    int a[n];
    loop(i,0,n)
    {
        cin>>a[i];
    }
    */

    /*
    cout<<ans<<'\n';

    if(f) cout<<"YES\n";
    else cout<<"NO\n";

    if(f) cout<<"Yes\n";
    else cout<<"No\n";
    */

    return 0;
}


Measured memory_bytes: 5108