akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
#define pi 3.141592653589793
using namespace std;
int saidaikouyakusuu(int a,int b){
    if(b==0) return a;
    return saidaikouyakusuu(b,a%b);
}
int saisyoukoubaisuu(int a,int b){
    return a*b/saidaikouyakusuu(a,b);
}
int n,m,cnt=0,aa[220000],ans=0,x,y,ab[220000];
pair<int,int> pp[220000];
string s,ss[220000];
char c;
queue<char> que;
signed main(){
    cin>>s>>ss[0];
    rep(i,s.size()){
        que.push(s[i]);
    }
    rep(i,s.size()){
        cnt=0;
        rep(j,s.size()){
            if(que.front()!=ss[0][j]){
                cnt++;
            }
            que.push(que.front());
            que.pop();
        }
        if(cnt==0){
            cout<<"Yes"<<endl;
            return 0;
        }
        que.push(que.front());
        que.pop();
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 10500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  int x;
  cin >> x;

  vector<bool> t(200001, false);
  for (int i = 0; i <= x; i++) {
    if (i == 100 || i == 101 || i == 102 || i == 103 || i == 104 || i == 105) {
      t[i] = true;
    }

    if (t[i]) {
      t[i + 100] = true;
      t[i + 101] = true;
      t[i + 102] = true;
      t[i + 103] = true;
      t[i + 104] = true;
      t[i + 105] = true;
    }
  }

  int ans = 0;
  if (t[x]) {
    ans = 1;
  }

  cout << ans << endl;

  return 0;
}

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

string s, t;
int main ()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // I am Khanh Doan
    /*
    p[1] = 1;

    for (i = 2; i <= 5000; i++)
    {
        p[i] = i;
        for (j = 2; j <= i/2; j++)
        if (i % j == 0)
        {
            t = i / j;
            if (p[i] > p[j] + p[t] + 2)
                p[i] = p[j] + p[t] + 2;
        }
    }

    s[1] = 1;

    for (i = 2; i <= 5000; i++)
    {
        s[i] = p[i];
        for (j = 2; j <= i - 1; j++)
        {
            t = i - j;
            if (s[i] > s[j] + p[t] + 2)
                s[i] = s[j] + p[t] + 2;
        }
    }

    while (cin >> n)
        cout << s[n] << "\n";
    */
    cin >> s;
    cin >> t;
    for(ll i = 0; i < s.length(); i++){
        if(s[i] != t[i]){
            cout <<"No";
            return 0;
        }
    }
    cout <<"Yes";

}



Measured memory_bytes: 3652
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Edge {
  int s,t,next;
  Edge() {}
  Edge(int a,int b,int c):s(a),t(b),next(c) {}
};

Edge e[200005];
int head[100005];

bool vis[100005];
int id;

void dfs1(int x,int fa) {
  vis[x]=1;
  for(int i=head[x];i;i=e[i].next)
    if (e[i].t!=fa) {
    	int u=e[i].t;
    	if (!vis[u]) dfs1(u,x);
    	else id=i; 
	}
}

ll num[100005];
int fa[100005];
bool dep[100005];

void dfs2(int x) {
  num[x]=1;
  for(int i=head[x];i;i=e[i].next)
    if (e[i].t!=fa[x]&&((i+1)>>1)!=((id+1)>>1)) {
    	int u=e[i].t;
    	fa[u]=x;dep[u]=dep[x]^1;
    	dfs2(u);
    	num[x]-=num[u];
	}
}

ll now[100005];

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[2*i-1]=Edge(x,y,head[x]);
  	head[x]=2*i-1;
  	e[2*i]=Edge(y,x,head[y]);
  	head[y]=2*i;
  }
  dfs1(1,0);
  if (!id) {
  	dfs2(1);
  	if (num[1]!=0) puts("-1");
  	else {
  		ll ans=0;
  		for(int i=1;i<=n;i++) ans+=abs(num[i]);
  		printf("%lld\n",ans);
	  }
  }
  else {
  	int p=e[id].s,q=e[id].t;
  	dfs2(p);
  	if (dep[p]^dep[q]) {
  		if (num[p]!=0) puts("-1");
  		else {
  			int cnt=0;
  			for(int i=q;i!=p;i=fa[i]) 
			  now[++cnt]=(dep[i]^dep[q])?-num[i]:num[i];
			now[++cnt]=0;
  			nth_element(now+1,now+((cnt+1)>>1),now+cnt+1);
  			ll t=now[(cnt+1)>>1];
  			for(int i=q;i!=p;i=fa[i]) 
  			  if (dep[i]^dep[q]) num[i]+=t; else num[i]-=t;
  			ll ans=abs(t);
  			for(int i=1;i<=n;i++) ans+=abs(num[i]);
  			printf("%lld\n",ans);
		  }
	  }
	else {
		if (num[p]&1) puts("-1");
		else {
			ll t=(abs(num[p])>>1);
			if (num[p]>0) {
			  for(int i=q;i!=p;i=fa[i])
			    if (dep[i]^dep[q]) num[i]+=t; else num[i]-=t;
		    }
		    else {
			  for(int i=q;i!=p;i=fa[i])
			    if (dep[i]^dep[q]) num[i]-=t; else num[i]+=t;
			}
			num[p]=0;
			ll ans=t;
			for(int i=1;i<=n;i++) ans+=abs(num[i]);
			printf("%lld\n",ans); 
		}
	}
  }
  return 0;
}

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

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

  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  vector<ll> c(n+1);
  for (int i = n-1; i >= 0; --i) {
    c[i] = c[i+1] + a[i];
    c[i] %= M;
  }
  ll ans = 0;
  for (int i = 0; i < n-1; ++i) {
    ll tmp = a[i] * c[i+1] % M;
    ans = (ans + tmp) % M;
  }
  cout << ans << endl;
}

Measured memory_bytes: 6324
q = int(input())
m = 10**9+7
for _ in range(q):
    x, y = sorted(map(int, input().split()))
    s = 0
    i = j = 1
    while j <= x and i+j <= y:
        i, j = j, i+j
        s += 1
    if x == 1 or y <= 2:
        print(1, x*y % m)
    else:
        a = 0
        a += max(0, (y-j) // i+1)
        a += max(0, (x-j) // i+1)
        i = j = 1
        for c in range(s-1):
            k, l = j, i+j*2
            for _ in range(s-c-1):
                k, l = l, k+l
            if x >= k:
                a += max(0, (y-l) // k+1)
            if y >= k:
                a += max(0, (x-l) // k+1)
            i, j = j, i+j
        print(s, a % m)


Measured memory_bytes: 81216
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	char ch,ans;
	cin>>ch;
	if(ch=='A')ans='T';
	else if(ch=='T')ans='A';
	else if(ch=='C')ans='G';
	else if(ch=='G')ans='C';
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
program abc133c
   implicit none

   integer(8) :: L, R, i, j , skip
   integer :: ans, calc_mod

   read(*,*) L, R

   ans = 2018

   do i = L, R-1
      do j =i+1, R

         calc_mod = mod(i*j,2019)
         if (ans > calc_mod ) then
            ans = calc_mod
            if (ans == 0) goto 999
         else
            cycle
         end if
      enddo
   enddo
999 continue

   print *, ans


end program abc133c


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> sc;
  rep(i, m) {
    int s, c;
    cin >> s >> c;
    sc.emplace_back(s, c);
  }
  for (int i = 0; i < 1000; i++) {
    int keta = 0;
    {
      int ii = i;
      while (ii) keta++, ii /= 10;
      if (i == 0) keta = 1;
    }
    if (keta != n) continue;

    string str = to_string(i);
    bool ok = true;
    rep(j, m) {
      int s, c;
      tie(s, c) = sc[j];
      s--;
      if (str[s] - '0' != c) ok = false;
    }
    if (ok) {
      cout << i << endl;
      return;
    }
  }
  cout << -1 << endl;
}


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


int main() {
  int N;
  cin >> N;
  set<int> A;
  for (int i=0; i<N; i++) {
    int x;
    cin >> x;
    A.insert(x);
  }
  cout << ((A.size()%2==0)?A.size()-1:A.size()) << endl;
  return 0;
}


Measured memory_bytes: 4992
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = list(input())
n = len(s)
t = list(input())
m = len(t)
res = m
for i in range(n):
    if i+m > n: break
    cnt = 0
    for j in range(m):
        if s[i+j] != t[j]:
            cnt += 1
    res = min(res, cnt)
print(res)

Measured memory_bytes: 77568
#include<stdio.h>
int main()
{
    char vc;
    scanf("%c",&vc);
    if(vc=='a' || vc=='e' || vc=='i' || vc=='o' || vc=='u')
    {
        printf("vowel\n");
    }
    else
    {
        printf("consonant\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

#define TOL 1e-10

using namespace std;
int main(){
    double x[3],y[3];
    scanf("%lf %lf %lf %lf",&x[0],&y[0],&x[1],&y[1]);
    double v1_x,v2_x,v1_y,v2_y;
    double n1,n2,i_v,o_v;
    v1_x = x[1]-x[0];
    v1_y = y[1]-y[0];
    n1 = v1_x*v1_x + v1_y*v1_y;
    int q;
    scanf("%d",&q);
    int i;
    for (i=0; i<q; i++){
        scanf("%lf %lf",&x[2],&y[2]);
        v2_x = x[2]-x[0];
        v2_y = y[2]-y[0];
        n2 = v2_x*v2_x + v2_y*v2_y;
        i_v = v1_x*v2_x + v1_y*v2_y;
        o_v = v1_x*v2_y - v2_x*v1_y;
        if(o_v > TOL){
            printf("COUNTER_CLOCKWISE\n");
        } else if(o_v < -TOL) {
            printf("CLOCKWISE\n");
        } else if(i_v < 0){
            printf("ONLINE_BACK\n");
        } else if(n1 < n2){
            printf("ONLINE_FRONT\n");
        } else {
            printf("ON_SEGMENT\n");
        }
    }
    return 0;
    
}


Measured memory_bytes: 2752
import java.util.*;

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

    String s = "1" + sc.next();
    String[] a = {"dream", "dreamer", "erase", "eraser"};

    s = s.replaceAll(a[3], "");
    s = s.replaceAll(a[2], "");
    s = s.replaceAll(a[1], "");
    s = s.replaceAll(a[0], "");

    System.out.println(s.equals("1") ? "YES" : "NO");

  }
}

Measured memory_bytes: 30536
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <bitset>
#include <complex>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;

int main(){
    ll X;
    cin >> X;
    for(ll A=-200; A<200; A++){
        for(ll B=-200; B<200; B++){
            if(A*A*A*A*A-B*B*B*B*B==X){
                cout<<A<<" "<<B<<endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int ans = 1;
    rep(i, 0, n){
        ans = min(ans * 2, ans + k);
    }
    cout << ans << endl;
}


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

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

using i64 = int_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n;
    vector<i64> a(n);
    i64 sum = 0;
    for (auto& e : a) {
        cin >> e;
        sum ^= e;
    }

    for (auto& e : a) {
        cout << (sum ^ e) << endl;
    }
}

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


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

using namespace std;

int n;
string s;
int red = 0;
int blue = 0;

int main(){
  cin >> n;
  cin >> s;
  for(int i = 0; i < s.length(); ++i){
    if(s[i] == 'R'){
      red++;
    }else if(s[i] == 'B'){
      blue++;
    }
  }
  if(red > blue){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
MIN = float('inf')
for bit in range(1<<N):
    tmpA = A[:]
    L = []
    for i in range(N):
        if bit & (1<<i):
            L.append(i)
    SUM = 0
    for l in L:
        MAX = max(tmpA[:l]+[0])
        if MAX >= tmpA[l]:
            SUM += MAX+1-tmpA[l]
            tmpA[l] = MAX+1
    count = 0
    MAX = 0
    for i in range(N):
        if tmpA[i] > MAX:
            count += 1
            MAX = tmpA[i]
    if count >= K:
        MIN = min(MIN,SUM)
print(MIN)

Measured memory_bytes: 9240
/*
                IftekharMd.Shishir
                Dept. of Information and Communication Engineering
                University of Rajshahi
*/

#include<bits/stdc++.h>

#define ll  long long
#define ull  unsigned long long
#define ld  long double
#define f(i,n)  for(i=0;i<n;i++)
#define F(i,n)  for(i=n-1;i>=0;i--)
#define fa(i,a,b)  for(i=a;i<=b;i++)
#define Fa(i,a,b)  for(i=a;i>=b;i--)
#define printArray(i,a,n)  f(i,n)cout<<a[i]<<" "; cout<<endl;
#define printSet(a)  for(auto setData:a) cout<<setData<<" ";cout<<endl;
#define printMap(a)  for(auto mapData:a) cout<<mapData.first<<" "<<mapData.second<<endl;
#define printVector(a)  for(auto vectorData:a)cout<<vectorData<<" ";cout<<endl;
#define printLinkedList()  temp=head;while(temp){cout<<temp->data<<" ";temp=temp->post;} cout<<endl;

#define pb(x)  push_back(x)
#define all(a)  a.begin(),a.end()
#define rall(a)  a.rbegin(),a.rend()
#define sor(a)  sort(a.begin(),a.end())
#define rev(a)  reverse(a.begin(),a.end())
#define mem(a,x)  memset(a,x,sizeof(a))
//[ ll *it; it = maxElement(a,a+n); ]

#define bs  binary_search
#define lb  lower_bound
#define ub  upper_bound
#define mp  make_pair
#define txtIO  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define txtTest freopen("C:/Users/Iftekhar/Documents/what/input.txt", "r", stdin);
#define FastIO  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define TestCase  ll t;cin>>t;while(t--)
#define points(x)  fixed<<setprecision(x)
#define scd(a,x,y)  a/__gcd(x,y);
#define nl  cout<<endl;
#define done  return 0

const ld PI= 3.14159265358979323846264338327950288;  //2*acos(0.0);
const long long MOD= 1000000007;
const long long MAX = 32000;

// stringstream demo(str);  demo >> x;
// stringstream demo;  demo << x;  name=demo.str();

using namespace std;


int main()
{
        FastIO;
        //txtTest;
        ll n,i,cnt=0,flag=0;
        cin>>n;
        vector<ll> a(n),b(n);
        f(i,n){
              cin>>a[i]>>b[i];
              if(a[i]==b[i]) cnt++;
              else
              {
                       cnt=0;
              }
              if(cnt>=3) flag=1;
        }
        if(flag) cout<<"Yes"<<endl;
        else
        {
                 cout<< "No" <<endl;
        }
        
        done;
}

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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MAX = 1e5 + 5;
int a[MAX], b[MAX], c[MAX];
ll pref[MAX];

int main() {
	int n;
	scanf("%d", &n);
	fori(i, 1, n + 1) {
		scanf("%d", a + i);
	}
	fori(i, 1, n + 1) {
		scanf("%d", b + i);
	}
	fori(i, 1, n + 1) {
		scanf("%d", c + i);
	}
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	sort(c + 1, c + n + 1);
	fori(i, 1, n + 1) {
		int less = lower_bound(a + 1, a + n + 1, b[i]) - a - 1;
		pref[i] = pref[i - 1] + less;
	}
	ll ans = 0;
	fori(i, 1, n + 1) {
		int less = lower_bound(b + 1, b + n + 1, c[i]) - b - 1;
		ans += pref[less];
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i <n; i++)
#define INF 100000000;

using namespace std;
int main(void){
    int n =0;
    cin >> n;
    string town = " ";
    int value =0;
    vector<tuple<string, int, int>>vec;
    rep(i, n){
        cin >> town >> value;
        vec.push_back(make_tuple(town, -value, i+1));
    }
    sort(vec.begin(), vec.end()); // 文字列は辞書順に。数値は低い順にソート。
    rep(i, n){
        cout << get<2>(vec[i]) << endl;
    }
}

Measured memory_bytes: 256
import java.io.*;

import java.util.*;





class Main{

		
		public static void main(String args[]) throws IOException{

			ArrayList<Double> equ = new ArrayList<Double>();

			Scanner scan = new Scanner(System.in);

			int n = 0;

			

			while(scan.hasNext()){

					String str1 = scan.next();

					n = Integer.valueOf(str1).intValue();

			}

		
		int money = 100000;
		int check,surp;


		for(int i = n;i>0;i--){	

			
			check = (int)(money * 1.05);
			surp = check%1000;
			if(surp == 0)money = check;
			else{
				money = check-surp+1000;
			}
		}
		System.out.println(money);

	}
		

}

Measured memory_bytes: 11000
import java.util.*;

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

        long k = sc.nextInt();

        long seven = 7;

        for(int i = 0; i <= k; i++){
            if(seven % k == 0){
                System.out.println(i + 1);
                return;
            }
            seven *= 10;
            seven += 7;
            seven %= k;
        }

        System.out.println(-1);
    }
}


Measured memory_bytes: 35784
import sys
list_ = []
for i in range(5):
    list_.append(int(input()))
k =int(input())
for i in range(5):
    for j in range(5):
        diff = list_[i]-list_[j]
        if abs(diff) > k :
            print(':(')
            sys.exit()
print('Yay!')    
        
        


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MODADD(ADD_X,ADD_Y)  (ADD_X+ADD_Y)%MOD;
#define MODSUB(SUB_X,SUB_Y)  (SUB_X-SUB_Y)+MOD)%MOD;
#define MODMUL(MUL_X,MUL_Y)  (MUL_X*MUL_Y)%MOD;
#define LCM(LCM_X,LCM_Y) (LCM_X*LCM_Y)/__gcd(LCM_X,LCM_Y);
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
int dx[]= {1,0,-1,0,1,-1,1,-1};
int dy[]= {0,1,0,-1,1,-1,-1,1};

int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    string s;
    cin>>s;
    int len=s.length();
    if(s[len-1]=='s')
        s+="es";
    else
        s+="s";
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 3648
#include <algorithm>
#include <cstdio>

const int N = 100000;
const int D = 20;

int n, x[N], l, jump[D][N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
        scanf("%d", x + i);
    }
    scanf("%d", &l);
    for (int i = 0, j = 0; i < n; ++ i) {
        while (j + 1 < n && x[j + 1] - x[i] <= l) {
            j ++;
        }
        jump[0][i] = j;
    }
    for (int j = 1; j < D; ++ j) {
        for (int i = 0; i < n; ++ i) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
        }
    }
    int q;
    scanf("%d", &q);
    while (q --) {
        int l, r;
        scanf("%d%d", &l, &r);
        l --;
        r --;
        if (l > r) {
            std::swap(l, r);
        }
        int result = 0;
        for (int j = D - 1; j >= 0; -- j) {
            if (jump[j][l] < r) {
                result += 1 << j;
                l = jump[j][l];
            }
        }
        printf("%d\n", result + 1);
    }
}


Measured memory_bytes: 8960
"""
https://atcoder.jp/contests/dp/tasks/dp_g

Using list to store adjacent list is faster than using sets.
Maybe it is because the append operation of list in python is faster than add operation of sets.

Using defaultdict instead of list to store adj is faster. Maybe it is because in case the graph is
sparse, defauldict can save more query time.
"""
from sys import stdin
from collections import defaultdict, deque
input = stdin.readline
N, M = map(int, input().split())
d = [0] * (N + 1)
adj = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    d[y] += 1

dp = [0] * (N + 1)  # dp denotes longest path ends at i

Q = deque([i for i in range(1, N + 1) if d[i] == 0])

while Q:
    cur = Q.popleft()
    for nxt in adj[cur]:
        dp[nxt] = max(dp[nxt], dp[cur] + 1)
        d[nxt] -= 1
        if d[nxt] == 0:
            Q.append(nxt)
print(max(dp))


Measured memory_bytes: 67164
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

i32 gcd (i32 a, i32 b) {
  if (a == 0) return b;
  if (b == 0) return a;
  i32 r = a % b;
  while (r > 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

i32 calc (i32 *a, i32 n, i32 g) {
  if (n == 1) return g;
  i32 m = n / 2;
  i32 b = g;
  for (i32 i = m; i < n; ++i) {
    b = gcd (b, a[i]);
  }
  b = calc (a, m, b);
  i32 c = g;
  for (i32 i = 0; i < m; ++i) {
    c = gcd (c, a[i]);
  }
  c = calc (a + m, n - m, c);
  return b > c ? b : c;
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *a = (i32 *) calloc (n, sizeof (i32));
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, a + i);
  }
  i32 ans = calc (a, n, 0);
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
    public static Scanner sc;
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            String s = sc.next();
            
            String a = s.substring(0, s.indexOf("+"));
            String b = s.substring(s.indexOf("+")+1, s.indexOf("="));
            String c = s.substring(s.indexOf("=")+1, s.length());
            
            boolean bo = true;
            
            for (Integer i = 0; i < 10; i++) {
                if (i==0 && a.charAt(0)=='X' && a.length() >= 2) continue;
                if (i==0 && b.charAt(0)=='X' && b.length() >= 2) continue;
                if (i==0 && c.charAt(0)=='X' && c.length() >= 2) continue;
                BigDecimal ia = new BigDecimal(a.replace("X", i.toString()));
                BigDecimal ib = new BigDecimal(b.replace("X", i.toString()));
                BigDecimal ic = new BigDecimal(c.replace("X", i.toString()));
                
                if (ia.add(ib).compareTo(ic) == 0) {
                    System.out.println(i);
                    bo = false;
                    break;
                }
            }
            if (bo) System.out.println("NA");
        }
    }
}

Measured memory_bytes: 30080
fun main(arr:Array<String>) {
    val (w,a,b) = readLine()!!.split(" ").map { it.toInt() }
    if(a <= b && b<= a+w) {
        println(0)
        return
    }
    if(b <= a && a <= b + w) {
        println(0)
        return
    }
    val ans = Math.min(Math.min(Math.abs(a+w-b), Math.abs(b+w-a)), Math.abs(a-b))
    println(ans)
}

Measured memory_bytes: 36196
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a+b<24){
        System.out.println(a+b);
        }else{
        System.out.println((a+b)%24);    
        }
    }
}

Measured memory_bytes: 23764
while True:
    (H, W) = [int(x) for x in input().split()]
    if H == W == 0:
        break

    for hc in range(H):
        if hc == 0 or hc == H -1:
            print('#' * W)
        else:
            print('#' + '.' * (W -2) + '#')
    print()

Measured memory_bytes: 6720
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,w;
    cin>>n>>w;
    long long int arr[n][w+1];
    long long int ww,v;
    for(int r=0;r<n;r++)
    {
        arr[r][0] = 0;
    }
    for(int i=0;i<n;i++)
    {
        cin>>ww>>v;
        for(int j=1;j<=w;j++)
        {
            if(i==0)
            {
               if(j<ww)
               {arr[i][j]=0;}
               else
               {arr[i][j] = v;}
            }
            else
            {
                if(j<ww)
                {arr[i][j] = arr[i-1][j];}
                else
                {
                    if((arr[i-1][j])>(v+arr[i-1][j-ww]))
                    {
                        arr[i][j] = arr[i-1][j];
                    }
                    else
                    {
                       arr[i][j] = v+arr[i-1][j-ww];
                    }
                }
            }
        }
    }
    cout<<arr[n-1][w];



}


Measured memory_bytes: 78336
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int MAX = 999999999;

int main(){
    int a, b, x;
    cin >> a >> b >> x;

    if(a <= x && a + b >= x) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 256
import math

a,b,x = map(int, input().split(' '))
menseki = a**2
taiseki = menseki * b
half = taiseki * (1/2)
sakai = half - x
nokori = taiseki - x
if sakai == 0:
    rad = math.atan(b/a)
    deg = math.degrees(rad)
elif sakai < 0:
    n =2 *  nokori / a**2
    rad = math.atan(n/a)
    deg = math.degrees(rad)
elif sakai > 0:
    ah = 2 * x / (a*b)
    rad = math.atan(b/ah)
    deg = math.degrees(rad)
print(deg)

Measured memory_bytes: 3064
import copy
n=int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

L=prime_factorize(n)
M=L.copy()
M=list(set(M))

cnt=0
for x in M:
    m=L.count(x)
    for i in range(L.count(x)):
        if m-i-1 >= 0:
            m -= i+1
            cnt += 1

print(cnt)


Measured memory_bytes: 9344
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>   
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    bool flag = true;
    int alice = 0;
    int bob = 0;
    for(int i=0;i<N;i++){
        int x;
        cin >> x;
        a[i] = x;
    }
    sort(a.begin(),a.end());
    for(int j=N-1;j>=0;j--){
        if(a[j] != 0){
            if(flag == true){
                alice +=a[j];
                flag = false;
                
            }else{
                bob +=a[j];
                flag = true;
            }
        }
    }
    int ans = alice-bob;
    cout << ans << endl;
    }

Measured memory_bytes: 256
main :: IO ()
main = interact $ pickOdds2

pickOdds, pickOdds'
  :: [a] -> [a]
pickOdds []       = []
pickOdds [a]      = [a]
pickOdds (a:b:bs) = a : pickOdds bs 

pickOdds' = map snd . filter (odd . fst) . zip [1..]

pickOdds2 = map snd . filter fst . zip (cycle [True, False])

Measured memory_bytes: 1020
from collections import Counter
N, M = map(int, input().split())
A = list(map(int, input().split()))
count_a = Counter(A)
A = [(v, k) for k, v in count_a.items()]
for i in range(M):
    B, C = map(int, input().split())
    A.append((B, C))
A = sorted(A, reverse=True, key=lambda x: x[1])
ans = 0
for k, v in A:
    N = N - k
    if N <= 0:
        ans += k*v+N*v
        break
    ans += k*v
print(ans)


Measured memory_bytes: 38848
//Catchharsh
    #include<bits/stdc++.h>
    #define ll long long int 
    #define ld long double
    #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    #define F first
    #define S second
    #define pb push_back
    #define endl '\n'
    const ll MOD = 1e9+7;
    const ll INF = 1011111111;
    const ll LLINF = 1000111000111000111LL;
    const ld EPS = 1e-10;
    const ld PI = 3.14159265358979323;
    using namespace std;
    ll power (int x,int n)
    {
        if(n==0)
        return 1;
        else if(n%2==0)
        return power((x*x),n/2);
        else
        return x*power((x*x),(n-1)/2); 
    }
    vector<ll> seve;
    void  seveprime()
    {
      int prime[1000000]={0};
      for(int i=2;i*i<1000000;i++)
       {
        if(prime[i]==0)
         {
      	  for(int j=i*2;j<=1000000;j+=i)
           prime[j]=1;
         }
       }
       for(int i=2;i<=1000000;i++)
       {
       	if(prime[i]==0)
       		seve.pb(i);
       }
    }
    ll ar[100005];
    bool compare(pair<ll,ll> a,pair<ll,ll> b)
    {
    	return a.S>b.S;
    }
    int main()
    {   
         IOS;
         ll n,m,i,k;
         cin>>n>>m;
         vector<ll> v(n);
         for(i=0;i<n;i++)
         	cin>>v[i];
         vector<pair<ll,ll> > v1(m);
         for(i=0;i<m;i++)
         	cin>>v1[i].F>>v1[i].S;
         sort(v.begin(),v.end());
         sort(v1.begin(),v1.end(),compare);
          ll j=0;
         for(i=0;i<m;i++)
         	{
         		ll kitne=v1[i].F;	
         		ll kisse=v1[i].S;
                 while(v[j]<kisse&&kitne!=0&&j<n)
                 {
                 	v[j]=kisse;
                 	kitne--;
                 	j++;
                 }
         	}
         ll ans=0;
         for(i=0;i<n;i++)
         	ans+=v[i];
         cout<<ans;

    }

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

int main() {
  char ar[20];
  cin >> ar;
  for (int i=0; i<19; i++) {
    if (ar[i] == ',') { 
      cout << " ";
    } else {
      cout << ar[i];
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			int num1 = sc.nextInt();
			int num2 = sc.nextInt();
			if (num1 == 0 && num2 == 0) break;
			if(num1 < num2) {
				System.out.println(num1 + " " + num2);
			} else {
				System.out.println(num2 + " " + num1);
			}
		}
	}
}


Measured memory_bytes: 34368
#include <iostream>
using namespace std;
int a, b;
int main(void){
    // Your code here!
    cin >> a >> b;
    a--; b--;
    cout << (a / 50 + b / 50) * 2 + 4 << ' ' << 100 << endl;
    for (int i = 0; i < a / 50; i++) {
        for (int j = 0; j < 50; j++) {
            cout << '.' << '#';
        }
        cout << endl;
        for (int j = 0; j < 100; j++) {
            cout << '#';
        }
        cout << endl;
    }
    for (int i = 0; i < a % 50; i++) {
        cout << '.' << '#';
    }
    for (int i = 0; i < 100 - a % 50 * 2; i++) {
        cout << '#';
    }
    cout << endl;
    for (int i = 0; i < 100; i++) {
        cout << '#';
    }
    cout << endl;
    for (int i = 0; i < 100; i++) {
        cout << '.';
    }
    cout << endl;
    for (int i = 0; i < b / 50; i++) {
        for (int j = 0; j < 50; j++) {
            cout << '#' << '.';
        }
        cout << endl;
        for (int i = 0; i < 100; i++) {
            cout << '.';
        }
        cout << endl;
    }
    for (int i = 0; i < b % 50; i++) {
        cout << '#' << '.';
    }
    for (int i = 0; i < 100 - b % 50 * 2; i++) {
        cout << '.';
    }
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

int main() {
  	fastio;
    int x, y, z;
  	cin >> x >> y >> z;
  	swap(x, y);
  	swap(x, z);
  	printf("%d %d %d", x, y, z);
	return 0;
}


Measured memory_bytes: 256
var
 st:ansistring;
 i,s1,s2:longint;
begin
 readln(st);
 for i:=1 to length(st) do
  begin
   if st[i]='S' then inc(s1);
   if (s1>0)and(st[i]='T') then
    begin
     dec(s1);
     s2:=s2+2;
    end;
  end;
 writeln(length(st)-s2);
end.

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

signed main() {
	string s;
	cin >> s;
	sort(all(s));
	if ((s[0] == s[1] and s[2] == s[3]) and (count(all(s), s[0]) == 2 and count(all(s), s[2]) == 2)) {
		puts("Yes");
	} else {
		puts("No");
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;

vector<int> prime;
bool is_prime[55556];

int sieve() {
  int h = 55556;
  int p = 0;
  for(int i=0; i<=h; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;

  for(int i=2; i<=h; i++) {
    if(is_prime[i]) {
      prime.push_back(i);
      for(int j=2*i; j<=h; j+=i) is_prime[j] = false;
    }
  }
}

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

  cin >> n;
  sieve();

  for(int count=0, i=0; i<prime.size(); i++) {
    if(prime[i] % 5 == 1) {
      cout << prime[i] << endl;
      count++;
    }
    if(count == n) break;
  }
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define MAX 10010
int main(){
    int H;
    int W;
   
while(true){
    scanf("%d %d",&H,&W);
    if(W==0 && H == 0)break;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if((i+j) %2 == 1)putchar('.');
            else putchar('#');
        }
    printf("\n");
    }
    printf("\n");
}
return 0;
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,m;
    cin>>n>>m;
    ll b[3];
    rep(0,i,3)b[i]=-1;
    rep(0,i,m){
        ll x,y;
        cin>>x>>y;
        --x;
        if(b[x]==-1){
            b[x]=y;
            if(x==0&&y==0&&!(n==1)){
                cout<<-1<<endl;
                return 0;
            }
        }else{
            if(b[x]!=y){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    rep(0,i,n){
        if(b[i]==-1){
            if(i==0 && (n!=1))cout<<1;
            else cout<<0;
        }else{
            cout<<b[i];
        }
    }
    cout<<endl;
}

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

using namespace std ;

const int N = 1e5 + 5 ;
int a[N] , ans[N] ;
int n , k ;


int go(int i){

    if(ans[i] != 2e9)
        return ans[i] ;


    int j = i - k ;
    if(j < 0)
        j = 0 ;


    for(j ; j < i ; j++)
        if( go(j) + abs(a[i] - a[j] ) < ans[i] )

            ans[i] = go(j) + abs(a[i] - a[j]) ;




    return ans[i] ;
}



int main(){

    scanf("%d %d" , &n , &k);
    for(int i = 1 ; i < n ; i++)
        ans[i] = 2e9 ;

    for(int i = 0 ; i < n ; i++)
        scanf("%d" , &a[i]) ;



    printf("%d\n" , go(n - 1));
}


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
int n;
string s;
int a,b;
int x,y;
bool dir = true; // true: x, false: y

vector<int> xdir, ydir;


bool go(vector<int> v, int x, int y) {
  set<int> s = { x };
  for (int i: v) {
    set<int> _s;
    for (int j: s) {
      _s.insert(j-i); _s.insert(j+i);
    }
    swap(s, _s);
  }
  return s.count(y);
}

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

  cin>>s>>a>>b;
  int i=0;
  while (i<int(s.length()) && s[i]=='F') {
    x++; i++;
  }
  s = s.substr(i);
  n = s.length();

  for (int i=0; i<n; ) {
    assert(s[i]=='T');
    dir = !dir;
    int j=i+1;
    while (j<n && s[j]=='F') j++;
    int len = j-i-1;
    if (len) {
      if (dir) xdir.push_back(len); else ydir.push_back(len);
    }
    i = j;
  }

  // cout<<"xdir: ";
  // for (int x: xdir) cout<<x<<" ";
  // cout<<endl;
  // cout<<"ydir: ";
  // for (int x: ydir) cout<<x<<" ";
  // cout<<endl;


  if (go(xdir,x,a) && go(ydir,y,b)) out("Yes");
  out("No");  

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
Int const INF = 1e9;

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

    int n,y; cin>>n>>y; y/=1000; bool key=false;
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n-i; j++){
            for (int k = 0; k <= n-i-j; k++){
                if(10*i+5*j+k==y&&i+j+k==n){
                    cout<<i<<' '<<j<<' '<<k;
                    key=true;
                }
                if(key)break;
            }
            if(key)break;
        }
        if(key)break;
    }
    if(!key)cout<<"-1 -1 -1"<<'\n';
}

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

int main(){
    int i, j, k;
    int L, N = 0;
    cin >> L;
    while(1<<N <= L) N++;
    vector<vector<int>> ans;

    // 2進数の辺を作る
    for(i=1; i<N; i++){
        ans.push_back({i, i+1, 1<<(i-1)});
        ans.push_back({i, i+1, 0});
    }

    // 今できている経路の最大長。これをL-1にするまで経路を足す。
    int now = (1<<(N-1)) - 1;

    for(i=N-1; i>=1; i--){
        if(now == L-1) break;
        
        // 頂点iからのショートカット追加で増える経路数
        int gain = 1<<(i-1);

        if(now + gain <= L-1){
            ans.push_back({i, N, now+1});
            now += gain;
        }
    }

    int M = ans.size();
    cout << N << " " << M << endl;
    for(auto v : ans){
        cout << v[0] << " " << v[1] <<  " " << v[2] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int M = 1000000007;

int main() {
    while (1) {
        int n;
        cin >> n;
        if (!n) return 0;

        vector<int> power(n);
        map<string, int> mp;
        vector<vector<string>> nearby(n);
        for (int i = 0; i < n; ++i) {
            string s;
            int c;
            cin >> s >> power[i] >> c;
            if (i) {
                for (auto& j : nearby[0]) {
                    if (s == j) {
                        --i;
                        --n;
                        for (int k = 0; k < c; ++k)
                            cin >> s;

                        goto A;
                    }
                }
            }
            mp[s] = i;
            nearby[i].resize(c);
            for (int j = 0; j < c; ++j)
                cin >> nearby[i][j];

            A:
            continue;
        }
        power.resize(n);
        nearby.resize(n);
        vector<long long> isnearby(n, 0LL);
        for (int i = 0; i < n; ++i)
            for (auto& j : nearby[i])
                if (mp.count(j))
                    isnearby[i] |= 1LL << mp[j];

        int n1 = n / 2;
        int n2 = n - n1;
        vector<int> dp(1 << n1, 0);
        for (int i = 1; i < (1 << n1); i += 2) {
            int ma = 0;
            long long inb = 0;
            for (int j = 0; j < n1; ++j) {
                if ((i >> j) & 1) {
                    inb |= isnearby[j];
                    dp[i] += power[j];
                    ma = max(ma, dp[i ^ (1 << j)]);
                }
            }
            if (i & inb)
                dp[i] = ma;
        }
        int msk = (1 << n1) - 1;
        int ans = dp[msk];
        for (int i = 1; i < (1 << n2); ++i) {
            int sum = 0;
            long long inb = 0;
            for (int j = 0; j < n2; ++j) {
                if ((i >> j) & 1) {
                    inb |= isnearby[n1 + j];
                    sum += power[n1 + j];
                    if (i & (inb >> n1)) break;
                }
            }
            if (!(i & (inb >> n1)))
                ans = max(ans, sum + dp[(inb & msk) ^ msk]);
        }
        cout << ans << "\n";
    }
}

Measured memory_bytes: 7404
import java.util.Scanner;

public class Main {

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

		long left=Long.MIN_VALUE;
		long right=Long.MAX_VALUE;
		for (int i = 0; i < M; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();

			left = Math.max(left, A);
			right = Math.min(right, B);

			if (left > right) {
				System.out.println(0);
				break;
			}

			if (i == M-1) {
				System.out.println(right-left+1);
				break;
			}

		}

	}
}




Measured memory_bytes: 59160
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)

typedef pair<int, int> pii;

const int inf = 1e9;

struct edge {
	int to, cost, time;
	edge(int to0,int cost0,int time0) {
		to = to0; cost = cost0; time = time0;
	};
};

vector<edge> G[100];
int d[100];

int N, M;

void dijkstra(int s, int mode)
{
	priority_queue<pii, vector<pii>, greater<pii> > q;

	fill(d, d + M, inf);
	d[s] = 0;

	q.push(MP(0, s));

	while (q.size()) {
		pii p = q.top(); q.pop();
		int v = p.scd;
		if (d[v] < p.fst) continue;
		rep(u, G[v].size()) {
			edge e = G[v][u];
			int a = mode == 0 ? e.cost : e.time;
			if (d[e.to] > d[v] + a) {
				d[e.to] = d[v] + a;
				q.push(MP(d[e.to], e.to));
			}
		}
	}
}

signed main()
{
	while (scanf("%d %d", &N, &M), N || M) {
		rep(i, M) G[i].clear();

		rep(i, N) {
			int a, b, cost, time; scanf("%d %d %d %d", &a, &b, &cost, &time); a--; b--;
			G[a].PB(edge(b, cost, time));
			G[b].PB(edge(a, cost, time));
		}

		int K; scanf("%d", &K);

		rep(i, K) {
			int p, q, r; scanf("%d %d %d", &p, &q, &r); p--; q--;
			dijkstra(p, r);
			printf("%d\n", d[q]);
		}
	}
}

Measured memory_bytes: 1128
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0){
                break;
            }
            int[] scores =new int[n];
            for(int i=0;i<n;i++){
                scores[i]=sc.nextInt();
            }
            Arrays.sort(scores);
            int sum=0;
            int ave=0;
            for(int j=1;j<n-1;j++){
                sum+=scores[j];
            }
            ave=sum/(n-2);
            System.out.println(ave);
        }
        sc.close();
    }
}


Measured memory_bytes: 28736
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int[] a = sc.IntArray();

        int x4 = a.Where(num => num % 4 == 0).Count();
        int x2 = a.Where(num => num % 2 == 0).Count() - x4;

        int can = x4 * 2 + 1;
        can += x2 >= 2 ? x2 - 1 : 0;

        bool ok = can >= a.Count();

        string answer = ok ? "Yes" : "No";

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 19680