akhauriyash/Code-Regression huggingface dataset:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    ans = float("inf")
    for i in range(n):
        x,y = p[i]
        q = [(p[j],(x-p[j][0])**2+(y-p[j][1])**2) for j in range(n) if j != i]
        q.sort(key = lambda x:-x[1])
        rx,ry = q[0][0]
        r2 = q[0][1]/4
        mx,my = (x+rx)/2,(y+ry)/2
        for P,D in q:
            s,t = P
            d2 = (s-mx)**2+(t-my)**2
            if d2 > r2+1e-6:
                break
        else:
            r = r2**0.5
            if r < ans:
                ans = r
    for i in range(n):
        ax,ay = p[i]
        for j in range(i):
            bx,by = p[j]
            sb,tb = ax-bx,ay-by
            mbx,mby = (ax+bx)/2,(ay+by)/2
            for k in range(j):
                cx,cy = p[k]
                l = -100000000
                r = 100000000
                while r-l > 1e-6:
                    m = (l+r)/2
                    mx,my = mbx-tb*m,mby+sb*m
                    d1 = (ax-mx)**2+(ay-my)**2
                    d2 = (cx-mx)**2+(cy-my)**2
                    if d1 < d2:
                        l = m
                    else:
                        r = m
                if r == 100000000:
                    l = -100000000
                    r = 100000000
                    while r-l > 1e-6:
                        m = (l+r)/2
                        mx,my = mbx-tb*m,mby+sb*m
                        d1 = (ax-mx)**2+(ay-my)**2
                        d2 = (cx-mx)**2+(cy-my)**2
                        if d1 < d2:
                            r = m
                        else:
                            l = m
                mx,my = mbx-tb*m,mby+sb*m
                r2 = (ax-mx)**2+(ay-my)**2
                for l in range(n):
                    if l in (i,j,k):
                        continue
                    s,t = p[l]
                    d2 = (s-mx)**2+(t-my)**2
                    if d2 > r2+1e-6:
                        break
                else:
                    r = r2**0.5
                    if r < ans:
                        ans = r

    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 51180
#include <stdio.h>

int main(void) {
	// your code goes here
	double w,h,x,y;
	int a=0;
	scanf("%lf%lf%lf%lf",&w,&h,&x,&y);
	if(w/2==x&&h/2==y){
		a +=1;
	}
	
	printf("%lf %d",(w*h)/2,a);
	return 0;
}

Measured memory_bytes: 128
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    N=int(input())
    A=list(map(int,input().split()))
    state=0
    temp=A[0]
    cnt=1
    for i in range(1,N):
        if state==0:
            if A[i]>temp:
                state=1
                temp=A[i]
            elif A[i]<temp:
                state=-1
                temp=A[i]
            else:
                temp=A[i]

        elif state==1:
            if A[i]<temp:
                state=0
                cnt+=1
                temp=A[i]
            else:
                temp=A[i]
        else:
            if A[i] > temp:
                state = 0
                cnt += 1
                temp = A[i]
            else:
                temp = A[i]
    print(cnt)
resolve()

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

vector<vector<int>> cost(10, vector<int>(10));
void warshall_floyd( int N ){
  for( int i = 0; i < N; i++ ){ //経由
    for( int j = 0; j < N; j++ ){ //始点
      for( int k = 0; k < N; k++ ){ //終点
        cost.at(j).at(k) = min(cost.at(j).at(k), cost.at(j).at(i)+cost.at(i).at(k));
      }
    }
  }
}

signed main(){
  int H, W;
  cin >> H >> W;
  
  for( int i = 0; i < 10; i++ ){
    for( int j = 0; j < 10; j++ ) cin >> cost.at(i).at(j);
  }
  
  warshall_floyd(10);
  int ans = 0;
  for( int i = 0; i < H; i++ ){
    for( int j = 0; j < W; j++ ){
      int A;
      cin >> A;
      if( A != -1 ) ans += cost.at(A).at(1);
    }
  }
  cout << ans << endl;
  
}


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

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

  vector<int> p(n);
  for (int i = 0; i < n; i++){
    cin >> p.at(i);
  }

  int count = 0;
  for (int i = 0; i < n - 2; i++){
    int temp_max = max(max(p.at(i), p.at(i+1)), p.at(i+2));
    int temp_min = min(min(p.at(i), p.at(i+1)), p.at(i+2));
    if (p.at(i+1) != temp_max && p.at(i+1) != temp_min) {
      count++;
    }
  }

  cout << count <<endl;

}


Measured memory_bytes: 256
#include <iostream>
using namespace std;;
int main(){
int t,n;
for(int i=0;i<4;i++){
cin>>t>>n;
if(t==1) cout<<6000*n<<endl;
if(t==2) cout<<4000*n<<endl;
if(t==3) cout<<3000*n<<endl;
if(t==4) cout<<2000*n<<endl;
}
return 0;
}



Measured memory_bytes: 3052
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

int main()
{
    string s, t;
    cin >> s >> t;
    int ans = 1001001001;
    for(int i = 0; i < s.length()-t.length()+1; i++){
        int len = 0;
        for(int j = 0; j < t.length(); j++){
            if(s[i+j] != t[j]){
                len++;
            }
        }
        ans = min(ans, len);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = LLONG_MAX;
const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N, sum = 0;
    cin >> N;
    set<int> st;
    for (int i = 1;; ++i) {
        sum += i;
        st.insert(i);
        if (sum >= N) {
            int diff = sum - N;
            if (diff != 0) {
                st.erase(st.find(diff));
            }
            for (auto num : st) {
                cout << num << endl;
            }
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define data_type long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    data_type n,r;
    cin>>n>>r;
    cout<<r+100*(10-min(10LL,n))<<endl;
    return 0;
}




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

int main(){
    vector<vector<vector<int>>> a(4 , vector<vector<int>>(3 , vector<int>(10)));
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 10; k++){
                a.at(i).at(j).at(k) = 0;
            }
        }
    }
    int n, b, f, r, v;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> b >> f >> r >> v;
        a.at(b - 1).at(f - 1).at(r - 1) += v;
    }
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 10; k++){
                cout << " " << a.at(i).at(j).at(k);
            }
            cout << endl;
        }
        if(i == 0 || i == 1 || i == 2){
        cout << "####################" << endl;
        }
    }
}


Measured memory_bytes: 3072
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    string s;
    cin >> s;
    if (s.length() == 2)
    {
        cout << s << endl;
    }
    else
    {
        cout << s[2] << s[1] << s[0] << endl;
    }
    return 0;
}

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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    string s;
    cin>>s;
    if(s=="ABC")
    {
        cout<<"ARC"<<endl;
    }
    else
    {
        cout<<"ABC"<<endl;
    }

    return 0;

}













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

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>	tree_set;
typedef long long ll;
typedef long double ld;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

ll mod=1e9 + 7;
ll fct[3000],inv[3000],invfct[3000];
void precalc(){
    fct[0]=fct[1]=1;
	inv[1]=1;
	invfct[0]=invfct[1]=1;
	for(ll i=2;i<3000;i++)
	{
		fct[i]=i*fct[i-1]%mod;
		inv[i]=ll(mod-inv[mod%i])*(mod/i)%mod;
		invfct[i]=ll(inv[i])*invfct[i-1]%mod;
	}
}


int main()
{
    fast();
    precalc();
    ll n,k;
    cin>>n>>k;
    for(ll i=1;i<=k;i++)
    {
        if( i > (n-k+1))
        {
            cout<<0<<endl;
            continue;
        }
        ll ans_1 = ( (fct[n-k+1]*invfct[i])%mod * invfct[n-k+1-i] )%mod;
        ll ans_2 = ( (fct[k-1]*invfct[i-1])%mod * invfct[k-i])%mod;
        ll ans = (ans_1*ans_2)%mod;
        cout<<ans<<endl;
    }
}



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

alst = []
for i in range(n):
    a = list(map(int, input().split()))
    alst.append(a)
    
blst = []
for i in range(m):
    b = list(map(int, input().split()))
    blst.append(b)
    
for i in range(n):
    clst = []
    for j in range(l):
        c = 0
        for k in range(m):
            c += alst[i][k]*blst[k][j]
        clst.append(c)
    print(*clst) 


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int dp[n+1][3];
    dp[n][0]=0;
    dp[n][1]=0;
    dp[n][2]=0;
    for (int i=n-1;i>=0;i--){
        if(s[i]=='R'){
            dp[i][0]=dp[i+1][0]+1;
            dp[i][1]=dp[i+1][1];
            dp[i][2]=dp[i+1][2];
        }
        else if(s[i]=='G'){
            dp[i][0]=dp[i+1][0];
            dp[i][1]=dp[i+1][1]+1;
            dp[i][2]=dp[i+1][2];
        }
        else{
            dp[i][0]=dp[i+1][0];
            dp[i][1]=dp[i+1][1];
            dp[i][2]=dp[i+1][2]+1;
        }
    }
    long long int ans=0;
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            if(s[i]!=s[j]){
                set <char> t={s[i],s[j]};
                if(t.find('R')==t.end()) ans+=dp[j+1][0];
                else if(t.find('G')==t.end()) ans+=dp[j+1][1];
                else ans+=dp[j+1][2];
                if(2*j-i<n and t.find(s[2*j-i])==t.end()) ans--;
            }
        }
    }
    cout<<ans<<"\n";
	return 0;
}

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

#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define elif else if
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef string S;
typedef queue<int> qi;

int main(){
    ll q,h,s,d,n;
    cin >> q >> h >> s >> d >> n;
    ll Q=8*q,H=4*h,S=2*s,D=d;
    if(n==1){
        cout << min({Q,H,S})/2 << endl;
        return 0;
    }else{
        cout << (n/2)*min({Q,H,S,D}) + (n%2)*(min({Q,H,S})/2) << endl;
        return 0;
    }
    return 0;
}


Measured memory_bytes: 256
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  s = InputLine.to_s
  puts ('x' * s.size)
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1788
use std::io::Read;
use std::cmp::max;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: usize = iterator.next().unwrap().parse().unwrap();
    let b: usize = iterator.next().unwrap().parse().unwrap();

    for i in 1..10000 {
        if ((i as f64) * 0.08) as usize == a
            && ((i as f64) * 0.10) as usize == b {
            return i.to_string();
        }
    }

    return "-1".to_string();
}


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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define trav(a, x) for (auto& a : x)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;
#define INF (1ll<<60)

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    ll N;
    cin >> N;
    int ans = 100000;
    for (int i = 1; i <= sqrt(N); i++) {
        if (N % i != 0) continue;
        ll A = i;
        ll B = N / i;
        string a = to_string(A);
        string b = to_string(B);
        ans = min(ans, max(SZ(a), SZ(b)));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import itertools
N = int(input())
P = tuple(int(i) for i in input().split())
Q = tuple(int(i) for i in input().split())

permutations = list(itertools.permutations(range(1, N + 1)))

print("{}".format(abs(permutations.index(P) - permutations.index(Q))))

Measured memory_bytes: 8052
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#define N 100005
#define fi(a, b, c) for(int a = (b); a < (c); a++)
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
using namespace std;

int n, c[26], m, b[N], ans;
char s[N], t[N];

int main(){
	scanf("%s", s);
	n = strlen(s);
	
	fi(i, 0, n){
		if(s[i] != 'x') {
			t[m++] = s[i];
		}else{
			b[m]++;
		}
	}
	
	fi(i, 0, m){
		if(t[i] != t[m - i - 1]){
			puts("-1");
			return 0;
		}
	}
	
	m++;
	fi(i, 0, m) ans += abs(b[i] - b[m - i - 1]);
	
	printf("%d\n", ans / 2);
	
	
}

Measured memory_bytes: 640
// Template
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>

using namespace std;
const int MOD = 1000000007;

#define v_exists(elem, v) find(v.begin(),v.end(),elem)!=v.end()
#define s_exists(elem, s) s.find(elem)!=s.end()
#define mod_mul(x, y) x*y%MOD
#define mod_add(x, y) (x+y)%MOD
#define mod_sub(x, y) (x-y)%MOD
#define INF_INT 2147483647

long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long lcm( long m, long n ){
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}


long nCr(long n, long r){
    if(n==r || r==0){
        return 1;
    } else {
        return mod_add(nCr(n-1,r),nCr(n-1,r-1));
    }
}


int main(){
    int N,C; cin >> N >> C;
    int D[40][40]; int map[501][501];

    for(int i=0; i<C; i++){
        for(int j=0; j<C; j++){
            cin >> D[i][j];
        }       
    }

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

    int cost[3][31];
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            for(int c=0; c<C; c++){
                cost[(i+j)%3][c] += D[map[i][j]][c];
            }
        }       
    }

    int ans = INF_INT;
    for(int i=0; i<C; i++){
        for(int j=0; j<C; j++){

            if(i==j) continue;

            for(int k=0; k<C; k++){

                if(k==i || k==j) continue;

                ans = min(ans, cost[0][i]+cost[1][j]+cost[2][k]);
            }
        }       
    }

    cout << ans << endl;

    return 0;

}


Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		System.out.println((a + b) / 2 + (a +b) % 2);
		scan.close();

	}

}


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

int main()
{
    ll n,i,j,k;
    string a;
    cin>>a;
    n=a.size();
    ll ans=0;
    for(i=0;i<n;i++){
        j=a[i]-'0';
        ans=((ans%9)+(j%9))%9;
    }
    if(ans==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


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


int cal(int n,int k)
{
    if(n%k==0)
        return n/k;
    else
        return cal(n-n/k-1,k);
}
int cal2(int c,int r,int k)
{
    r%=c+1;
    if(r==0)
        return c;
    else
        return cal2(c-1,k-(c-r)-1,k);
}
int solve(int n,int k)
{
    if(k<32000)
        return cal(n,k);
    else
        return cal2(n/k,n%k,k);
}
int main()
{

    int n,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int a,k;
        scanf("%d%d",&a,&k);
        ans^=solve(a,k);
    }
    puts(ans?"Takahashi":"Aoki");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<deque>
using namespace std;
int main() {
	string S;
	int Q;
	int T;
	int rev = 0;
	int F = 0;
	char C;
	cin >> S >> Q;
	deque<char> dS(S.size());
	for (int i = 0; i < S.size(); i++) {
		dS[i] = S[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> T;
		if (T == 1) {
			if (rev == 0) {
				rev = 1;
			}
			else {
				rev = 0;
			}
		}
		else {
			cin >> F;
			if (F == 1) {
				cin >> C;
				if (rev == 1) {
					dS.push_back(C);
				}
				else {
					dS.push_front(C);
				}
			}
			else {
				cin >> C;
				if (rev == 0) {
					dS.push_back(C);
				}
				else {
					dS.push_front(C);
				}
			}
		}
	}
	if (rev == 0) {
		for (int i = 0; i < dS.size(); i++) {
			cout << dS[i];
		}
	}
	else {
		for (int i = 0; i < dS.size(); i++) {
			cout << dS[dS.size()-1-i];
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 896
let modulo = 1_000_000_007
let (+%) a b = (a + b) mod modulo
let (-%) a b = let tmp = (a - b) mod modulo in
               if tmp >= 0 then tmp
               else tmp + modulo
let ( *% ) a b = (a * b) mod modulo
let rec ( **% ) a n =
  if n = 0 then 1
  else if n mod 2 = 1 then a *% a **% (n - 1)
  else let t = a **% (n / 2) in t *% t
let (/%) a b =
  let inv a = a **% (modulo - 2)
  in
  a *% inv b

let m_fact = Array.make 3000 (-1)
let rec fact n =
  if n = 0 then 1
  else
    if m_fact.(n) >= 0 then m_fact.(n)
    else (m_fact.(n) <- n *% fact (n - 1);
          m_fact.(n))
  
let m_nCr = Array.make_matrix 3000 3000 (-1)
let rec nCr n r =
  if n < r then 0
  else
    fact n /% fact (n - r) /% fact r
  
let () =
  let (n, k) = Scanf.sscanf (input_line stdin) "%d %d" (fun a b -> (a, b)) in
  let rec loop i =
    if i > k then ()
    else
      let ans = nCr (n-k+1) i *% nCr (k-1) (i-1) in
      (print_int ans;
       print_newline ();
       loop (i + 1))
  in loop 1
    


Measured memory_bytes: 73848
#include <algorithm>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <iostream>
#include <queue>
#include <set>

using namespace std;

int main(){
  string s; cin >> s;
  int k; cin >> k;
  const int n = s.size();
  vector<string> v;

  REP(i,n){
    for(int j = 1; j <= 5 && i + j <= n; j++)
      v.push_back(s.substr(i, j));
  }

  sort(v.begin(), v.end());
  unique(v.begin(), v.end());

  cout << v[k - 1] << endl;

  return 0;
}

Measured memory_bytes: 1660
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

group = [0] * n
color = 1


def dfs(s, c):
    stack = [s]
    group[s] = c
    cnt = 1
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if group[v] == 0:
                group[v] = c
                stack.append(v)
                cnt += 1

    return cnt


ans = 0
for i in range(n):
    if group[i] == 0:
        cnt = dfs(i, color)
        color += 1
        ans = max(ans, cnt)

print(ans)


Measured memory_bytes: 80304
#include<iostream>
#include<string>
using namespace std;
struct Dice{
  int s[6];
  void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
  }
  int top() {
    return s[0];
  }
};
int main(){
  Dice d;
  for(int i=0;i<6;i++) cin >> d.s[i];
  string s;cin >> s;
  for(int i=0;i<s.size();i++) d.roll(s[i]);
  cout << d.top() << endl;
  return 0;
}



Measured memory_bytes: 3168
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    string S;
    cin >> S;
    int N = sz(S);
    if (S.back() == '1' || S[0] == '0') {
        cout << -1 << endl;
        return;
    }
    int M = (N - 1) / 2;
    rep(i, M)if (S[i] != S[N - 2 - i]) {
        cout << -1 << endl;
        return;
    }

    int cur = 1, ne = 2;
    vector<pii> ans;
    for (int i = 2; i <= N - 1; ++i) {
        if (S[i - 1] == '1') {
            while (sz(ans) + 1 != i) {
                ans.emplace_back(cur, ne++);
            }
            ans.emplace_back(cur, ne);
            cur = ne++;
        }
    }

    each(a, ans)cout << a.first << ' ' << a.second << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

Measured memory_bytes: 2372
def horizontal_input(T=str):
    return list(map(T,input().split()))

def vertical_input(n,T=str,sep=False,septype=tuple):
    data=[]
    if sep:
        for i in range(n):
            data.append(septype(map(T,input().split())))
    else:
        for i in range(n):
            data.append(T(input()))
    return data

n,k=horizontal_input(int)
prisoner=0
for i in range(n-1):
    prisoner+=1
    prisoner+=(prisoner-1)//(k-1)
print(prisoner)


Measured memory_bytes: 5604
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int INF = 2e6;
 

int main(){
    string s; cin >> s;
    int n = s.size();

    int l = n - 1;
    bool ok = true;
    while(l > 0) {
        if(s[l] == 'm' && s[l-1] == 'a' && s[l-2] == 'e' && s[l-3] == 'r' && s[l-4] == 'd') {
            l = l - 5;
            continue;
        }
        if(s[l] == 'e' && s[l-1] == 's' && s[l-2] == 'a' && s[l-3] == 'r' && s[l-4] == 'e') {
            l = l - 5;
            continue;
        }
        if(s[l] == 'r' && s[l-1] == 'e'){
            if(s[l-2] == 'm' && s[l-3] == 'a' && s[l-4] == 'e' && s[l-5] == 'r' && s[l-6] == 'd') {
                l = l - 7;               
                continue;
            }else if(s[l-2] == 's' && s[l-3] == 'a' && s[l-4] == 'r' && s[l-5] == 'e') {
                l = l - 6;
                continue;             
            }else{
                cout << "NO" << endl;
                return 0;
            }
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

struct UnionFind{
    vint v;
    UnionFind(int n){ v.assign(n,-1); }
    int  find(int x){ return v[x]<0? x:v[x]=find(v[x]); }
    void unite(int x,int y){
        x=find(x),y=find(y); if(x==y) return;
        if(v[x]>v[y]) swap(x,y); v[x]+=v[y],v[y]=x;
    }
    int  size(int x){ return -v[find(x)]; }
    bool same(int x,int y){ return find(x)==find(y); }
    bool root(int x){ return v[x]<0; }
};

signed main()
{
    int N,Q; cin>>N>>Q;
    UnionFind tree(N);
    while(Q--){
        int q,x,y; cin>>q>>x>>y;
        if(q==0) tree.unite(x,y);
        else cout<<tree.same(x,y)<<endl;
    }
}



Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <complex>
#include <numeric>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

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

const int INF = 1e9;
const int MOD = 1e9+7;

int main(void){
  int n;
  cin >> n;
  vector<ll> a(n), b(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];
  ll k = 0;
  REP(i, n) {
    k += b[i] - a[i];
  }

  if(k < 0) {
    cout << "No" << endl;
    return 0;
  }

  ll ak = k, bk = k;
  REP(i, n) {
    if(a[i] > b[i]) {
      bk -= a[i] - b[i];
    } else if (a[i] < b[i]) {
      if((b[i] - a[i]) % 2) bk--;
      ak -= (b[i] - a[i] + 1) / 2;
    }
  }
  //cout << ak << " " << bk << endl;
  if(ak < 0 || bk < 0) {
    cout << "No" << endl;
  } else if (ak * 2 == bk) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

	return 0;
}

Measured memory_bytes: 384
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    fast;
    ll a,k; cin>>a>>k;
    vec<ll> m(a), dp(a, 1e18);
    for(int q=0; q<a; q++) cin>>m[q];
    for(int q=0; q<k; q++) dp[q] = abs(m[q]-m[0]);
    for(int q=k; q<a; q++){
        for(int w=1; w<=k; w++) dp[q] = min(dp[q], dp[q-w]+abs(m[q]-m[q-w]));
    }
    cout<<dp[a-1];
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  double den = 0;
  rep(i,N) den += 1/(1.0 * A[i]);
  cout << fixed << setprecision(10) << 1 / den << endl;
  return 0;
}

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

const int INF = 1e9;

int main() {
  int a[3];
  for(int i=0;i<3;i++)cin>>a[i];
  sort(a,a+3);
  int ans=0;
  int tmp1=(a[2]-a[0])/2;
  ans+=tmp1;
  a[0]+=2*tmp1;
  int tmp2=(a[2]-a[1])/2;
  ans+=tmp2;
  a[1]+=2*tmp2;

  if(a[0]==a[2]&&a[1]==a[2]){
    cout<<ans<<endl;
    return 0;
  }
  if(a[0]==a[2]-1&&a[1]==a[2]-1){
    cout<<ans+1<<endl;
    return 0;
  }
  cout<<ans+2<<endl;

}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i32,
        b: i32,
    }

    println!("{}", std::cmp::max(std::cmp::max(a + b, a - b), a * b));
}


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

int main() {
    string s,t;
  cin>>s>>t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if(s<t)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;


// 68 11 55 - rank 3
// 69 12 19 - rank 3
// 70 12 34 - rank 100
// 71 12 58 - rank 4
// 72 13 24 - rank 20
// 73 13 39

ull gcd(ull a, ull b) {
    while (b != 0) {
        auto na = a % b;
        a = b;
        b = na;
    }
    return a;
}


void oneCase() {
    int n;
    cin >> n;
    for (auto l : to_string(n)) {
        if (l == '9') {
            cout << "Yes" << "\n";
            return;
        }
    }
    cout << "No" << "\n";
}


int main() {
    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}

ll fact(ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        res = (res * n) % mod;
        --n;
    }
    return res;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())

    K = 0
    for i in range(1,10**3):
        if i * (i-1) // 2 == N:
            K = i
            break

    if K == 0:
        print("No")
        exit()
    
    S = [[0] * (K-1) for _ in range(K-1)]

    a = 1
    for i in range(K-1):
        for j in range(i+1):
            S[i][j] = a
            S[j][i] = a
            a += 1

    tri = [S[i][i] for i in range(K-1)]

    print("Yes")
    print(K)

    for s in S:
        print(K - 1, *s)
    
    print(K - 1, *tri)

    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9224
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int cnt = 0 ;
    string s;
    cin >> s;
    int mx = 0;
    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='R')
        {
            cnt++;
        }
        else
        {
            mx = max(mx,cnt);
            cnt = 0;
        }
    }
    mx = max(mx,cnt);
    cout << mx << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

map <ll,ll> mpd,mpt;
int main() {
	int N,M;
	cin>>N;vector<int> D(N);
	rep(i,N)cin>>D[i];

	cin>>M;vector<int> T(M);
	rep(i,M)cin>>T[i];

	rep(i,N)mpd[D[i]]++;
	rep(i,M)mpt[T[i]]++;
	string ans = "YES";
	rep(i,M){
		if(mpt[T[i]]>mpd[T[i]]){
			ans = "NO";
			break;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 26752
#include <bits/stdc++.h> 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ld double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define sz(x) ((long long)x.size())
#define all(x) (x).begin(), (x).end()
const int MOD =1e9+7;

int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1LL;}return res%p;}
const int N=2*1e5+2,M=20;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int f(int a[],int n,int x)
{
	int b[n];
	ordered_set s;
	for(int i=0;i<n;i++)
	{
		if(a[i]>=x) b[i]=1;
		else b[i]=-1;
	}
	for(int i=1;i<n;i++) b[i]+=b[i-1];
	s.insert({0,-1});
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		cnt+=s.order_of_key({b[i]+1,-1e12});
		s.insert({b[i],i});
	}
	return cnt;
}
int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	int l=1,r=1e9;
	int m=n*(n-1)/2+n+1;
	int ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int get=f(a,n,mid);
		if(get>=m/2)
		{
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans;
}  

Measured memory_bytes: 8064
def main():
    x, y = map(int, input().split())
    answer = 0
    if abs(x) != abs(y):
        answer += abs(abs(x) - abs(y))
    if (x < 0 and y < x < 0) or (0 < y < x):
        answer += 2
    elif x * y < 0 or (0 < x and y == 0) or (x == 0 and y < 0):
        answer += 1
    print(answer)


if __name__ == '__main__':
    main()



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;

#define ff first
#define ss second
//#define pb push_back
#define mp make_pair
#define sz size()
#define all(a)  A.begin(), A.end()
#define mem(a, b)     memset(a, b, sizeof(a))
#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))


#define forr(i,n) for(i=0; i<n; i++)
#define whilee(i,t) while(i!=t)
#define pb(x) push_back(x);

//sort(A.begin(),A.end());
//binary_search(A.begin(),A.end(),x);
//reverse(A.begin(), A.end());
//cout << *max_element(A.begin(), A.end());
//cout << *min_element(A.begin(), A.end());
//accumulate(A.begin(), A.end(), 0);
//next_permutation(A.begin(), A.end());
//prev_permutation(A.begin(), A.end());

//vector <int> A;
//deque <int> A;
//queue <int> A;
//stack <int> A;
//set <int> A;
//map <int,int> A;
//pair <int,int> A ;
//vector <pair <int,int>> A ;
//string S, T;
int i, j, k, a, b, c, d, l, m, n, p, q, r, s, t, x, y, z, cnt=0;

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

    cin>>n;
    if(n<=111)
    {
       cout<<111<<endl;
    }
    else if(n<=222)
    {
        cout<<222<<endl;
    }
    else if(n<=333)
    {
       cout<<333<<endl;
    }
    else if(n<=444)
    {
       cout<<444<<endl;
    }
    else if(n<=555)
    {
       cout<<555<<endl;
    }
    else if(n<=666)
    {
        cout<<666<<endl;
    }
    else if(n<=777)
    {
       cout<<777<<endl;
    }
    else if(n<=888)
    {
        cout<<888<<endl;
    }
    else if(n<=999)
    {
       cout<<999<<endl;
    }
    return 0;
}



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

# define ll long long
const int N = 405;

ll dp[N][N], sum[N], a[N], n;

ll f(int l, int r){
  return sum[r] - sum[l - 1];
}

ll calc(int l, int r){
  // cout << "l:" << l << " r:" << r << endl;
  if(dp[l][r]) {
    // cout << "dp[" << l << "][" << r << "]:" << dp[l][r] << endl;
    // cout << endl;
    return dp[l][r];
  }
  if(l == r) {
    // cout << 0 << endl;
    // cout << endl;
    return 0;
  }
  ll ans = 1e18;
  for(int i = l + 1; i <= r; i++){
      // cout << l << " " << i - 1 << endl;
      ll L = calc(l, i - 1);
      // cout << i << " " << r << endl;
      ll R = calc(i, r);
      // cout << "l:" << l << " i-1:" << i-1  << " i:" << i << " r:" << r << " L:" << L << " R:" << R << " L+R:" << L + R << " ans:" << ans << endl;
      ans = min(ans, L + R);
      // cout << "ans:" << ans << endl;
  }
  // cout << endl;
  dp[l][r] = ans + f(l, r);
  // cout << "dp[" << l << "][" << r << "]:" << dp[l][r] << " = ans:" << ans << " + f:" << f(l, r) << endl;
  // cout << endl;
  return dp[l][r];
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
      cin >> a[i];
      sum[i] = sum[i - 1] + a[i];
    }
    // for(int i = 0; i <= n; i++){
    //   cout << sum[i] << " ";
    // }
    // cout << endl;
    // cout << endl;
    cout << calc(1, n) << endl;
}


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

int main() {
    ll x, k, d;
    cin >> x >> k >> d;
    ll ans;
    x = abs(x);
    if (x / d >= k) ans = x - k * d;
    else {
        if ((x / d + k) % 2 == 0) ans = x % d;
        else ans = d - x % d;
    } 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
from heapq import *

n, m, s = map(int, input().split())
s = min([s, 50*n])
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
while hq:
    t, p, g = heappop(hq)
    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))

Measured memory_bytes: 97968
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();
		System.out.println((a == b && b != c) || (a == c && b != c) || (b == c && a != c) ? "Yes" : "No");
	}

	public static int arrayMax(int[] array) {
		int ans = Integer.MIN_VALUE;
		for (int i = 0; i < array.length; i++) {
			if (array[i] > ans)
				ans = array[i];
		}
		return ans;
	}

	public static int[] arrayInt(Scanner sc, int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static Integer[] arrayInteger(Scanner sc, int n) {
		Integer[] array = new Integer[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static long[] arrayLong(Scanner sc, int n) {
		long[] array = new long[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextLong();
		}
		return array;
	}

	public static double[] arrayDouble(Scanner sc, int n) {
		double[] array = new double[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextDouble();
		}
		return array;
	}
}

Measured memory_bytes: 21844
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
	char s[51];
	chin(s);
	s[strlen(s)-8]=0;
	puts(s);
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
	int n,i,j;
	scanf("%d", &n);
	for (i = 1; i <= 9; i++){
		for (j = 1; j <= 9; j++){
			if (i*j == n){
				printf("Yes\n");
				return 0;
			}
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define sz(v) (ll)v.size()
#define inf 100000000000000
#define vll vector<ll>
#define pll pair<ll,ll>nnnn
using namespace std;
const int N=200004;
ll dp[N][26];
ll fst[N];
void solve()
{
	
	string a,b;
	ll n,m,idx,i,tot=0,j;
	cin>>a;
	cin>>b;
	n=a.length();
	m=b.length();
	a="0"+a;
	b="0"+b;
	for(i=1;i<=n;i++)
		if(!fst[a[i]-'a'])
			fst[a[i]-'a']=i;
	for(i=n-1;i>=1;i--)
	{
		for(j=0;j<26;j++)
			dp[i][j]=dp[i+1][j];
		dp[i][a[i+1]-'a']=i+1;
	}
	for(i=1;i<=m;i++)
		if(!fst[b[i]-'a'])
		{
			cout<<-1;
			return;
		}
	idx=fst[b[1]-'a'];
	i=2;

	while(i<=m)
	{
		if(dp[idx][b[i]-'a'])
			idx=dp[idx][b[i]-'a'];
		else
			idx=fst[b[i]-'a'],tot++;
		i++;
	}
	cout<<(tot*n+idx);

}
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
 
    
    return 0;
}

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

n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
b =[]
for i in range(m):
    b.append(int(input()))
    
for i in range(n):
    bek = 0
    for j in range(m):
        bek += a[i][j] * b[j]
    print(bek)


Measured memory_bytes: 6016