akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Data{
public:
	int N{-1},E;
	ll S;
	bool operator<(const Data& r){
		return N<r.N;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	while(true){
		int N=in();
		if(!N) break;
		map<int,Data> H;
		REP(i,N){
			int E=in();
			ll P=in<ll>(),Q=in<ll>();
			H[E].S+=P*Q;
			H[E].E=E;
			if(H[E].N==-1) H[E].N=i;
		}
		vector<Data> D;
		for(auto& x:H) D.push_back(x.second);
		sort(ALL(D));
		int num=0;
		for(auto& x:D){
			if(x.S>=1000000LL){
				out(x.E);
				num++;
			}
		}
		if(!num) out("NA");
	}
	
	return 0;
}


Measured memory_bytes: 3212
n = gets.to_i
as = []

n.times do
  as.push gets.to_i
end
max = as.max
flg = true
flg = !flg if as.select{|i| max == i}.count >= 2
as.each_with_index do |v, i|
  if max == v && flg
    as_as = as.dup
    as_as.delete_at(i)
    puts as_as.max
  else
  	puts max
  end
end

Measured memory_bytes: 7036
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int dy8[] = {0,1,1,1,0,-1,-1,-1};
int dx8[] = {1,1,0,-1,-1,-1,0,1};

/*==================================================*/
/*variable*/
int H, W;
string S[55];

/*==================================================*/
/*function*/

/*==================================================*/

int main() {
    cin>>H>>W;
    REP(i,0,H){
        cin>>S[i];
    }


    REP(i,0,H){
        REP(j,0,W){
            bool f = false;
            if(S[i][j] == '.'){
                bool f = true;
                continue;
            }
            REP(k,0,4){
                int ny = i + dy[k];
                int nx = j + dx[k];

                if(!CK(ny, 0, H) || !CK(nx, 0, W)){
                    continue;
                }

                if(S[ny][nx] == '#'){
                    f = true;
                }
            }
            if(!f){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }

    cout<<"Yes"<<endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var buff []byte

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buff, bufio.MaxScanTokenSize*1024)
	log.SetFlags(log.Lshortfile)
}

func main() {
	N := nextInt()
	X := nextInt()
	Y := nextInt()
	var g [2001][2001]int
	for i := 0; i < 2001; i++ {
		for j := 0; j < 2001; j++ {
			g[i][j] = 1e9
		}
	}
	g[X][Y] = 1
	g[Y][X] = 1
	for i := 1; i < N+1; i++ {
		for j := 1; j < N+1; j++ {
			g[i][j] = abs(i - j)
			g[j][i] = abs(i - j)
		}
	}
	ans := make([]int, N)
	for i := 1; i < N+1; i++ {
		for j := i + 1; j < N+1; j++ {
			d := minInt(j-i, g[i][X]+g[Y][j]+1, g[i][Y]+g[X][j]+1)
			ans[d]++
		}
	}
	for i := 1; i < N; i++ {
		fmt.Println(ans[i])
	}
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextFloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func nextInts(n int) (r []int) {
	r = make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func maxInt(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func minInt(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 32896
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=1e9;
const ll MOD=1e9+7;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}

int dis2(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int main(){
    ll n;cin>>n;
    vector<int> ans;
    ll m=1;
    while(!((m-1)*m/2<n&&n<=m*(m+1)/2)) m++;
    while(n>0){
        if(n<=m){
            ans.push_back(n);
            break;
        }else{
            ans.push_back(m);
            n-=m;
            m--;
        }
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<(int)ans.size();i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 384
N = int(input())
event = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0, 0, 0] for _ in range(N)]
dp[0] = event[0]

for i in range(1, N):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + event[i][j])
print(max(dp[N - 1]))


Measured memory_bytes: 105996
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	string s;
    cin>>s;

    int sum=0;
    for(int i=0;i<6;i++){
        if(s[i]=='1'){
            sum++;
        }
    }
	
	
    cout << sum << endl;

	return 0;
}


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

int main() {
  // ここにプログラムを追記
  int a, b, x;
  cin >> a >> b;
  x = (a + b) / 2;
  if((a + b) % 2 != 0){
    x = x + 1;
  }
  cout << x << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<stack>
#include<sstream>
#include<string>
#include<cassert>
#include<ctime>
#include<functional>
#include<deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
int kase = 0;
int n, m;
const int maxn = 1e5 + 10;
vector<int> G[maxn];


int dfs(int u, int pa)
{
	int sg = 0;
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if (v != pa)
			sg = sg ^ (dfs(v, u) + 1);
	}
	return sg;
}

int main() {
	while(cin>>n)
	{
		for (int i = 0; i <= n; i++)  G[i].clear();
		for (int i = 0; i < n-1; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		if (dfs(1, -1)) printf("Alice\n");
		else printf("Bob\n");
	}
}

Measured memory_bytes: 11904
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

ll GCD (ll a, ll b) {
    if (a < b) {
        swap(a, b);
    }

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

    return b;
}

ll LCM (ll a, ll b) {
    ll g = GCD (a, b);
    return a * b / g;
}

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

    ll N, M;
    cin >> N >> M;
    vec a(N);
    Rep (i, N) {
        cin >> a[i];
        a[i] /= 2;
    }

    ll now = a[0];
    Rep (i, N) {
        now = LCM(now, a[i]);
    }

    Rep (i, N) {
        if (now / a[i] % 2 == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    cout << (M / now + 1) / 2 << endl;
}

Measured memory_bytes: 1024
def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

    class BIT():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        # 位置iに値vを足す
        def add(self, i, v):
            x = i+1
            while x < self.n + 1:
                self.bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret = 0
            x = i
            while x > 0:
                ret += self.bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    def value(v):
        if n == 1:
            if v <= a[0]:
                return True
            else:
                return False
        b = [0]+list(ac([(i >= v)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            return True
        else:
            return False

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(b_search(0, 10**9+1, value))


main()


Measured memory_bytes: 120172
import sys
input = sys.stdin.readline

def main():
    S = input().strip()

    n = (len(S) + 1) // 2

    a = S[:n]
    b = S[n-1:]

    k = len(a[:-1])



    if k % 2 == 1:
        kn = k // 2
        aa = a[:-1][:kn]
        ab = a[:-1][kn+1:]

        ba = b[1:][:kn]
        bb = b[1:][kn+1:]
    else:
        kn = k // 2
        aa = a[:-1][:kn]
        ab = a[:-1][kn:]

        ba = b[1:][:kn]
        bb = b[1:][kn:]

    if a==b[::-1] and aa==ab[::-1] and ba==bb[::-1]:
        print('Yes')
    else:
        print('No')




if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 1000005
#define mod 1000000007



int main(){
    fastio;
    int n;
    cin>>n;
    cout<<(1000-(n%1000))%1000<<"\n";
    return 0;
}



Measured memory_bytes: 3628
#include<iostream>
using namespace std;
 int main()
{
int a,b,c,d;
long ar1,ar2;
cin>>a>>b>>c>>d;
ar1=a*b;
ar2=c*d;
if(ar1>ar2)
cout<<ar1;
else if(ar1<ar2)
cout<<ar2;
else
cout<<ar1;
return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def knapsack_problem(n,cap,value,weight):
    ans = 0
    dp = [[0]*(cap+1) for i in range(n+1)]
    
    for i in range(n):
        for w in range(cap+1):
            if w >= weight[i]:
                dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i],dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]

    can = 0
    for s in dp:
        can = max(can,max(s))

    return can
        
if __name__ == "__main__":
    n,w = map(int,input().split())
    vl = [0] * n
    wl = [0] * n
    for i in range(n):
        vl[i], wl[i]= map(int,input().split())

    print(knapsack_problem(n,w,vl,wl))



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

int main() {
  string s, t;
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) != t.at(i)){
      cout << "No" << endl;
      break;
    }
    else if(i == s.size() - 1){
      cout << "Yes" << endl;
    }
  }
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
typedef long long llong;
using namespace std;
const llong DIV = 1000000007;

llong mod_pow(llong M, llong N, llong mod = DIV)
{
	if (N == 0)
	{
		return 1;
	}
	if (N == 1)
	{
		return M;
	}

	llong ret = mod_pow(M, N / 2, mod);
	ret = ret * ret % mod;

	if (N & 1)
	{
		ret = (ret * M) % mod;
	}

	return ret;
}

llong ncr(llong N, llong r, llong mod = DIV)
{
	r = min(r, N - r);
	llong ret = 1;
	for (int i = 1; i <= r; i++)
	{
		ret = ret * (N - i + 1) % mod;
		ret = ret * mod_pow(i, mod - 2) % mod;
	}
	return ret;
}

int main()
{
	llong N,M;
	vector<llong> Ss,Ts;
	cin>>N>>M;
	for(llong i=0;i<N;i++){
		int s;
		cin>>s;
		Ss.push_back(s);
	}
	for(llong i=0;i<M;i++){
		int t;
		cin>>t;
		Ts.push_back(t);
	}
	vector<vector<llong> > dp (N,vector<llong>(M,0));
	
	dp[0][0] = 1;
	if (Ss[0]==Ts[0]){
		dp[0][0]=2;
	}
	for(llong i=1;i<N;i++){
		dp[i][0]=dp[i-1][0];
		if(Ss[i]==Ts[0]){
			dp[i][0]+=1;
		}
	}
	for(llong i=1;i<M;i++){
		dp[0][i]=dp[0][i-1];
		if(Ss[0]==Ts[i]){
			dp[0][i]+=1;
		}
	}
	int n=1,m=1;
	for(llong n=1;n<N;n++){
		for(llong m=1;m<M;m++){
			if(Ss[n-1]==Ts[m]){

			}
			dp[n][m] = (dp[n][m-1]+dp[n-1][m]+DIV-dp[n-1][m-1])%DIV;
			if(Ss[n]==Ts[m]){
				dp[n][m] += dp[n-1][m-1];
				dp[n][m] = dp[n][m]%DIV;
			}
		}
 
	}
	cout<<(dp[N-1][M-1]%DIV)<<endl;
	return 0;
}

Measured memory_bytes: 31616
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 k = sc.nextInt();
        if((b-a+1)/2 < k){
            for(int i=a; i<=b; i++){
                System.out.println(i);
            }
            return;
        }
        for(int i=a; i<a+k; i++){
            System.out.println(i);
        }
        for(int i=b-k+1; i<=b; i++){
            System.out.println(i);
        }
    }
}


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

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

	int A, B, C, D;

	cin >> A >> B >> C >> D;

	bool win = true;

	while(A > 0 and C > 0){

		C -= B;

		if(C <= 0){
			break;
		}

		A-= D;

		if(A <= 0){
			win = false;
			break;
		}
	}

	if(win)
		cout << "Yes";
	else
		cout << "No";


	return 0;
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    ll N,K;
    vector<ll> P,C;
    vector<ll> sumC[5001];
    vector<ll> maxC;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        ll p; cin >> p;
        p--;
        P.pb(p);
    }
    for (int i = 0; i < N; i++) {
        ll c; cin >> c;
        C.pb(c);
    }
    for (int i = 0; i < N; i++) {
        ll c = 1;
        ll now = P[i];
        ll cnt = C[i];
        ll maxx = cnt;
        sumC[i].pb(cnt);
        while(now != i && c < K){
            c++;
            cnt += C[now];
            now = P[now];
            maxx = max(maxx,cnt);
            sumC[i].pb(cnt);
        }
        maxC.pb(maxx);
    }
    ll ans = -LINF;
    for (int i = 0; i < N; i++) {
        if(sumC[i][sumC[i].size()-1] > 0 && sumC[i].size() != K){
            ll cnt = K / sumC[i].size();
            ll diffcnt = K % sumC[i].size();
            if(diffcnt == 0){
                cnt--;
                diffcnt = sumC[i].size();
            }
            ll num = sumC[i][sumC[i].size()-1] * cnt;
            ans = max(ans,num);
            for (int j = 0; j < diffcnt; j++) {
                ans = max(ans,num+sumC[i][j]);
            }
        } else {
            ans = max(ans,maxC[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 218964
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> Vl;
typedef vector<double> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<VS> VSS;  
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;  //ll とdoubleは違う
// cout << << endl;
// cin >> ;

int main(){
    ll a,b,c,d=0,k=0,n,m,h,w,p,q,ans=0;
    string s,s1,s2;
    cin >> a >> b >> c >> d;

    n = c - a;
    m = d - b;

    cout << string(m,'U') << string(n,'R');
    cout << string(m,'D') << string(n,'L');

    cout << 'L' <<  string(m+1,'U') << string(n+1,'R') << 'D';
    cout << 'R' <<  string(m+1,'D') << string(n+1,'L') << 'U';

    cout << endl;
    return 0;
}

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

a = 0
for i in range(1, n + 1):
    if (i % 3 is 0) and (i % 5 is 0):
        # print("FizzBuzz")
        continue
    elif i % 3 is 0:
        # print("Fizz")
        continue
    elif i % 5 is 0:
        # print("Buzz")
        continue
    else:
        a += i

print(a)


Measured memory_bytes: 9172
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

vvi d;
const int INF = 1001001001;

void warshall_floyd(int n) { // n: 頂点数
    rep(k, n) { // k : 経由する頂点
        rep(i, n) {
            rep(j, n) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

void Main() {
    int n, m, R; 
    cin >> n >> m >> R;

    vi r(R); 
    rep(i, R) {
        cin >> r[i]; 
        r[i]--;
    }
    
    d = vvi(n, vi(n, INF));
    rep(i, n) d[i][i] = 0;
    
    rep(i, m){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    
    warshall_floyd(n);
    
    ll ans = INF;
    sort(all(r));
    
    do{
        ll tot = 0;
        rep(i, R-1) tot += d[r[i]][r[i+1]];
        ans = min(ans, tot);
    }while(next_permutation(all(r)));
    
    cout << ans << endl;
    return;
}

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

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

max = 0
ans = 1

for i in range(1, N+1):
    count = 0
    a = i
    while True:
        if a % 2 == 1:
            if max < count:
                max = count
                ans = i
        else:  
            a = int(a / 2)
            count += 1
            continue
        break

print(ans)

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

int main(){
	int N, M, X;
	cin >> N >> M >> X;
	int a[M];
	for (int i=0; i<M; i++){
		cin >> a[i];
	}

	int small = 0;
	int large = 0;
	for (int i = 0; i < M; i++) {
		if (a[i] < X) {
			small++;
		} else if (a[i] > X) {
			large++;
		}
	}

	cout << min(small, large) << endl;
}

Measured memory_bytes: 256
"use strict"

const MOD = 1000000007;

function main(arg) {
    let tmp = arg.trim().split('\n');
    let n = tmp[0].split(" ").map(Number)[0];
    let m = tmp[0].split(" ").map(Number)[1];
    tmp.shift()
    tmp = tmp.map(Number)

    let a = tmp
    let step = new Array(n + 1).fill(0)
    for (let i = 0; i < a.length; i++) {
        step[a[i]] = -1
    }

    step[0] = 1
    // console.log(step)

    for (let i = 0; i < n; i++) {
        if (step[i] == -1) continue
        if (step[i+1] != -1) {
            step[i+1] += step[i]
            step[i+1] %= MOD;
        }
        if (step[i+2] != -1) {
            step[i+2] += step[i]
            step[i+2] %= MOD;
        }
    }

    // for (let i = 0; i < n; i++) {
    //     if (step[i] == -1) continue;
    //     if (step[i+1] != -1){
    //         step[i+1] +=step[i];
    //         step[i+1] %=MOD;
    //     }
    //     if (step[i+2] != -1){
    //         step[i+2] +=step[i];
    //         step[i+2] %=MOD;
    //     }
    // }
    console.log(step[n]);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));



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

#define REP(i,n) for(decltype(n) i=0; i<(n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define st first
#define nd second
#define pb push_back

typedef pair<int,int> pii;
typedef vector<int> vi;

int n;
int A[300][300];

void solve(){
    cin>>n;
    REP(i,n)
        REP(j,n)
            cin>>A[i][j];
    long long ans = 0;
    REP(i,n){
        REP(j,i){
            bool ok = true;
            REP(k,n){
                if(k==i || k == j) continue;
                if(A[i][k] + A[k][j] < A[i][j]){
                    cout<<"-1\n";
                    return;
                }
                if(A[i][k] + A[k][j] == A[i][j])
                    ok = false;
            }
            if(ok)
                ans += A[i][j];
        }
    }
    cout<<ans<<'\n';
}

int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  int n;
  map<int, int> data;
  cin >> n;
  REP(i, n) {
    int x;
    cin >> x;
    data[x] += 1;
  }
  bool flag = true;
  for (int i = (n - 1) % 2; i < n; i += 2) {
    if (i == 0) {
      if (data[0] != 1) {
        flag = false;
        break;
      }
    } else {
      if (data[i] != 2) {
        flag = false;
        break;
      }
    }
  }
  ll ans = 1;
  if (flag) {
    for (int i = 1; i <= n / 2; i++) {
      ans *= 2;
      ans %= MOD;
    }
  }
  if (flag) {
    cout << ans << endl;
  } else {
    cout << 0 << endl;
  }
}

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

int main(){

  //initialization
  int N, A;
  int surplus;
  //input
  cin >> N;
  cin >> A;
  
  //solver
  surplus = N % 500;
  if(A >= surplus) cout << "Yes" << "\n";
  else cout << "No" << "\n";
}


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

inline int read(){
	re int ans = 0;re bool f = 1;re char ch = getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f = 0;ch = getchar();}
	while(ch>='0'&&ch<='9'){
		ans = (ans<<3)+(ans<<1)+(ch^48);
		ch = getchar();
	}
	return f?ans:-ans;
}
int minn(int a,int b){return a>b?b:a;}
int aBs(int a){return a>0?a:-a;}
signed main(void){
	int n,k;
	n = read();k = read();
	printf("%lld\n",min(aBs(n%k-k),n%k));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1<<29)
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int p){
	for(int i=2;i<=sqrt(p);i++){
		if(!p%i)return false;
	}
	return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b==1)return a%MOD;
    if(b%2)return modpow(a,b-1)*a%MOD;
    else return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
    if(b==0||a==b)return 1;
    if(b==1)return a%MOD;
    return (comb(a-1,b-1)+comb(a-1,b))%MOD;
}
int n,m,a,b,x[9][9],o[8],ans=0;
signed main(){
    cin>>n>>m;
    rep(i,m){
        cin>>a>>b;
        x[a][b]=x[b][a]=1;
    }
    rep(i,n)o[i]=i+1;
    do{
        for(int i=1;i<n;i++){
            if(x[o[i-1]][o[i]]==0)goto bed;
        }
        ans++;
        bed:;
    }while(next_permutation(o+1,o+n));
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input())
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))

ans = 0
for i in range(N):
    tmp = 0
    tmp += sum(A1[0:i+1])
    tmp += sum(A2[i:N+1])
    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 3060
n = int(input())
a_list = list(map(int,input().split()))

reply_list =  []
for i in range(n):
    if i == 0:
        reply_list.append(sum(a_list[::2]) - sum(a_list[1::2]))
    elif i == 1:
        reply_list.append(a_list[0] + sum(a_list[1::2]) - sum(a_list[2::2]))
    else:
        reply_list.append(reply_list[-2] + a_list[i-2]*(-2) + a_list[i-1]*2)

reply_list = map(str, reply_list)
print(' '.join(reply_list))

Measured memory_bytes: 18120
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
vector<vector<int>>dp; // dp(i,j) ways when i children and ith children get j candies
vector<int>v;



void solve(){
    int n,k;cin>>n>>k;
    v.resize(n);
    dp.resize(n,vector<int>(k+1,-1));
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<=k;i++){
        dp[0][i] = i<=v[0] ? 1 :0;
    }
    for(int i=0;i<n;i++){
        dp[i][0]=1;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j] = (mod + (dp[i-1][j] +dp[i][j-1])%mod - ((j-v[i]-1>=0) ? dp[i-1][j-v[i]-1]: 0))%mod;
        }
    }
    cout<<dp[n-1][k]<<"\n";
}

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

    cout.precision(10);
    int t=1;//cin>>t;
    while(t--){

        solve();
    }
    return 0;
}


Measured memory_bytes: 39808
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int N;
    cin >> N;
    V(char) s(N);

    bool res = false;
    rep(i, N) {
        cin >> s[i];
        if(s[i] == 'Y') res = true;
    }

    if(res) cout << "Four";
    else cout << "Three";
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 100
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{
	int fr,to,val;
}e[(MN*MN<<1)+5];
int d[13][13],a,b,cnt;
bool vis[13][13];
int main()
{
	a=in();b=in();
	for (int i=1;i<=a;++i)
	for (int j=1;j<=b;++j) d[i][j]=in();
	for (int i=0;i<=MN;++i)
	for (int j=0;j<=MN;++j){
		int mx=0;
		for (int k=1;k<=a;++k)
		for (int l=1;l<=b;++l) mx=max(mx,d[k][l]-i*k-j*l);
		e[++cnt].fr=i+1;e[cnt].to=((MN+1)<<1)-j;e[cnt].val=mx;
		for (int k=1;k<=a;++k)
		for (int l=1;l<=b;++l)
		if (d[k][l]==mx+i*k+j*l) vis[k][l]=1;
	}
	for (int i=1;i<=a;++i)
	for (int j=1;j<=b;++j)
	if (!vis[i][j]) {puts("Impossible");return 0;}
	puts("Possible");printf("202 %d\n",cnt+(MN<<1));
	for (int i=1;i<=MN;++i) printf("%d %d X\n%d %d Y\n",i,i+1,i+MN+1,i+MN+2);
	for (int i=1;i<=cnt;++i) printf("%d %d %d\n",e[i].fr,e[i].to,e[i].val); 
	puts("1 202");return 0;
}

Measured memory_bytes: 384
N, K = map(int, input().split())

if K % 2 == 0:
    c1 = 0
    c2 = 0
    for i in range(1, N+1):
        if i % K == K//2:
            c2 += 1
        if i % K == 0:
            c1 += 1
    print(c1**3+c2**3)
else:
    c = 0
    for i in range(1, N+1):
        if i % K == 0:
            c += 1
    print(c**3)
    

Measured memory_bytes: 3060
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [x*(-1) for x in a]
heapq.heapify(a)

for i in range(m):
    c = (heapq.heappop(a)*(-1)//2)*(-1)
    heapq.heappush(a, c)
print(-sum(a))



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

int main() {
	int N;
	cin >> N ;
	vector<int> a(N), ans(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		ans[a[i]-1] = i+1;
	}
	for (int i = 0; i < N; i++) cout << ans[i] << " ";

	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MAX 8001

bool eqsum(int k, vector<int> &v){
	int sum=0;
	for(int i=0; i<v.size(); i++) sum+=v[i];
	if((sum+k)%2==1) return false;

	vector<bool> d(MAX, false), dd(MAX);
	d[0]=true;
	for(int m=0; m<v.size(); m++){
		for(int i=0; i<=MAX; i++){
			dd[i]=d[i];
			if(i>=v[m]) dd[i]=dd[i]|d[i-v[m]];
		}
		d=dd;
	}
	return d[(sum+k)/2];
}

int main(){
	string s;
	int x, y;
	cin >> s >> x >> y;
	vector<int> v;
	int m=0, cnt=0;
	char c='F';
	for(int i=0; i<s.length(); i++){
		if(s[i]=='T'){
			v.push_back(cnt);
			cnt=0;
		}else{
			cnt++;
		}
	}
	v.push_back(cnt);

	vector<int> ve, vo;
	for(int i=2; i<v.size(); i+=2) ve.push_back(v[i]);
	for(int i=1; i<v.size(); i+=2) vo.push_back(v[i]);

	if(eqsum(abs(x-v[0]), ve) && eqsum(abs(y), vo)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 384
import bisect
from operator import itemgetter

Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax+1))
primes [1] = 0

for i in range(2, int(rmax**0.5)+ 2):
    for j in range(2 * i, rmax+1, i):
        primes[j] = 0
primes = [prime for prime in primes[:] if prime!=0]

lst2017 = [x for x in primes if x != 2 and (x+1)//2 in primes]

for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print(nr - nl)

Measured memory_bytes: 33420
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
//#include <unordered_map>
#define N 1000010
//#define lson x<<1
//#define rson x<<1|1
//#define mid ((lt[x].l+lt[x].r)/2)
//#define ID(x, y) ((x)*m+(y))
//#define CHECK(x, y) ((x)>=0 && (x)<n && (y)>=0 && (y)<m)
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL INF=0x3f3f3f3f;
void Open()
{
    #ifndef ONLINE_JUDGE
        freopen("F:/in.txt","r",stdin);
        //freopen("F:/my.txt","w",stdout);
    #endif // ONLINE_JUDGE
}
LL n, ans;
LL d[N];
int w[N];
vector<LL> G[N];
vector<LL> lis[N];
queue<LL> que;
int main2()
{
//    Open();
    scanf("%lld", &n);
    for(LL i = 0; i < n; i++){
        LL l;
        scanf("%lld%lld", &w[i], &l);
        if(l != -1) G[i].push_back(l), d[l]++;
    }
    for(LL i = 0; i < n; i++)
    {
        if(d[i] == 0) que.push(i);
    }
    while(!que.empty())
    {
        LL u = que.front();que.pop();
        for(LL i = 0; i < G[u].size();i++)
        {
            LL v = G[u][i];
            lis[v].push_back(w[u]);
            w[v] += w[u];
            d[v]--;
            if(d[v] == 0) que.push(v);
        }
    }
    ans = 0;
    for(LL i = 0; i < n; i++)
    {
        sort(lis[i].begin(), lis[i].end());
        LL siz = lis[i].size();
        for(LL j = siz-2, cnt = 1; j >= 0; j--, cnt++)
        {
            ans += lis[i][j] * cnt;
        }
    }
    printf("%lld\n", ans);
    exit(0);
}
extern int main2(void) __asm__ ("_main2");
int main()
{
    int size = 256 << 20;  // 256Mb
    char *p = (char *)malloc(size) + size;
    __asm__ __volatile__(
        "mov  %0, %%rsp\n"      
        "push $_exit\n"
        "jmp _main2\n"
        :: "r"(p));
    return 0;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int ans = min(N * A, B);
  cout << ans << endl;
};


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long ans = x / 11l * 2l;
        long mod = x % 11;
        if(mod > 6) {
            ans += 2;
        } else if(mod > 0) {
            ans += 1;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 36036
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,a;
  cin>>n>>m;
  int b[10]={0,2,5,5,4,5,6,3,7,6};
  string c[10]={"0","1","2","3","4","5","6","7","8","9"};
  vector<bool> f(10,false),ff(10010,false);
  for(int i=0;i<m;i++){
    cin>>a;
    f[a]=true;
  }
  vector<string> dp(10010,"");
  ff[0]=true;
  for(int i=2;i<=n;i++){
    for(int j=1;j<10;j++){
      if(f[j]&&i>=b[j]){
        if(ff[i-b[j]]){
          ff[i]=true;
          string s=dp[i-b[j]]+c[j];
          if(s.size()>=dp[i].size()){
            sort(s.begin(),s.end(),greater<char>());
            dp[i]=s;
          }
        }
      }
    }
  }
  cout<<dp[n];
}


Measured memory_bytes: 26112
n = gets.to_i
c = Hash[("a".."z").map{ |a| [a,1000] }]
n.times{
  d = Hash[("a".."z").map{ |a| [a,0] }]
  #p d
  gets.chomp.split("").each{ |a| d[a] += 1 }
  d.each{ |a,v| c[a] = [c[a], v].min }
}
puts c.map{ |a,v| a * v }.sort.join


Measured memory_bytes: 2044
#include <iostream>

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL;

template<typename T>
T pow(T x, T e){
    T res = 1;
    for(; e>0; e>>=1, (x*=x)%=mod)if(e & 1)(res *= x) %= mod;
    return res;
}

int main(){
    ll n, m;
    cin >> m >> n;
    cout << pow(m, n) << '\n';
    return 0;
}

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

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

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

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;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

bool IsPrime(ll num)
{
  if (num < 2)
    return false;
  else if (num == 2)
    return true;
  else if (num % 2 == 0)
    return false;
  ld sqrtNum = sqrt(num);
  for (ll i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}

//実行部
void Main()
{
  str s; cin >> s;
  ll ans = 0, k = s.size();
  rep(i, k) if(s[i] == 'o') ans++;
  if(ans + (15 - k) >= 8) fin("YES");
  fin("NO");
}

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

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    string str;
    cin >> str;
 
    auto size = str.size();
    vector<int> vec;
    vec.reserve(size);
    char pre = str[0];
    int a = 1;
    for (auto i = 1; i < size; ++i) {
        if (str[i] == '<') {
            if (pre == '<') {
                a ++;
            } else {
                vec.push_back(a);
                a = 1;
                pre = '<';
            }
        } else {
            if (pre == '>') {
                a ++;
            } else {
                vec.push_back(a * -1);
                a = 1;
                pre = '>';
            }
        }
    }
    if (pre == '>') {
        vec.push_back(a);
    } else {
        vec.push_back(a * -1);
    }
 
    /*
    for (auto n: vec) {
        cout << n <<  " ";
    }
    cout << endl;
    */
 
    long sum = 0, last = 0;
    for (auto n : vec) {
        if (n > 0) {
            if (n <= last) {
                sum += last;
                // cout << last << ">";
                n -= 1;
            }
            for (auto i = n; i > 0; --i) {
                sum += i;
                // cout << i << ">";
            }
            // cout << endl;
        } else {
            n *= -1;
            for (auto i = 0; i < n; ++i) {
                sum += i;
                // cout << i << "<";
            }
            // cout << endl;
            last = n;
        }
    }
    if (vec[vec.size() - 1] > 0) {
        sum += 0;
        // cout << 0 << endl;
    } else {
        sum += last;
        // cout << last << endl;
    }
    cout << sum << endl;
 
 
    return 0;
}

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

int N, cnt[4];
double f[302][302][302], ans;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int a;
	cin >> N;
	for(int i = 1; i <= N; ++i)
		cin >> a, ++cnt[a];
	f[cnt[1]][cnt[2]][cnt[3]] = 1.0;
	double exp, tot, dN = 1.0 * N;
	for(int k = cnt[3]; k >= 0; --k)
		for(int j = N; j >= 0; --j)
			for(int i = N; i >= 0; --i) {
				tot = double(i + j + k);
				if(tot > 0) {
					exp = dN / tot, ans += exp * f[i][j][k];
					if(k) f[i][j + 1][k - 1] += f[i][j][k] * double(k) / tot;
					if(j) f[i + 1][j - 1][k] += f[i][j][k] * double(j) / tot;
					if(i) f[i - 1][j][k] += f[i][j][k] * double(i) / tot;
				}
			}
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

Measured memory_bytes: 215424
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int i = 1;
    for ( i = 1 ; i < n+1; i++)
    {
        if (i%3==0)
        {
            cout << " " << i;

        }else if (i%10==3)
        {
            cout << " " << i;
        }else if ((i/10)%10==3)
        {
            cout << " " << i;
        }else if ((i/100)%10==3)
        {
            cout << " " << i;
        }else if ((i/1000)%10==3)
        {
            cout << " " << i;
        }else if ((i/10000)%10==3)
        {
            cout << " " << i;
        }
        
    }
    cout << endl;
    
    
    

return 0;

}


Measured memory_bytes: 3084
#include<iostream>
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  while(h!=0){
    int i,j;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	if((i%2==0&&j%2==0)||(i%2==1&&j%2==1))
	  cout << "#";
	else cout << ".";
      }
      cout << endl;
    }
    cout << endl;
    cin >> h >> w;
  }
  return 0;
}



Measured memory_bytes: 3104
import pprint
N=int(input())
A=list(map(int,input().split()))
bitlen=42
flag=1
exor=0
andsum=0
ex=[0]*bitlen
an=[0]*bitlen
num=0
for i in range(2,N):
    exor=exor^A[i]
andsum=(A[0]+A[1])-exor

if (andsum%2!=0)or(andsum<0):
    flag=0
else:
    andsum=andsum//2
    for i in range(bitlen):
        if (exor>>i)&1:
            ex[i]=1
        if (andsum>>i)&1:
            an[i]=1
    num=andsum
    for i in range(bitlen):
        if (an[i]==1)and(ex[i]==1):
            flag=0
            break
    if num>A[0]:
        flag=0
    for i in range(bitlen-1,-1,-1):
        if ex[i]==1:
            if num+pow(2,i)<=A[0]:
                num=num+pow(2,i)
    #print(num)
    if num==0:
        flag=0
if flag==0:
    print(-1)
else:
    print(A[0]-num)


Measured memory_bytes: 72100
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
int main(){
  int n;
  cin>>n;
  vector<int> l(n),r(n);
  int ans=0;
  rep(i,n){
    cin>>l[i]>>r[i];
    ans += r[i]-l[i]+1;
  }
  cout<<ans<<endl;
}

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

using ll = long long;

ll xorSum(ll a){
    if(a % 4 == 1) return 1;
    if(a % 4 == 2) return a + 1;
    if(a % 4 == 3) return 0;
    if(a % 4 == 0) return a;
}

int main(){
    ll A, B; cin >> A >> B;
    cout << (xorSum(A - 1) ^ xorSum(B)) << endl;
}

Measured memory_bytes: 256
from sys import exit
N,Y = [int(n) for n in input().split()]
# N = int(input())
# s = set()
for i in range(N+1):
    for j in range(N+1):
        if (Y-10000*i-5000*j)//1000 == N - i - j and Y-10000*i-5000*j >= 0:
            print(i,j,N - i - j)
            exit()
print(-1,-1,-1)
# print(len(s))
# S = str(input())
# L = len(S)
# T = str(input())
# exit()

Measured memory_bytes: 3064
n = int(input())
x = input()

dp = [0] * (n+1)

for i in range(1,n+1):
    tmp = bin(i).count("1")
    dp[i] = dp[i%tmp] + 1

t = x.count('1')
po = []

for i in range(n):
    t1 = t
    if x[i] == '1':
        t1 -= 1
    else:
        t1 += 1
    po.append(t1)

t21 = 0
t22 = 0

for i in range(n):
    if x[i] == '1':
        if t > 1:
            t21 += pow(2, (n-i-1), t-1)
            t22 += pow(2, (n-i-1), t+1)
            t21 %= t-1
            t22 %= t+1
        else:
            t22 += pow(2, (n-i-1), t+1)
            t22 %= t+1

for i in range(n):
    if x[i] == '1':
        t3 = t21
    else:
        t3 = t22
    if po[i] == 0:
        print(0)
    else:
        if x[i] == '1':

            t3 -= pow(2, (n-i-1), po[i])
        else:
            t3 += pow(2,(n-i-1), po[i])
        print(dp[t3%po[i]]+1)


Measured memory_bytes: 83608
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

taoshi_count = 0
for i in range(N):
    nokori = A[i] - B[i]
    if A[i] - B[i] >= 0 :
        taoshi_count += B[i]
    else :
        taoshi_count += A[i]
        nokori_power = abs(nokori)
        if A[i + 1] >= nokori_power :
            taoshi_count += nokori_power
            A[i + 1] -= nokori_power
        else :
            taoshi_count += A[i + 1]
            A[i + 1] = 0
print(taoshi_count)

Measured memory_bytes: 18476
#include <bits/stdc++.h>
using namespace std;
const long long mod=924844033;
const long long MAXN=4010;
long long n,k,a[MAXN],cnt=0,fac[MAXN],dp[MAXN][MAXN][2];
int main(){
	scanf("%lld%lld",&n,&k);
	fac[0]=1ll;for(register int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	a[0]=MAXN;
	for(register int i=1;i<=k;i++){
		for(register int j=i;j<=n;j+=k) a[++cnt]=j;
		for(register int j=i;j<=n;j+=k) a[++cnt]=j;
	}	
	dp[0][0][0]=1;
	for(register int i=1;i<=(n<<1);i++){
		for(register int j=0;j<=i/2;j++){
			dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%mod;
			if(j && a[i]-a[i-1]==k)dp[i][j][1]=dp[i-1][j-1][0];
		}
	}
	long long ans=0;
	for(register int i=0;i<=n;i++){
		long long aim=(dp[n<<1][i][0]+dp[n<<1][i][1])%mod*fac[n-i]%mod;
		if(i&1) ans=((ans-aim)%mod+mod)%mod;
		else ans=(ans+aim)%mod;
	}
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 248704
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
 
int main(){
  long long int S;
  cin >> S;
 
  bool ym = false, my= false;
  if(1 <= S/100 && S / 100 <= 12){
    my = true;
  }
  if(1<= S %100 && S % 100 <= 12){
    ym = true;
  }
  
  if(my && ym)
    cout << "AMBIGUOUS";
  else if(my && !ym)
    cout << "MMYY";
  else if(!my && ym)
    cout << "YYMM";
  else
    cout << "NA";
  
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
int fac[N], ifac[N], inv[N];

int mul(int x, int y) { return x * 1ll * y % mod; }
int add(int x, int y) { return x+y < mod ? x+y : x+y-mod; }
int sub(int x, int y) { return x-y < 0 ? x-y+mod: x-y; }
int norm(int x) { return x < 0 ? add(x, mod) : sub(x, mod); }
template<class T, class... O> int mul(T x, O... y) { return mul(x, mul(y...)); }

int main() {
  int n, a; cin >> n >> a;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = mul(fac[i-1], i);
    inv[i] = i == 1 ? 1 : mod - mul(mod / i, inv[mod % i]);
    ifac[i] = mul(ifac[i-1], inv[i]);
  }
  int ans = 0;
  for (int i = 1; i <= a+1; i++) // [1 .. i-1]
    for (int j = 0; j+1 < i; j++) // j singletons before
      ans = norm(ans + ((j & 1) ? -1 : 1) * mul(fac[i-1], ifac[j], ifac[i-2-j], fac[n-j-1], i == a+1 ? 1 : inv[n-a+i-1-j]));
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 120808