akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
const int N=100010;
 
int n,a[N],b[N];
ll tot;
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		if(a[i]<b[i]){
			tot+=(b[i]-a[i]+1)/2;
			if(b[i]-a[i]&1) tot--;
		}
		else{
			tot-=a[i]-b[i];
		}
	}
	puts(tot<0?"No":"Yes");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
    using namespace std;
    bool check(int i, int a, int b){
      int sum = 0;
      sum += i/10000 + i/1000%10 + i/100%10 + i/10%10 + i%10;
      if (a<=sum && sum<=b){
        return true;
      }else{
        return false;
      }
    }
     
    int main() {
      int n,a,b; cin >>n >>a >>b;
      int ans = 0;
      for (int i=1; i<n+1; i++){
        if (check(i,a,b)){
          ans += i;
        }
      }
      cout <<ans <<endl;
    }

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

if sum(b)>sum(a):
    print(-1)
else:
    c = [a[i]-b[i] for i in range(n) if a[i]-b[i]>=0]
    d = [a[i]-b[i] for i in range(n) if a[i]-b[i]<0]
    d.append(0)
    c.sort(reverse=True)
    from itertools import accumulate
    c = list(accumulate(c))
    from bisect import bisect_left
    index= bisect_left(c,-1*sum(d))
    if d == [0]:
        d.pop(0)
    print(len(d)+index)

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

int main () {
  string s,t;
  cin >> s >> t;
  
  int i=0;
  int ans=0;
  for (char x :s) {
    if (x==t[i]) ++ans;
    ++i;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3612
n = int(input())
a = input().rstrip()
b = input().rstrip()
pattern = []
l = 0
while l < n:
    if a[l] == b[l]:
        pattern.append(1)
        l += 1
    else:
        pattern.append(0)
        l += 2

ans = 1
for i in range(len(pattern)):
    if i == 0:
        if pattern[i] == 1:
            ans *= 3
        else:
            ans *= 6
        continue
    if pattern[i-1] == 1 and pattern[i] == 1:
        ans *= 2
    elif pattern[i-1] == 0 and pattern[i] == 0:
        ans *= 3
    elif pattern[i-1] == 1 and pattern[i] == 0:
        ans *= 2
        
print(ans % (10**9+7))

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	int cnt,ma;
	ma=1e9;
	for(int i=1;i<n;i++){
		int j=i;
		int k=n-i;
		cnt=0;
		while(j){
			cnt+=j%10;
			j/=10;
		}
		while(k){
			cnt+=k%10;
			k/=10;
		}
		if(cnt<ma)
		ma=cnt;
	}
	cout<<ma;
	return 0;
}

Measured memory_bytes: 256
import Control.Applicative

main :: IO ()
main = do
    n <- readLn :: IO Int
    a <- map read . words <$> getLine

    putStrLn $ show (solve a 0)

solve :: [Int] -> Int -> Int
solve a i
    | sum modLst == 0 = solve divLst (i + 1)
    | otherwise       = i
    where dmLst  = [(d, m) | x <- a, let (d, m) = divMod x 2]
          divLst = [d | (d, m) <- dmLst]
          modLst = [m | (d, m) <- dmLst]


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll X; cin >> X;

    ll a, b;
    for(ll i = -300; i <= 300; i++) {
        for(ll j = -300; j <= 300; j++) {
            ll i5 = i*i*i*i*i;
            ll j5 = j*j*j*j*j;
            if(i5 - j5 == X) {
                a = i, b = j;
                break;
            }
        }
    }
    cout << a << " " << b << endl;
}


Measured memory_bytes: 3620
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll int
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define fur(i,x,y) for(i=x;i<=y;i++)
#define fdr(i,x,y) for(i=x;i>=y;i--)
#define Fur(i,x,y) for(ll i=x;i<=y;i++)
#define Fdr(x,y) for(ll i=x;i>=y;i--)
#define in2(x,y) in(x);in(y)
#define in3(x,y,z) in2(x,y);in(z)
#define in4(a,b,c,d) in2(a,b);in2(c,d)
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
/*---------------------------------------*/

namespace fib{char b[300000]= {},*f=b;}
#define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce{~foce(){pob;fflush(stdout);}} _foce;
namespace ib{char b[100];}
inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}
inline void outn(ll x){out(x);pc('\n');}
inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
/*------------------------------------------------------------------------------------------------*/

/*------------------------------------------------------------------------------------------------*/
#define N 101
int main(){
	ll n;in(n);outn(n/3) ;
}

/*

*/

Measured memory_bytes: 256
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();
		int c = scan.nextInt();
		int k = scan.nextInt();
		int max;
		int tmp;
		
		if (a > b && a > c) {
			max = a;
		} else if (b > a && b > c) {
			max = b;
		} else {
			max = c;
		}
		
		tmp = max;
		
		for (int i = 0; i < k; i++) {
			tmp *= 2;
		}
		
		System.out.println(tmp + a + b + c - max);
	}
}

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, str>> vpls;
typedef vector<tuple<str, ll, ll>> vtsl;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  char a, b; cin >> a >> b;
  if(a < b) fin("<")
  else if(a > b) fin(">")
  else fin("=")
}

//前処理
int main()
{
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}


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

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    string s, t, u;
    cin >> n >> s >> t;
    for (int i = 0; i < n; ++i) {
        if(s[i] == t[i]) u += "A";
        else {
            u += "B";
            ++i;
        }
    }
    ll x;
    x = (u[0] == 'A' ? 3LL : 6LL);
    for (int i = 1; i < u.length(); ++i) {
        if(u[i-1] == 'A' && u[i] == 'A') x = x * 2 % MOD;
        if(u[i-1] == 'A' && u[i] == 'B') x = x * 2 % MOD;
        if(u[i-1] == 'B' && u[i] == 'B') x = x * 3 % MOD;
    }
    cout << x << "\n";
    return 0;
}


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

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

    int t;
    int start[N + 2] = {};
    int goal[N + 2] = {};
    for (int i = 1; i <= N; i++)
    {
        cin >> t;
        goal[i] = start[i] + 2 * t;
        start[i + 1] = goal[i];
    }
    goal[N + 1] = goal[N];

    int v[N + 2] = {};
    for (int i = 1; i <= N; i++)
    {
        cin >> v[i];
        v[i] *= 2;
    }

    vector<int> x(goal[N] + 1, INT_MAX);
    x[0] = 0;
    int ans = 0;
    for (int i = 1; i < goal[N] + 1; i++)
    {
        for (int j = 0; j < N + 2; j++)
        {
            if (i < start[j])
            {
                x[i] = min(x[i], v[j] + start[j] - i);
            }
            else if (goal[j] < i)
            {
                x[i] = min(x[i], v[j] + i - goal[j]);
            }
            else
            {
                x[i] = min(x[i], v[j]);
            }
        }
        ans += x[i - 1] + x[i];
    }
    cout << setprecision(10) << (double)ans / 8 << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 200010
using namespace std;
typedef long long LL;
char s[maxn];
int opt[maxn], h[maxn];
int main() {
    scanf("%s", s+1);
    int len = strlen(s+1);
    for (int i = 1; i <= len; ++i) h[i] = h[i-1] ^ (1<<(s[i]-'a'));
    map<int, int> dp;
    for (int i = 1; i <= len; ++i) {
        opt[i] = (!h[i] || dp[h[i]]) ? dp[h[i]] : inf;
        int mask = 1;
        for (int j = 0; j < 26; ++j) {
            if ((h[i]^mask) == 0 || dp[h[i]^mask]) opt[i] = min(opt[i], dp[h[i]^mask]);
            mask <<= 1;
        }
        ++opt[i];
        if (!dp[h[i]] && h[i]) dp[h[i]] = opt[i];
        else dp[h[i]] = min(dp[h[i]], opt[i]);
    }
    printf("%d\n", opt[len]);
    return 0;
}


Measured memory_bytes: 205824
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  sort(a.begin(), a.end());
  
  cout << a[n/2] - a[n/2-1] << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,i;
    cin>>n;
    string str,s1,s2;
    cin>>str;
    for(i=0;i<n/2;i++)
        s1+=str[i];
    for(i=n/2;i<n;i++)
        s2+=str[i];
    if(s1==s2)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if(A==B && B!=C){
   cout << "Yes" << endl; 
  }
  
  else if(A==C && A!=B){
   cout << "Yes" << endl; 
  }
  
  else if(C==B && A!=C){
   cout << "Yes" << endl; 
  }
  
  else{
   cout << "No" << endl; 
  }
}


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


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

  vector<int> A(N);

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

  int ok[1000001] = {0};
  int cnt[1000001] = {0};
  
  for(int i = 0; i < N; i++) {
    cnt[A[i]]++;
  }
  
  for(int i = 1; i <= 1000000; i++) {
    if(cnt[i] > 0) {
      if(cnt[i] > 1) {
        ok[i] = 1;
      }

      for(int j = i + i; j <= 1000000; j += i) {
        ok[j] = 1;
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < N; i++) {
    if(ok[A[i]] == 0) ans++;
  }

  cout << ans;



  return 0;
}

Measured memory_bytes: 11964
#include <bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
}a[100];
int b[100];
double f(double x1,double y1,double x2,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	
}
int main(){
	node n;
	int k;
	cin >> k;
	for(int i=1;i<=k;i++){
		cin >> a[i].x >> a[i].y;
	}
	double sum=0;
	for(int i=1;i<=k;i++)b[i]=i;
	do{
		int p=b[1];
		for(int i=2;i<=k;i++){
			sum+=f(a[p].x,a[p].y,a[b[i]].x,a[b[i]].y);
			p=b[i];
		}
	}while(next_permutation(b+1,b+k+1));
	int ant=1;
	for(int i=1;i<=k;i++){
		ant*=i;
	}
	printf("%.8lf\n",sum/ant);
} 

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');
		int h = int.Parse(input[0]);
		int w = int.Parse(input[1]);
    string[] strings = new string[h];
    for(int i = 0; i < h; i++) strings[i] = Console.ReadLine();
    long mod = 1000000007;
    long[,] dp = new long[h+1,w+1];

    for(int i = 1; i <= h; i++)
    {
      for(int j = 1; j <= w; j++)
      {
        if(strings[i-1][j-1] == '.') dp[i,j] = dp[i-1,j] + dp[i,j-1];
        else dp[i,j] = 0;
        dp[i,j] %= mod;
        if(i+j == 2) dp[i,j] = 1;
      }
    }
    
		Console.WriteLine(dp[h,w]);
	}
}

Measured memory_bytes: 26716
n, m, d = gets.split.map(&:to_i)
def c(i, j, d)
  x = i + j
  y = i - j
  2 * ((x % (2 * d)) / d) + ((y % (2 * d)) / d)
end
puts n.times.map{|i| m.times.map{|j| 'RYGB'[c(i, j, d)]}.join}

Measured memory_bytes: 2684
# include <bits/stdc++.h>
# define INF 1e9
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.compare(t) < 0){
    cout << "Yes" << endl;
  } else{
    cout << "No" <<endl;
  }

}


Measured memory_bytes: 256
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse= True)

def check(i):
  if i <= P-1:
    return True
  vote = (V-1)*M
  vote -= (N-1-i)*M
  vote -= (P-1)*M
  if vote <= 0:
    return A[i]+M >= A[P-1]
  else:
    for j in range(i-1,P-1,-1):
      if A[j] > A[i]+M:
        return False
      vote -= min(A[i]+M-A[j],M)
      if vote <= 0:
        break
    if vote <= 0:
      return A[i]+M >= A[P-1]
    else:
      return A[i]+M >= A[P-1]+vote

ok = -1
ng = N
while(ok+1 < ng):
  md = (ok+ng)//2
  if check(md):
    ok = md
  else:
    ng = md
print(ok+1)


Measured memory_bytes: 62704
# 素数判定 O(√N)
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def Eratosthenes_sieve(n):
    table = [True]*(n+1)
    for i in range(n+1):
        if is_prime(i):
            for j in range(2*i,n+1,i): # 素数の倍数は非素数
                table[j] = False
        else:
            table[i] = False
    return table

a = 55555
t = Eratosthenes_sieve(a)

N = int(input())
ans = []
for i in range(1,55556,5):
    if t[i]:
        ans.append(i)
ans = ans[:N]
print(*ans)

Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct TEMP_OMAZINAI_ { TEMP_OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } TEMP__omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void TEMP_INPUT_IMPL_() {};
template <class T, class... Args> void TEMP_INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; TEMP_INPUT_IMPL_(args...); }
void TEMP_OUTPUT_IMPL_() {};
template <class T, class... Args> void TEMP_OUTPUT_IMPL_(T dest, Args... args) { cout << dest << (sizeof...(Args) ? " " : ""); TEMP_OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; TEMP_INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define unique_v(v) v.erase(std::unique(v.begin(), v.end()), v.end()) //必ずソート後に実行
#define out(...) (TEMP_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

// ^^^ Template ^^^ //


int main() {
	in(ll, A, B, C);
	if (A & B & C & 1)
		cout << min({ A*B, B*C, C*A }) << endl;
	else
		cout << 0 << endl;
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<cmath>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;i++)
int H, W;
char* str;
int main() {
	scanf("%d%d", &H, &W);
	vector<vector<char>>str(H, vector<char>(W + 1, 0));
	vector<vector<int>>route(W, vector<int>(H,W+H));
	rep(i, 0, H)scanf("%s", str[i].data());
	route[0][0] = str[0][0] == '#';
	rep(x, 0, W)rep(y, 0, H) {
		if (x > 0)route[x][y] = min(route[x][y],
			route[x - 1][y] + (str[y][x] == '#' && str[y][x - 1]  == '.'));
		if (y > 0)route[x][y] = min(route[x][y],
			route[x][y - 1] + (str[y][x] == '#' && str[y - 1][x] == '.'));
	}
	printf("%d", route[W - 1][H - 1]);
	return 0;
}

Measured memory_bytes: 256
N = int(input())

A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]
A = sorted(A, key=lambda x: -x[1])  # sort by y-axis [max,..., min]
B = sorted(B, key=lambda x: x[0])   # sort by x-axis [min,..., max]

for i in range(N):
    for j in range(len(A)):
        if A[j][0] < B[i][0] and A[j][1] < B[i][1]:
            A.pop(j)
            break

print(N - len(A))


Measured memory_bytes: 3064
from collections import deque

N, M = map(int, input().rstrip().split(' '))

edges = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().rstrip().split(' '))
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)

vertices = [False] * N

count = 0
d = deque()
for i in range(N):
    if vertices[i] == False:
        vertices[i] = True
        count += 1
        d.append(i)
        while len(d) > 0:
            v = d.popleft()
            for p in edges[v]:
                if vertices[p] == False:
                    d.append(p)
                    vertices[p] = True
                

print(count)

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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 4003;

int sum(int a, int b, int mod=MOD) {
    int c = a + b;
    if (c >= mod) {
        c -= mod;
    }

    return c;
}

inline int prod(int a, int b, int mod=MOD) {
    return (1LL * a * b) % mod;
}

int modpow(int base, int exp, int mod=MOD) {
    int res = 1;
    int cur = base;
    for (int p = 1; p <= exp; p <<= 1) {
        if (p & exp) {
            res = prod(res, cur, mod);
        }

        cur = prod(cur, cur, mod);
    }

    return res;
}

inline int inv(int x, int mod=MOD) {
    return modpow(x, mod - 2, mod);
}

int fact[MAXN], tcaf[MAXN];

void gen_fact() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = prod(fact[i - 1], i);
    }

    tcaf[MAXN - 1] = inv(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; --i) {
        tcaf[i] = prod(tcaf[i + 1], i + 1);
    }
}

int choose(int n, int k) {
    if (!(0 <= k and k <= n)) {
        return 0;
    }

    return prod(fact[n], prod(tcaf[k], tcaf[n - k]));
}

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

    gen_fact();

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= k; ++i) {
        // break up k balls into i non-empty groups
        // (k - 1) choose (i - 1)
        int splits = choose(k - 1, i - 1);

        // n + 1 places to put them
        int spots = choose(n - k + 1, i);

        cout << prod(splits, spots) << '\n';
    }
    
    return 0;
}


Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
#N = I()
#A = [LI() for _ in range(N)]

a, b = list(map(int,sys.stdin.readline().rstrip().split()))

if a > 0:
    print('Positive')
elif a <= 0 and b >= 0:
    print('Zero')
else:
    if (a+b)%2 == 0:
        print('Negative')
    else:
        print('Positive')

Measured memory_bytes: 20948
import Text.Printf

ft (s, l) =
    printf "%F %F\n" s l

circle :: [Double] -> (Double, Double)
circle (r:_) =
  ( pi * r * r, 2.0 * pi * r)

main = do
  r <- getLine
  putStrLn $ ft $ circle $ map (read :: String -> Double) $ words r

Measured memory_bytes: 4036
import java.math.BigDecimal;
import java.util.*;

public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int N = sc.nextInt();
        long[] as = new long[N];
        long sum = 0;

        for (int i = 0; i < N; i++) {
            as[i] = sc.nextLong();
            sum += as[i];
        }

        // calc cumulative sums
        long[] cumulativeSums = new long[N];
        cumulativeSums[0] = as[0];
        for (int i = 1; i < N; i++) {
            cumulativeSums[i] = as[i] + cumulativeSums[i - 1];
        }

        long diffMin = Long.MAX_VALUE;
        for (int i = 0; i < N - 1; i++) {
            long opponent = sum - cumulativeSums[i];
            long diff = Math.abs(opponent - cumulativeSums[i]);
            diffMin = Math.min(diffMin, diff);
        }
        System.out.println(diffMin);
    }

}

Measured memory_bytes: 64860
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

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

    return 0;
}

Measured memory_bytes: 3548
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int sum(int n){
    int res = 0;
    while(n){
        res += n % 10;
        n /= 10;
    }
    return res;
}

int main(){
	int N; cin >>  N;
    int ans = INF;
    repr(i,1,N){
        ans = min(ans,sum(i)+sum(N-i));
    }
    cout << ans << endl;
}
   


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int maks, minn, inf, n, jj, ii, a[1000001];
int main()
{
	inf=2000000000;
	scanf("%d", &n);
	maks = -inf;
	minn = inf;
	for (int i = 1; i <= n; i++) 
	{
		scanf("%d", &a[i]);
		if (a[i]> maks){
			maks = a[i];
			ii = i;
		}
		if (a[i]<minn){
			minn = a[i];
			jj = i;
		}
	}
	printf("%d\n", 2*n-1);
	if (maks>abs(minn))
	{
		for (int i = 1; i <= n; i++) printf("%d %d\n", ii, i);
		for (int i = 1; i<n; i++) printf("%d %d\n", i, i+1);
	}else
	{
		for (int i = 1; i<= n; i++) printf("%d %d\n", jj, i);
		for (int i = n; i > 1; i--) printf("%d %d\n", i, i-1);
	}
	
}

Measured memory_bytes: 256
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for _ in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if b == A[i][j]:
                A[i][j] = 'x'
f = False
for i in range(3):
    if all(a == 'x' for a in A[i]):
        f = True
if all((A[0][0] == 'x', A[1][1] == 'x', A[2][2] == 'x')):
    f = True
if all((A[0][2] == 'x', A[1][1] == 'x', A[2][0] == 'x')):
    f = True
for j in range(3):
    tmp = []
    for i in range(3):
        tmp.append(A[i][j])
    if all(a == 'x' for a in tmp):
        f = True
print('Yes' if f else 'No')


Measured memory_bytes: 3064
import java.util.Scanner;

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();
		int ab = Math.abs(a - b);
		int bc = Math.abs(b - c);
		int ca = Math.abs(c - a);
		int ans = ab + bc + ca - Math.max(ab, Math.max(bc, ca));
		System.out.println(ans);

	}

}


Measured memory_bytes: 21844
s = int(input())
mod = 10**9 + 7
ans = [0, 0, 0, 1, 1, 1, 2, 3, 4]
val = sum(ans[3:7])
for i in range(7, s-1):
    ans.append(val+1)
    ans[-1] %= mod
    val += ans[i]
    val %= mod
print(ans[s])


Measured memory_bytes: 8968
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import math
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N, K = MAP()
    A = LIST()

    if K == 0:
        print(max(A))
        return

    # X決め打ち二分探索
    left = 0
    right = 10**9+7
    for i in range(100):
        # while right - left > 1.0e-6:
        mid = (right + left) / 2
        count = 0
        for a in A:
            count += int(math.ceil(a / mid))-1
        if count <= K:
            right = mid
        else:
            left = mid
    print(int(math.ceil(left)))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 94164
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, s, n, m) for(int i = s; i < (int)(n); i+=m)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) { 
        os << v[i]; 
        if (i != (int)v.size() - 1) 
            os << " "; 
    } 
    return os; 
} 

int main()
{
    ll K, X;
    cin >> K >> X;
    rep(i, X - K + 1, X + K, 1) {
        cout << i << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ALL(u) begin(u),end(u)
#define PB push_back
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

typedef long long int ll;
const int INF = (1<<30) - 1;
const double EPS = 1e-9;
const int MOD = 1000000007;

int W, H;
int dw[] = {0, 0, 1, -1};
int dh[] = {1, -1, 0, 0};

int dfs(vector<string> &field, int h, int w){
    field[h][w] = '#';
    
    int res = 1;
    for(int i=0; i<4; i++){
        int nh = h + dh[i];
        int nw = w + dw[i];
        if(0<=nh && nh<H && 0<=nw && nw<W && field[nh][nw]=='.'){
            res += dfs(field, nh, nw);
        }
    }
    return res;
}

//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(16);
    //cout.setf(ios::fixed);
    
    while(cin >> W >> H, W|H){
        vector<string> field(H);
        for(auto &l: field)
            cin >> l;
        
        for(int i=0; i<H; i++)
            for(int j=0; j<W; j++) if(field[i][j] == '@')
                cout << dfs(field, i, j) << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 3240
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		String arr[] = s.nextLine().split(" ");
		ArrayList<Integer> arrr = new ArrayList<Integer>();
		for(String str : arr){
			arrr.add(Integer.parseInt(str));
		}

		Collections.sort(arrr);
		int a = arrr.get(0);
		int b = arrr.get(1);
		int c = arrr.get(2);
		
		if((a+b) == c){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 9044
import sys
def input():
	return sys.stdin.readline()[:-1]

def least_bit_set(x):
	return x & (-x)


def delete_zeros_from(values, start):
	i = start
	for j in range(start, len(values)):
		if values[j] != 0:
			values[i] = values[j]
			i += 1
	del values[i:]


def eliminate(values):
	values = list(values)
	i = 0
	while True:
		delete_zeros_from(values, i)
		if i >= len(values):
			return values
		j = i
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) < least_bit_set(values[j]):
				j = k
		values[i], values[j] = (values[j], values[i])
		for k in range(i + 1, len(values)):
			if least_bit_set(values[k]) == least_bit_set(values[i]):
				values[k] ^= values[i]
		i += 1


def in_span(x, eliminated_values):
	for y in eliminated_values:
		if least_bit_set(y) & x != 0:
			x ^= y
	return x == 0



#values = [1, 5, 8, 2, 10]
#eliminated_values = eliminate(values)
#print(eliminated_values)
#x = int(input())
#print(in_span(x, eliminated_values))

t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	values = []
	ok = True
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			values.append(a[i])
		else:
			elim = eliminate(values)
			if not in_span(a[i], elim):
				ok = False
				break
	if ok:
		print(0)
	else:
		print(1)

Measured memory_bytes: 70816
#define DINGER_GISBAR
#include <bits/stdc++.h>
using namespace std;
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
#ifdef ZEROKUGI
#include <dumper.hpp>
#define dump(x) dumper::dumper(cerr, __LINE__, (#x), (x), 50, 1, 1)
#define tick(...) dumper::tick(__VA_ARGS__)
#pragma message "Compiling " __FILE__
#else
#define dump(x)
#define tick(...)
#endif
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n) \
    for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c)   \
    sort(all(c)); \
    for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto&
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) { return 1LL << x; }
template <class T>
inline int size(const T& a) {
    return (int)a.size();
}
template <class T>
inline bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
    return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T>& v, const char& c) {
    return make_pair(v, c);
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
#ifdef ZEROKUGI
    if (v.empty()) {
        cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
        exit(EXIT_FAILURE);
    }
#endif
    for (auto& x : v) is >> x;
    return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const pair<vector<T>, char>& v) {
    bool t = 0;
    for (const T& x : v.first) {
        if (t) os << v.second;
        os << x;
        t = 1;
    }
    return os;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
    return os << v * ' ';
}
struct before_main {
    before_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
        tick(0, 0);
    };
} __before_main;
//}}}TEMPLATE_END

char a[10][10];

int main() {
    int h, w;
    cin >> h >> w;
    rep(i, h) cin >> a[i];

    int y = 0, x = 0;
    while (!(y == h - 1 && x == w - 1)) {
        bool down = a[y + 1][x] == '#';
        bool right = a[y][x + 1] == '#';
        if (down ^ right) {
            if (down) y++;
            if (right) x++;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    }

    while (!(y == 0 && x == 0)) {
        bool up = y > 0 && a[y - 1][x] == '#';
        bool left = x > 0 && a[y][x - 1] == '#';
        if (up ^ left) {
            if (up) y--;
            if (left) x--;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    cout << "Possible" << endl;
    return 0;
}


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

int main() {
  string str;
  int smallCnt = 0;
  string strBef,strAft;
  int i = 0;
  bool check = false;
  
  cin >> str;
  
  while(str.size() > 1){
    // 最後の文字削除
    str.erase(--str.end());
    // 奇数なら不可なので次へ
    if(str.size() % 2 == 1) continue;
    
    i = str.size() / 2;
    strBef = str.substr(0,i);
    strAft = str.substr(i);
    
    // チェック
    if(strBef == strAft){
      smallCnt = str.size();
      break;
    }
  }
  cout << smallCnt;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var odd = 0L;
            for (int i = 1; i <= N; i++)
            {
                if (i % 2 == 1)
                {
                    odd++;
                }
            }
            return (double)odd / N;
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 11092
n, k = list(map(int, input().split()))
trans = list(map(int, input().split()))
trans = [-1] + trans
dest = 1
seen = [False] * (n+1)
start = 0
output = 0
t = []
for _ in range(k):
  dest = trans[dest]
  if seen[dest]:
    for i, x in enumerate(t):
      if x == dest:
        start = i
    break
  seen[dest] = True
  t.append(dest)
if len(t) < k:
  s = t[start:]
  output = s[(k - len(t[:start]) - 1) % len(s)]
else:
  output = t[k-1]
print(output)
  

Measured memory_bytes: 32372
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int K = scan.nextInt();
        if (N % K == 0) {
            System.out.println(0);
        } else {
            System.out.println(1);
        }
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int a;
bool isprime(int x)
{
	if(x==2) return true;
	if(x%2==0) return false;
	else 
	{
		for(int i=2;i<sqrt(x);i++)
		{
			if(x%i==0) return false;
		}
		return true;
	}
}
int main()
{
	cin>>a;
	for(int j=a;;j++)
	{
		if(isprime(j)) return !printf("%d\n",j);
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 1 + 1e5;
const ll oo = 1  +1e18;
typedef pair < int, int > II;
typedef pair < int, II > III;



int main(){
    int n;
    cin >> n;
    int ans = n / 1.08;
    if (int (ans * 1.08) == n)cout << ans << '\n';
    else if (int ((ans + 1) * 1.08) == n)cout << ans + 1 << '\n';
    else cout << ":(" << '\n';
   
    return 0;
}


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

string FILENAME = "filename";
#define io ifstream fin(FILENAME + ".in"); ofstream fout(FILENAME + ".out")
#define fwrite(X) fout << X;
#define fwriteln(X) fout << X << endl;
#define qio ios_base::sync_with_stdio(false); cin.tie(NULL)

#define forl(V, N) for(int V = 0; V < N; V++)
#define for1(V, N) for(int V = 1; V <= N; V++)
#define fore(E, X) for(auto &E:X)
#define newl cout << endl
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
#define rem(X) X.top(); X.pop()
#define setmin(A, B) A = min(A, B)
#define setmax(A, B) A = max(A, B)

#define graph unordered_map<int, unordered_set<int>>
#define um unordered_map
#define us unordered_set
#define vi vector<int>
#define pi pair<int, int>
#define ll long long
#define pb push_back
#define mp make_pair
#define ins insert

int main() {
    qio; char c; cin >> c;
    string al = "abcdefghijklmnopqrstuvwxyz";
    int loc = al.find(c);
    println(al[loc+1]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define in insert
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n;
    cin>>n;
    int a[n+1][4];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            cin>>a[i][j];
        }
    }

    vector<int> dp1(n);
    vector<int> dp2(n);
    vector<int> dp3(n);
    dp1[1]=a[1][1];
    dp2[1]=a[1][2];
    dp3[1]=a[1][3];
    for(int i=2;i<=n;i++){
        dp1[i]=a[i][1]+max(dp2[i-1],dp3[i-1]);
        dp2[i]=a[i][2]+max(dp1[i-1],dp3[i-1]);
        dp3[i]=a[i][3]+max(dp2[i-1],dp1[i-1]);
    }
    cout<<max(dp1[n], max(dp2[n],dp3[n]) );
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+5;
const long long inf=0x3f3f3f3f;
long long a[maxn],b[maxn],c[maxn],sum=0;
long long d[maxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	long long n,q;
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		d[a[i]]++;
	}
	cin>>q;
	for(long long i=1;i<=q;i++)
	{
		cin>>b[i]>>c[i];
		long long x=d[b[i]];
		long long y=x*(c[i]-b[i]);
		sum+=y;
		d[b[i]]=0;
		d[c[i]]+=x;
		cout<<sum<<"\n";
	}
	return 0;
}




Measured memory_bytes: 6680
#include<iostream>
#include<vector>
#include<utility>
#include<map>
#include<deque>
#include<numeric>
#include<algorithm>
#include<unordered_map>
#include<cmath>

using namespace std;
using ll = long long int;
constexpr int INF = 1 << 29;
constexpr ll MOD = ll(1e9 + 7);

int n, m;
vector<string> a, b;

bool is_sub_img(int x, int y) {
	bool ret = true;
	for (int i = 0; i < m; i++) {
		if (a[y + i].substr(x, m) != b[i]) {
			ret = false;
			break;
		}
	}
	return ret;
}


int main(void) {
	cin >> n >> m;
	a = vector<string>(n);
	b = vector<string>(m);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];

	string ret = "No";
	for (int i = 0; i <= n - m; i++) {
		for (int j = 0; j <= n - m; j++) {
			if (is_sub_img(i, j)) {
				ret = "Yes";
				break;
			}
		}
	}
	cout << ret << endl;
	return 0;
}

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

static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra() {
  int minv;
  int d[MAX], color[MAX];
  for (int i = 0; i < n; i ++) {
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0] = 0;
  color[0] = GRAY;
  while (true) {
    minv = INFTY;
    int u = -1;
    for (int i = 0; i < n; i ++) {
      if (minv > d[i] && color[i] != BLACK) {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    color[u] = BLACK;
    for (int v = 0; v < n; v ++) {
      if (color[v] != BLACK && M[u][v] != INFTY) {
        if (d[v] > d[u] + M[u][v]) {
          d[v] = d[u] + M[u][v];
          color[v] = GRAY;
        }
      }
    }
  }

  for (int i = 0; i < n; i ++) {
    cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < n; j ++) M[i][j] = INFTY;
  }

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

  dijkstra();

  return 0;
}



Measured memory_bytes: 3104
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    for(ll i=1;i * (i-1) / 2 <= 100000; ++i)
    {
        if((n * 2) % i == 0 && (n * 2) / i == (i - 1))
        {
            cout << "Yes" << endl;
            ll numsets = i;
            // i = # of sets
            vector<pair<int,int>> pairs;
            for(int j=0;j<numsets;++j)
            {
                for(int k=j+1;k<numsets;++k)
                {
                    pairs.push_back(MP(j,k));
                }
            }
            cout << numsets << endl;
            vector<int> sets[numsets];
            for(int k=0;k<numsets;++k)
            {
                for(int j=0;j<pairs.size();++j)
                {
                    if(pairs[j].first == k || pairs[j].second == k)
                    {
                        sets[k].push_back(j+1);
                    }
                }
                cout <<  sets[k].size() << " ";
                for(int j=0;j<sets[k].size();++j)
                {
                    cout << sets[k][j] << " \n"[j == (sets[k].size() - 1)];
                }
            }

            
            return 0;
        }
    }
    cout << "No" << endl;
}

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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) (int)((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	string s;
	cin >> s;
	int a = 0, b = 0;
	for (char c : s)
		if (c == 'A') a++;
		else b++;
	if (a > 0 && b > 0) puts("Yes");
	else puts("No");
}


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

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i, n) cin >> vec[i];
  int cnt = 1;
  int status = 0;
  rep(i, n-1){
    if(status == 0){
      if(vec[i+1]-vec[i] < 0) status = -1;
      else if(vec[i+1]-vec[i] > 0) status = 1;
    }else if(status == 1){
      if(vec[i+1]-vec[i] < 0){
        status = 0;
        cnt++;
      }
    }else{
      if(vec[i+1]-vec[i] > 0){
        status = 0;
        cnt++;
      }
    }
  }
  cout << cnt << endl;
  return 0;
}
  


Measured memory_bytes: 640
/* ITP1_5_D: Structured Programming */
/* 20181121 AOJ */

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void) {
	int n, i = 0, temp ;

	scanf("%d", &n);

	while((++i) <= n) {
		temp = i;
		if(temp % 3 == 0 || temp % 10 == 3) {
			printf(" %d", i);
		} else{
			    while(temp /= 10) {
					if(temp % 10 == 3) {
						printf(" %d", i);
						break;
					}
				}
		}
	}

	putchar('\n');

	return 0;
}


Measured memory_bytes: 2136
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author noob_coder
 */
public class Main {
        public static void main(String[] args) {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                InputReader in = new InputReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                TaskA solver = new TaskA();
                solver.solve(1, in, out);
                out.close();
        }

        static class TaskA {
                public void solve(int testNumber, InputReader in, PrintWriter out) {
                        int a = in.i();
                        int b = in.i();
                        int c = in.i();
                        int d = in.i();
                        out.println(Math.min(a + c, Math.min(a + d, Math.min(b + c, b + d))));
                }

        }

        static class InputReader {
                InputStream is;
                private byte[] inbuf = new byte[1024];
                public int lenbuf = 0;
                public int ptrbuf = 0;

                public InputReader(InputStream is) {
                        this.is = is;
                }

                private int readByte() {
                        if (lenbuf == -1) throw new InputMismatchException();
                        if (ptrbuf >= lenbuf) {
                                ptrbuf = 0;
                                try {
                                        lenbuf = is.read(inbuf);
                                } catch (IOException e) {
                                        throw new InputMismatchException();
                                }
                                if (lenbuf <= 0) return -1;
                        }
                        return inbuf[ptrbuf++];
                }

                public int i() {
                        int num = 0, b;
                        boolean minus = false;
                        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
                        if (b == '-') {
                                minus = true;
                                b = readByte();
                        }

                        while (true) {
                                if (b >= '0' && b <= '9') {
                                        num = num * 10 + (b - '0');
                                } else {
                                        return minus ? -num : num;
                                }
                                b = readByte();
                        }
                }

        }
}



Measured memory_bytes: 21460