akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main(){
	int a, b, c,t;
	cin >> a >> b >> c;
	if (a > b) {
		t = a;
		a = b;
		b = t;
	}
	if (a > c) {
		t = a;
		a = c;
		c = t;
	}
	if (b > c) {
		t = b;
		b = c;
		c = t;
	}

	cout << a << " " << b << " " << c << endl;
    return 0;
}




Measured memory_bytes: 3068
def main():
    s = input()
    q = int(input())

    reverse = 0
    head = ""
    tail = ""

    for i in range(q):
        v = list(input().split())
        if int(v[0]) == 1:
            reverse += 1
        elif reverse % 2 == 0:
            if int(v[1]) == 1:
                head += v[2]
            else:
                tail += v[2]
        elif reverse % 2 == 1:
            if int(v[1]) == 1:
                tail += v[2]
            else:
                head += v[2]

    s = head[::-1] + s + tail
    if reverse % 2 == 1:
        s = s[::-1]

    print(s)


if __name__ == "__main__":
    main()


Measured memory_bytes: 222300
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(ll x, ll n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}

ll cube(ll x){
  return x*x*x;
}


/*
n k

n k 2*10^5
 */
ll n,k;

int main(){
  cin>>n>>k;
  if(k%2==0){
    cout<< cube(n/k) + cube((2*n+k)/(2*k)) <<endl;
  } else {
    cout<< cube(n/k) <<endl;    
  }

  return 0;
}


Measured memory_bytes: 256
def main():
    N, x = map(int, input().split())
    a_list = list(map(int, input().split()))

    a_list_sort = sorted(a_list)
    cum_sum = [sum(a_list_sort[:i+1]) for i in range(N)]
    # print(cum_sum)

    if cum_sum[0] > x:
        print(0)
        return

    for i in range(N):
        # print(cum_sum[i], x)
        if cum_sum[i] == x:
            print(i+1)
            return
        elif cum_sum[i] > x:
            print(i)
            return

    print(N - 1)

main()

Measured memory_bytes: 3064
#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dp (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
        (cons (subseq str 0 pos)
              (split x (subseq str (+ pos size))))
        (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defmacro aif (expr then else)
  `(let ((it ,expr))
     (if it ,then ,else)))

(defmacro awhen (expr &rest then)
  `(aif ,expr (progn ,@then) nil))

(defun comulative (function list &key base)
  (if base
      (comulative function (cons base list))
      (do ((lst (cdr list) (cdr lst))
           (acc (list (car list))))
          ((null lst) (reverse acc))
        (push (funcall function (car acc) (car lst)) acc))))

(defun binary-search (function left right
                      &optional
                        (eps 1)
                        (average-function (lambda (x y) (ash (+ x y) -1))))
  (if (<= (abs (- left right)) eps)
      right
      (let ((mid (funcall average-function left right)))
        (if (funcall function mid)
            (binary-search function left mid eps average-function)
            (binary-search function mid right eps average-function)))))

(defun arithmetic-mean (&rest body)
  (/ (apply #'+ body) (length body)))

(defvar +MOD+ (+ (expt 10 9) 7))

(defun main (n sum kids)
  (let ((sums (coerce (comulative #'+ (sort (copy-list kids) #'<)) 'vector)))
    (- (binary-search (lambda (x) (> (aref sums x) sum)) -1 n)
       (if (< (apply #'+ kids) sum) 1 0))))

(let ((n (read))
      (x (read)))
  (princ (main n x (read-times n))))


Measured memory_bytes: 11324
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

ll a[100001];
int main()
{
    ll n,m,s=0;
    cin>>n>>m;
    priority_queue<ll> p;

    forn(i,n){
    cin>>a[i];
    p.push(a[i]);
    }

    while(m){
        ll mi=p.top();
        p.pop();
        mi=mi/2;
        p.push(mi);
        m--;
    }
    
    while(!p.empty()){
        s+=p.top();
        p.pop();
    }
    cout<<s;
}

Measured memory_bytes: 1912
#include <string>
#include <map>
using namespace std;

int main(){
  string s,t;
  map<string,int>m;
  for(;cin>>s;)m[s]++;
  s=t=(*m.begin()).first;
  int M=(*m.begin()).second,l=s.length();
  for(map<string,int>::iterator it=m.begin();it!=m.end();it++){
    if(M<(*it).second)M=(*it).second,s=(*it).first;
    if(l<(*it).first.length())l=(*it).first.length(),t=(*it).first;
  }
  cout<<s<<' '<<t<<endl;
}

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

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll numbers = b - a + 1;
    ll div_c = (numbers / c) + ((b % c == 0) && (a % c == 0));
    ll div_d = (numbers / d) + ((b % d == 0) && (a % d == 0));

    ll num_c = b/c - (a-1) / c;
    ll num_d = b/d - (a-1) / d;
    c = c * d / (__gcd(c, d));

    ll num_cd = b/c - (a-1)/c;
    cout << numbers - (num_c + num_d - num_cd) << endl;
}

Measured memory_bytes: 3636
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint mo=1000000007;
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
lint zyo[2001001],rz[2001001];
lint cal(int a,int b){
	return (zyo[a+b]*rz[a])%mo*rz[b];
}
int main()
{
	zyo[0]=1;rep(i,2000100) zyo[i+1]=(zyo[i]*(i+1))%mo;
	rep(i,2000100) rz[i]=invMod(zyo[i],mo);
	int r1,r2,c1,c2;cin>>r1>>c1>>r2>>c2;
	lint now=cal(r1,c1),out=now;
	//cout<<now<<endl;
	REP(i,r1+c1,r2+c2){
		now*=2;
		if(i+1-r1<=c2) now+=cal(r1-1,i-r1+1);
		if(i+1-c1<=r2) now+=cal(c1-1,i-c1+1);
		if(i+1-c2>r1) now-=cal(c2,i-c2);
		if(i+1-r2>c1) now-=cal(r2,i-r2);
		now%=mo;out+=now;out%=mo;
		//cout<<now<<endl;
	}
	out%=mo;out+=mo;out%=mo;
	cout<<out<<endl;
}


Measured memory_bytes: 31488
h, w = gets.chomp.split.map(&:to_i)

field = []

h.times do
  field << gets.chomp.chars
end

w.times do |x0|
  h.times do |y0|
    next if field[y0][x0] == '#'
    count = 0
    (-1..1).each do |x1|
      (-1..1).each do |y1|
        next if x1 == 0 && y1 == 0
        next unless 0 <= (x0 + x1) && (x0 + x1) < w
        next unless 0 <= (y0 + y1) && (y0 + y1) < h
        count += 1 if field[y0 + y1][x0 + x1] == '#'
      end
    end
    field[y0][x0] = count.to_s
  end
end

field.each do |l|
  puts l.join
end


Measured memory_bytes: 2172
#include<bits/stdc++.h>
#include <unordered_map>
#define int long long int
#define double long double
#define endl "\n"
#define PI 3.141592653589793238462643383279502884
#define sum_up(x)  (x*(x+1))/2
#define sp(x)   setprecision(x)
#define ceil(a,b)   (a+(b-1))/b

using namespace std;

void base()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
/*
bool prime[100001];
void sieve(int n)
{
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}
int power(int x, int y)
{
    int res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = res * x;
        y = y >> 1;
        x = x * x;
    }
    return res;
}

double float_sq(double n)
{
    double x = n;
    double y = 1;
    double e = 0.000001;
    while (x - y > e)
    {
        x = (x + y) / 2;
        y = n / x;
    }
    return x;
}

int int_sq(int x)
{
    if (x == 0 || x == 1)
        return x;
    int start = 1, end = x, ans;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (mid*mid == x)
            return mid;
        if (mid*mid < x)
        {
            start = mid + 1;
            ans = mid;
        }
        else
            end = mid-1;
    }
    return ans;
}*/
map<int,bool>DP;
int cnt=0;
void ans(int n){
if(n == 1){
        return;
    }
    for(int i = 2 ; i * i <= n ; i ++){
        if(n % i == 0){
            if(!DP[i]){
                cnt ++;
            }
            DP[i] = 1;
            ans(n / i);
            return;
        }
    }
    if(!DP[n]){
        cnt ++;
    }
}
int32_t main()
{
    base();
    int a, b;
    cin>>a>>b;
    ans(__gcd(a,b));
    cout<<cnt+1;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

		int L = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		
		int cnt = 0;
		
		while(true) {
			if(A <= 0 && B <= 0) {
				break;
			} else {
				A-=C;
				B-=D;
				cnt++;
			}
		}
		
		System.out.println(L - cnt);
	}
}

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

int main(void){
    char s[15],t[5]="YAKI";
    scanf("%s",s);
    if (strncmp(s,t,4)==0){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
	return 0 ;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            int n = Integer.parseInt(br.readLine());
            int a = Integer.parseInt(br.readLine());
            System.out.println(n * n - a);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 22356
#include<bits/stdc++.h>
#define int long long
#define rep1(i,a,b) for(int i=a;i<b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define mod 1000000007
#define garou99 ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
signed main() {
 int n;
 cin>>n;
 vector<int> v(n,0);
 for(int i=0;i<n;i++)
 cin>>v[i];
 int ct=0,x=0;
 rep1(i,0,n){
x=(x%mod+v[i]%mod);
 }
 rep1(i,0,n){
	 ct=(ct%mod+((x%mod-v[i]+mod)%mod)*(v[i]%mod));
	 x=(x%mod-v[i]%mod+mod)%mod;
 }
 cout<<ct;
	}

Measured memory_bytes: 4840
#include<bits/stdc++.h>
#include<vector>
#define ll long long
#define mem(x) memset(x,0,sizeof(x)) 
#define sca(x) scanf("%d",&x)
#define scaa(x,y) scanf("%d%d",&x,&y)
#define inf 0x7f7f7f7f
#define io ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC optimize(2)
using namespace std;
const double pi=acos(-1); 
const double eps=1e-6;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
const ll mod=1e9+7;
#define maxn 300005
char s[500005];
int main()
{
	cin>>(s+200000);
	int l=200000;
	int r=l+strlen(s+200000)-1;
	int tt;
	sca(tt);
	int ss=0;
	while(tt--)
	{
		int t;
		sca(t);
		if(t==1)
		{
			ss=ss^1;
		}
		else
		{
			int f;
			sca(f);
			char c;
			cin>>c;
			if(f==1)
			{
				if(ss==0)
				{
					s[l-1]=c;
					l--;
				}
				else
				{
					s[r+1]=c;
					r++;
				}
			}
			else
			{
				if(ss==0)
				{
					s[r+1]=c;
					r++;
				}
				else
				{
					s[l-1]=c;
					l--;
				}
			}
		}
	}
	if(ss==0)
	{
		for(int i=l;i<=r;i++)
		printf("%c",s[i]);
	}
	else
	{
		for(int i=r;i>=l;i--)
		printf("%c",s[i]);
	}
}

Measured memory_bytes: 768
if __name__ == "__main__":
    S = input()
    list_s = [s for s in S]
    ans = 0
    if list_s[0] == 'S' and list_s[1] == 'S' and list_s[2] == 'S':
        ans = 0
    elif list_s[0] == 'S' and list_s[1] == 'S' and list_s[2] == 'R':
        ans = 1
    elif list_s[0] == 'S' and list_s[1] == 'R' and list_s[2] == 'R':
        ans = 2
    elif list_s[0] == 'R' and list_s[1] == 'R' and list_s[2] == 'R':
        ans = 3
    elif list_s[0] == 'R' and list_s[1] == 'S' and list_s[2] == 'R':
        ans = 1
    elif list_s[0] == 'R' and list_s[1] == 'R' and list_s[2] == 'S':
        ans = 2
    elif list_s[0] == 'R' and list_s[1] == 'S' and list_s[2] == 'S':
        ans = 1
    elif list_s[0] == 'S' and list_s[1] == 'R' and list_s[2] == 'S':
        ans = 1

    print(ans)






Measured memory_bytes: 9136
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
S = LIST()

for i in range(3):
	print(S[i][0].upper(), end="")

print()


Measured memory_bytes: 13784
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>
#include <set>
#include <numeric>

using namespace std;

template <typename T>
using TABLE = vector<vector<T>>;

using LONG = long long;
using LVEC = vector<long long>;

#define FOR(i, s, e) for(i = s; i < e; ++i)
#define FOR_INV(i, s, e) for(i = e - 1; i >= s; --i)

long long PRIME = 1e9 + 7;
long long PRIME2 = 998244353;


using pos = std::pair<LONG, LONG>;


int main(){    
    LONG N;
    cin >> N;

    vector<pos> red_x(N);
    vector<int> red_y(N);

    vector<pos> blue_x(N);
    vector<int> blue_y(N);

    vector<LONG> index_check(2 * N, 0);

    LONG i, x;

    FOR(i, 0, N){
        cin >> x >> red_y[i];
        index_check[x] = i;
    }
    FOR(i, 0, N){
        cin >> x >> blue_y[i];
        index_check[x] = N + i;
    }

    set<int, greater<int>> q;
    LONG count = 0;

    for(int i = 0; i < 2 * N; ++i){
        if(index_check[i] < N){
            // red
            int y = red_y[index_check[i]];
            q.insert(y);
        }
        else{
            // blue
            int y = blue_y[index_check[i] - N];
            auto it = q.lower_bound(y);
            if(it != q.end()){
                ++count;
                q.erase(*it);
            }
        }
    }

    cout << count;

}


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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {

    long long int n;
    cin >> n;

    long long int ans = 0;
    for ( long long int i = 1; i <= n; i++ ) {
        if ( ( i % 3 ) == 0 ) continue;
        if ( ( i % 5 ) == 0 ) continue;
        ans += i;
    }

    cout << ans << endl;

    return 0;

}


Measured memory_bytes: 3624
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>
#include <cstdint>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef unsigned long long		SQWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	int N;
	cin >> N;
	vector<P> vo(100001, {0, 0}), ve(100001, {0, 0});
	REP(i, N) {
		int v;
		cin >> v;
		if (IsEven(i)) {
			ve[v].first++;
			ve[v].second = v;
		} else {
			vo[v].first++;
			vo[v].second = v;
		}
	}
	sort(ve.rbegin(), ve.rend());
	sort(vo.rbegin(), vo.rend());

	ll ans = (ll)INF;
	REP(i, 2) {
		REP(j, 2) {
			if (ve[i].second != vo[j].second) {
				ll ansOne = N - ve[i].first - vo[j].first;
				ans = min(ans, (ll)ansOne);
			}
		}
	}


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


Measured memory_bytes: 3328
N,M = map(int, input().split())
p = []
S = []
acnum = [-1]*N
for i in range(M):
    tmp1,tmp2 = input().split()
    p.append(int(tmp1))
    S.append(tmp2)
account = 0
wacount = [0]*N
waans = 0
for i in range(M):
    if acnum[p[i] - 1] == -1:
        if S[i] == "AC":
            acnum[p[i] - 1] = 1
            account += 1
            waans += wacount[p[i] - 1]
        else:
            wacount[p[i] - 1] += 1
print(account,waans)

Measured memory_bytes: 14920
NN = 19
BIT = [0] * (2 ** NN + 1)
def addbit(i, x=1):
    while i <= 2**NN:
        BIT[i] += x
        i += i & (-i)
def getsum(i):
    ret = 0
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret

N, Q = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    X[r-1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addbit(1, N)
for r in range(N):
    c = C[r]
    addbit(last[c] + 2, -1)
    addbit(r + 2)
    last[c] = r
    for l, i in X[r]:
        ANS[i] = getsum(1 << NN) - getsum(l + 1)
print(*ANS, sep = "\n")

Measured memory_bytes: 177336
def Z_algorithm(S):
    l=len(S)
    A=[0]*l
    A[0]=l
    i=1; j=0
    while i<l:
        while i+j<l and S[j]==S[i+j]:
            j+=1
        if not j:
            i+=1
            continue
        A[i]=j
        k=1
        while l-i>k<j-A[k]:
            A[i+k]=A[k]
            k+=1
        i+=k; j-=k
    return A

def Z_find(txt,pattern):
    lp=len(pattern)
    jointxt=pattern+'-'+txt
    Z=Z_algorithm(jointxt)
    return [Z[i]==lp for i in range(lp+1,len(jointxt))]

def solve(s,t):
    ls=len(s); lt=len(t)
    Judge=Z_find(s*2,t)
    ret=0
    Visited=[-1]*ls
    for i in range(ls) :
        if Judge[i] and Visited[i]==-1:
            idx=i
            cnt=0
            while Judge[idx]:
                if Visited[idx]!=-1:
                    cnt+=Visited[idx]
                    break
                cnt+=1
                Visited[idx]=1
                idx=(idx+lt)%ls
                if idx==i:
                    return -1
            Visited[i]=cnt
            ret=max(ret,cnt)
    return ret

s=input(); t=input()
s*=(len(t)+len(s)-1)//len(s)
print(solve(s,t))

Measured memory_bytes: 145104
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; }
template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) {
	inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; }
	return s;
}

template<typename T> T MV(T v) { return v; }
template<typename T, typename ... U> auto MV(T v, int a, U ... b) { return vector<decltype(MV(v, b ...))>(a, MV(v, b ...)); }

auto fl = [](auto a, auto b) { assert(b != 0); return a / b - (a % b != 0 && ((a >= 0) != (b >= 0)) ? 1 : 0); };
auto ce = [](auto a, auto b) { assert(b != 0); return a / b + (a % b != 0 && ((a >= 0) == (b >= 0)) ? 1 : 0); };
auto mo = [](auto a, auto b) { assert(b != 0); a %= b; if(a < 0) { a += abs(b); } return a; };

int main() {
	IN(int, h, w);
	vector<string> s(h);
	cin >> s;
	
	int INF = 1e5;
	auto dp = MV(INF, h, w);
	inc(i, h) {
	inc(j, w) {
		int x = (s[i][j] == '.' ? 0 : 1);
		if(i == 0 && j == 0) {
			dp[i][j] = x;
		} else {
			if(i > 0) { int y = (s[i - 1][j] == '.' ? 0 : 1); setmin(dp[i][j], dp[i - 1][j] + (y == 0 && x == 1 ? 1 : 0)); }
			if(j > 0) { int y = (s[i][j - 1] == '.' ? 0 : 1); setmin(dp[i][j], dp[i][j - 1] + (y == 0 && x == 1 ? 1 : 0)); }
		}
	}
	}
	OUT(dp[h - 1][w - 1]);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fr(i, n) for (int i = 0; i < n; i++)
#define frab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

const ll MOD = 1e9 + 7;
const ll INF = 2e15 + 10;
const ll MAX = 1e14 + 10;
const ld EPS = 1e-9;
const int N = 1e4 + 10;
const int M = 110;

ll d[N][M][2];

void add(ll& x, ll y) {
    x += y;
    if (x >= MOD)
        x -= MOD;
}

ll prec(string& s, int dd) {
    int n = s.size();
    d[0][0][1] = 1;
    fr(i, n)
        fr(j, dd + 1) {
            for (int dig = 0; dig <= 9; dig++)
                add(d[i + 1][(j + dig) % dd][0], d[i][j][0]);
            for (int dig = 0; dig < s[i] - '0'; dig++)
                add(d[i + 1][(j + dig) % dd][0], d[i][j][1]);
            add(d[i + 1][(j + s[i] - '0') % dd][1], d[i][j][1]);
        }
}

void solve() {
    string s;
    int dd;
    cin >> s >> dd;
    ll ans = 0;
    prec(s, dd);
    cout << (d[s.size()][0][0] + d[s.size()][0][1] + MOD - 1) % MOD;
}



int main() {
    //freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 17536
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include <random>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;



int main() {
  int n;
  scanf("%d",&n);
  vi a(n);
  rrep(i,n-1) scanf("%d",&a[i]);
  rrep(i,n-1) a[i]--;
  vi d(n);
  rrep(i,n-1) d[a[i]]++;
  vvi e(n);
  queue<int> q;
  rep(i,n) if (d[i] == 0) q.push(i), d[i] = -1;
  int ans = 0;
  while (sz(q)) {
    int i = q.front(); q.pop();
    sort(rng(e[i]));
    reverse(rng(e[i]));
    int mx = 0;
    rep(j,sz(e[i])) maxs(mx,e[i][j]+j+1);
    maxs(ans,mx);
    // cout<<i<<" "<<mx<<endl;
    e[a[i]].pb(mx);
    d[a[i]]--;
    if (d[a[i]] == 0) {
      q.push(a[i]), d[a[i]] = -1;
    }
  }
  cout<<ans<<endl;
  return 0;
}































Measured memory_bytes: 6528
#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int re1,re2;
	if(n<2)
	re1=0;
	else
	{
		re1=(n*(n-1))/2;
	}
	if(m<2)
	re2=0;
	else
	{
		re2=(m*(m-1))/2;
	}
	cout<<re1+re2;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<stdlib.h>
using namespace std;


struct node{
    int x,y,cnt;
};
int n,m;
int ans;
queue<node> q;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

int vis[1005][1005];

int main(){
    cin>>n>>m;
    ans=0;
    memset(vis,-1,sizeof(vis));
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=1;j<=m;j++){
            if(s.at(j-1)=='#'){
                vis[i][j]=1;
                node a;
                a.x=i;
                a.y=j;
                a.cnt=0;
                q.push(a);
            }
            else{
                vis[i][j]=0;
            }
        }
    }
    while(!q.empty()){
        node a=q.front();
        q.pop();
        ans=max(ans,a.cnt);
        for(int i=0;i<4;i++){
            node b=node{a.x+dx[i],a.y+dy[i],a.cnt+1};
            if (vis[b.x][b.y]==0){
                vis[b.x][b.y]=1;
                q.push(b);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 16400
//Author ::  ABHINAV3010 ::

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef pair<ll,ll> p;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    new_data_set;
ll mod=1000000007;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
ll power(ll x, ll y, ll p=mod)
{ll res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1;x = (x*x) % p;}return res;}
int main()
{
fast;
ll n;
cin>>n;
vector<ll>v;
for(ll i=0;i<n;i++)
{
    ll a;
    cin>>a;
    v.pb(a);
}
ll ans=0;
map<ll,ll>mp;
for(ll i=0;i<n;i++)
{
    ll val=v[i]-i;
    if(mp.count(val))
    {
        ans+=mp[val];
    }
    ll val2=-v[i]-i;
    mp[val2]++;
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 17100
#include<stdio.h>
int main()
{
	int n,i,m,k;
	scanf("%d",&n);
	int s=0;
	k=n;
	for(i=0;n>0;i++)
		{
			m=n%10;
			n=n/10;
			s+=m;
		}
	if(k%s==0)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.math.*;

class Main{
public static void main(String args[]){
   Scanner sc = new Scanner(System.in);
   int k = sc.nextInt();
   int n = sc.nextInt();
   int array[] = new int[n+1];
   int ret = 0;
   int maxe = 0;
   for (int i=0;i<n;i++){    
    int temp = sc.nextInt();
    array[i] = temp;
   }
   array[n] = k+array[0];
   for (int i=0;i<n;i++){
     ret += array[i+1]-array[i];
     maxe = Math.max(maxe,array[i+1]-array[i]);
   }
   System.out.println(ret-maxe);
}
}


Measured memory_bytes: 79184
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
using namespace std;

#define Yes(a) a ? "Yes" : "No";
#define YES(a) a ? "YES" : "NO";
#define rep(i,n) for(int i=0;i<n;i++)

void sout(string* a, string* b) {
	if (*a > * b) {
		string c = *a;
		*a = *b;
		*b = c;
	}
}

int combination(int n, int k) {
	if (n > k && k > 0) {
		return (combination(n - 1, k) + combination(n - 1, k - 1));
	}
	else
		return 1;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n - 1);
	rep(i, n) cin >> a.at(i);
	rep(i, n) cin >> b.at(i);
	rep(i, n - 1) cin >> c.at(i);
	int sum = b.at(0);
	for (int i = 1; i < n; i++) {
		sum += b.at(i);
		if (a.at(i - 1) == a.at(i) - 1) {
			sum += c.at(a.at(i-1)-1);
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
N,W = map(int,input().split())
w,v = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    w[i],v[i] = map(int,input().split())
SUM_V = sum(v)+1
# print(SUM_V)
INF = float('inf')
dp = [[INF for _ in range(SUM_V)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(SUM_V):
        # print(i,sum_v)
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i][sum_v],dp[i+1][sum_v])
res = 0
# for i in dp:
#     print(i)

for sum_v in range(SUM_V):
    if dp[N][sum_v] <= W:
        res = sum_v

print(res)

Measured memory_bytes: 247188
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int N = Integer.parseInt(in.next());
		long[] ans = new long[N+1];
		ans[0] = 2;
		ans[1] = 1;
		for(int i = 2; i <= N; i++)ans[i] = ans[i-1] + ans[i-2];
		System.out.println(ans[N]);
	}
}

Measured memory_bytes: 23892
def d(num):
    if(num%2==0): return num/2
    else: return num*3 + 1

s = int(input())
nextn = d(s)
nums = set()
nums.add(nextn)
res = 3

while(1):
    nextn = d(nextn)
    if(nextn in nums):break
    else: 
        res += 1
        nums.add(nextn)
if(s in [1, 2, 4]): print(4)
else: print(res)

Measured memory_bytes: 3188
a = gets.split.map(&:to_i)
sum = 0
if a[0]+a[1] <= a[2]*2
  sum = a[0]*a[3]+a[1]*a[4]
else
  if a[3] < a[4]
    sum += a[3]*a[2]*2
    if a[1] <= a[2]*2
      sum += (a[4]-a[3])*a[1]
    else
      sum += (a[4]-a[3])*a[2]*2
    end
  else
    sum += a[4]*a[2]*2
    if a[0] <= a[2]*2
      sum += (a[3]-a[4])*a[0]
    else
      sum += (a[3]-a[4])*a[2]*2
    end
  end
end
puts sum

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    
    if(a < b && b < c){
        cout << a << " " << b << " " << c << endl;
    }
    else if(a < c && c < b){
        cout << a << " " << c << " " << b << endl;
    }
    else if(b < a && a < c){
        cout << b << " " << a << " " << c << endl;
    }
    else if(b < c && c < a){
        cout << b << " " << c << " " << a << endl;
    }
    else if(c < a && a < b){
        cout << c << " " << a << " " << b << endl;
    }
    else if(c < b && b < a){
        cout << c << " " << b << " " << a << endl;
    }
    else if(a > b && b == c){
        cout << b << " " << c << " " << a << endl;
    }
    else if(a < b && a == c){
        cout << a << " " << c << " " << b << endl;
    }
}


Measured memory_bytes: 3112
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  ll i = 0;
  for (auto x : v) {os << " [" << i++ << "]" << x; if (i % 10 == 0) os << std::endl;}
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp) {os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

ll H, W;

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

  std::cin >> H >> W;

  std::vector< std::vector<std::string> > grid(H, std::vector<std::string>(W));
  for (ll y = 0; y < H; y++) {
    for (ll x = 0; x < W; x++) {
      std::cin >> grid[y][x];
    }
  }

  std::string ans;
  for (ll y = 0; y < H; y++) {
    for (ll x = 0; x < W; x++) {
      if (grid[y][x] == "snuke") {
	char a = 'A' + x;
	std::ostringstream oss;
	oss << y + 1;
	ans += a + oss.str();
	print(ans);
	return 0;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 384
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

class Main {

	public static void main(String[] args) {

		Scanner sc = null;
		Map<String, Integer> map = new TreeMap<String, Integer>();
		try {
			sc = new Scanner(System.in);
			String[] sentence = sc.nextLine().split(" ");

			int maxFrequency = 0;
			int maxLength = 0;
			String maxFrequencyWord = "";
			String maxLengthWord = "";
			for (String s : sentence) {
				map.put(s, map.containsKey(s) ? map.get(s) + 1 : 1);
				if (maxFrequency < map.get(s)) {
					maxFrequency = map.get(s);
					maxFrequencyWord = s;
				}
				if (maxLength < s.length()) {
					maxLength = s.length();
					maxLengthWord = s;
				}
			}

			System.out.println(maxFrequencyWord + " " + maxLengthWord);

		} finally {
			sc.close();
		}
	}
}

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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >
//------------------------------------------------------

int main() {
    int n;
    string s;
    cin >> n >> s;
    string f, b;
    f = s.substr(0, n);
    b = s.substr(n);
    reverse(b.begin(), b.end());
    map< pair<string, string>, ll> left, right;
    set< pair<string, string> > st;

    rep(k, 1 << n) {
        bitset<20> bs(k);
        string red, blue;

        rep(i, n) {
            if (bs[i]) red.push_back(f[i]);
            else blue.push_back(f[i]);
        }
        left[MP(red, blue)]++;
        st.insert(MP(red, blue));
    }

    rep(k, 1 << n) {
        bitset<20> bs(k);
        string red, blue;

        rep(i, n) {
            if (bs[i]) red.push_back(b[i]);
            else blue.push_back(b[i]);
        }
        right[MP(red, blue)]++;
        st.insert(MP(red, blue));
    }

    ll ans = 0;
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        ans += left[*itr] * right[*itr];
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 157440
import sys
sys.setrecursionlimit(10**6)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


inf = float('Inf')
f = [2, 3, 5]
cost = [0]*4


d = dict()


def dfs(x, d):
    if x in d:
        return(d[x])
    ret = cost[-1]*x
    for i in range(3):
        if x < f[i]:
            continue
        if x % f[i] == 0:
            ret = min(ret, dfs(x // f[i], d) + cost[i])
        else:
            k = x // f[i]
            ret = min(ret, cost[i] + dfs(k, d) + (x %
                                                  f[i]) * cost[-1], cost[i] + dfs(k+1, d) + ((k+1)*f[i]-x)*cost[-1])
    d[x] = ret
    return(ret)


def main():
    T = int(input())
    for _ in range(T):
        N, *c = map(int, input().split())
        for i in range(4):
            cost[i] = c[i]
        print(dfs(N, dict()))


main()


Measured memory_bytes: 10940
// #include<bits/stdc++.h>
// using namespace std;
 
// const int N = 100, MAXI = 100001, D = 9;
 
// int main() {
//     freopen("output.txt", "r", stdin);
//     freopen("input.txt", "w", stdout);
//     srand(time(nullptr));
//     int tc = 100, flag = 1;
//     cout << tc << "\n";
//     int n = 1;

//     while (tc--)
//     {
    	
//     	int n = rand()%N + 1, m = rand()%N + 1;

//     	int a[n][m];
//     	for(int i=0;i<n;i++)
//     	{
//     		for(int j=0;j<m;j++)
//     		{
//     			int flag = rand()%4;
//     			if(flag==0)
//     				a[i][j] = -1;
//     			else
//     				a[i][j] = rand()%MAXI;
//     		}
//     	}

//     	a[n-1][0] = rand()%MAXI;

//     	cout << n << " " << m << "\n";
//     	for(int i=0;i<n;i++){
//     		for(int j=0;j<m;j++)
//     			cout << a[i][j] << " ";
//     		cout << "\n";
//     	}

//     	cout << "~\n";
//     }
 
//     return 0;
// }
 
 
//  int n, a[N];

// int MEM(int ind, vector<int> &v)
// {
// 	if(ind==n)
// 	{
// 		// o(n)
// 	}

// 	int ans = 0;
// 	if(a[ind]==-1)
// 	{
// 		for(int i=0;i<n;i++)
// 		{
// 			if(i!=ind)
// 			{
// 				v[ind] = i;
// 				ans += MEM(ind+1, v);
// 				if(ans>=mod)
// 					ans %= mod;
// 			}
// 		}
// 	}
// 	else
// 		ans = MEM(ind+1, v);

// 	return ans;

// }
 
 
 
 
 
//---------------------------------------------//
 
 
 
/*
#define int long long 
#define mod (int)(1e9+7)
#define endl '\n'
#define MAXI (int)(3e17+10)
#define N 200005
 */ 
 
 
 
 

//  /* while(!cin.eof()) */
 
#include<bits/stdc++.h>
using namespace std; 
#define int long long 
#define mod (int)(1e9+7)
#define MAXI (int)(3e17+10)
#define N 1005




// Driver code to test above functions
int32_t main()
{
    
     
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
	cout.tie(NULL);

	
	int A, B; cin >> A >> B;
    char C; cin >> C;
    int D; cin >> D;
    B *= 100; B += D;
    int X = A*B; X /= 100;
    cout << X;

    return 0;
 
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long int ull;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> o_set; 

#define     int                 ll
#define     pb                  push_back
#define     mp                  make_pair
#define     xx                  first
#define     yy                  second    
#define     all(a)              a.begin(),a.end()
#define     vi                  vector<int>
#define     vpi                 vector<pii>
#define     pii                 pair<int, int>
#define     present(DT, val)    (DT.find(val) != DT.end()) //for set and map
#define     cpresent(DT, val)   (find(all(DT),val) != DT.end()) //vectors
#define     input               "/home/pollution/Desktop/WorkSpace/C++/Files/input.txt"
#define     output              "/home/pollution/Desktop/WorkSpace/C++/Files/output1.txt"
#define     error               "/home/pollution/Desktop/WorkSpace/C++/Files/error.txt"
#define     IO()                ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define     INF                 2e18
#define     MOD                 1000000007
#define     clr(x)              memset(x, 0, sizeof(x))
#define     init(x, a)          memset(x, a, sizeof(x))
#define     out(a)              for (auto i: a) cout<<i<<' '; cout<<'\n'
#define     cpy(a,b)            memcpy(a,b,sizeof(b))
#define     is(a)               to_string(a)
#define     ci(a,c)             a-c
#define     debug(i)            cout<<"point :"<<i<<'\n';
#define     setd(val,n)         cout<<fixed<<setprecision(n)<<val<<'\n'

void solve(){
    int n, sum = 0; cin>>n;
    for(int i = 1; i <= n; ++i){
    	for(int j = 1; j <= n; ++j){
    		for(int k = 1; k <= n; ++k) sum+=__gcd(i,__gcd(j,k));
    	}
    }
    cout<<sum<<'\n';
}

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

Measured memory_bytes: 3660
h, w = map(int, input().split(" "))
dp = [[0 for i in range(w)] for j in range(h)]
mod=1e9+7
for i in range(h):
    s = input()
    for j in range(w):
        if i==0 and j==0:
            dp[0][0]= 1 if (s[j]=='.') else 0
        elif i==0:
            dp[0][j]= dp[0][j-1] if (s[j]=='.') else 0
        elif j==0:
            dp[i][0]= dp[i-1][0] if (s[0]=='.') else 0
        else:
            dp[i][j]= (dp[i-1][j]%mod+dp[i][j-1]%mod)%mod if s[j]=='.' else 0
print(int(dp[h-1][w-1]%mod))


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

using namespace std;

#define ll long long 
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ff first
#define ss second
#define endl "\n"
#define MOD 1000000007
#define MOD1 998244353
#define inf 1e18

ll GCD(ll x,ll y){if(y==0)return x;return GCD(y,x%y);}
ll LCM(ll x,ll y){return (x*y)/(GCD(x,y));}
ll LOGK(ll x,ll k){if(x>=k)return 1+LOGK(x/k,k);return 0;}
ll MPOW( ll a, ll b, ll m) { if(b==0) return 1; ll x=MPOW(a,b/2,m); x=(x*x)%m; if(b%2==1) x=(x*a)%m; return x;}
ll MINV(ll a,ll m) {return MPOW(a,m-2,m);}

class pnc{
  ll FACT_MAX,MODU;
  vector<ll> fact;
public:
  pnc( ll n, ll m) { FACT_MAX = n; fact.resize(FACT_MAX); MODU = m; MFACT_INIT(MODU);}
  void MFACT_INIT( ll m) { fact[0]=1; for(ll i=1;i<FACT_MAX;++i) fact[i]=(i*fact[i-1])%MODU;}
  ll MFACT( ll n) { return fact[n];}
  ll PERM( ll n, ll r) { return (fact[n]*::MINV(fact[n-r],MODU))%MODU;}
  ll COMB( ll n , ll r) { return (PERM(n,r)*::MINV(fact[r],MODU))%MODU;}
};

ll ans[100005]={0};

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

    ll test=1;
    // cin>>test;
    while(test--)
    {
        ll n;
        cin>>n;

        for(ll x=1;x<=100;x++)
        {
            for(ll y=1;y<=100;y++)
            {
                for(ll z=1;z<=100;z++)
                {
                    ll temp=x*x+y*y+z*z+x*y+y*z+x*z;
                    if(temp<=10005)
                    ans[temp]++;
                }
            }
        }

        for(ll i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 3728
from collections import Counter
s = raw_input()
t = raw_input()

s=sorted(s)
t=sorted(t, reverse=True)

for x in xrange(min(len(s), len(t))):
    if s < t:
        print "Yes"
        break
    elif s>t:
        print "No"
        break
else:
    if len(s) < len(t):
        print "Yes"
    else:
        print "No"


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

int main() {
  int n;
  cin >> n;
  vector<int> ps(n, 0);
  int ans = 0;
  for(int i=0; i<n; i++) {
    cin >> ps[i];
    if(i > 1) {
      if((ps[i-2] > ps[i-1] && ps[i] < ps[i-1]) || (ps[i-2] < ps[i-1] && ps[i] > ps[i-1])) {
        ans += 1;
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
bool f(int cur, int left){
  if(left == 0){
    return true;
  }
  if(left < cur || cur <= 0){
    return false;
  }
  return f(cur - 1, left - cur);
}

int main(){
  while(true){
    int N;
    cin >> N;
    if(N == 0){
      break;
    }

    int ans = 0;
    for(int i = 1; i < N; i++){
      if(f(i, N)){
        ans ++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
using namespace std;

char S[60];

int main() {
  int N=0, K=0;
  scanf("%d%d", &N, &K);
  scanf("%s", S);
  S[K-1] += 32;
  cout << S << endl;
}

Measured memory_bytes: 256
import numpy as np

raw = input()
rawl = raw.split()
A = int(rawl[0])
B = int(rawl[1])
H = int(rawl[2])
M = int(rawl[3])
theta = 2*np.pi*(H/12+M/720-M/60)
print((A*A+B*B-2*A*B*np.cos(theta))**(0.5))


Measured memory_bytes: 27172