akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text.RegularExpressions;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine(); //標準入力

            if (Regex.IsMatch(str, "a") && Regex.IsMatch(str, "b") && Regex.IsMatch(str, "c"))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 16320
#include <bits/stdc++.h>
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; 0 <= i; i--)
#define for_(i, start, end) for (int i = start; i < end; i++)
#define rfor(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD53       = 998'244'353;
constexpr double PI       = 3.14159265358979323846;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

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

    int N, K;
    scan(N, K);

    int ans  = INF32;
    auto fun = [&](auto f, int now, int cnt) {
        if (N == cnt) {
            chmin(ans, now);
            return;
        }
        f(f, now + K, cnt + 1);
        f(f, now * 2, cnt + 1);
    };
    fun(fun, 1, 0);
    print(ans);

    return 0;
}

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

int main() {
    int N;
    cin >> N;
    int k = 0;
    for(; k * k < 3 * N; ++k) {
        if(N == k * (k - 1) / 2) break;
    }
    if(N != k * (k - 1) / 2) {
        cout << "No" << endl;
        return 0;
    }

    set<int> res[k];
    int n = 1;
    for(int i=0; i<k-1; ++i) {
        for(int j=0; j<=i; ++j) {
            res[i].insert(n);
            res[j].insert(n);
            ++n;
        }
        res[k - 1].insert(n - 1);
    }

    cout << "Yes" << endl;
    cout << k << endl;
    for(int i=0; i<k; ++i) {
        cout << res[i].size();
        for(auto itr = begin(res[i]); itr != end(res[i]); ++itr) {
            cout << ' ' << *itr;
        }
        cout << endl;
    }
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
	if(n/100 == n%10)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	
	return 0;
} 

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

const int N = 2e5 + 5;
int a[N];

int main()
{
        int n, k;
        scanf("%d %d", &n, &k);

        for(int i = 0; i < n; i++) {
                int x;
                scanf("%d", &x);
                a[x]++;
        }
        vector< int > v;

        for(int i = 0; i < N; i++) {
                if(a[i]) v.push_back( a[i] );
        }
        sort( v.begin(), v.end() );
        reverse( v.begin(), v.end() );

        long long ans = 0LL;

        while( v.size() > k ) {
                ans += v.back();
                v.pop_back();
        }

        printf("%lld\n", ans);


        return 0;
}


Measured memory_bytes: 2168
#include <stdio.h>

char s[3], abc[5];
bool f= true;

int main(){
    scanf("%s", s);
    for(int i=0; i<3; i++){
        if(abc[s[i]-'a'] > 0)
            f = false;
        else
            abc[s[i]-'a'] += 1;
    }
    if(f)
        printf("Yes\n");
    else
        printf("No\n");
}


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

int main() {
int64_t N;
  cin >> N;
  int64_t c,c0;
  c0 = 1+N;
  for(int i = sqrt(N); i>= 1; i--){
  	if(N%i == 0){
      c = i + N/i;
      if(c0 > c){
        c0 = c;
      }
      break;
    }
  }
  cout << c0-2 << endl;
}

Measured memory_bytes: 256
number = input()

number_list = number.split(' ')

a = int(number_list[0])
b = int(number_list[1])

if 1 <= a <= 100 and 1 <= b <= 100:
    menseki = a * b
    nagasa = 2 * (a + b)

    print(str(menseki) + " " + str(nagasa))



Measured memory_bytes: 5592
s = gets.strip.split('')

result = 0

if s.length==1
  p s.first.to_i
  exit
end

(2**(s.length-1)).times do |index|

  current=s[0].to_i

  ("%0#{s.length-1}b" % index).split('').each_with_index do |chr, idx|
    if chr.to_i.zero?
      current = current*10 + s[idx+1].to_i
    else
      result += current
      current=s[idx+1].to_i
    end
  end
  result += current unless current.zero?

end

p result


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

// セグメント木
// ref:https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
template <typename Mnd>
struct segment_tree {
    int sz;
    vector<Mnd> data;
    function<Mnd(Mnd, Mnd)> f;
    Mnd e;
    //サイズだけ指定して初期化
    segment_tree(int _sz, function<Mnd(Mnd, Mnd)> _f, Mnd _e) : f(_f), e(_e) {
        sz = 1;
        while (sz < _sz) sz <<= 1;
        data.assign(sz * 2, e);
    }
    //参照渡しなので代入とかもできる
    Mnd& operator[](const int& k) {
        return data[k + sz];
    }
    //木を構築 O(n)
    void build() {
        for (int i = sz - 1; i > 0; i--) data[i] = f(data[2 * i], data[2 * i + 1]);
    }
    //更新しつつ木を再構築 O(log n)
    void update(int k, Mnd x) {
        data[k += sz] = x;
        while (k >>= 1) data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    //[a,b)でのクエリに答える　O(log n)
    Mnd query(int a, int b) const {
        Mnd l = e, r = e;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) l = f(l, data[a++]);
            if (b & 1) r = f(r, data[--b]);
        }
        return f(l, r);
    }
};

int main() {
    int n;
    cin >> n;
    segment_tree<lint> a(
        n, [](lint a, lint b) { return max(a, b); }, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    a.build();
    lint money = 1000;
    for (int i = 0; i < n - 1; i++) {
        if (i + 1 < n && a[i] == a[i + 1]) {
            continue;
        }
        if (a[i] < a[i + 1]) {
            lint nkab = money / a[i];
            money += nkab * (a[i + 1] - a[i]);
        }
    }
    cout << money << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

int main() {
	int s, w;
	cin >> s >> w;

	cout << (w >= s ? "unsafe" : "safe") << endl;
	return 0;
}


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

int64_t fact(int n)
{
    int64_t ret = 1;
    while (n > 1)
    {
        ret *= n;
        n--;
    }
    return ret;
}

double dist(pair<double, double> p1, pair<double, double> p2)
{
    double ret;
    ret = hypot(p2.first - p1.first, p2.second - p1.second);
    return ret;
}

int main()
{
    int n, count = 0;
    double sum = 0.0;
    cin >> n;
    vector<int> T(n);
    for (int i = 0; i < n; i++)
        T[i] = i + 1;

    vector<pair<double, double>> vec;
    for (int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        vec.push_back(make_pair(x, y));
    }

    do
    {
        count++;
        for (int i = 0; i < n - 1; i++)
        {
            sum += dist(vec[T[i] - 1], vec[T[i + 1] - 1]);
        }

    } while (next_permutation(T.begin(), T.end()));
    sum /= fact(n);
    cout << setprecision(10) << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n,x; cin >> n >> x;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin >> a[i];
    ll ans = 0;

    if(a[0] > x){
        ans += a[0] - x;
        a[0] = x;
    }

    for(ll i=0;i<n-1;i++){
        if(a[i]+a[i+1] > x){
            ll d = a[i] + a[i+1] - x;
            ans += d;
            a[i+1] -= d;
        }
    }

    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3996
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        
        // board[i][j]: チョコレートの模様
        char[][] board = new char[h][w];
        for (int i = 0; i < h; i++) {
            String str = sc.next();
            for (int j = 0; j < w; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        
        // bit: 横線の引き方のbit全探索
        // min: cutの最小値
        int min = (h-1)*(w-1);
        for (int bit = 0; bit < 1<<(h-1); bit++) {
            // bit -> group[i]: i行が属するグループ番号
            int[] group = new int[h];
            int g = 0;
            group[0] = g;
            for (int i = 0; i < h-1; i++) {
                // bitXが1なら次のグループにする
                if ((bit & (1<<i)) != 0) {
                    g++;
                }
                group[i+1] = g;
            }
            
            // board -> cut: 縦/横の切れ込みを入れた回数
            int cut = g;
            
            // count[i]: グループiの現在の'1'の個数
            // last: 最後に引いた縦線の位置
            // ok: 1列だけでk個を超すグループが存在しないならtrue
            int[] count = new int[g+1];
            int last = 0;
            boolean ok = true;
            
            // 縦方向に数えていく
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (board[j][i] == '1') {
                        count[group[j]]++;
                    }
                        
                    if (count[group[j]] > k) {
                        if (last != i) {
                            cut++;
                            Arrays.fill(count, 0);
                            last = i;
                            i--;
                            break;
                        } else {
                            ok = false;
                        }
                    }
                }
            }
            
            if (ok) {
                min = Math.min(min, cut);
            }
        }
        
        System.out.println(min);
    }
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

ll S;

void hoge(int x1,int y1,int x2,int y2,int x3,int y3) {
	_P("%d %d %d %d %d %d\n",x1,y1,x2,y2,x3,y3);
	
	x2-=x1;
	x3-=x1;
	y2-=y1;
	y3-=y1;
	
	ll a=1LL*x2*y3-1LL*y2*x3;
	assert(S==abs(a));
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	if(S<=1000000000LL) hoge(0,0,S,0,0,1);
	if(S%1000000000LL==0) hoge(0,0,1000000000,0,0,S/1000000000);
	ll Y=S/1000000000;
	ll X=S%1000000000;
	hoge(X,0,0,Y,1000000000,Y+1);
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long ksm(long long a, long long b) {
    if (b == 0) return 1;
    else if (b & 1) return a * ksm(a * a % mod, b >> 1) % mod;
    else return ksm(a * a % mod, b >> 1);
}
int main() {
    int n;
    cin >> n;
    cout << ((ksm(10, n) - 2 * ksm(9, n) + ksm(8, n)) % mod + mod) % mod << '\n';
    return 0;
}

Measured memory_bytes: 3624
use std::env;
use std::io::*;
use std::str::*;
use std::mem;
use std::collections::HashMap;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}
fn read_char() -> char {
    let c = read::<String>();
    let c = c.chars().collect::<Vec<char>>();
    c[0]
}
fn read_String_Vec() -> Vec<char> {
    let S = read::<String>();
    S.chars().collect::<Vec<char>>()
}

fn vecchar_to_String(Vs: &Vec<char>) -> String {
    let mut S = String::new();
    for i in 0..Vs.len() {
        S.push(Vs[i]);
    }
    S
}

/*
A : 65
Z : 90
a : 97
z : 122
*/

/*
let N = read::<i32>();
let S = read::<String>();
let S = read_String_Vec();
let C = read_char();
*/

/*
 .to_string() : * -> String
 &*S          : String -> &str
*/

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let mut s = read_String_Vec();
    let mut t = read_String_Vec();

    s.sort();
    t.sort();
    t.reverse();
    let s = vecchar_to_String(&s);
    let t = vecchar_to_String(&t);
    let mut Ss = vec![s.clone(), t.clone()];
    Ss.sort();
    let mut Sss = vec![s.clone(), t.clone()];
    if Ss == Sss && s != t {
        println!("Yes");
    } else {
        println!("No");
    }



}


Measured memory_bytes: 4476
#include <bits/stdc++.h>     // [PRIMES]               1777 ~2^10.80  
using namespace std;                     //                       10333 ~2^13.33
using ll=long long;                      // seq 1 128 | factor   100333 ~2^16.61
using vl=vector<ll>;                     //   | grep -v ' .* '  1300111 ~2^20.31
using vvl=vector<vl>;                    //                    10300777 ~2^23.30
using vb=vector<bool>;                   //                   100400999 ~2^26.58
using vs=vector<string>;                 //                  1300400999 ~2^30.28
using pll=pair<ll,ll>;                   //                 10200500333 ~2^33.25
const ll oo =0x3f3f3f3f3f3f3f3fLL;       //                100200400777 ~2^36.54
const double eps=1e-9;                   //               1200300700111 ~2^40.13
#define sz(c) ll((c).size())             //              10200300500777 ~2^43.21
#define all(c) begin(c),end(c)           //             100200300400777 ~2^46.51
#define mp make_pair                     //            1200300400600999 ~2^50.09
#define mt make_tuple                    //           10200300400600111 ~2^53.18
#define pb push_back                     //          100200300400600333 ~2^56.48
#define eb emplace_back                  //         1200300400500800999 ~2^60.06
#define xx first
#define yy second
#define FOR(i,a,b) for(ll i=(a); i<(b); i++)
#define FORD(i,a,b) for(ll i=ll(b)-1;i>=(a);i--)
#define TR(X) ({if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

ll modi = 1000000007;

int main() {
	ll n, m;
	cin >> n >> m;

	ll dp[n][m];

	FOR(i, 0, n) {
		FOR(j, 0, m) {
			if(i == 0 && j == 0) dp[i][j] = 1;
			else dp[i][j] = 0;			

			char next; cin >> next;
			if(next == '.') {
				if(i > 0) dp[i][j] += dp[i - 1][j];
				dp[i][j] %= modi;
				if(j > 0) dp[i][j] += dp[i][j - 1];
				dp[i][j] %= modi;
			}
		}
	}

	cout << dp[n - 1][m - 1] << endl;

	return 0;
}

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

int main(){
  int n;
  int m;
  cin >> n >> m;
  int a[n];
  int l=0;
  int total=0;
  while(cin >> a[l]){
    total = total + a[l];
      l++;
  }
  int j=4 * m;
  int MMM = total / j;
  if(total % j != 0)MMM++;
  int hhh=0;
  for(int i=n-1; i>=0; i--){
    if(a[i] >= MMM)hhh++;
  }
  if(hhh >= m){
    cout << "Yes" << endl;return 0;}
  
  if(hhh < m){cout << "No" << endl;return 0;}
}


Measured memory_bytes: 256
use std::io::prelude::*;

fn main() {
    let stdin_ = std::io::stdin();
    let stdout_ = std::io::stdout();
    let mut stdin = stdin_.lock();
    let mut stdout = stdout_.lock();

    let mut buffer = String::new();
    stdin.read_line(&mut buffer).unwrap();
    let b = buffer.trim().chars().map(|x| x as u8).collect::<Vec<_>>();
    let mut ans = b.len();

    for i in 0..2 {
        let mut cnt = 0;
        for j in 0..b.len() {
            if (j % 2 == 0 && b[j] != i + '0' as u8) || (j % 2 == 1 && b[j] == i + '0' as u8) {
                cnt += 1;
            }
        }
        ans = std::cmp::min(ans, cnt);
    }

    write!(stdout, "{}\n", ans).unwrap();
}


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

int main() {
  
  int N;
  cin >> N;
  
  int64_t a = 0;
  int64_t s = 0;
  int64_t s2 = 0;
  for (int i = 0; i < N; i++) {
    cin >> a;
    s = (s+a*s2)%1000000007;
    s2 = (s2+a)%1000000007;
  }

  cout << s << endl;    

return 0;
}      

Measured memory_bytes: 3632
N = int(input())
K = int(input())

l = len(str(N))
"""
print("N=",N)
print("K=",K)
print("l=",l,"桁")
"""
#l桁の数字

if K == 1:
    y = 9*(l-1)
    for i in range(1,10):
        p = i*10**(l-1)
        # print(p)
        if p <= N:
            y += 1
        else:
            break
    print(y)
    
elif K == 2:
    # print("mode 2")
    #l-1桁まででNより小さい数の個数
    y = 81*(l-1)*(l-2)//2
    # print(y)
    
    #l桁の数
    for i in range(1,int(str(N)[0])+1):
        for j in range(1,10):
            for k in range(l-1):
                # print(i,j,k)
                p = int(str(i)+"0"*k+str(j)+"0"*(l-2-k))
                if p <= N:
                    y += 1
                # print(p)
    print(y)

else:
    # print("mode 3")
    #l-1桁まででNより小さい数の個数
    y = 729*(l-1)*(l-2)*(l-3)//6
    # print(y)
    
    #l桁の数で頭の数がNのそれより小さい場合
    top = int(str(N)[0])
    y += (top-1)*81*(l-1)*(l-2)//2
    
    #l桁の数(頭の数字はNと一緒)
    for j in range(1,10):
        for k in range(1,10):
            for m in range(l-2):
                for n in range(l-2-m):
                    # print(m,n,l-3-m-n)
                    p = int(str(top)+"0"*m+str(j)+"0"*n+str(k)+"0"*(l-3-m-n))
                    if p <= N:
                        y += 1
                    # print("p:",p)
    print(y)

Measured memory_bytes: 3064
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    ss=[a for a in s]
    S.append(ss)
answers=[]
start=[]
for h,c_h in enumerate(S):
    for w,c_w in enumerate(c_h):
        if c_w=='.':
            start.append([h,w])
for a in start:
    S[a[0]][a[1]]='s'
    stack=[]
    stack.append(a)
    visited_area=[[0 for _ in range(W)] for _ in range(H)]
    def bfs(S,visited_area,stack):
        while len(stack)>0:
            h,w=stack.pop()
            for x,y in ([1,0],[-1,0],[0,1],[0,-1]):
                new_h=h+x
                new_w=w+y
                if new_h<0 or new_h>=H or new_w<0 or new_w>=W:
                    continue
                if S[new_h][new_w]=='.' and visited_area[new_h][new_w]==0:
                    visited_area[new_h][new_w]=visited_area[h][w]+1
                    stack.insert(0,[new_h,new_w])
        kotae=[]
        for z in range(H):
            saidai=max(visited_area[z])
            kotae.append(saidai)
        large=max(kotae)
        answers.append(large)
        S[a[0]][a[1]] = '.'
    bfs(S, visited_area, stack)
print(int(max(answers)))


Measured memory_bytes: 3188
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let (a, b): (Vec<usize>, Vec<usize>) = {
        let (mut a, mut b) = (vec![], vec![]);
        for _ in 0..(N - 1) {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            a.push(iter.next().unwrap().parse().unwrap());
            b.push(iter.next().unwrap().parse().unwrap());
        }
        (a, b)
    };

    let G = {
        let mut G = vec![std::collections::HashSet::new(); N + 1];
        for i in 0..(N - 1) {
            G[a[i]].insert((b[i], i));
            G[b[i]].insert((a[i], i));
        }
        G
    };

    let mut q = std::collections::VecDeque::new();
    q.push_back(1);
    let mut prev = vec![0; N + 1];
    let mut res = vec![0; N - 1];
    let mut K = 0;
    // prev[1] = 0;
    while !q.is_empty() {
        let i = q.pop_front().unwrap();
        // println!("i = {}", i);
        let mut z = 1;
        for &(j, k) in &G[i] {
            // println!("{} {}", j, k);
            // println!("i, p = {}, {}", i, prev[i]);
            if prev[j] == 0 && j != 1 {
                if z == prev[i] {
                    z += 1;
                }
                // println!("(i, j) = {} {}", i, j);
                // println!("z; {}", z);
                // println!("k; {}", k);
                res[k] = z;
                prev[j] = z;
                z += 1;
                q.push_back(j);
            }
        }
        // println!("{}", z);
        K = std::cmp::max(z - 1, K);
    }

    println!("{}", K);
    // println!("{:?}", res);
    println!(
        "{}",
        res.iter()
            .map(|&r| r.to_string())
            .collect::<Vec<_>>()
            .join("\n")
    );
}


Measured memory_bytes: 92540
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pqueg = priority_queue<int, vector<int>, greater<int>>;
using pquel = priority_queue<int, vector<int>, less<int>>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
int lcm(int a, int b){
  return a / __gcd(a, b) * b;
}
int r_int(int a, int b){
  return rand() % b + a;
}
const lint mod=1e9+7;

int main()
{
  lint a, b, c, k;
  cin >> a >> b >> c >> k;

  lint res = 0;
  if(k > a) res += a;
  else res += k;
  k -= a;
  k -= b;
  if(k > 0 && k > c) res -= c;
  else if(k > 0 && k <= c) res -= k;

  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
const int mod=1e9+7;

int64_t f(int64_t x){
  x++;
  long long ans=0;
  for(int i=0;i<50;i++){
    long long l=(1LL<<(i+1));//整数xのibit目に1が現れる周期は2のi乗
    long long cnt=(x/l)*(l/2);//1周期に1が現れる個数は周期の半分.その数までの周期全体の1を数える。
    cnt+=max(0LL,(x%l)-(l/2));//0インデックスの周期のパターンはすべて{0,0,0...,0,1,1,1,...,1}となるから。
    if(cnt%2==1){
      ans+=(1LL<<i);
    }
  }
  return ans;
}
int main(){
  int64_t A,B;
  cin>>A>>B;
  int64_t ans=f(B)^f(A-1);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3604
N = int(input())
listT = [int(_) for _ in input().split()]
M = int(input())
total_listT = sum(listT)

answer = []
for i in range(M):
    temp = [int(_) for _ in input().split()]
    answer.append(total_listT - listT[temp[0]-1] + temp[1])

for _ in answer:
    print(_)

Measured memory_bytes: 3064
N, T = map(int, input().split())
A = list(map(int, input().split()))
#全て同じではない

#buy = int(T / 2)
#一番安い町で買って、高い町で売る
now = 10 ** 10
max_sub = 0
count = 1
for i in range(N):
  bb = A[i] - now
  if bb > max_sub:
    max_sub = bb
    count = 1
  elif bb == max_sub:
    count += 1

  now = min(now, A[i])
  #print(bb, max_sub, now, count)
  
#print(max_sub, count)
print(count)    


Measured memory_bytes: 20448
use std::error::Error;
use std::io;

fn main() {
    if let Err(e) = run() {
        println!("{}", e);
    }
}

fn run() -> Result<(), Box<Error>> {
    let mut s = String::new();
    io::stdin().read_line(&mut s)?;
    let b = s.trim().as_bytes();
    let b1 = String::from_utf8(vec![b[0]]).unwrap();
    let b2 = String::from_utf8(vec![b[b.len()-1]]).unwrap();
    println!("{}{}{}", b1, b.len()-2, b2);
    Ok(())
}


Measured memory_bytes: 4352
N,H=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
 a,b=map(int,input().split())
 A[i]=a
 B[i]=b
A.sort(reverse=True)
B.sort(reverse=True)

cnt=0
for b in B:
 if A[0] < b:
  H-=b
  cnt+=1
 else:break
 if H<=0:break
print(cnt+((H//A[0])+(H%A[0]!=0)if H>0 else 0))


Measured memory_bytes: 11312
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#li=input().split()
#import fractions
#n=int(input())
#lis=list(map(int,input().split()))

S=input()
ant=S[:2]
post=S[2:]
flag=0
m=["01","02","03","04","05","06","07","08","09","10","11","12"]
ans="NA"
if ant in m:
    ans="MMYY"
    flag=1
if post in m:
    if flag==1:
        ans="AMBIGUOUS"
    else:
        ans="YYMM"



print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll>PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
struct Edge {
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w) {}
};
vector<vector<Edge>> g(1e5);
bool dfs ( int a, vector<int>& color, vector<vector<Edge>>& g, int cur = 0 ) {
    color[a] = cur;
    for ( auto tmp_g : g[a] ) {
        if ( color[tmp_g.to] != -1 ) {
            if ( tmp_g.weight % 2 == 0 ) {
                if ( color[tmp_g.to] != cur ) return false;
                continue;
            }
            else {
                if ( color[tmp_g.to] == cur ) return false;
                continue;
            }
        }
        int next_cur = ( tmp_g.weight % 2 == 0 ) ? cur : 1 - cur;
        if (!dfs(tmp_g.to, color, g, next_cur )) return false;
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    int sp = 0;
    rep(i, n - 1) {
        int tmp_u, tmp_v;
        ll tmp_w;
        cin >> tmp_u >> tmp_v >> tmp_w;
        --tmp_u, --tmp_v;
        if ( i == 0 ) sp = tmp_u;
        g[tmp_u].push_back(Edge(tmp_v, tmp_w));
        g[tmp_v].push_back(Edge(tmp_u, tmp_w));
    }
    vector<int> color(n, -1);
    for ( int v = 0; v < n; ++v ) {
        if ( color[v] != -1 ) continue;
        bool test = dfs(v, color, g);
    }
    rep(i, n) cout << color[i] << endl;
    return 0;
}


Measured memory_bytes: 10624
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define big bignum
#define lowbit(x) (x & -x)
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define R register
#define For(i, j, k) for(R int i = (j); i <= (int) (k); ++i)
#define Rep(i, j, k) for(R int i = (j); i >= (int) (k); --i)
#define Cross(i, j, k) for(R int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll INF = 5e16;

namespace IO {

	inline char gc() {
		static char buf[100000], *p1 = buf, *p2 = buf;
		return (p1 == p2) && (p2 = (p1 = buf) +
			fread(buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
	}

	#define dd ch = getchar()
	inline ll read() {
		R ll x = 0; R int f = 0; R char dd;
		for (; !isdigit(ch); dd) f ^= (ch == '-');
		for (; isdigit(ch); dd)  x = x * 10 + (ch ^ 48);
		return f? -x: x;
	}
	#undef dd

	inline void write ( ll x ) {
		if (x < 0) x = -x, putchar('-');
		if (x > 9) write(x / 10); putchar(x % 10 | 48);
	}

	inline void wrn ( ll x ) { write(x), putchar(' '); }

	inline void wln ( ll x ) { write(x), putchar('\n'); }

	inline void wlnn ( ll x, ll y ) { wrn(x), wln(y); }

}

using IO::wln;
using IO::read;

namespace Cesare {
	
	/*
		a[i] + a[j] - 1
		a[i] -> a[j]
	*/
	
	ll n, Ans, a[N], S[N];
	
	int main() {
		n = read();
		For ( i, 1, n ) ++S[a[i] = read()];
		sort(a + 1, a + n + 1);
		For ( i, 1, 2e3 ) S[i] += S[i - 1];
		For ( i, 1, n ) For ( j, i + 1, n ) 
			Ans += S[a[i] + a[j] - 1] - j; return wln(Ans), 0;
	}
	
}

int main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	return Cesare :: main();
}

/*

*/





Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n,a,b,k=0,l=0,m=0;
    cin>>n>>a>>b;
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        if(p<=a){
            k++;
        }else if(p<=b){
            l++;
        }else{
            m++;
        }
    }
    cout<<min(min(l,m),k)<<endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define clr(x, y) memset(x,y,sizeof(x));
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define rep(i, m, n) for(int i=m ; i<n ; i++)
#define forr(i, m, n) for(int i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define re return
const int N = 1e5 + 5;
int OO = 1e9 + 7;
using namespace std;

int n;
ll a[N], b[N], sum = 0;

int main() {
    IO;
    cin >> n;
    rep(i, 0, n + 1) cin >> b[i];
    rep(i, 0, n) cin >> a[i];

    rep(i, 0, n) {
        // i
        ll cur = min(a[i], b[i]);
        a[i] -= cur;
        b[i] -= cur;
        sum += cur;
        // i+1
        cur = min(a[i], b[i + 1]);
        a[i] -= cur;
        b[i + 1] -= cur;
        sum += cur;
    }

    cout << sum;


}

Measured memory_bytes: 1792
#!/usr/bin/python
# -*- coding:utf-8 -*-

n = int(input())
s = input()

right = []
left = []
bufl = 0
bufr = 0
for i in range(n):
    if 'W' == s[i]:
        bufl += 1
    left.append(bufl)
    if 'E' == s[(n-1)-i]:
        bufr += 1
    right.append(bufr)
right.reverse()

m = n
for i in range(n):
    if m > (right[i] + left[i]) - 1:
        m = (right[i] + left[i]) - 1
print(m)


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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);

int main() {
	cin.sync_with_stdio(false);
	int N;
	cin >> N;
	vector<ll>a(N), b(N),c(N),d(N);
	ll ans = 0;
	rep(i, N)cin >> a[i];
	rep(i, N)cin >> b[i];
	rep(i, 29) {
		ll x = 1 << i;
		rep(j, N) {
			c[j] = a[j] % (x << 1);
			d[j] = b[j] % (x << 1);
		}
		sort(d.begin(), d.end());
		ll cnt = 0;
		rep(j, N) {
			cnt += (lower_bound(d.begin(), d.end(), x * 2 - c[j]) - lower_bound(d.begin(), d.end(), x - c[j]));
			cnt += (lower_bound(d.begin(), d.end(), x * 4 - c[j]) - lower_bound(d.begin(), d.end(), 3*x - c[j]));
		}

		if (cnt % 2 == 1)ans += x;
	}
	cout << ans << endl;

	return 0;
}


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

int grade500m(double t1) {
  if(t1 < 35.50)
    return 0;
  if(t1 < 37.50)
    return 1;
  if(t1 < 40.00)
    return 2;
  if(t1 < 43.00)
    return 3;
  if(t1 < 50.00)
    return 4;
  if(t1 < 55.00)
    return 5;
  if(t1 < 70.00)
    return 6;

  return 7;
}

int grade1000m(double t2) {
  if(t2 < 71.00)
    return 0;
  if(t2 < 77.00)
    return 1;
  if(t2 < 83.00)
    return 2;
  if(t2 < 89.00)
    return 3;
  if(t2 < 105.00)
    return 4;
  if(t2 < 116.00)
    return 5;
  if(t2 < 148.00)
    return 6;

  return 7;
}

int main() {
  double t1,t2;
  while(cin >> t1 >> t2) {
    int rank1 = grade500m(t1);
    int rank2 = grade1000m(t2);
    int rank = max(rank1,rank2);
    if(rank == 0)
      cout << "AAA" << endl;
    if(rank == 1)
      cout << "AA" << endl;
    if(rank == 2)
      cout << "A" << endl;
    if(rank == 3)
      cout << "B" << endl;
    if(rank == 4)
      cout << "C" << endl;
    if(rank == 5)
      cout << "D" << endl;
    if(rank == 6)
      cout << "E" << endl;
    if(rank == 7)
      cout << "NA" << endl;
  }
}

Measured memory_bytes: 0
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces
if n >= m:
	print 0
else:
	xis = map(int, raw_input().split())
	xis.sort()


	distances = [v- u for u,v in zip(xis,xis[1:])]
	distances.sort(key = lambda x:-x)
	print sum(distances[n-1:] or [0])

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

const int MAXN = 100005;

struct node {
	int to, next, dis;
} edge[MAXN*6];
int head[MAXN], top = 0;
inline void push(int i, int j, int d)
{ edge[++top] = (node) {j, head[i], d}, head[i] = top; }

int dis[MAXN], vis[MAXN];
queue<int> que;

bool bfs(int S)
{
	que.push(S), vis[S] = 1, dis[S] = 0;
	while (!que.empty()) {
		int nd = que.front(); que.pop();
		for (int i = head[nd]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (vis[to]) {
				if (dis[to] != dis[nd]+edge[i].dis) return 0;
			} else dis[to] = dis[nd]+edge[i].dis, vis[to] = 1, que.push(to);
		}
	}
	return 1;
}

int n, m;

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v, d; scanf("%d%d%d", &u, &v, &d);
		push(u, v, d);
		push(v, u, -d);
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i]) {
			if (!bfs(i)) { puts("No"); return 0; }
		}
	puts("Yes");
	return 0;
}


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

int N, B[40];
vector<int> D[40];

int dfs(int n, int *flag_)
{
    int preproc = 0, res = 0;
    int flag[40];
    copy(flag_, flag_ + N, flag);
    
    flag[n] = 1;
    for(int i = 0; i < D[n].size(); ++i)
        flag[D[n][i]] = -1;
    
    for(int i = n + 1; i < N; ++i)
    {
    	if(flag[i] != 0) continue;
        bool f = true;
        for(int j = 0; j < D[i].size(); ++j)
            if(flag[D[i][j]] != -1) {
                f = false; break;
            }
        if(f)
            flag[i] = 1, preproc += B[i];
    }
    
    for(int i = n + 1; i < N; ++i)
    {
        if(flag[i] != 0) continue;
        res = max(res, B[i] + dfs(i, flag));
        flag[i] = -1;
    }
    
    return preproc + res;
}

int main()
{
    int C;
    string A, Dt;
    
    while(cin >> N && N)
    {
        map<string, int> table;
        vector<string> Ds[40];
        for(int i = 0; i < 40; ++i) D[i].clear();
        
        for(int i = 0; i < N; ++i)
        {
            cin >> A >> B[i] >> C;
            for(int j = 0; j < C; ++j)
                cin >> Dt, Ds[i].push_back(Dt);
            table[A] = i;
        }
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < Ds[i].size(); ++j)
                D[i].push_back(table[Ds[i][j]]);
        
        int flag[40] = {};
        int res = B[0] + dfs(0, flag);
        cout << res << endl;
    }
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
 
#define REP( i, n) for( int i = 0; i < (n); ++i)
#define FOR( i, a, b) for( int i = (a); i < (b); ++i)
 
#define pb push_back
 
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
 
using ll = long long;
 
using namespace std;
 
int main(){
 
  int n;
  set<int> st;
  int tmp;
 
  cin >> n;
  REP( i, n){
    cin >> tmp;
    auto itr = st.find(tmp);
    if( itr == st.end() ){
      st.insert(tmp);
    }else{
      st.erase(itr);
    }
  }
  cout << st.size() << endl;
}
 
 

Measured memory_bytes: 4864
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
int gcd(int one, int two) {
	while (one != 0 && two != 0) {
		if (one > two) {
			one = one % two;

		}
		else {
			two = two % one;
		}

	}

	return std::max(one, two);

}
int main()
{
	using namespace std;
	int a = 0, b = 0, c = 1, d = 0, e = 0, min = 0, ma = 0, ans = 0, count = 0, nagax = 0, nagay = 0, size = 0;
	int sa[10000] = {};

	std::string str[150], strs;

	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> sa[i];
	}
	sa[a] = 1000000007;
	std::sort(sa, sa + a);
	int i = 0;
	while (1) {

		count += sa[i];
		if (count > b) {
			cout << i << endl;
			return 0;
		}
		if (count == b) {
			cout << i + 1 << endl;
			return 0;
		}
		if (i == (a - 1)) {
			cout << i << endl;
			return 0;
		}
		i++;
	}

}






Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int ans = a * b / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3572
x=int(input())
m=list()
n=list()
for i in range(200):
    m.append(i**5)
    n.append(-i**5)
    if (x+(i**5)) in m:
        a=m.index(x+(i**5))
        b=i
        break
    if (x-i**5) in m:
        a=m.index(x-(i**5))
        b=-i
        break
    if (x-(i**5)) in n:
        a=i
        b=n.index(x-i**5)
        break    
print(a," ",b)

Measured memory_bytes: 9168
def main():

    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse = True)
    totA = sum(A)
    count = 1
    for i in range(N):
        totA -= A[i]
        if 2 * totA >= A[i]:
            count += 1
        else:
            break
    return count

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 14320
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define pii pair<int, int>
#define vpli vector<pair<long long, int>>
#define deb(x) cout << "deb " << #x << " " << x << endl;
#define all(x) x.begin(), x.end()
#define endl "\n"
const ll BIG = 1e18;

void swap(ll &a, ll &b)
{
    ll t = a;
    a = b;
    b = t;
}

ll Min(ll a, ll b, ll c)
{
    return min(a, min(b, c));
}

void printvec(vi &vec)
{
    for (int x : vec)
    {
        cout << x << " ";
    }
    cout << endl;
}

int sum(int a)
{
    int ans = 0;
    while (a)
    {
        ans += (a % 10);
        a = a / 10;
    }
    return ans;
}
void print(vi &mp)
{
    for (auto x : mp)
    {
        cout << x;
    }
    cout << endl;
}
void solve()    
{
    ll a;
    string s;
    int b=0;
    cin>>a>>s;
    int mul = 1;
    for(int i=s.size()-1;i>=0;i--)
    {
        if(s[i] == '.') continue;
        b = b + (s[i]-'0')*mul;
        mul *= 10;
    }
    cout<<((a*b)/100);

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 3640
N,L=map(int,input().split())
d=list(range(1,N+1))
s=[]
a=1000
b=0

for i in range(N):
  s.append(L+i)
for j in range(N):
  if a > abs(s[j]):
    a=abs(s[j])
    b=s[j]
print(sum(s)-b)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define FOR(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define FORUL(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define FORULE(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#if defined(_MSC_VER) || __cplusplus > 199711L
#define AUTOVAR(newvar,v) auto newvar = (v)
#else
#define AUTOVAR(newvar,v) __typeof(newvar) r = (v)
#endif
#define PB(x) push_back(x)
#define MP(x,y) make_pair((x),(y))
#define MEMSET(m,v) memset(m,v,sizeof(m))

typedef long long				 ll;
typedef unsigned long long		ull;

#define DEBUG 0

#if DEBUG
#define DOUT cout<<"["<<__LINE__<<"]:"
#else
#define DOUT 0 && cout
#endif

using namespace std;

int N;
int K;
string S;

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);

	cin >> N >> K;
	cin >> S;
	
	// Lはじまり
	// LRLRRL : 000100
	// LLRLRL : 010000, LRLLLL:000111, LLLRLL : 011010
	// LRRLRL : 001000
	// L にする方針
	int lr=0;
	int rr=0;
	int ll=0;
	int rl=0;
	FOR(n,N) {
		if(n==0) {
			continue;
		}
		if(S[n-1]=='L') {
			if(S[n]=='L') {
				ll++;
			}
			else {
				lr++;
			}
		}
		else {
			if(S[n]=='R') {
				rr++;
			}
			else {
				rl++;
			}
		}
	}
	DOUT << "ll="<<ll<<endl;
	DOUT << "rr="<<rr<<endl;
	DOUT << "lr="<<lr<<endl;
	DOUT << "rl="<<rl<<endl;
	int rot = min(K,min(lr,rl));
	DOUT << "rot="<<rot<<endl;
	int plus = 2*rot;
	int happy = ll+rr+plus;
	if(K-min(lr,rl)>0) {
		if(happy<N-1) {
			happy++;
		}
	}
	cout << happy << endl;

	return 0;
}




Measured memory_bytes: 512
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

VI e[2000];

int dfs(int now, int past, int k){
    int res = 1;
    if (k == 0) return res;
    REP(i,e[now].size()){
        int next = e[now][i];
        if (next == past) continue;
        res += dfs(next, now, k-1);
    }
    return res;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<P> p(n-1);
    REP(i,n-1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        e[a].push_back(b);
        e[b].push_back(a);
        p[i] = make_pair(a, b);
    }

    int ans = 0;

    if (k % 2 == 0){
        REP(i,n){
            ans = max(ans, dfs(i,-1,k/2));
        }
    }else{
        int l = (k-1)/2;
        REP(i,n-1){
            int a = p[i].first, b = p[i].second;
            ans = max(ans, dfs(a,b,l)+dfs(b,a,l));
        }
    }

    cout << n-ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1<<30
#define il inline
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void readl(ll &x) {
	x=0;
	ll f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=-f;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
}
il void read(int &x) {
	x=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=-f;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 100005
int n;
ll X;
ll x[N];
int main() {
	int i;
	ll ans;
	read(n);
	readl(X);
	for(i=1; i<=n; i++) readl(x[i]);
	sort(x+1,x+n+1);
	if(n==1) {
		printf("%lld",abs(x[1]-X));
		return 0;
	}
	if(X>=x[n]) {
		ans=X-x[n];
		for(int j=n-1; j>=1; j--) {
			ans=__gcd(ans,x[j+1]-x[j]);
		}
		printf("%lld",ans);
	} else {
		if(X<=x[1]) {
			ans=x[1]-X;
			for(int j=2; j<=n; j++) ans=__gcd(ans,x[j]-x[j-1]);
			printf("%lld",ans);
		} else {
			for(i=1; i<=n; i++) if(x[i]<=X&&x[i+1]>=X) break;
			ans=X-x[i];
			ans=__gcd(ans,x[i+1]-X);
			for(int j=i-1; j>=1; j--) ans=__gcd(ans,x[j+1]-x[j]);
			for(int j=i+1; j<=n; j++) ans=__gcd(ans,x[j]-x[j-1]);
			printf("%lld",ans);
		}
	}
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int main(void){
    int n;
    cin>>n;
    vector<pair<ll, int> > v(n);
    rep(i, n) {
        int a;
        cin>>a;
        v[i]=make_pair(a, i);
    }

    sort(v.begin(), v.end());
    vector<pair<ll, int> > s(n);
    rep(i, n){
        s[v[i].second]=make_pair(v[i].first, i);
    }
    /*rep(i, n) cout<<v[i].first<<" "<<v[i].second<<endl;
    rep(i, n) cout<<s[i].first<<" "<<s[i].second<<endl;*/
    rep(i, n){
        if(s[i].second<n/2){
            cout<<v[n/2].first<<endl;
        }
        else cout<<v[n/2-1].first<<endl;
    }
    return 0;

}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
const int INF = 1e9;
const long long LINF = 1e18;
const double EPS = 1e-8;
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
vector<ll> s;
int main(){
	int N;
	cin >> N;
	rep(i,N){
		ll a;
		cin >> a;
		s.pb(a);
	}
	ll cnt = 0;
	rep(i,N){
		cnt += s[i]/2;
		s[i] %= 2;
		if(i < N-1 && s[i] == 1 && s[i+1] > 0){
			cnt++;
			s[i+1]--;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long a,b,c;
    cin>>a>>b>>c;
    a=abs(a);
    long long t=a/c;
    if(a>0&&t>=b){
        cout<<abs(a-b*c);
        return 0;
    }
    a-=t*c;
    b-=t;
    if(b%2==0){
        cout<<abs(a);
    }
    else  {
        cout<<min((abs(a+c)),abs(a-c));
    }
    return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int a, b, c;
    cin >> a >> b >> c;
    if(b - a == c - b) cout << "YES";
    else cout << "NO";
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(1,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(1,len(T)):
    dicT[func(i,l,M)] = i+1

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if S[0] != T[0]: flag = False
if flag: print(l)
else: print(-1)

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

using namespace std;

int main(void){
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    int count = 0;
    transform(s.begin()+k-1, s.begin()+k, s.begin()+k-1, ::tolower);
    cout << s<< endl;
    
}

Measured memory_bytes: 256