akhauriyash/Code-Regression huggingface dataset:
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 1000;
const int INF = 10000000;
typedef pair<int, int> P;
int h,w,n;
// 移動の4方向
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
// チーズ工場のマップ
short field[MAX][MAX];
// スタートから各点への最短距離
int d[MAX][MAX];
// 幅優先探索の関数の返り値用
typedef struct {
  int x;
  int y;
  int cnt;
} Cheeze;

// 地点(sx,sy)から目標地点（工場i）までの最短距離を求める幅優先探索
Cheeze bfs(int sx, int sy, char i) {
  // スタート地点は距離0
  d[sy][sx] = 0;
  queue<P> qu;
  qu.push(P(sx, sy));

  // 工場iに達するまで繰り返す
  while (true) {
    P p = qu.front();
    qu.pop();
    // ゴールなら終了
    if (field[p.second][p.first] == i) {
      Cheeze res = {p.first, p.second, d[p.second][p.first]};
      return res;
    }
    // 4方向
    for (int j = 0; j < 4; j++) {
      int nx = p.first + dx[j];
      int ny = p.second + dy[j];
      // 移動可能判定など
      if (nx >= 0 && nx < w && ny >= 0 && ny < h &&
          d[ny][nx] == INF && field[ny][nx] != -1) {
        qu.push(P(nx,ny));
        d[ny][nx] = d[p.second][p.first] + 1;
      }
    }
  }
}

int main() {
  // 入力
  int sx, sy;
  int cnt = 0;
  Cheeze cheeze;
  // ifstream ifs( "test.txt" );
  cin >> h >> w >> n;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      char cel;
      cin >> cel;
      if (cel == 'X') {
        field[i][j] = -1;
      } else if (cel == '.') {
        field[i][j] = 0;
      } else if (cel == 'S') {
        field[i][j] = 0;
        sx = j;
        sy = i;
      } else {
        field[i][j] = (short)(cel - '0');
      }
    }
  }

  // 計算
  for (int i = 1; i <= n; i++) {
    // 最短距離dの初期化
    for (int j = 0; j < MAX; j++) {
      for (int k = 0; k < MAX; k++) {
        d[j][k] = INF;
      }
    }
    cheeze = bfs(sx, sy, i);
    // スタート地点を更新
    sx = cheeze.x;
    sy = cheeze.y;
    cnt += cheeze.cnt;
  }

  // 出力
  cout << cnt << endl;
}

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

int main() {
  int64_t N,A,B,ans=0;
  cin >> N >> A >> B;
  ans=A*(N/(A+B));
  N-=(N/(A+B))*(A+B);
  if(N>A){
    ans+=A;
  }else{
    ans+=N;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
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<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Graph{
	public:
	int n;
	vvi g,rg;
	vi scc,used;
	stack<int> stc;
	void Order(int v){
		used[v]=1;
		for(auto u:g[v]) if(!used[u]) Order(u);
		stc.push(v);
	}
	void DFS(int v,int t){
		used[v]=1;
		for(auto u:rg[v]) if(!used[u]) DFS(u,t);
		scc[v]=t;
	}
	int SCC(){
		scc=used=vi(n);
		rg=vvi(n);
		for(int i=0;i<n;i++){
			if(!used[i]) Order(i);
			for(auto v:g[i]) rg[v].push_back(i);
		}
		int t=0;
		used=vi(n);
		while(!stc.empty()){
			int v=stc.top();
			stc.pop();
			if(!used[v]) DFS(v,t++);
		}
		return t;
	}
	Graph(int v){
		n=v;
		g=vvi(v);
	}
	void add_edge(int s,int t){
		g[s].push_back(t);
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		int n;
		cin>>n;
		if(n==0) break;
		vs a(n);
		for(int i=0;i<n;i++) cin>>a[i];
		bool B=0;
		Graph g(26);
		for(int i=1;i<n;i++){
			int s=a[i-1].size(),s1=a[i].size();
			bool flag=0;
			for(int j=0;j<min(s,s1);j++) if(a[i-1][j]!=a[i][j]){
				g.add_edge(a[i-1][j]-'a',a[i][j]-'a');
				flag=1;
				break;
			}
			if(!flag&&s>s1) B=1;
		}
		if(B){
			cout<<"no"<<endl;
			continue;
		}
		if(g.SCC()<26) cout<<"no"<<endl;
		else cout<<"yes"<<endl;
	}
}


Measured memory_bytes: 3252
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


vector<int> dijkstra(vector<vector<P> > G,int start){
  int n = G.size();
  vector<int> D(n,INF);
  vector<int> visited(n,0);
  priority_queue<P,vector<P>,greater<P> > Q;
  Q.push(P(0,start));
  D[start] = 0;
  while(!Q.empty()){
    int cost,pos; tie(cost,pos) = Q.top(); Q.pop();
    if(visited[pos]++) continue;

    for(auto p:G[pos]){
      int to = p.first;
      int ncost = cost + p.second;
      if(D[to] <= ncost) continue;
      D[to] = ncost;
      Q.push(P(ncost,to));
    }
  }
  return D;
}

int dijkstra(vector<vector<P> > G,int start,vector<int> DU,vector<int> DV){
  int n = G.size();
  vector<int> D(n,INF);
  vector<int> visited(n,0);
  priority_queue<P,vector<P>,greater<P> > Q;
  Q.push(P(DU[start],start));
  D[start] = DU[start];
  int res = INF;
  while(!Q.empty()){
    int cost,pos; tie(cost,pos) = Q.top(); Q.pop();
    if(D[pos] < cost) continue;
    
    Min(res, cost + DV[pos]);
    for(auto p:G[pos]){
      if(p.second) continue;
      int to = p.first;
      int ncost = min(cost,DU[to]);
      if(D[to] <= ncost) continue;
      D[to] = ncost;
      Q.push(P(ncost,to));
    }
  }
  return res;
}

signed main(){
  int n,m;
  cin>>n>>m;
  int s,t;
  cin>>s>>t; s--,t--;
  int u,v;
  cin>>u>>v; u--,v--;
  
  vector<vector<P> > G(n);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c; a--,b--;
    G[a].push_back(P(b,c));
    G[b].push_back(P(a,c));
  }

  auto DS = dijkstra(G,s);
  auto DT = dijkstra(G,t);
  auto DU = dijkstra(G,u);
  auto DV = dijkstra(G,v);
  
  for(int i=0;i<n;i++)
    for(auto &p:G[i]) {
      int a = i;
      int b = p.first;
      int c = p.second;
      if(DS[a] + c + DT[b] == DS[t]) p.second = 0;
    }

  int a = DU[v];
  int b = dijkstra(G,s,DU,DV);
  int c = dijkstra(G,s,DV,DU);
  int ans = min({a,b,c});
  cout<<ans<<endl;
  
  
  return 0;
}



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

//define gcd and lcm (using 64bit)
ll gcd(ll a,ll b){
    if (a < b) {
        //^はxor(bitwise operator)。以下三行でswap(a,b)を行っている。
        a ^= b;
        b ^= a;
        a ^= b;
    }
    //only when b==0,this program finds that b means false and returns a.
    return b ? gcd(b, a % b) : a;
}

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


int main(){
    int k,x;
    cin>>k>>x;
    rep(i,(2*k-1)){
        cout<<(x-k+1+i)<<endl;
    }
    return 0;
}

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

int main()
{
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; ++i) cin >> a[i];
	
	bool b[n];
	
	for (int i = 0; i < n; ++i)
	{
		if (a[i] % 2 == 0)
		{
			if ((a[i] % 3 == 0) || (a[i] % 5 == 0))
			{
				b[i] = true;
			}
			else
			{
				b[i] = false;
			}
		}
		else
		{
			b[i] = false;
		}
	}
	
	for (int i = 0; i < n; ++i)
	{
		if ((a[i] % 2 == 0) && (b[i] == false))
		{
			cout << "DENIED" << endl;
			return 0;
		}
	}
	
	cout << "APPROVED" << endl;
	
	return 0;
}


Measured memory_bytes: 256
a3 = """
aab
b.b
baa
"""
a6 = """
aabccd
b.bd.d
baadcc
ccdaab
d.db.b
dccbaa
"""

g4 = """
aaca
bbca
cabb
cacc
"""

g4 = list(map(list, g4.split()))

g5 = """
aabba
bcc.a
b..cb
a..cb
abbaa
"""

g5 = list(map(list, g5.split()))

g7 = """
caabb..
cb..cc.
aba....
a.a..aa
c..a..b
c..a..b
.aaccaa
"""

g7 = list(map(list, g7.split()))

def main():
    N = int(input())
    if N == 2: print(-1)
    elif N == 3: print("\n".join(a3.split()))
    elif N == 6: print("\n".join(a6.split()))
    else:
        x = [['.']*N for i in range(N)]
        for v4 in range(N//4+1):
            for v5 in range((N-v4*4)//5+1):
                v7 = (N-v4*4-v5*5)//7
                if v4*4+v5*5+v7*7 != N: continue

                idx = 0
                for i in range(v4):
                    for j in range(4):
                        x[idx+j][idx:idx+4] = g4[j]
                    idx += 4
                

                for i in range(v5):
                    for j in range(5):
                        x[idx+j][idx:idx+5] = g5[j]
                    idx += 5
                

                for i in range(v7):
                    for j in range(7):
                        x[idx+j][idx:idx+7] = g7[j]
                    idx += 7

                for q in x:
                    print(''.join(q))
                
                return

if __name__ == '__main__':
    main()

Measured memory_bytes: 11892
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <time.h>
using namespace std;

int main(){
	int N, A, B;
	cin >> N >> A >> B;

	int a, b;

	a = min(A, B);
	b = (A + B) - N;
	if (b < 0)
		b = 0;

	cout << a << " " << b << endl;

	return 0;
}

Measured memory_bytes: 256
S = input()
l = 0
r = len(S) - 1
ans = 0
while l < r:
  if S[l] == S[r]:
    l += 1
    r -= 1
  elif S[l] == "x":
    l += 1
    ans += 1
  elif S[r] == "x":
    r -= 1
    ans += 1
  else:
    print(-1)
    break
else:
  print(ans)

Measured memory_bytes: 3316
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	
	while(true){
		int B,R,G,C,S,T;
		scanf("%d%d%d%d%d%d",&B,&R,&G,&C,&S,&T);
		if(T==0)break;
		T-=S;
		int ans=100;
		ans+=77*B;
		T-=6*B;
		ans+=51*R;
		T-=4*R;
		ans+=4*G;
		T-=G;
		ans-=C;
		T-=C;
		ans-=3*T;
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1188
def find_max( list ):
    x = 0
    x2 = 0
    x_i = 0
    x2_i = 0
    for i in range( len(list) ):
        if x < list[i]:
            x = list[i]
            x_i = i
    for i in range( len(list) ):
        if i == x_i:
            continue
        if x2 < list[i] <= x:
            x2 = list[i]
            x2_i = i
    return x,x2,x_i,x2_i

n = int( input() )
v = list ( int(x) for x in input().split() )

v_sort = sorted( v )

v_odd = [ 0 for i in range( v_sort[-1] + 1 ) ]
#奇数
v_eve = [ 0 for i in range( v_sort[-1] + 1 ) ]
#偶数
for i in range( n ):
    if i % 2 == 0:
        v_eve[ v[i] ] += 1
    if i % 2 == 1:
        v_odd[ v[i] ] += 1

vex,vex2,vex_i,vex2_i = find_max( v_eve )
vox,vox2,vox_i,vox2_i = find_max( v_odd )

ok = 0
# ok: figure that need not to fix
if vex_i != vox_i:
    ok = vex + vox
else:
    ok = max( vex + vox2 , vex2 + vox )

ans = n - ok
print( ans )

Measured memory_bytes: 21292
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using std::vector;
using std::printf;
using std::cout;
using std::endl;
using std::string;
using std::cin;
using std::pair;
using std::sort;

#define i64t long long int
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

template<typename T>
void dump(vector<T> vec) {
    for (auto x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// ---------------------------

const i64t MOD = 1000000007;

int main() {
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> A(Q, 0);
    for (int i = 0; i < Q; ++i) {
        cin >> A[i];
    }

    // printf("%d %d %d", N, K, Q);
    // dump<int>(A);

    vector<int> P(N+1, K-Q);

    for (int q = 0; q < Q; ++q) {
        P[A[q]] += 1;
    }

    for (int i = 1; i <= N; ++i) {
        if (P[i] > 0) {
            printf("Yes");
        }
        else {
            printf("No");
        }
        if (i != N) {
            printf("\n");
        }
    }

    // dump<int>(P);
}

Measured memory_bytes: 1408
from collections import defaultdict
dic = defaultdict(int)
w = input()
for i in range(len(w)):
    dic[w[i]] += 1

flag = True
for v in dic.values():
    if v % 2 != 0:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")
    

Measured memory_bytes: 3316
n,m=map(int,input().split())

ans=[[] for i in range(m)]
p_list=[[] for i in range(n+1)]

for i in range(m):
 p,y=map(int,input().split())

 ans[i]=str(p).zfill(6)

 p_list[p].append([i,y])

for pp in p_list:
 pp=sorted(pp,key=lambda x:x[1])
 num=0
 for ppp in pp:
  num+=1
  ans[ppp[0]]+=str(num).zfill(6)
 num=0

for i in ans:
 print(i)

Measured memory_bytes: 44112
use std::cmp;

pub struct Scanner{
    line : Vec<String> ,
    idx : usize
}

impl  Scanner{
   #[allow(dead_code)]
   fn new() -> Scanner{
       return Scanner{ line: vec![], idx : 0}
   }
   #[allow(dead_code)]
   fn next<T: std::str::FromStr> (&mut self) -> T{
       if self.idx == self.line.len() {
           let mut buffer = String::new();
           std::io::stdin().read_line(&mut buffer).ok();

           let a : Vec<&str>  = buffer.trim().split(' ').collect();
           self.line = a.iter().map(|&s| String::from(s)).collect();
           self.idx = 0;
       }
       let ret : T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
       self.idx += 1;
       ret
   }
}


fn main() {
    let mut scan = Scanner::new();
    let n:usize  = scan.next();
    let x:i32  = scan.next();
    let y:i32  = scan.next();
    let mut v : Vec<i32>= Vec::with_capacity(n);
    for _ in (0..n){
        v.push(0);
    }

    for a in (0..n){
        for b in (a+1..n){
            let i : i32 = a as i32;
            let j : i32 = b as i32;
            let mut d : i32 = j - i;
            d = cmp::min(d, (i - (x - 1)).abs() + 1 + (j - (y - 1)).abs());
            v[d as usize] += 1;
        }
    }

    for k in (1..n){
        println!("{}", v[k]);
    }
}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstring>

const int N = 1e5 + 10;
int n, cnt;
char s[N];

int main() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 1; i < n; i++)
        if (s[i] != s[i - 1])
            cnt++;
    printf("%d\n", cnt);
    return 0;
}



Measured memory_bytes: 256
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
#define debegin printf("debug\nbegin\n")
#define deend printf("debug\nend\n")
#define isfind printf("find\n")
template<class T>inline void rread(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************	
const int maxn=1e5+5;
int n;
ll A,B;
ll a[maxn],b[maxn];
bool check(ll T){
	rep(i,1,n)b[i]=a[i]-B*T;
	ll cnt=0;
	rep(i,1,n)if(b[i]>0)cnt+=(b[i]+(A-B)-1)/(A-B);
	return cnt<=T;
}
int main(){
	rread(n);rread(A);rread(B);
	rep(i,1,n)rread(a[i]);
	ll l=1,r=1e9,ans=1e9;
	while(l<=r){
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
import java.math.*

fun main(args: Array<String>) {
    val N = readInputLine().toLong()

    var ans = Int.MAX_VALUE

    for (i in LongRange(1L, Math.ceil(Math.sqrt(N.toDouble())).toLong())) {
        if (N % i != 0L) {
            continue
        }
        ans = Math.min(ans, countDigits(N / i))
    }

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}

fun countDigits(i: Long): Int {
    var ans = 0
    var tmp = i
    while (tmp != 0L) {
        ans++
        tmp /= 10L
    }
    
    return ans
}


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

int main(){
    long long n, a, b;
    cin >> n >> a >> b;
    if (a > b){
        cout << 0 << endl;
        return 0;
    }
    if (n == 1) {
        if (a != b) cout << 0 << endl;
        else cout << 1 << endl;
        return 0;
    }
    cout << (b - a) * (n - 2) + 1 << endl;
}

Measured memory_bytes: 256
N , A , B = map(int,input().split())
count = 0 
for i in range(N):
    stri =  str(i+1)
    num = 0 
    for i2 in range(len(stri)):
        num += int(stri[i2])
    if A <= num and B >= num:
        count += i+1 
print(count)


Measured memory_bytes: 2940
# coding: utf-8
# Your code here!

while True:
   try:
      s = input()
      
      Jc = 0
      Ic = 0
      for i in range(len(s) - 2):
         if s[i] == "J" and s[i + 1] == "O" and s[i + 2] == "I":
            Jc += 1
         if s[i] == "I" and s[i + 1] == "O" and s[i + 2] == "I":
            Ic += 1
      print(Jc)
      print(Ic)

   except EOFError:
      break



Measured memory_bytes: 5576
/*
 		Resilience is the greatest of all virtues.
 		Code by rajiv
 */
 #include <iostream>
 #include <cstring>
 #include <vector>
 #include <map>
 #include <set>
 #include <stack>
 #include <queue>
 #include <deque>
 #include <sstream>
 #include <iomanip>
 #include <cassert>
 #include <sys/time.h>
 #include <algorithm>
 #include <bitset>
 #include <cmath>
 #include <functional>
 #include <cmath>
 #include <climits>

 using namespace std ;

 #define xx first
 #define yy second
 #define ll long long
 #define ld long double
 #define el (char)0x0A
 #define sp " "
 #define pb push_back
 #define mp make_pair
 #define all(x) (x).begin(),(x).end()
 #define clr(x) memset((x),0,sizeof(x))
 #define uint unsigned int
 #define abs(x) ((x<=0)?(-x):(x))
 #define CASET  int t;cin>>t;while(t--)
 #define FORN(i,x,y) for(int i=x;i<y;i++)
 #define MAXN 100005
 #define INF 10000000010
 #define MOD 1000000007
 #define last_set_bit(x) log2((x)&(-x))
 #define add(x,y) (x)=((x)+(y))%MOD
 #define PI 3.141592653589793

 typedef pair<int,int> PII ; typedef vector<int> VI ; typedef vector<vector<int> > VVI ; typedef vector<bool> VB ; typedef vector<string> VS ;
 typedef map<int,int> MII ; typedef map<int,VI > MIV ; typedef set<int> SI ; typedef set<PII > SPII ; typedef vector<PII > VPII ; typedef vector<VPII > VVPII ;
 const int N = 100050 ;

int main(){
    int n , m ; cin >> n >> m ;
    int a[m] ;
    memset(a, 0, sizeof a) ;
    for(int i = 0 ; i < n ; i++){
        int k ; cin >> k ;
        for(int j = 0 ; j < k ; j++){
            int x ; cin >> x ; x-- ;
            a[x]++ ;
        }
    }
    int cnt = 0 ;
    for(int i = 0 ; i < m ; i++){
        cnt += (a[i]==n)?1:0 ;
    }
    cout << cnt << el ; 
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void) {
  int K;
  char S[101];
  scanf("%d", &K);
  scanf("%s", S);
  int len = strlen(S);
 
  if (len <= K) {
    printf("%s\n", S);
  } else {
    for (int i = 0; i < K; i++) {
      printf("%c", S[i]);
    }
    printf("...\n");
  }
  return 0;
}

Measured memory_bytes: 1640
n,ais = int(raw_input()), map(int, raw_input().split())
ais.sort(key = lambda x:-x)
n -=2
s = 0
s += ais[0]
i = 1
while(n):
	s += ais[i]
	n-=1
	if n:
		s += ais[i]
		n -=1
	i+=1

print s


Measured memory_bytes: 103100
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

num = [9, 0, 900, 0, 90000]

def main():
    n = ri()
    ans = 0
    for d in range(6):
        m = pow(10, d+1)
        if n < m:
            if d % 2 == 0:
                ans += n%m - (m//10-1)
            break
        else:
            ans += num[d]
    print(ans)


if __name__ == '__main__':
    main()


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

vector <int> asd[100005];
bool visit[100005];
int ans[100005];

void dfs(int a)
{
	visit[a]=true;
	int e=asd[a].size();
	for(int q=0;q<e;q++)
	{
		if(visit[asd[a][q]]==false)
		{
			dfs(asd[a][q]);
			ans[a]=max(ans[a],1+ans[asd[a][q]]);
		}
		else
		{
			ans[a]=max(ans[a],1+ans[asd[a][q]]);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int z,x;
	cin>>z>>x;
	int a,s;
	while(x--)
	{
		cin>>a>>s;
		asd[a].push_back(s);
	}
	int d=0;
	for(int q=1;q<=z;q++)
	{
		if(visit[q]==false)
		{
			dfs(q);
		}
//		if(ans[q]>d)cout<<q<<"  asdasd"<<endl;
		d=max(d,ans[q]);
	}
	cout<<d<<endl;
}

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

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) i64((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

int main(int argc, char *argv[]) {
  i64 H1, W1, H2, W2;
  const i64 NUM = 998244353LL;
  cin >> H1 >> W1 >> H2 >> W2;

  vvi A(H2+1, vi(W2+1, 0));
  i64 h, w;
  A[H1][W1] = 1;
  REP(W1+1, W2+1, w) {
    A[H1][w] = (A[H1][w-1] * H1) % NUM;
  }
  
  REP(H1+1, H2+1, h) {
    A[h][W1] = (A[h-1][W1] * W1) % NUM;
    REP(W1+1, W2+1, w) {
      i64 v1 = (A[h-1][w] * w) % NUM;
      i64 v2 = (A[h][w-1] * h) % NUM;
      i64 v3 = (((A[h-1][w-1] * (h - 1)) % NUM) * (w - 1)) % NUM;
      //cout << v1 << " " << v2 << " " << v3 << endl;
      
      A[h][w] = v1 + v2 - v3 + NUM;
      A[h][w] %= NUM;
    }
  }

  /*
  REP(0, H2+1, h) {
    REP(0, W2+1, w) {
      cout << A[h][w] << " ";
    }
    cout << "\n";
  }
  */
  cout << A[H2][W2] << endl;

  return 0;
}


Measured memory_bytes: 73648
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

x = inp()
dp = []
for i in range(5000):
    dp.append(i**5)

for i in range(5000):
    if (x - dp[i]) in dp:
        print(i,-1 * dp.index((x - dp[i])))
        exit()
    if (dp[i] - x) in dp:
        print(i,dp.index((dp[i] - x)))
        exit()

Measured memory_bytes: 31328
n, m = map(int, input().split())

city = []
for i in range(m):
    p, y = map(int, input().split())
    city.append([p, y, i])

cityN = [ [] for i in range(n)]
for i in city:
    cityN[i[0]-1].append(i)

for i in range(n):
    if len(cityN[i])>1:
        cityN[i] = sorted(cityN[i], key=lambda x: x[1])
    for j,li in enumerate(cityN[i]):
        li.append(j)

city = []
for i in range(n):
    city.extend(cityN[i])

city = sorted(city, key=lambda x: x[2])

for i in city:
    print(str(i[0]).rjust(6, "0") + str(i[3]+1).rjust(6, "0"))






Measured memory_bytes: 40328
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef vector<long long> vll;
int main(){
  ll n,cnt=0;cin >> n;
  vll a(n),b(n);
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  rep(i,n){
	ll x = b[i] - a[i];
    if(x < 0) cnt += x;
    else cnt += x/2;
  }
  if(cnt<0) puts("No");
  else puts("Yes");
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    string S;
    cin >> S;
    ll count = 0;
    rep(i,N){
        if (S[i] == 'R') count++;
    }
    ll ans = 0;
    rep(i,count){
        if (S[i] == 'W') ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3748
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, init, n) for(int i = init; i <(int)(n); i++)

int main() {

    string s;
    cin >> s;
    int n = s.size();
    char c;
    int ans = 0;
    if (n % 2 == 0){
        c = s[n / 2];
        int i = 1;
        while(i <= n / 2 && s[n / 2 - i] == c && s[n / 2 - 1 + i] == c) i++;
        i--;
        ans = (n / 2) + i;
    }else{
        c = s[n / 2];
        int i = 0;
        while(i <= n / 2 && s[n / 2 - i] == c && s[n / 2 + i] == c) i++;
        i--;
        ans = (n / 2) + 1 + i;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    # N, M = get_inputs(int)
    # if N == M:
    #     print('Yes')
    # else:
    #     print("No")
    a, b = get_inputs(int)
    A = str(a)*b
    B = str(b) * a
    if A < B:
        print(A)
    else:
        print(B)

    return


if __name__ == '__main__':
    main()


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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v, n) sort(v, v+n)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define ddvi vector<vector<int>>

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

template< typename T >
struct BIT {
  vector< T > data;

  BIT(int sz) {
	data.assign(++sz, 0);
  }

  T sum(int k) {
	T ret = 0;
	for(++k; k > 0; k -= k & -k) ret += data[k];
	return (ret);
  }

  void add(int k, T x) {
	for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
// ここに処理を記述

	ll N;
	ll P[8], Q[8];

	cin >> N;

	REP(i,N){
		cin >> P[i];
	}
	
	REP(i,N){
		cin >> Q[i];
	}

	ll fact[8] = {0,0,0,0,0,0,0,0};
	fact[0] = 1;
	REP(i,7){
		fact[i+1] = fact[i]*(i+1);
		// cout << fact[i+1] << " ";
	}
	// cout << "\n";

	BIT<int> P_b(8);
	BIT<int> Q_b(8);

	ll p_ind = 0;
	ll q_ind = 0;

	REP(i,N) {
		// factorialは計算済みとする
		p_ind += ((P[i]-1) - P_b.sum(P[i]-1)) * fact[N-i-1];
		P_b.add(P[i], 1);
		// cout << p_ind << " ";
	}
	p_ind++;

	// cout << "\n" << p_ind << "\n";

	REP(i,N) {
		// factorialは計算済みとする
		q_ind += ((Q[i]-1) - Q_b.sum(Q[i]-1)) * fact[N-i-1];
		Q_b.add(Q[i], 1);
	}
	q_ind++;

	// cout << q_ind << "\n";

	cout << abs(p_ind - q_ind) << "\n";

return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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 (b<a) { a=b; return 1; } return 0; }

int N;
double sum,a;

int main(){
    cin>>N;
    rep(i,N){
        cin>>a;
        sum+=1/a;
    }
    out(1/sum);

    
    
}


Measured memory_bytes: 256
#include <cstdio>
const int N=100005;
bool vis[N];int cnt[N];
int main (){
    int n,m;scanf ("%d%d",&n,&m);vis[1]=true;
    for (int i=1;i<=n;i++) cnt[i]=1;
    for (int i=1,x,y;i<=m;i++){
        scanf ("%d%d",&x,&y);
        vis[y]|=vis[x],cnt[x]--,cnt[y]++;
        if (cnt[x]==0) vis[x]=false;
    }
    int ans=0;for (int i=1;i<=n;i++) ans+=vis[i];
    printf ("%d",ans);
    return 0;
}

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

#define sf scanf
#define pf printf
#define pfn printf("\n");
#define pfk printf(" ");
#define pf0 printf("0");
#define pf1 printf("1");
#define ll long long
#define sfd(n) scanf("%d",&n);
#define sfdd(n,m) scanf("%d%d",&n,&m);
#define sfld(n) scanf("%lld",&n);
#define sfldd(n,m) scanf("%lld%lld",&n,&m);
#define sflf(n) scanf("%lf",&n);
#define sflff(n,m) scanf("%lf%lf",&n,&m);
#define sfc(n) scanf("%c",n);
#define sfcc(n,m) scanf("%c%c",n,m);
#define sfs(n) scanf("%s",n);
#define sfss(n,m) scanf("%s%s",n,m);
#define pfd(n) printf("%d",n);
#define pfld(n) printf("%lld",n);
#define pflf(n) printf("%lf",n);
#define pfc(n) printf("%c",n);
#define pfs(n) printf("%s",n);

#define csh(a,n) memset(a,n,sizeof(a));
int main()
{
    string a;
    cin>>a;
    int sum=0;
    for(int i=0;i<a.size()/2;i++){
    	if(a[i]!=a[a.size()-i-1]){
    		sum++;
		}
	}
	cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
// Problem : B - Minor Change
// Contest : AtCoder - AtCoder Beginner Contest 172
// URL : https://atcoder.jp/contests/abc172/tasks/abc172_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

void solve(){
    string s,t;
    cin>>s>>t;
    int cnt = 0;
    for(int i=0;i<sz(s);i++){
        if(s[i] != t[i]) cnt++;
    }
    cout<<cnt<<endl;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

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

typedef uint32_t u32;
typedef uint64_t u64;
typedef std::pair<int, int> pii;

int main() {

  for(;;) {
    int res = 0;
    int n;
    int a[16][6];
    std::cin >> n;
    if( n == 0 ) break;
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < 5; ++j) {
        std::cin >> a[n - i - 1][j];
      }
    }
    for(int t = 0; t < 100; ++t) {
      for(int i = 0; i < n; ++i) {
        if( a[i][0] == a[i][1] and a[i][1] == a[i][2] and a[i][2] == a[i][3] and a[i][3] == a[i][4] ) {
          res += a[i][0] * 5;
          a[i][0] = a[i][1] = a[i][2] = a[i][3] = a[i][4] = 0;
        }
        for(int j = 0; j < 2; ++j) {
          if( a[i][j] == a[i][j + 1] and a[i][j + 1] == a[i][j + 2] and a[i][j + 2] == a[i][j + 3] ) {
            res += a[i][j] * 4;
            a[i][j] = a[i][j + 1] = a[i][j + 2] = a[i][j + 3] = 0;
          }
        }
        for(int j = 0; j < 3; ++j) {
          if( a[i][j] == a[i][j + 1] and a[i][j + 1] == a[i][j + 2] ) {
            res += a[i][j] * 3;
            a[i][j] = a[i][j + 1] = a[i][j + 2] = 0;
          }
        }
      }
      for(int j = 0; j < 5; ++j) {
        for(int k = 0; k < 10; ++k) {
          for(int i = 0; i < n - 1; ++i) {
            if( a[i][j] == 0 and a[i + 1][j] != 0 ) {
              a[i][j] = a[i + 1][j];
              a[i + 1][j] = 0;
            }
          }
        }
      }
    }
    std::cout << res << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 3072
A,B,C,X,Y=map(int,input().split())
l=[[A,X],[B,Y]]
l.sort(key=lambda x:x[1], reverse=True)
#print(l)
if (A+B)>2*C:
    l[0][1]=l[0][1]-min(X,Y)
    l[1][1]=l[1][1]-min(X,Y)
    if l[0][1]*l[0][0]<C*2*l[0][1]:
        print(2*C*min(X,Y)+l[0][1]*l[0][0])
    else:
        print(2*C*max(X,Y))
else:
    print(A*X+B*Y)




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

// from https://atcoder.jp/contests/abc138/submissions/7013118
#define sz(x) int(x.size())


int main(){
    string s,t;
    cin >> s>>t;
    int n=sz(s),m=sz(t);
    vector<vector<int>> is(26);
    for (int i=0;i<n;i++) is[s[i]-'a'].push_back(i);
    for (int i=0;i<n;i++) is[s[i]-'a'].push_back(i+n);
    long long ans=0;
    int p=0;
    for (int i=0;i<m;i++) {
        int c=t[i]-'a';
        if (sz(is[c])==0) {
            puts("-1");
            return 0;
        }
        p=*lower_bound(is[c].begin(), is[c].end(),p)+1;
        if(p>=n){
            p-=n;
            ans+=n;
        }
    }
    ans+=p;
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 1724
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(){

	int N;
	cin >> N;
	std::vector<int > W(N);

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

	std::vector<int> sum(N);
	sum[0] = W[0];
	for (int i = 1; i < N; i++)
	{
		sum[i] = sum[i-1] + W[i];
	}
	int s1,s2;
	int ans = 1000;

	for (int i = 0; i < N; i++)
	{
		s1 = sum[i];
		s2 = sum[N-1]-s1;
		ans = min(ans,abs(s1-s2));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]
cum_A = [0] * N
cum_A[0] = A[0]
for i in range(1, N):
    cum_A[i] = cum_A[i - 1] + A[i]

ans = 0
for i in range(N - 1):
    inner_sum = cum_A[-1] - cum_A[i]
    ans += A[i] * inner_sum

print(ans % (10**9 + 7))


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

typedef long long lli;

const int MAX = 300;
const lli INF = 1LL << 59;
int n;
lli v[MAX];

lli calc(int a1, int a2, int b1, int b2){
  lli res = 0;
  int a = 0, b = 0, c = 0;
  for(int i=a1;i<=a2;i++) a += v[i];
  for(int i=b1;i<=b2;i++) b += v[i];

  while(a > 0 || b > 0){
    int x = a % 10, y = b % 10;
    a /= 10;
    b /= 10;
    res += x * y + c;
    // cout << x << ' ' << y << ' ' << c << " : ";
    c = (x + y + c >= 10);
    //cout << c << endl;
  }
  res += c;

  return res;
}

void solve(){
  lli dp[MAX][MAX];

  fill(dp[0],dp[MAX],INF);
  for(int i=0;i<n;i++) dp[i][i] = 0;

  for(int k=2;k<=n;k++){
    for(int i=0;;i++){
      int j = i + k - 1;
      if(j >= n) break;
      for(int l=i;l<j;l++){
        dp[i][j] = min(dp[i][j], dp[i][l] + dp[l+1][j] + calc(i,l,l+1,j));
      }
    }
  }

  assert(dp[0][n-1] < INF);
  cout << dp[0][n-1] << endl;
}

int main(){
  while(cin >> n){
    for(int i=0;i<n;i++) cin >> v[i];
    solve();
  }
}

Measured memory_bytes: 1868
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp5
{

    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String S = Console.ReadLine();
            String[] line = S.Split(' ');
            double [] A = new double[N];
            double sum = 0;

            for(int i=0; i<N; i++)
            {
                A[i] = int.Parse(line[i]);
                sum = sum + 1 / A[i];
            }

            double ans = 1 / sum;
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
#include <stack>
#include <functional>
#include <queue>
using namespace std;
#define int long long

signed main()
{
    {
        if (fopen("input.txt", "r")) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }

    int h, n;
    cin >> h >> n;
    int s = 0;
    for (int i = 0; i != n; ++i) {
        int a;
        cin >> a;
        s += a;
    }
    if (s >= h)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int n,m,C;
vector<pi> g[111];
int dist[111][111];

typedef pair<int,pi> tri;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	while(cin>>n>>m>>C && n){
		rep(i,n)g[i].clear();
		rep(i,m){
			int f,t,c;
			cin>>f>>t>>c;
			f--;t--;
			g[f].pb(mp(t,c));
		}
		priority_queue<tri,vector<tri>,greater<tri>> Q;
		rep(i,n)rep(j,n)dist[i][j] = INF;
		dist[0][0] = 0;
		Q.push(mp(0,mp(0,0)));
		while(sz(Q)){
			tri tr = Q.top(); Q.pop();
			int d = tr.fir, v = tr.sec.fir, t = tr.sec.sec;
			if(d > dist[v][t])continue;
			rep(i,sz(g[v])){
				int to = g[v][i].fir;
				int cost = g[v][i].sec;
				if(d + cost < dist[to][t]){
					dist[to][t] = d + cost;
					Q.push(mp(d+cost, mp(to,t)));
				}
				if(t<n-1 && d < dist[to][t+1]){
					dist[to][t+1] = d;
					Q.push(mp(d, mp(to,t+1)));
				}
			}
		}
		rep(i,n)if(dist[n-1][i] <= C){
			cout<<i<<endl; break;
		}
	}
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a,b;
    int count = 0,flag = 0;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        if(a == b) count ++;
        else count = 0;
        if(count == 3) flag = 1;
    }
    if(flag == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3632
import itertools

a=[int(input()) for j in range(5)]
#print(a)

x=list(itertools.permutations(a))
#print(x)

def cal(b,c):
  if b <= c:
    return c
  else:
    c+=10
    return cal(b,c)
  
a=x[0]  
time1=cal(a[0],0)
time2=cal(time1+a[1],0)
time3=cal(time2+a[2],0)
time4=cal(time3+a[3],0)
time5=time4+a[4]
#print(time5)
ans=100000000  
for i in range(len(x)):
  time1=cal(x[i][0],0)
  time2=cal(time1+x[i][1],0)
  time3=cal(time2+x[i][2],0)
  time4=cal(time3+x[i][3],0)
  time5=time4+x[i][4]

  if ans > time5:
    ans=time5
    
print(ans)

Measured memory_bytes: 3064
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
p = list(map(int, input().split()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
groups = {}
for i in range(n):
    x = union_find.find(i)
    if x not in groups:
        groups[x] = []
    groups[x].append(i)

for k, v in groups.items():
    idx_set = set(v)
    ps_set = set([p[i]-1 for i in v])
    res += len(idx_set-ps_set)
print(n-res)



Measured memory_bytes: 29408
from collections import defaultdict

n=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
L=defaultdict(int)

def soinsu(n):
	l=defaultdict(int)
	for j in range(2,int(n**0.5)+1):
		while n%j==0:
			l[j]+=1
			n//=j
	if l=={}:
			l[n]+=1
	else:
		if n!=1:
			l[n]+=1
	for k,v in l.items():
		L[k]=max(L[k],v)

for i in range(n):
	soinsu(A[i])

LM=1
for k,v in L.items():
	LM*=k**v
	LM%=MOD

r=0
for i in range(n):
	r+=LM*pow(A[i],MOD-2,MOD)
	r%=MOD
print(r)

Measured memory_bytes: 4852
#include <stdio.h>
int main(void){
    int a, b, ans = 0;
    
    scanf("%d %d", &a, &b);
    
    if(b%a != 0){
        ans = b - a;
    }else if(b%a == 0){
        ans = a + b;
    }
    
    printf("%d\n", ans);
    
}


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

#define int             long long int
#define ff              first
#define ss              second
#define pb              push_back

#define vi              vector <int>
#define pii             pair <int, int>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))

#define endl            "\n"
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl



template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 3000005;
vi a;
int n, k;

bool check(int len)
{
	int cnt = 0;
	loop(i, 0, n)
	{
		int x = a[i] / len;
		if (a[i] % len == 0) cnt += (x - 1);
		else cnt += x;
	}
	if (cnt <= k) return true;
	else return false;
}


void solve()
{
	cin >> n >> k;
	a.resize(n);
	loop(i, 0, n) cin >> a[i];
	int ans;
	int s = 1, e = 1e9 + 5;
	while (s <= e)
	{
		int mid = s + (e - s) / 2;
		if (check(mid))
		{
			ans = mid;
			e = mid - 1;
		}
		else s = mid + 1;
	}
	cout << ans << endl;

	return;
}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt",  "r",  stdin);
	freopen("output.txt", "w", stdout);
#endif

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

	return 0;
}

Measured memory_bytes: 4784
#include  <stdio.h>

int max(int x, int y) {
	return x > y ? x : y;
}
int min(int x, int y) {
	return x < y ? x : y;
}


int main() {
	int N, M;
	int i, j;
	int L[100000];
	int R[100000];
	int maxL = 1;
	

	scanf("%d %d", &N, &M);
	int minR = N;
	for (i = 0; i < M; i++) {
		scanf("%d %d", &L[i], &R[i]);
	}
	for (i = 0; i < M; i++) {
		maxL = max(maxL, L[i]);
		minR = min(minR, R[i]);
	}
	if (maxL <= minR) {
		printf("%d\n", minR - maxL + 1);
	}
	else {
		printf("%d\n", 0);
	}
	return 0;
}


Measured memory_bytes: 896
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] height = new int[num];
        for (int i = 0; i < num; i++) {
            height[i] = sc.nextInt();
        }
        boolean success = true;
        int max = height[0];
        for (int i = 0; i < height.length - 1; i++) {
            if (height[i] > height[i + 1]) {
                height[i]--;
                if (height[i] > height[i + 1] || max > height[i]) {
                    success = false;
                    break;
                } else {
                    max = height[i];
                }
            }
        }
        if (success) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 51260
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;
long long MOD = 1e9 + 7;

int main() {
  int N;
  cin >> N;
  cout << N * N * N << endl;
  return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
P = list(map(int, input().split()))

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            

uni = UnionFind(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    uni.connect(x, y)

ans = 0
for i in range(N):
    if uni.same(i + 1, P[i]):
        ans += 1

print (ans)



Measured memory_bytes: 95852