akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        int a, b, c, d;
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        if (a + b == c + d) {
            System.out.println("Balanced");
            return;
        }
        if (a + b > c + d) {
            System.out.println("Left");
        } else {
            System.out.println("Right");
        }
    }
}


Measured memory_bytes: 23124
import java.io.*;

class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split(" ");
        int n = Integer.parseInt(nums[0]);
        int m = Integer.parseInt(nums[1]);
        int i, j;
        int[][] A = new int[n][m];
        int[] b = new int[m];
        int ci;
        String[] row;
        for (i = 0; i < n; i++) {
            row = br.readLine().split(" ");
            for (j = 0; j < m; j++) {
                A[i][j] = Integer.parseInt(row[j]);
            }
        }
        for (j = 0; j < m; j++) {
            b[j] = Integer.parseInt(br.readLine());
        }
        for (i = 0; i < n; i++) {
            ci = 0;
            for (j = 0; j < m; j++) {
                ci += A[i][j] * b[j];
            }
            System.out.println(ci);
        }
    }
}

Measured memory_bytes: 27032
#include <bits/stdc++.h>
using namespace std; 
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long int
#define ld long double
#define endl "\n"
#define rep(i,a,b) for(int i=a;i<b;i++)
#define reprev(i,a,b) for(int i=b-1;i>=a;i--)
#define all(c) c.begin(),c.end()
#define sz(c) (int)c.size()
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vin(a,n) vi a(n); rep(i,0,n) cin>>a[i];
#define vout(a) rep(i,0,sz(a)) cout<<a[i]<<" "; cout<<endl;
#define pb push_back
#define mp  make_pair
#define mod 1000000007
#define mod2 998244353
#define inf LLONG_MAX
#define pi 3.1415926535897932384626
#define tr(container, it) \
for(auto it = container.begin(); it != container.end(); it++)

int power(int x, unsigned int y, int p)  
{  
    int res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}

signed main()
{
    IOS
    int n;
    cin>>n;
    string name;
    while(n>0)
    {
        int tmp=n%26;
        n/=26;
        if(tmp==0) {name.pb('z'); n--;}
        else name.pb(tmp+'a'-1);   
    }
    reverse(all(name));
    cout<<name;
    return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1e9+1
#define inf1 1e18+1
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a);}
int LCSRe[5005][5005];
void longestRepeatedSubstring(string str) 
{ 
    int n = str.length();
    string res; // To store result 
    int res_length  = 0; // To store length of result 
  
    // building table in bottom-up manner 
    int i, index = 0; 
    for (i=1; i<=n; i++) 
    { 
        for (int j=i+1; j<=n; j++) 
        { 
            // (j-i) > LCSRe[i-1][j-1] to remove 
            // overlapping 
            if (str[i-1] == str[j-1] && 
                LCSRe[i-1][j-1] < (j - i)) 
            { 
                LCSRe[i][j] = LCSRe[i-1][j-1] + 1; 
  
                // updating maximum length of the 
                // substring and updating the finishing 
                // index of the suffix 
                if (LCSRe[i][j] > res_length) 
                { 
                    res_length = LCSRe[i][j]; 
                    index = max(i, index); 
                } 
            } 
            else
                LCSRe[i][j] = 0; 
        } 
    } 
  
    // If we have non-empty result, then insert all 
    // characters from first character to last 
    // character of string 
    cout<<res_length;
} 
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    longestRepeatedSubstring(s);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 96768
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,a,b,c,ans = INF,x[10];
	cin >> n >> a >> b >> c;
	for(int i = 0;i < n;i++) cin >> x[i];
	for(int i = 0;i < (1 << (2 * n));i++){
		int A = 0,B = 0,C = 0,An = 0,Bn = 0,Cn = 0,tmp = 0;
		for(int j = 0;j < n;j++){
			int s = (i >> (2 * j)) & 3;
			if(!s){
				A += x[j];
				An++;
			}
			else if(s == 1){
				B += x[j];
				Bn++;
			}
			else if(s == 2){
				C += x[j];
				Cn++;
			}
		}
		if(An && Bn && Cn){
			tmp += (An + Bn + Cn - 3) * 10 + abs(A - a) + abs(B - b) + abs(C - c);
			ans = min(ans,tmp);
		}
	}
	cout << ans << endl;
}

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

using namespace std;
using ll = long long;


int main()
{
    ll n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    for(int i = 0; i < n; i++)cin >> w[i] >> v[i];
    vector<ll> dp(300000, 10000000000000000);
    dp[0] = 0;

    for(int i = 0; i < n; i++){
        vector<ll> DP = dp;
        for(int j = 0; j <= 100000; j++){
            dp[j + v[i]] = min(dp[j + v[i]], DP[j] + w[i]);
        }
    }
    ll ans = 100000000000000000;
    for(int i = 0; i<= 100000; i++){
        if(dp[i] > W)continue;
        ans = i;
    }
    cout << ans << endl;

}

Measured memory_bytes: 5080
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  int dp[N];
  int a[N];
  for (int i = 0; i < N; i++) cin >> a[i];
  dp[0] = 0;
  dp[1] = abs(a[0] - a[1]);
  for (int i = 2; i < N; i++) {
      dp[i] = min(dp[i-1] + abs(a[i-1] - a[i]), dp[i-2] + abs(a[i-2] - a[i]));
  }
  
  cout << dp[N-1] << endl;
}
   

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

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

    vector<string> vec(7);
    vec = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    for( i = 0; i < 7 ; i++ ){
        if( vec.at(i) == s ){
            break;
        }
    }
    cout << 7 - i <<endl;
}

Measured memory_bytes: 256
N = int(input())
A = [int(input()) for _ in range(N)]

L = [0] * (200000+1)
R = [0] * (200000+1)

L[0] = 0
for i in range(1, N+1):
    L[i] = max(A[i-1], L[i-1])

R[N] = 0
for i in range(N-1, 0, -1):
    R[i] = max(R[i+1], A[i])

#print(L)
#print(R)

for i in range(N):
    ans = max(L[i], R[i+1])
    print(ans)

Measured memory_bytes: 15636
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
#include <map>
#include <queue>
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
using namespace std;
using ll = long long;
ll MOD = 1e9+7;


int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    cout << (n-2)*180 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
using namespace std;
const int INF = 1000000000000;
const int mod = 1000000007;
signed main() {
	int n, m, k, cnt = 0; cin >> n >> m >> k;
	vector<vector<int>>test(n + 1);
	vector<vector<int>>aa(k, vector<int>(2));
	map<int, map<int, int>>maze;//障害物
	for (int h = 0; h < k; h++) {
		cin >> aa[h][0] >> aa[h][1];
		maze[aa[h][0]][aa[h][1]] = 1;
	}
	sort(aa.begin(), aa.end());
	for (int h = 0; h < k; h++) {
		test[aa[h][0]].push_back(aa[h][1]);
	}
	int saidai = 1;
	for (int h = 2; h <= n; h++) {
		if (maze[h][saidai + 1] != 1) { saidai++; }
		if ((test[h].empty() == false) && (test[h][0] < saidai)) {
			cout << h - 1 << endl; return 0;
		}
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 59648
#include<stdio.h>
 
#define N 100001
  
int Partition(int A[],int p,int r);
  
int main(){
  int i,n,A[N],q;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
 
  q=Partition(A,0,n-1);
 
  for(i=0;i<n;i++){
    if(i==q){
      printf("[%d] ",A[i]);
    } else if(i!=n-1) {
      printf("%d ",A[i]);
    }
    else printf("%d",A[i]);
  }
  printf("\n");
 
  return 0;
}
 
int Partition(int A[],int p,int r){
  int i,j,s,t,u;
  s=A[r];
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(A[j]<=s){
      i++;
      t=A[i];
      A[i]=A[j];
      A[j]=t;
    }
  }
  u=A[i+1];
  A[i+1]=A[r];
  A[r]=u;
  return i+1;
}



Measured memory_bytes: 2248
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
#define BR "\n"
#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it,cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it,cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)

#define DumpArray(cont,from,to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
int H,W,N;
P Start;
string S,T;
void no() {
    cout << "NO" << endl;
    exit(0);
}
int main() {
    cin >> H >> W >> N;
    cin >> Start.fi >> Start.se;
    cin >> S >> T;
    Start.fi--;Start.se--;

    // lr
    {
        int l=0,r=W-1;
        for(int i=N-1;i>=0;--i) {
            if (S[i]=='L') ++l;
            if (S[i]=='R') --r;
            if (l>r)no();
            if (i>0&&T[i-1]=='L') ++r;
            if (i>0&&T[i-1]=='R') --l;
            if (l<0)l=0;
            if (r>W-1)r=W-1;
        }
        if (Start.se<l||Start.se>r||l>r)no();
    }
    {
        int u=0,d=H-1;
        for(int i=N-1;i>=0;--i) {
            if (S[i]=='U') ++u;
            if (S[i]=='D') --d;
            if (u>d)no();
            if (i>0&&T[i-1]=='U') ++d;
            if (i>0&&T[i-1]=='D') --u;
            if (u<0)u=0;
            if (d>H-1)d=H-1;
        }
        if (Start.fi<u||Start.fi>d||u>d)no();
    }
    cout << "YES" << endl;

    return 0;
}


Measured memory_bytes: 776
import java.util.*;

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

		int a[] = new int[100000];

		while(n > 0){
			int sum = 0;
			
			for(int i=0; i<n; ++i){
				a[i] = sc.nextInt();
				sum += a[i];
			}
			
			double average = (double)sum / n;
			
			int answer = 0;
			for(int i=0; i<n; ++i){
				if( a[i] <= average ){
					answer++;
				}
			}
			
			System.out.println(answer);
			
			n = sc.nextInt();
		}
		
	}
}



Measured memory_bytes: 59236
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
	
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	int ans=max(A*B,C*D);
	ce(ans)
}

Measured memory_bytes: 256
from bisect import bisect_left

n = int(input())
S = list(map(int, input().split()))

q = int(input())
T = list(map(int, input().split()))


cnt = 0

for v in T:
    index = bisect_left(S, v)
    if index < len(S) and S[index] == v:
        cnt += 1

print(cnt)



Measured memory_bytes: 16736
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n) ; ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define emb emblace_back

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


template<typename T>
void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << v << ",";
  }
  cout << "]" << endl;
}

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

  if(n < 11) cout << r + 100*(10-n) << endl;
  else cout << r << endl;


  return 0;
}


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

using namespace std;

int main(void){
    
    vector<int> a;
    
    int count = 0;
    while(1){
        int x; cin >> x;
        if(x == 0) break;
        count++;
        a.push_back(x);
    }
    
    for(int i = 0;i < count;i++){
        cout << "Case " << i+1 << ": " << a[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3188
#pragma region
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()
#pragma endregion


int main()
{
	ll MOD = 1e9 + 7;
	int n; cin >> n;
	string s; cin >> s;
	vector<ll> alp(26, 0);
	for (char x : s)++alp[x - 'a'];
	ll res = 0;
	rep(i, n)
	{
		--alp[s[i] - 'a'];
		ll tmp = 1;
		rep(j, 26)
		{
			if (j == s[i] - 'a')continue;
			tmp *= (alp[j] + 1);
			tmp %= MOD;
		}
		res += tmp;
		res %= MOD;
	}
	cout << res << endl;
}

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

int main() {
	int x, a;

	cin >> x >> a;

	if (x < a) {
		cout << 0 << endl;
	}
	else {
		cout << 10 << endl;
	}
}

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

#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< pii,vector<pii> ,greater< pii >>

using namespace std;


//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*int power(int a,int n)
{
    if(n == 1)return a%mod;
    if(n == 0)return 1;
    if(n&1)return ((a%mod)*(power((a*a)%mod,n/2))%mod)%mod;
    return power((a*a)%mod,n/2)%mod;
}*/
//const int md = 998244353;

/*int inverse(int x){

    return power(x,mod-2)%mod;//little fermat....
}*/
const int inf = (int) 1e18;
const int md = (int) 1e9+21;


signed main()
{
    showoff;
    string s;
    cin >> s;
    int ans = 0;
    FOR(i,0,sz(s)){
        if(i&1 && s[i] == '0')++ans;
        else if(i%2 == 0 && s[i] == '1')++ans;
    }
    int ans2 = 0;
    FOR(i,0,sz(s)){
        if(i&1 && s[i] == '1')++ans2;
        else if(i%2 == 0 && s[i] == '0')++ans2;
    }
    cout << min(ans,ans2);
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...


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

int main(void){

  char str[21], ans[21];
  int len, i;

  scanf("%s", str);
  len = strlen(str);

  for(i=0; i<len; i++){
    ans[i] = str[len-1-i];
  }
  ans[len]=str[len];
  printf("%s\n", ans);
  return(0);
}



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

int solve(string a,string b)
{
    int cnt=0;
    for(int i=0;i<a.length();i++)
    {
        if(a[i]!=b[i])
            cnt++;
    }
    return cnt;
}

int main()
{
    string a,b;
    cin>>a>>b;
    cout<<solve(a,b)<<endl;
}


Measured memory_bytes: 4132
from collections import deque
k = int(input())
lis = {1,2,3,4,5,6,7,8,9,10}
def dfs(x):
    d = ['-1','0','1']
    que = deque([x])
    cnt = 1
    while len(que) != 0:
        val = que.pop()
        #print(val)
        val3 = str(val)
        if len(str(val)) < 10:
            #print(len(str(val)))
            for i in range(3):
                val2 = int(val3[-1]) + int(d[i])
                #print(val3[-1])
                if val2 >= 0 and val2 < 10:
                    lis.add(int(str(val) + str(val2)))
                    que.append(int(str(val) + str(val2)))
        else:
            lis.add(val)
    return lis
for i in range(1,10):
    ans = dfs(i)
lis = list(lis)
lis.sort()
#print(len(lis))
#print(lis)
#print('3'.join('4'))
#print(lis[:20])
print(lis[k-1])
#print(lis[k])


Measured memory_bytes: 21228
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<bool>> path(N, vector<bool>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			path[i][j] = false;
		}
	}
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		path[a-1][b-1] = true;
		path[b-1][a-1] = true;
	}

	vector<int> perm(N-1);
	for (int i = 0; i < N - 1; i++) perm[i] = i + 1;
	int ans = 0;
	do {
		if (!path[0][perm[0]]) continue;
		int flag = true;
		for (int i = 0; i < N - 2; i++) {
			if (!path[perm[i]][perm[i+1]]) {
				flag = false;
				break;
			}
		}
		if (flag) ans++;
	} while (next_permutation(perm.begin(), perm.end()));
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> ans(n+1,0);
    int f;
    int x=1, y = 1, z = 1;
    while (x*x + y*y + z*z + x*y + y*z +z*x <= n){
        while (x*x + y*y + z*z + x*y + y*z +z*x <= n){
            z=1;
            while (x*x + y*y + z*z + x*y + y*z +z*x <= n){
                ans[x*x + y*y + z*z + x*y + y*z +z*x]++;
                z++;
            }
            y++;z=1;
        }
        x++;y=1;z=1;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << endl;
}


Measured memory_bytes: 3508
#include <iostream>
#include <string>
#include<cstring>
using namespace std;

int main(void){
  char s[100];
  cin >> s;
  int len = strlen(s);
  int back = len - 1;
  int i, cnt = 0; 
  for (i=0; i<len/2; ++i){
    if (s[i] != s[back])
      ++cnt;
    --back;
  }
  cout << cnt;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	mp := map[rune]bool{}
	ar := make([][]int, 26)
	for i, v := range s {
		mp[v] = true
		ar[v-'a'] = append(ar[v-'a'], i+1)
	}
	for _, v := range t {
		if !mp[v] {
			fmt.Println(-1)
			return
		}
	}
	sum := 0
	now := 0
	cr := make([]int, 26)
	for _, v := range t {
		vv := ar[v-'a']
		left, right := 0, len(vv)-1
		se := -1
		for left <= right {
			mid := (left + right) / 2
			v2 := vv[mid]
			if now < v2 {
				if cr[v-'a'] >= v2 {
					left = mid + 1
					continue
				}
				if se == -1 {
					se = v2
					right = mid - 1
					continue
				}
				if v2 < se {
					se = v2
					right = mid - 1
					continue
				}
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		if se != -1 {
			now = se
			cr[v-'a'] = now
			continue
		}
		sum++
		now = vv[0]
		cr = make([]int, 26)
		cr[v-'a'] = now
	}
	fmt.Println(sum*len(s) + now)
}


Measured memory_bytes: 7808
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUF_SIZE 100100
int main(void) {
  char line[BUF_SIZE];
  FILE* fp = stdin;
  if(!fgets(line, BUF_SIZE, fp)) return 0;

  char *tmp;
  int len = 0;
  for(tmp = line; *tmp != '\n'; tmp++, len++) ;
  int i;

  int flag = 1;
  for(i = len-1; i >= 0;) {
    switch(line[i]) {
      case 'm': // dream
        i -= 5;
        if(i+1 >= 0 && !strncmp(&line[i+1], "dream", 5)) {
        } else { flag = 0; }
        break;
      case 'e': // erase
        i -= 5;
        if(i+1 >= 0 && !strncmp(&line[i+1], "erase", 5)) {
        } else { flag = 0; }
        break;
      case 'r': // eraser, dreamer
        if(i-5>=0 && !strncmp(&line[i-5], "eraser", 6)) {
          i -= 6;
        } else if (i-6>=0 && !strncmp(&line[i-6], "dreamer", 7)) {
          i -=7;
        } else { flag = 0; }
        break;
      default:
        flag = 0;
        break;
    }
    if(!flag) break;
  }
  printf("%s\n", flag ? "YES" : "NO");

  return 0;
}

Measured memory_bytes: 256
#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 what_is(x) cerr << #x << " is " << x << 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>>;

ll solve2(ll a) {
	if (a <= 0) return 0;
	if (a % 2 == 1) return ((a + 1) / 2) % 2;
	else return a ^ solve2(a-1);
}

int dp[50];

ll solve(ll a) {
	if (a <= 0) return 0;
	for (int i = 0; i < 50; i++) dp[i] = 0;
	for (int i = 0; i < 50; i++) {
		if (a & (1LL<<i)) {
			ll tmp = a % (1LL<<i);
			dp[i] = 1 - (tmp & 1LL);
		}
	}
	if (a & 2LL) dp[0] = 1 - dp[0];
	ll ret = 0;
	for (int i = 0; i < 50; i++)
		if (dp[i]) ret |= 1LL<<i;
	return ret;
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	ll a, b;
	cin >> a >> b;
	ll answer = solve(b) ^ solve(a-1);
	printf("%lld\n", answer);
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
vector<int>G;
long long ans,sum;
int main()
{
	long long  m , d, c;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&d,&c);
		ans+=c;
		sum+=d*c;
	}
	long long dad=0;
	dad=ans-1+(sum-1)/9;
	cout<<dad;
	return 0;
}

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

long long pw3(int x){
	return 1LL * x * x * x;
}
int main(){
	int n, k;
	cin >> n >> k;
	long long ans = pw3(n / k);
	if (k % 2 == 0 && n >= k / 2)
		ans += pw3((n - k / 2) / k + 1);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;

int main()
{
    int n,m,a[100000];
for(;;){
cin >> n >> m;
if(n==0&&m==0)return 0;
for(int i=0;i<n;i++)cin >> a[i];
int ans=0;
int x=0;
for(int i=0;i<m;i++)x+=a[i];
ans=max(ans,x);
for(int i=0;i<n-m;i++){
x+=a[i+m];
x-=a[i];
ans=max(ans,x);
}
printf("%d\n",ans);
}
}

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

template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '"' + s + '"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? "true" : "false");}string to_string(vector<bool> v) {  bool first = true;  string res = "{";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(v[i]);  }  res += "}";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = "";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = "{";  for (const auto &x : v) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(x);  }  res += "}";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << " " << to_string(H);  debug_out(T...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
	read(first);
	read(args...);
}

int n,m;
int dp[110][110];
char mp[110][110];

int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++)cin>>(mp[i]+1);
	memset(dp,7,sizeof(dp));
	dp[1][1] = 1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j] = min(dp[i][j],min(dp[i-1][j]+(mp[i][j] != mp[i-1][j]),dp[i][j-1]+(mp[i][j] != mp[i][j-1])));
		}
	}
	cout<<dp[n][m]/2+(mp[1][1] == '#' && mp[n][m] == '#')<<endl;
	return 0;
}


Measured memory_bytes: 256
n,x = map(int,input().split())
A = list(map(int,input().split()))
Arev = A[::-1]
ans = 0
if A[0] > x:
    ans += A[0] - x
    A[0] = x
for i in range(1, n):
    if A[i] + A[i-1] > x:
        c = A[i] + A[i-1] - x
        A[i] -= c
        ans += c

ans2 = 0
if Arev[0] > x:
    ans2 += Arev[0] - x
    Arev[0] = x
for i in range(1, n):
    if Arev[i] + Arev[i-1] > x:
        c = Arev[i] + Arev[i-1] - x
        Arev[i] -= c
        ans2 += c

print(min(ans, ans2))

Measured memory_bytes: 14400
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, less<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[&](auto f,auto... args){return f(f,args...);};

int main(){
    lint n,k;
    cin>>n>>k;
    vec a(n);
    rep(i,n)cin>>a[i];
    lint ans=0;
    rep(i,n){
        ans+=2*min(abs(a[i]),abs(k-a[i]));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b,a||b){
    for(int i=0;i<b;i++){
      cout<<"#";
    }
    cout<<endl;
    for(int i=0;i<a-2;i++){
      cout<<"#";
      for(int j=0;j<b-2;j++){
	cout<<".";
      }
      cout<<"#";
      cout<<endl;
    }
    for(int i=0;i<b;i++){
      cout<<"#";
    }
    cout<<endl;
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  
  long long ans=1;
  for(int i=1; i<=N; i++){
   ans=(ans*i)%(1000000000+7); }// 要はN!を求めるのだが、
             // longlong型でも値が巨大になりすぎるため、常に%(10^9+7)を
  cout<<ans;// 入れて計算することでlonglong型からのオーバーフローを防げる
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int d;
    cin >>d;
    if (d == 22)
        cout << "Christmas Eve Eve Eve" << endl;
    else if (d == 23)
        cout << "Christmas Eve Eve" << endl;
    else if (d == 24)
        cout << "Christmas Eve" << endl;
    else
        cout << "Christmas" << endl;
}



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

int main(){
	int n,x,y,b,p;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d%d",&x,&y,&b,&p);
		printf("%d\n",min(x*b+y*p,(x*(b<5?5:b)+y*(p<2?2:p))*4/5));
	}
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    int R;
    
    cin >> N;
    cin >> R;
    
    int ans;
    
    if (N>=10) {
        ans = R;
    } else {
        ans = R + 100*(10-N);// ans - 100*(10-N) = R
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	// #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin);
	//     freopen("output.txt", "w", stdout);
	// #endif
 
	int k,n;
	cin>>k>>n;
	vector<int> a(n);

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

	//you start from any point and return back to that!!
	//possible for 3:
		// 1->2->3 , 2->3->1 , 3->1->2 ,1->3->2 ,3->2->1 , 2->1->3
	//so you can walk atmost k
	int ans= 0 ;
	//now find the max distance and just dont walk that distance

	for(int i=0;i<n-1;i++){
		ans = max(ans , a[i+1]-a[i]);
	}
	ans = max(ans , k-a[n-1]+a[0]);//last to first
	cout<<k-ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
//useful library
int long long gcd(int long long a, int long long b){
    return b?gcd(b,a%b):a;
} //最大公約数
int long long lcm(int long long a, int long long b){
    return a/gcd(a,b)*b;
} //最小公倍数
int long long GetDigit(int long long num){
    int long long digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
} //桁数
int long long GetDigitN(int long long num, int long long N){
    int long long digit=0;
    while(num!=0){
        num /= N;
        digit++;
    }
    return digit;
} //十進数でnumの際のN進数における桁数

int main(){
    bool B = false;
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int long long D = 0;
    for(int i = 0; i < N; i++){
        cin >> A.at(i);
        D = D + A.at(i);
    }
    sort(A.begin(), A.end(), greater<int>());
    double C = D / floor(4 * M);
    if(A.at(M - 1) >= C){
        B = true;
    }
    if(B == true){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
s = input()

li = ['dream', 'dreamer', 'erase', 'eraser']

#print(s[-5:],s[-6:],s[-7:])

while True:
    if s[-5:] in li:
        s = s[0:-5]
    elif s[-6:] in li:
        s = s[0:-6]
    elif s[-7:] in li:
        s = s[0:-7]
    else:
        print('NO')
        exit()
    if s=='':
        break
print('YES')

Measured memory_bytes: 3188
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

MOD = 1000000007
ans = 0
for i in range(N):
    cnt = 0
    pcnt = 0
    for j in range(N):
        if A[i] > A[j]:
            if i < j:
                cnt += 1
            else:
                pcnt += 1
    ans += cnt*(K)*(K+1) // 2
    # ans += pcnt*(K)
    # ans += pcnt*(K-1)
    ans += pcnt*(K-1)*(K) // 2

print(ans%MOD)

Measured memory_bytes: 3188
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
struct A{
	int t,x,y;
}a[111111];
bool cmp(A c,A b){
	return c.t<b.t;
}
int main()
{
	int n;
	while(~scanf("%d",&n)){
		int k=1;
		a[0].t=0;
		a[0].x=0;
		a[0].y=0;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);
		}
		sort(a,a+n,cmp);
		for(int i=1;i<=n;i++){
			if((abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)>a[i].t-a[i-1].t)||(a[i].t-a[i-1].t-abs(a[i].x-a[i-1].x)-abs(a[i].y-a[i-1].y))%2!=0){
				puts("No");
				k=0;
				break;
			}
		}
		if(k)puts("Yes");
	}
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main() {

    fast

    int a,b;
    cin>>a>>b;

    int res=a-2*b;
    if(res>0) cout<<res;
    else cout<<0;




	return 0;
}





Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	ll n,x;cin >> n >> x;
	
	ll ans = n;
	
	ll a = x;
	ll b = n - x;
	
	while(1)
	{
		if(a == b)
		{
			ans += a;
			break;
		}
		else
		{
			ll mi = min(a,b);
			ll ma = max(a,b);
			if(ma % mi == 0)
			{
				ll tmp = ma/mi;
				ans += (2*tmp-1)*mi;
				break;
			}
			else
			{
				ll tmp = ma/mi;
				ans += 2*tmp*mi;
				ma -= tmp*mi;
				a = mi;b = ma;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 384
import java.util.*;

import javax.xml.crypto.Data;
class Main {
	
	static ArrayList<Integer> p = new ArrayList<Integer>();
	static int INF = 2 << 27;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			if(n == 0 && m == 0) break;
			
			int[][] c = new int[n][n];
			for(int i = 0; i < n; i++) {
				Arrays.fill(c[i], INF);
			}

			for(int i = 0; i < m; i++) {
				int a = sc.nextInt()-1;
				int b = sc.nextInt()-1;
				int tmp = sc.nextInt();
				c[a][b] = Math.min(c[a][b], tmp);
				c[b][a] = Math.min(c[b][a], tmp);
			}
			
			int[][] min = new int[n][2];
			for(int i = 0; i < n; i++) {
				Arrays.fill(min[i], INF);
			}
			
			PriorityQueue<Data> q = new PriorityQueue<Data>();
			q.add(new Data(0,2,0));
			//min[0][0] = min[0][1] = 0;
			int ans = 0;
			while(!q.isEmpty()) {
				Data tmp = q.poll();
				if(tmp.now == n-1 && tmp.ticket != 1) {
					ans = tmp.cost;
					break;
				}
				if(tmp.ticket == 1) {
					for(int i = 0; i < n; i++) {
						if(c[tmp.now][i] != INF) {
							q.add(new Data(i,0,tmp.cost));
						}
					}
				}
				if(tmp.ticket == 0) {
					if(min[tmp.now][0] <= tmp.cost) continue;
					min[tmp.now][0] = tmp.cost;
					for(int i = 0; i < n; i++) {
						if(c[tmp.now][i] != INF) {
							q.add(new Data(i,0,tmp.cost + c[tmp.now][i]));
						}
					}
				}
				if(tmp.ticket == 2) {
					if(min[tmp.now][1] <= tmp.cost) continue;
					min[tmp.now][1] = tmp.cost;
					for(int i = 0; i < n; i++) {
						if(c[tmp.now][i] != INF) {
							q.add(new Data(i,2,tmp.cost + c[tmp.now][i]));
							q.add(new Data(i,1,tmp.cost));
						}
					}
				}
			}
			
			System.out.println(ans);
			
			
			
		}
	}
	
	static class Data implements Comparable<Data>{
		int now;
		int ticket;
		int cost;
		Data(int a, int b,int c) {
			now = a;
			ticket = b;
			cost = c;
		}
		@Override
		public int compareTo(Data o) {
			return this.cost - o.cost;
		}
	}
	
	
}

Measured memory_bytes: 36576
#include <bits/stdc++.h>
using namespace std;
#define PRINT(s) cout << s << endl;
#define FOR(i, n) for (int i = 0; i < (n); i++)

int main() {
    int s, w;
    cin >> s >> w;
    if (s > w) {
        PRINT("safe");
    } else {
        PRINT("unsafe");
    }
}


Measured memory_bytes: 3600
#include<iostream>
#include<string>

using namespace std;

int main()
{
	string S, T;
	cin >> S >> T;

    for(int i = 0; i < S.size(); i++){
        if(S[i] != T[i]){
            cout << "No" << endl;
            return 0;
        }
    }
	
	
	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a, b, c, x, y, sum = 0;
    cin >> a >> b >> c >> x >> y;
    if(a + b >= 2 * c)
    {
        if(x >= y)
        {
            sum += y * 2 * c;
            sum += (x - y) * min(a, 2 * c);
        }
        else
        {
            sum += x * 2 * c;
            sum += (y - x) * min(b, 2 * c);
        }
    }
    else
    {
        sum += x * a + y * b;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<bool, bool> pbb;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls (i << 1)
#define rs (i << 1 | 1)
#define enum(i, j, k) for(int i = j; i <= (k); i ++)
#define open(i, j, k) for(int i = j; i <  (k); i ++)
#define dec(i, j, k)  for(int i = j; i >= (k); i --)
#define fill(x, k) memset(x, k, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
#define fio(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
template <class T> bool chkmin(T &x, T y)
{ return y < x ? (x = y , true) : false; }
template <class T> bool chkmax(T &x, T y)
{ return y > x ? (x = y , true) : false; }
struct __init { __init()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cout.precision(16); cout << fixed;
	srand(time(0) ^ ui(ul(new char)));
}};
static __init __init__;
/* default code ends here */
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int n, m;
ll a[maxn], b[maxn];
int main()
{
	cin >> n >> m;
	enum(i, 1, n)
		cin >> a[i];
	enum(i, 1, m)
		cin >> b[i];
	ll s1 = 0, s2 = 0;
	enum(i, 1, n - 1)
		s1 = (s1 + (a[i + 1] - a[i]) * i % mod * (n - i)) % mod;
	enum(i, 1, m - 1)
		s2 = (s2 + (b[i + 1] - b[i]) * i % mod * (m - i)) % mod;
	cout << s1 * s2 % mod << '\n';
	return 0;
}


Measured memory_bytes: 1792
from heapq import heappush, heappop

N, A, B, C = [int(x) for x in input().split()]
S = [input() for i in range(N)]


sToIndex = {
    "AB": (0, 1),
    "AC": (0, 2),
    "BC": (1, 2),
}
heap = [(0, -min(A, B, C), (A, B, C))]
parent = {}
while heap:
    original = heappop(heap)
    negT, negMin, state = original

    if negT == -N:

        print("Yes")
        ans = []
        last = original
        while last in parent:
            nextLast = parent[last]
            diffIndex = None
            for i in range(3):
                if nextLast[2][i] + 1 == last[2][i]:
                    diffIndex = i
                    break
            ans.append("ABC"[diffIndex])
            last = nextLast
        print("\n".join(reversed(ans)))
        exit()

    index1, index2 = sToIndex[S[-negT]]

    nbr1 = list(state)
    nbr1[index1] += 1
    nbr1[index2] -= 1
    min1 = min(nbr1)
    if min1 >= 0:
        node = (negT - 1, -min1, tuple(nbr1))
        if node not in parent:
            heappush(heap, node)
            parent[node] = original

    nbr2 = list(state)
    nbr2[index1] -= 1
    nbr2[index2] += 1
    min2 = min(nbr2)
    if min2 >= 0:
        node = (negT - 1, -min2, tuple(nbr2))
        if node not in parent:
            heappush(heap, node)
            parent[node] = original

print("No")


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

mt19937_64 rng(high_resolution_clock::now().time_since_epoch().count());
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> istream& operator >> (istream &in,vector<T> &A){ for(auto &x:A) in>>x; return in; };
template<typename T> ostream& operator << (ostream &out,vector<T> &A){ for(auto &x:A) out<<x<<" "; return out; };
template<typename T,typename W> istream& operator >> (istream &in,pair<T,W> &A){ in>>A.fi>>A.se; return in; };
const int N = 2*1e5+3;

void solve()
{
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}	
	int l = 1,r=1e9;
	int ans=-1;
	while(l<=r)
	{
		int mid = (l+r)/2;
		// int mid = 4;
		int an=0;
		for(int i=0;i<n;i++)
		{
			if(a[i]>mid)
			{
				int o = a[i]/mid;
				int rem = a[i]%mid;
				if(rem) o++;
				int cnt=0;
				while(o>1){
					cnt+=o/2;
					o = o/2 + (o%2);
				}
				an+=cnt;
				// cout<<cnt<<"\n";
			}
		}
		// cout<<an<<"\n";
		if(an<=k)
		{
			// cout<<mid<<" "<<an<<"\n";	
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<ans<<"\n";
}
// x - > 2*(x/2)
/// 1+2+4+8+...2^n
//  (2^(n+1)-1)
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	#endif

	int t=1;
	// cin>>t;
	for(int _t=1;_t<=t;_t++){
		// cout<<"Case #"<<_t<<": ";
		solve();
	}
} 


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

#p = [-1]*m
#y = [-1]*m
ipy=[]

for i in range(m):
    ipy.append(list(map(int,(str(i) + " " + input()).split())))

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

ipy[0][2] = 1
for i in range(1,m):
    if ipy[i][1] == ipy[i-1][1]:
        ipy[i][2] = ipy[i-1][2]+1
    else:
        ipy[i][2] = 1

ipy = sorted(ipy, key = lambda x: x[0])

for i in range(m):
    print(f'{ipy[i][1]:06}'+f'{ipy[i][2]:06}')



Measured memory_bytes: 102328
#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
int main(){
    double a,b,c,d;
    double dis,ans;
    cin>>a>>b>>c>>d;
    dis=(c-a)*(c-a)+(d-b)*(d-b);
    ans=sqrt(dis);
    printf("%.8lf\n",ans);
    return 0;
}   


Measured memory_bytes: 3288
#include<stdio.h>

// ALDS1_1_A: insertion Sort
/* 配列の要素を順番に出力 */

void trace(int A[], int N) {
    int i;
    for ( i = 0; i < N; i++) {
        if ( i > 0) printf(" "); /* 隣接する要素の間に1つの空白を出力 */
        printf("%d", A[i]);
    }
    printf("\n");
}

/* 挿入ソート (0オリジン配列) */
void insertionSort(int A[], int N) {
    int j, i, v;
    for ( i = 1; i < N; i++ ) {
        v = A[i];
        j = i - 1;
        while ( j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main() {
    int N, i, j;
    int A[100];

    scanf("%d", &N);
    for ( i = 0; i < N; i++ ) scanf("%d", &A[i]);

    trace(A, N);
    insertionSort(A, N);

    return 0;
}


Measured memory_bytes: 2720