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

public class Main {
	static BufferedReader br;
	static StringTokenizer tokenizer;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		int n = nextInt();
		int[][] arr = new int[n][3];
		int[][] dp = new int[n][3];
		for(int i = 0; i < n; i++) {
			for(int k = 0; k < 3; k++)
				arr[i][k] = nextInt();
		}
		dp[0][0] = arr[0][0];
		dp[0][1] = arr[0][1];
		dp[0][2] = arr[0][2];
		for(int i = 0; i < n - 1; i++) {
			for(int k = 0; k < 3; k++) {
				dp[i + 1][(k + 1) % 3] = Math.max(dp[i + 1][(k + 1) % 3], dp[i][k] + arr[i + 1][(k + 1) % 3]);
				dp[i + 1][(k + 2) % 3] = Math.max(dp[i + 1][(k + 2) % 3], dp[i][k] + arr[i + 1][(k + 2) % 3]);
			}
		}
		System.out.println((int) Math.max(Math.max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]));
	}

	public static String next() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			String line = br.readLine();
			if (line == null)
				throw new IOException();
			tokenizer = new StringTokenizer(line);
		}
		return tokenizer.nextToken();
	}

	public static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
}


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

class Timer {
public:
    void start() {
        start_ = std::chrono::steady_clock::now();
    }
    int64_t elapsedMilliSec() {
        auto n = std::chrono::steady_clock::now();
        auto e = std::chrono::duration_cast<std::chrono::milliseconds>(n - start_);
        return e.count();
    }
private:
    std::chrono::steady_clock::time_point start_;
};

constexpr int64_t NUM = 26;
vector<int64_t> c(NUM);
vector<vector<int64_t>> s;

int64_t score(const vector<int64_t>& v) {
    vector<int64_t> last(NUM, -1);
    int64_t S = 0;
    for (int64_t i = 0; i < v.size(); i++) {
        //開催による満足度増加
        S += s[i][v[i]];

        //最終開催日更新
        last[v[i]] = i;

        //開催されないことによる満足度減少
        for (int64_t j = 0; j < NUM; j++) {
            S -= c[j] * (i - last[j]);
        }
    }

    return S;
}

int main() {
    //時間関連
    Timer timer;
    timer.start();
    constexpr int64_t LIMIT_MSEC = 1900;

    //入力
    int64_t D;
    cin >> D;
    for (int64_t& C : c) {
        cin >> C;
    }

    s.resize(D, vector<int64_t>(NUM));
    for (int64_t i = 0; i < D; i++) {
        for (int64_t j = 0; j < NUM; j++) {
            cin >> s[i][j];
        }
    }

    //乱数関連
    mt19937_64 engine(0);
    uniform_int_distribution<int64_t> day_dist(0, D - 1);
    uniform_int_distribution<int64_t> num_dist(0, NUM - 1);

    //ランダムに生成
    vector<int64_t> ans(D);
    for (int64_t& a : ans) {
        a = num_dist(engine);
    }

    int64_t best_score = score(ans);

    while (timer.elapsedMilliSec() < LIMIT_MSEC) {
        int64_t change_day = day_dist(engine);
        int64_t change_num = num_dist(engine);

        //変える
        int64_t before_num = ans[change_day];
        ans[change_day] = change_num;

        int64_t s = score(ans);

        if (s > best_score) {
            best_score = s;
        } else {
            //戻す
            ans[change_day] = before_num;
        }
    }

    for (int64_t& a : ans) {
        cout << a + 1 << endl;
    }
}

Measured memory_bytes: 3728
#include<bits/stdc++.h>
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000001
#define MAXN        400005
#define mod         1000000007
using namespace std;

ll a[MAXN];
ll dp[MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m,i,x;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>x;
        a[x]=1;
    }
    if(a[0]==1){
        dp[0]=0;
    }
    else{
        dp[0]=1;
    }
    if(a[1]==1){
        dp[1]=0;
    }
    else{
        dp[1]=1;
    }
    for(i=2;i<=n;i++){
        if(a[i]==1){
            dp[i]=0;
        }
        else{
            dp[i]=dp[i-1]+dp[i-2];
            dp[i]=dp[i]%mod;
        }
    }
    cout<<dp[n];
}

Measured memory_bytes: 3072
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1年生
{
    class Program
    {
        public static int[] a;
        public static int n = 0;
        public static long[,] table;
        public static bool[,] flag;
        public static long Fanc(int depth, int sum)
        {
            if (depth == n - 1) { return sum == a[depth] ? 1 : 0; }
            if (sum > 20 || sum < 0) { return 0; }
            if (flag[depth, sum]) { return table[depth, sum]; }
            long ret = 0;
            if (depth == 0) { ret = Fanc(depth + 1, sum + a[depth]); }
            else { ret = Fanc(depth + 1, sum + a[depth]) + Fanc(depth + 1, sum - a[depth]); }
            flag[depth, sum] = true;
            table[depth, sum] = ret;
            return ret;
        }
        static void Main(string[] args)
        {
            n = int.Parse(Console.ReadLine());
            a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            n = a.Length;
            long ans = 0;
            table = new long[n, 21];
            flag = new bool[n, 21];
            ans = Fanc(0, 0);
            Console.WriteLine(ans);
        }

    }
}



Measured memory_bytes: 18356
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 2e5 + 10, mod = 1e9 + 7;

vector<int> g[N];
int sz[N];
ll p2[N], p2_inv[N];

ll dfs(int u, int p, int n);
ll pwr(ll x, ll e);

int main() {
	fast_cin();
	int n; cin >> n;
	p2[0] = p2_inv[0] = 1;
	for (int i = 1; i <= n; ++i) {
		p2[i] = (2 * p2[i - 1]) % mod;
		p2_inv[i] = pwr(p2[i], mod - 2);
	}
	for (int i = 2; i <= n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	cout << dfs(1, 0, n) << '\n';
}

ll dfs(int u, int p, int n) {
	sz[u] = 1;
	vector<int> sizes;
	ll ans = 0, prob = 0;
	for (auto& v : g[u]) {
		if (v != p) {
			ans += dfs(v, u, n);
			sz[u] += sz[v];
			prob += p2_inv[n - sz[v]] * (mod + 1 - p2_inv[sz[v]]);
			prob %= mod;
		}
	}
	if (sz[u] < n) {
		prob += p2_inv[sz[u]] * (mod + 1 - p2_inv[n - sz[u]]);
		prob %= mod;
	}
	prob += p2_inv[n] + p2_inv[1];
	prob %= mod;
	ans %= mod;
	ans += (mod + 1 - prob);
	return ans % mod;
}

ll pwr(ll x, ll e) {
	ll res = 1;
	while (e) {
		if (e & 1) {
			res = (res * x) % mod;
		}
		x = (x * x) % mod;
		e /= 2;
	}
	return res;
}

Measured memory_bytes: 26240
n, k = gets.chomp.split(" ").map(&:to_i)
p = gets.chomp.split(" ").map(&:to_i)

q = []
q[0] = 0
(1..n).each do |i|
  q[i] = p[i-1] + q[i-1]
end
max = 0
(0..n-k).each do |i|
  m = q[k+i] - q[i]
    max = m if max < m
end
puts (max+k)/2.0

Measured memory_bytes: 17612
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1e9

int main(){
	int n;
	while(cin>>n){
		vector<double> a(n),cp(n,-INF);
		for(auto &i:a) cin>>i;
		double l=0, r=a[0]*2;
		
		cp[0]=a[0];
		for(int i=1;i<n;i++){
			for(int j=0;j<i;j++){
				double d=a[j]+a[i];
				double h=fabs(a[j]-a[i]);
				cp[i]=max(cp[i],sqrt(d*d-h*h)+cp[j]);
			}
			l=min(l,cp[i]-a[i]);
			r=max(r,cp[i]+a[i]);
		}
		cout<<fixed<<setprecision(13)<<r-l<<endl;
	}
	return 0;
}



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

using namespace std;

int main()
{
	string s;
	cin >> s;
	int y = (s[0] - '0') * 10 + (s[1] - '0');
	int m = (s[2] - '0') * 10 + (s[3] - '0');
	int sum = 0;
	if (m > 0 && m <= 12) {
		sum = 1;
	}
	if (y > 0 && y <= 12) {
		sum |= 2;
	}

	string ans[] = { "NA", "YYMM", "MMYY", "AMBIGUOUS" };
	cout << ans[sum] << endl;

	return 0;
}

Measured memory_bytes: 256
from fractions import gcd
import math

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    a =int(input())
    s = input()
    if a < 3200:
        print('red')
    else:
        print(s)


main()


Measured memory_bytes: 5716
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
abcd.sort()

d=deque([[1]])
for i in range(n):
    for j in range(len(d)):
        tmp=d.popleft()
        for k in range(m-tmp[-1]+1):
            d.append(tmp+[tmp[-1]+k])

ans=0
# print(d)
# print(type(d))
for i in range(len(d)):
    tmp=0
    lst=d[i]
    for j in range(q):
        a,b,c,e=abcd[j]
        if lst[b-1]-lst[a-1]==c:
            tmp+=e
    ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 109628
#include<stdio.h>
int main()
{
   int m,f,r,i;
   char grade;

   for(i=0;i<50;i++)
   {
   scanf("%d%d%d",&m,&f,&r);

   if(m== -1 && f==-1 && r==-1)break;
   else if(m== -1 || f==-1)grade='F';
   else if(m+f>=80)grade='A';
   else if(m+f>=65 && m+f<80)grade='B';
   else if(m+f>=50 && m+f<65)grade='C';
   else if(m+f>=30 && m+f<50 && r>=50 && r<=100)grade='C';
   else if(m+f>=30 && m+f<50 )grade='D';
   else if(m+f<30)grade='F';

  printf("%c\n",grade);
   }








    return 0;
}



Measured memory_bytes: 2104
// 標準入力
var fs = require('fs'),
length = fs.fstatSync(process.stdin.fd).size,
buffer = new Buffer(length),
bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
input = buffer.toString('utf8', 0, bytesRead).trim().split('\n');
main();
    
// ここから
function main(){
  var primeNumbers = calcPrimeNumbers();
  for(var i = 0, len = input.length; i < len; i++){
    console.log(primeNumbers[parseInt(input[i], 10)]);
  }
}
   
function calcPrimeNumbers(){
  var max = 999999;
  var primeNumbers = new Int32Array(max + 1);
   
  // 除外
  // primeNumbers[0] = primeNumbers[1] = 0;// ここをこうすると
  // for(var i = 2, maxI = ~~Math.sqrt(max); i <= maxI; i++){
  for(var i = 2; i <= 1000; i++){
    if(primeNumbers[i]){
      continue;
    }
       
    for(var j = (i<<1); j <= max; j+=i){
      primeNumbers[j] = 1;
    }
  }
  
  for(var i = 2; i <= max; i++){
    // これがこうなる
    primeNumbers[i] = primeNumbers[i-1] + 1 - primeNumbers[i];
  }
     
  return primeNumbers;
}

Measured memory_bytes: 12588
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define STARTUP {(cin.tie(0));\
 (ios::sync_with_stdio(false));}

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define VECCIN(vec) const int size = (vec).size(); REP(i,size) cin>>(vec)[i];

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

using ll = long long;
using namespace std;
ll mod = 1'000'000'007;

const int INF = 1'050'000'000;

int main() {
    STARTUP;

    int N;
    cin >> N;
    int max = 0;
    for (int i = 1; i * i <= N; i++) {
        max = i * i;
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>myvectorX;
    vector<int>myvectorY;
    int i;
    int x;
    for(i=0; i < n; i++){
            cin >> x;
        myvectorX.push_back(x);
    }
    for(i=0; i<n; i++){
        cin >> x;
        myvectorY.push_back(x);
    }
    int a = 0;
    for(i=0; i < n; i++){
        if(myvectorX[i] > myvectorY[i]){
            a += myvectorX[i] - myvectorY[i];
        }
    }
    cout << a;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll d,t,s;
    cin>>d>>t>>s;
    if(t*s>=d)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}



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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

char mp[2222][2222];
bool ng[2222][2222];
int high[2222][2222];

int seica(ll h,ll w){
	ll ret = 0;
	REP(i,h){
		stack<pair<ll,ll>> st;
		REP(j,w){
			ll tmp = j;
			while(!st.empty() && st.top().FI > high[i][j]){
				auto now = st.top();
				st.pop();
				ret = max(ret,(j - now.SE) * now.FI);
				tmp = min(tmp,now.SE);
				//cout << i << " " << j << " " << now.FI << " " << now.SE << " " << (j - now.SE) * now.FI << endl;
			}
			if(st.empty() || st.top().FI < high[i][j])st.push(MP(high[i][j],tmp));
			if(st.empty() || st.top().FI < i + 1)st.push(MP(i + 1,j));
		}
		while(!st.empty()){
			auto now = st.top();
			st.pop();
			ret = max(ret, (w - now.SE) * now.FI);
			//cout << i << " " << w << " " << now.FI << " " << now.SE << " " << (w - now.SE) * now.FI << endl;
		}
	}
	return ret;
}

int main(){
	
	int h,w;cin >> h >> w;
	REP(i,h){
		REP(j,w){
			cin >> mp[i][j];
		}
	}
	
	REP(i,h-1){
		REP(j,w-1){
			int y = i + 1;
			int x = j + 1;
			int cou = 0;
			if(mp[y][x] == '#')cou++;
			if(mp[y][x-1] == '#')cou++;
			if(mp[y-1][x] == '#')cou++;
			if(mp[y-1][x-1] == '#')cou++;
			if(cou % 2)ng[y][x] = true;
		}
	}
	
	REP(i,h){
		REP(j,w){
			if(i == 0)high[i][j] = 1;
			else {
				if(ng[i][j])high[i][j] = 1;
				else high[i][j] = high[i-1][j] + 1;
			}
		}
	}
	
	cout << seica(h,w) << endl;
	
	return 0;
}


Measured memory_bytes: 28928
#include <cstdio>
typedef long long ll;
int n, a, b, l, r=1e9, m, h[100005];

bool f(int p) {
	ll i, c=0;
	for(i=0; i<n; i++)
		c += h[i]>(ll)p*b ? (h[i]-p*b+a-1)/a : 0;
	return c<=p;
}

int main() {
	scanf("%d%d%d", &n, &a, &b);
	a -= b;
	for(int i=0; i<n; i++) scanf("%d", &h[i]);
	while(l<r) {
		m = (l+r) / 2;
		if(f(m)) r = m;
		else l = m+1;
	}
	printf("%d", r);
	return 0;
}

Measured memory_bytes: 512
using System;
using System.Linq;
class program{
  static void Main(){
    int n = int.Parse(Console.ReadLine());
    int[] a = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
    int amx = a.Max();
    bool[] table = new bool[amx+1];
    Array.Sort(a);
    if(a[0] == 1){
      if(n == 1){
        Console.Write(1);
        return;
      }
      if(a[1] == 1){
        Console.Write(0);
        return;
      }else{
        Console.Write(1);
        return;
      }
    }
    int ans = 0;
    for(int i = 0;i < n;i++){
      if(!table[a[i]]){
        if(i+1 < n){
          if(a[i] != a[i+1]) ans++;
        }else{
          ans++;
        }
        for(int j = a[i];j <= amx; j += a[i]) table[j] = true;        
      }
    }
    Console.Write(ans);
  }
}

Measured memory_bytes: 44020
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<ll>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
#define MOD 1000000007
using namespace std;
typedef long long ll;


int main(void) {
	int x; cin >> x;
	int a, b;
	a = x / 500;
	b = (x - a*500) / 5;
	cout << a * 1000 + b * 5 << endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n, q, a, v;
    int maxA, maxV;
    cin>>n>>q;
    vector<int> list(n, 0);
    maxA = maxV = 0;
    while(cin>>a>>v) {
        a--;
        list[a] += v;
        if(v>0) {
            if(maxV < list[a]) {
                maxA = a;
                maxV = list[a];
            } else if(maxV == list[a]) {
                maxA = min(maxA, a);
            }
        }
        if(v<0) {
            if(a == maxA) {
                maxV = -1;
                for(int i=0; i<n; i++) {
                    if(maxV < list[i]) {
                        maxA = i;
                        maxV = list[i];
                    }
                }
            }
        }
        cout<<maxA+1<<" "<<maxV<<endl;
    }
}

Measured memory_bytes: 4896
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    K = I()
    subs = set()
    for j in range(1, 6):
        for i in range(len(s)):
            st = i
            en = min(st + j, len(s))
            subs.add(s[st:en])
    print(sorted(list(subs))[K-1])
main()


Measured memory_bytes: 83688
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#include <string.h>
#include <fstream>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LI long int
#define LLI long long int
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
using namespace std;
//
const int MOD=1e9+7;
//

const int INF=1e9+7;

int main(void){
    int n,m; cin>>n>>m;
    int g[100][100],h[100][100];
    FOR(i,0,100) FOR(j,0,100) g[i][j]=INF;
    FOR(i,0,m){
        int a,b,c; cin>>a>>b>>c;
        g[a-1][b-1]=c;
        g[b-1][a-1]=c;
    }
    FOR(i,0,100) FOR(j,0,100) h[i][j]=g[i][j];
    FOR(k,0,100){
        FOR(i,0,100){
            FOR(j,0,100){
                g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
            }
        }
    }
    int ans=0;
    FOR(i,0,100){
        FOR(j,0,100){
            if(h[i][j]!=INF&&g[i][j]!=h[i][j]) ans++;
        }
    }
    cout<<ans/2<<endl;
}


Measured memory_bytes: 384
import java.util.*;
import java.math.*;
import java.io.*;


public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String args[]) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        for(int i = 0; i < n; i++) {
            if(i == k -1) {
                System.out.print(Character.toLowerCase(s.charAt(i)));
            } else {
                System.out.print(s.charAt(i));
            }
        }
        System.out.println();
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> x;
    rep(i, n){ ll tmp; cin >> tmp; x.push_back(tmp);}

    ll ans = 0;
    rep(i, n-1){
        ll diff = x[i+1]-x[i];
        ans += min(diff*a, b);
    }
    cout << ans << endl;
}



Measured memory_bytes: 1400
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <time.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
#define mt(A,B) memset(A,B,sizeof(A))
using namespace std;
typedef long long LL;
const double PI = acos(-1);
const int N=2e5+10;
const LL mod=1e9+7;
const int inf = 0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3fLL;

int main()
{
#ifdef Local
    freopen("data.txt","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n,m,ans=0;
    cin>>n>>m;
    if(2*n>=m)
    {
        ans=m/2;
    }
    else
    {
        ans=n+(m-2*n)/4;
    }
    cout<<ans<<endl;
#ifdef Local
    cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
}
/*char s[40];
int ans=0;
int vis[4][4][4];
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
bool check(int x,int y,int z)
{
    if(x<1||x>3||y<1||y>3||z<1||z>3||vis[x][y][z])return false;
    else return true;
}
void dfs(int cur,int x,int y,int z,int fx)
{
    vis[x][y][z]=1;
    if(cur==27)
    {
        ans++;
        return;
    }
    if(s[cur]=='I')
    {
        int X,Y,Z;
        X=x+dx[fx];
        Y=y+dy[fx];
        Z=z+dz[fx];
        if(check(X,Y,Z))dfs(cur+1,X,Y,Z,fx);
    }
    else
    {
        for(int i=0;i<6;i++)
        {
            if(i==fx)continue;
            int X,Y,Z;
            X=x+dx[fx];
            Y=y+dy[fx];
            Z=z+dz[fx];
            if(check(X,Y,Z))dfs(cur+1,X,Y,Z,i);
        }
    }
    vis[x][y][z]=0;
}*/
/*mt(vis,0);
    scanf("%s",s+1);
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int k=1;k<=3;k++)
            {
                dfs(1,i,j,k,-1);
            }
        }
    }
    if(ans)puts("YES");
    else puts("NO");*/


Measured memory_bytes: 256
s=input()
a=[0]
for i in range(1,len(s)):
    if s[i-1]==s[i]:
        a.append(i)
a.append(len(s))
x=0;y=0
for i in range(1,len(a)):
    if i%2==0:
        x+=a[i]-a[i-1]
    else:
        y+=a[i]-a[i-1]
#print(x,y)
print(min(x,y))


Measured memory_bytes: 45424
N, M = map(int, input().split())
lis = [[int(x) for x in input().split()] for _ in range(N)]
ans = 0
for item in range(1, M + 1):
  for i in lis:
    if not item in i[1:]:
      break
  else:
    ans += 1
print(ans)    

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}

ll k;

double S(ll i){
	ll res = 0;
	while(i > 0){
		res += i%10;
		i /= 10;
	}
	return res;
}

bool check(ll i,ll j){
	return i*S(j) > j*S(i);
}

int main(){
	cin >> k;
	vector<ll> buf;
	vector<ll> ans;
	ll b = 1;
	rep(i,15){
		ll bb = b - 1;
		FOR(j,1,300){
			buf.push_back(b*j + bb);
			// cout << b*j+bb << endl;
		}
		b *= 10;
	}
	sort(ALL(buf));

	rep(i,buf.size()){
		FOR(j,i+1,buf.size()){
			if(check(buf[i],buf[j]) || buf[i] == buf[j])break;
			if(j == buf.size()-1){
				// cout << buf[i] << endl;
				ans.push_back(buf[i]);
			}
		}
	}
	rep(i,min(k,(ll)ans.size()))cout << ans[i] << endl;

	// double M = 0;
	// FOR(i,1,1000000){
	// 	double a = (double)i/calc(i);
	// 	double b = (double)(i+1)/calc(i+1);
	// 	if(a - b < EPS  && M - a < EPS){
	// 		cout << i << " " << a << endl;
	// 		M = max(M,a);
	// 	}
	// }
	// return 0;
	// rep(i,100000){
	// 	cout << i << " " << (double)i/calc(i) << endl;
	// }
	// return 0;
	// vector<string> ans;
	// FOR(i,1,10){
	// 	string s;
	// 	s += ((char)('0'+i));
	// 	ans.push_back(s);
	// }
	// // string t = "9";
	// // FOR(i,1,10){
	// // 	string s;
	// // 	s = ((char)('0'+i)) + t;
	// // 	ans.push_back(s);
	// // }
	// FOR(i,1,10){
	// 	string s = "";
	// 	rep(j,i)s += "9";
	// 	FOR(j,1,18+1){
	// 		string tt = "";
	// 		if(j/10 != 0)tt += (char)('0' + j/10);
	// 		tt += (char)('0' + j%10);
	// 		tt += s;
	// 		ans.push_back(tt);
	// 	}
	// }
	// rep(i,min(k,(ll)ans.size()))cout << ans[i] << endl;
	
}

Measured memory_bytes: 384
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


D = {c:i for i,c in enumerate('abcdefghijklmnopqrstuvwxyz')}
a = 'abcdefghijklmnopqrstuvwxyz'
s = S()
k = I()
ans = []
cnt = 0
for i in s:
    if 26 - D[i] <= k and i != 'a':
        k -= 26 - D[i]
        ans += ['a']
    else:
        ans += [i]

if k:
    ans[-1] = a[D[ans[-1]] + k % 26]


print(''.join(ans))

Measured memory_bytes: 47344
#F問題
N = int(input())
S = list(map(int,input().split()))
S.sort(reverse=True)
visit = [0]*(2**N)
visit[0] = 1
used = [S[0]]

flag = 0
for i in range(N):
    add = used[::-1]
    k = 0
    for u in used:
        while k < 2**N:
            if visit[k] == 0 and S[k] < u:
                visit[k] = 1
                add.append(S[k])
                break
            k+=1
        if k >= 2**N:
            print("No")
            flag = 1
            break
    if flag == 1:
        break
    
    used = add[::-1]
    used.sort(reverse=True)
    
if flag == 0:
    print("Yes")

Measured memory_bytes: 34676
N = int(input())
'''
def factorization(n):
    arr = [1,1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                if arr[1] >= arr[0]:
                    arr[0] = arr[0]*i
                else:
                    arr[1] = arr[1]*i
                temp //= i   
    if temp!=1:
        if arr[1] >= arr[0]:
            arr[0] = arr[0]*temp
        else:
            arr[1] = arr[1]*temp
    if arr==[1,1]:
        arr[0] =n
    return arr

facro = factorization(N)
print(facro[0] +facro[1] -2)
'''
min_num = 1
 
for i in reversed(range(2,int(-(-N**0.5//1))+1)):
    if N%i == 0:
        #print(i)
        min_num = i
        break

print(min_num + N//min_num-2)

Measured memory_bytes: 2940
<?php
error_reporting(0);
list($Q,$H,$S,$D) = explode(" ",trim(fgets(STDIN)));
$N = trim(fgets(STDIN));
//q=0.25 h=0.5 s=1 d=2
$Q=$Q*4;
$H=$H*2;
$L1 = min($Q,$H,$S);
$L2 = $D;
if ($L1*2 < $L2 || $N == 1) {
  printf("%d\n",$L1 * $N);
}
else {
  if ($N%2==1) {
    printf("%d\n",($N-1)/2*$L2+$L1);
  }
  else {
    printf("%d\n",$N/2*$L2);
  }
}


Measured memory_bytes: 3828
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

int dis[10][10]; 

inline void solve(){ 
    int  h, w ; 
    cin >> h >> w ; 
    for (int i=0;i<10;i++) {
        for (int j=0;j<10;j++){
            cin >> dis[i][j] ;  
        }
    }
    for (int k=0;k<10;k++) {
        dis[k][k]=0;
        for (int i=0;i<10;i++){
            for (int j=0;j<10;j++){    
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    int ans=0;
    for (int i=0;i<h;i++){
        for (int j=0;j<w;j++){
            int x; cin>>x;
            if (x > -1) ans += dis[x][1];
        }
    }
    cout << ans << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


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

void calc_div(int sum, vector<int> &rez) {
    for (int ctr1 = 1; ctr1 * ctr1 <= sum; ++ctr1)
        if (sum % ctr1 == 0) {
            rez.push_back(ctr1);
            if (sum / ctr1 != ctr1)
                rez.push_back(sum / ctr1);
        }
}
 
int main() {
    int n, k;
    cin >> n >> k;
    int ar[n];
    for (int ctr1 = 0; ctr1 < n; ++ctr1)
        cin >> ar[ctr1];

    int sum = accumulate(ar, ar + n, 0);
    vector<int> divs;
    calc_div(sum, divs);
    sort(divs.begin(), divs.end());
    reverse(divs.begin(), divs.end());
    for (auto r : divs) {
        int t = 0;
        sort(ar, ar + n,
            [r](auto lhs, auto rhs) {
                return (lhs % r) < (rhs % r);
            });
        int tot = accumulate(ar, ar + n, 0,
                    [r](auto s, auto nxt) {
                        return s + (nxt % r);
                    });
        int cur = 0;
        for (int ctr1 = 0; ctr1 < n; ++ctr1) {
            cur += ar[ctr1] % r;
            if (tot == (n - ctr1 - 1) * r && cur <= k) {
                cout << r << "\n";
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int f(int n){
	int ret = 1;
	while(ret <= n){
		ret <<= 1;
	}
	return ret;
}

int main(){
	static int n;
	static int a[200010];
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; i++){
		scanf("%d",&a[i]);
	}
	
	static multiset<int> S;
	for(int i = 1 ; i <= n ; i ++){
		S.insert(a[i]);
	}
	
	int ret = 0;
	multiset<int>::iterator itr = S.end();
	itr--;
	while(itr != S.begin()){
		int x = *itr;
		S.erase(itr--);
		int y = f(x)-x;
		multiset<int>::iterator itr_ = S.find(y);
		if(S.find(y) != S.end()){
			ret ++;
			if(itr == itr_){
				if(itr == S.begin())break;
				else itr--;
			}
			S.erase(itr_);
		}
	}
	cout << ret << endl;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n, k, q;cin >> n >> k >> q;
    vector<int> a(n), b;
    inc(i, 0, n){
        cin >> a[i];
        b.pb(a[i]);
    }
    a.pb(0);
    b.pb(0);
    sort(b.begin(), b.end());

    int ans = INT_MAX;

    inc(i, 0, n+1){
        vector<int> u, v;
        inc(j, 0, n+1){
            if(a[j] <= b[i]){
                int m = u.size();
                if(m < k){
                    u.clear();
                    continue;
                }
                sort(u.begin(), u.end());
                inc(l, 0, m-k+1){
                    v.pb(u[l]);
                }
                u.clear();
            }else{
                u.pb(a[j]);
            }
        }

        int m = v.size();
        sort(v.begin(), v.end());
        if(m < q) continue;
        ans = min(ans, v[q-1]-v[0]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let a = read_vec::<i64>();
    if n == 2 {
        println!("{}", max(a[0], a[1]));
        return;
    }
    let mut dp = vec![vec![-std::i64::MAX; 3]; n];
    dp[0][0] = a[0];
    dp[1][1] = a[1];
    dp[2][2] = a[2];
    for i in 2..n {
        for j in 0..3 {
            if dp[i - 2][j] != -std::i64::MAX {
                dp[i][j] = max(dp[i - 2][j] + a[i], dp[i][j]);
            }
            if j < 2 && i >= 3 && dp[i - 3][j] != -std::i64::MAX {
                dp[i][j + 1] = max(dp[i - 3][j] + a[i], dp[i][j + 1]);
            }
            if j < 1 && i >= 4 && dp[i - 4][j] != -std::i64::MAX {
                dp[i][j + 2] = max(dp[i - 4][j] + a[i], dp[i][j + 2]);
            }
        }
    }
    if n % 2 == 0 {
        println!("{}", max(dp[n - 1][1], dp[n - 2][1]));
    } else {
        println!("{}", max(max(dp[n - 1][2], dp[n - 2][1]), dp[n - 3][0]));
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;

#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
 
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////



int main(){fastio
    ll h,w,n;cin>>h>>w>>n;
    if(h>w)swap(h,w);
    ll ans=(n+w-1)/w;
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,maxn=0,hei=0;string a;
    cin>>n>>a;
    for(int i=0;i<n;i++){
        maxn=max(maxn,hei);
        if(a[i]=='I')hei++;
        else if(a[i]=='D')hei--;
    }maxn=max(hei,maxn);
    cout<<maxn<<endl;
    return 0;
}

Measured memory_bytes: 256
import numpy as np
k,n = map(int, input().split())
a = list(map(int, input().split()))
b = np.zeros(n)
for i in range(0,n-1):
  b[i] = a[i+1] -a[i]
  
b[n-1] = k - a[n-1] + a[0]
ans = k - max(b)
print(int(ans))

Measured memory_bytes: 42676
#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <cstdlib>
//#include <fstream>
#include <complex>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n;i>0;i--)
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define SORT(v) sort((v).begin(),(v).end())
const ll INF = (1LL << 40);
typedef pair<int, int> P;
const int MOD = 1000000007;

int main() {

	long double a, b, c;
	cin >> a >> b >> c;

	if (a+b + 2*(long double)sqrt((long double)a*b) < c) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;

}

Measured memory_bytes: 256
import math

def factorization(n):
    d = [1]
    i = 2
    while True:
        if i > int(math.sqrt(n)):
            break
        if n % i == 0:
            d.append(i)
            n //= i
        else:
            i += 1
    if n != 1:
        d.append(n)
    return d


def main():
    A, B = map(int, input().split())
    fa = set(factorization(A))
    fb = set(factorization(B))
    print(len(fa & fb))


if __name__ == '__main__':
    main()


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

typedef long long ll;
typedef unsigned long long ull;

int log2(int x){
    for(int i=0;i<=21;i++){
        if((1<<i)>x){
            return i-1;
        }
    }
}

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

    int lg2;
    for(int i=0;i<=21;i++){
        if((1<<i)>L){
            lg2=i;
            break;
        }
    }

    int N=lg2;
    int M=2*(N-1);
    string s="";
    for(int i=1;i<N;i++){
        s=s+to_string(i)+" "+to_string(i+1)+" "+to_string(1<<(N-i-1))+"\n";
        s=s+to_string(i)+" "+to_string(i+1)+" "+to_string(0)+"\n";
    }
    int ok=(1<<(N-1))-1;
    int next=1<<(N-1);

    while(ok+1<L){
        int rest=L-1-ok;
        s+="1 "+to_string(N-log2(rest))+" "+to_string(next)+"\n";
        M++;
        ok+=1<<(log2(rest));
        next=ok+1;
    }
    cout << N << " " << M <<endl;
    cout << s << endl;

    return 0;
}

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

int main() {
  int T; cin >> T;
  while (T--) {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    if (B <= C) {
      cout << ( (A >= B && B <= D) ? "Yes" : "No" ) << endl;
      continue;
    } else {
      ll g = __gcd(B, D);
      ll l = floor(1.0L * (C - A) / g) + 1;
      ll r = ceil(1.0L * (B - A) / g) - 1;
      // cout << g << ' ' << l << ' ' << r << endl;
      cout << ( (A >= B && B <= D && l > r) ? "Yes" : "No" ) << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
using namespace std;
#define fs first
#define sc second
typedef pair<int, int> pii; 
const int N = 1e5 + 10;
const int mo = 1e9 + 7;
int n, m, x, dp[N], fac[N * 2], fav[N * 2];
pii a[N];
int qpow(int a, int b) {
	int ans = 1;
	for(; b >= 1; b >>= 1, a = 1ll * a * a % mo)
		if(b & 1) ans = 1ll * ans * a % mo;
	return ans;
}
void init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; i ++) fac[i] = 1ll * fac[i - 1] * i % mo;
	fav[n] = qpow(fac[n], mo - 2);
	for(int i = n; i >= 1; i --) fav[i - 1] = 1ll * fav[i] * i % mo;
}
int C(int x, int y) {
	return x < y ? 0 : 1ll * fac[x] * fav[y] % mo * fav[x - y] % mo;
}
int main() {
	scanf("%d%d%d", &n, &m, &x); init(n + m + 1);
	for(int i = 1; i <= x; i ++) {
		(void) scanf("%d%d", &a[i].fs, &a[i].sc);
	}
	sort(a + 1, a + x + 1); a[++ x] = pii(n, m);
	if(a[x] == a[x - 1]) { puts("0"); return 0; }
	for(int i = 1; i <= x; i ++) {
		dp[i] = C(a[i].fs - 1 + a[i].sc - 1, a[i].fs - 1);
		for(int j = 1; j < i; j ++) {
			if(a[j].fs <= a[i].fs && a[j].sc <= a[i].sc) {
				(dp[i] += mo - 1ll * dp[j] * C(a[i].fs - a[j].fs + a[i].sc - a[j].sc, a[i].fs - a[j].fs) % mo) %= mo;
			}
		}
	}
	(void) printf("%d", dp[x]);
	return 0;
}


Measured memory_bytes: 1792
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
long n;
long S[500001];
long cnt;
void merge(long left, long mid, long right){
	long n1 = mid - left;
	long n2 = right - mid;
	long* L = new long[n1+1];
	long* R = new long[n2+1];
	for (long i = 0; i < n1; ++i) L[i] = S[left + i];
	for (long i = 0; i < n2; ++i) R[i] = S[mid + i];
	L[n1] = LONG_MAX;
	R[n2] = LONG_MAX;
	long i = 0, j = 0;
	for (long k = left; k < right; ++k){
		if (L[i] <= R[j]){
			S[k] = L[i]; ++i;
		}
		else{
			S[k] = R[j]; ++j;
		}
		++cnt;
	}
	delete[] L;
	delete[] R;
}
void mergeSort(long left, long right){
	if (left + 1 < right){
		long mid = (left + right) / 2;
		mergeSort(left, mid);
		mergeSort(mid, right);
		merge(left, mid, right);
	}
}

int main(){
	long n; scanf("%ld",&n);
	for (long i = 0; i < n; ++i) scanf("%ld",&S[i]);
	mergeSort(0,n);
	for (long i = 0; i < n; ++i){
		if (i != 0) cout << ' ';
		cout << S[i];
	}
	cout << '\n' << cnt << '\n';
}

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

int main() {
  string S;
  cin >> S;
  int Q;
  cin >> Q;
  int count = 0;
  string front = "";
  string back = "";

  for(int i = 0; i < Q; i++){
    
    int T;
    cin >> T;
    if(T == 1){
      count += 1;
    }else if(T == 2){
      int F;
      string C;
      cin >> F >> C;
      if(count % 2 == 0){
        if(F == 1){
          front.insert(0,C);
        }
        else if(F == 2){
          back.insert(back.size(),C);
        }
      }else{
        if(F == 1){
          back.insert(back.size(),C);
        }
        else if(F == 2){
          front.insert(0,C);
        }
      }
    }
  }
  S.insert(0,front);
  S.insert(S.size(),back);
  
  if(count % 2 == 0){
    cout << S << endl;
  }else{
    reverse(S.begin(), S.end());
    cout << S << endl;
  }
}

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

using namespace std;

long long n,a[10001],b,c,sum;

int main()
{
cin >> n;
for(int i = 0;i<n;i++)
{
    cin >>a[i];
    sum+=a[i];
}
if(sum%10==0)
{
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        if((sum-a[i])%10!=0)
        {sum-=a[i];
    break;}}
}
if(sum%10==0)
    cout<<0;
else
    cout<<sum;



}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin>>N;
	for(int a=1;a<=9;a++)
	for(int b=1;b<=9;b++)
	{
		if(a*b==N)
		{
		cout<<"Yes"<<endl;
		return 0;
		}
	}
	cout<<"No"<<endl;
	
	
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static final int MAX = 1001;
    static final long MOD = (long) 1e9 + 7;
    static boolean[] isPrime;
    static ArrayList<Integer> primes;
    static long[] cnt;

    static void sieve() {
	isPrime = new boolean[MAX];
	Arrays.fill(isPrime, true);
	isPrime[0] = isPrime[1] = false;
	primes = new ArrayList<>();
	for (int i = 2; i < MAX; i++)
	    if (isPrime[i]) {
		for (int j = i * i; j < MAX; j += i)
		    isPrime[j] = false;
		primes.add(i);
	    }
    }

    static void f(int N) {
	int idx = 0;
	int pf = primes.get(idx);
	while (pf * pf <= N) {
	    int power = 0;
	    while (N % pf == 0) {
		N /= pf;
		power++;
	    }
	    cnt[pf] += power;
	    pf = primes.get(++idx);
	}
	if (N != 1)
	    cnt[N]++;
    }

    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	sieve();
	cnt = new long[MAX];
	for (int i = 2; i <= n; i++)
	    f(i);
	long ans = 1;
	for (int i = 2; i <= n; i++)
	    if (cnt[i] != 0)
		ans = (ans * (cnt[i] + 1)) % MOD;
	System.out.println(ans);
    }

}


Measured memory_bytes: 10196
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define ARR(array) for(int i=0;i<array.size();i++)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 1000000007
#define SIZE 10005
#define PI 	3.14159265358979323846

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

ll input(){
  ll a;
  cin >> a;
  return a;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    bool a[100005]={false};
    ll b[100005]={0};
    REP(i,m)a[input()]=true;
    b[0]=1;
    REP(i,n){
      b[i]%=MOD;
      if(!a[i+1])b[i+1]+=b[i];
      if(!a[i+2])b[i+2]+=b[i];
    }
    cout << b[n]%MOD << endl;
}


Measured memory_bytes: 1152