akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
 
using namespace std;

typedef long long tint;
 
#define forsn(i, s, n) for(int i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend() 
#define NACHO ios::sync_with_stdio(0); cin.tie(NULL);
#define dbg cout << "hu" << endl;
 
const int INF = 11000000;
const int MOD = 1000000007;

int main(){
	string s, t; cin >> s >> t;
	int n, m; cin >> n >> m;
	string c; cin >> c;
	if(c == s) n--;
	if(c == t) m--;
	cout << n << " " << m << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

vector<ll>lay;
ll n, k;

ll fun(ll n, ll x){
	if (n == 0)return (x <= 0 ? 0 : 1);
	ll p = (1LL << n) - 1;
	if (x <= 2*p)return fun(n - 1, x - 1);
	return p + 1 + fun(n - 1, x - 2 - lay[n - 1]);
}

int main(){
	cin >> n >> k;
	lay.push_back(1);
	for (int i = 1; i <= n; i++){
		ll l = lay[i - 1] * 2 + 3;
		lay.push_back(l);
	}
	cout << fun(n, k) << endl;
}


Measured memory_bytes: 256
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int m, f, r;

    for(;;){
      m = sc.nextInt();
      f = sc.nextInt();
      r = sc.nextInt();
      if(m + f + r == -3){
        break;
      }else if(m == -1 || f == -1){
        System.out.println("F");
      }else if(m + f >= 80){
        System.out.println("A");
      }else if(m + f >= 65){
        System.out.println("B");
      }else if(m + f >= 50){
        System.out.println("C");
      }else if(m + f >= 30){
        if(r >= 50){
          System.out.println("C");
        }else{
          System.out.println("D");
        }
      }else{
        System.out.println("F");
      }
    }


    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 19244
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    ls = []
    for i in range(3):
        a, b = list(map(int, input().rstrip('\n').split()))
        ls.append(a)
        ls.append(b)
    ls = collections.Counter(ls).most_common()
    print("YES" if ls[0][1] == 2 and ls[1][1] == 2 and ls[2][1] == 1 and ls[3][1] == 1 else "NO")


if __name__ == '__main__':
    solve()


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

int main() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    X--;
    Y--;
    vector<ll> ans(N-1, 0);
    rep(i, N){
        for(ll j = i+1; j < N; j++){
            ll dis = j - i;
            dis = min({abs(j-i), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)});
            ans[dis-1]++;
        }
    }
    rep(i, N-1){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

std::vector<int> UFT;
int Find(int a);
void Unite(int a,int b);
int main() {
    int N,M;
    std::cin >> N >> M;
    UFT.resize(N+1,0);
    for(int i=0;i<M;i++){
        int a,b;
        std::cin >> a >> b;
        int small,large;
        if(a>b){
            small = b;
            large = a;
        }else{
            small = a;
            large = b;
        }
        Unite(small,large);
    }
    for(int i=1;i<=N;i++){
        Find(i);
    }
    std::vector<int> cnt(N+1,0);
    for(int i=1;i<=N;i++){
        if(UFT[i] == 0){
            cnt[i]++;
        }else {
            cnt[UFT[i]]++;
        }
    }
    int max = 0;
    for(int i=1;i<=N;i++){
        if(cnt[i] > max){
            max = cnt[i];
        }
    }
    std::cout << max;

    return 0;
}

void Unite(int a,int b){
    int rootA,rootB;
    rootA = Find(a);
    rootB = Find(b);
    if(rootA == rootB){
        return;
    }
    UFT[rootB] = rootA;
    return;
}

int Find(int a){
    if(UFT[a] != 0){
        int root = Find(UFT[a]);
        UFT[a] = root;
        return root;
    }
    return a;
}

Measured memory_bytes: 5080
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;



int main(){
  string a, s, b;
  cin >> a >> s >> b;
  cout << "A" << s[0]  << "C"  << endl;


  return 0;
}


Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String[] sp = S.split("");
        int N = sp.length;
        
        String first = "";
        String last = "";
        
        for(int i = 0; i < (N-1)/2; i++) {
            first += sp[i];
        }
        for(int i = ((N+3)/2)-1; i < N; i++) {
            last += sp[i];
        }
        

        if(first.equals(last)) {
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  vector<int> array = {a, b, c};

  sort(array.begin(), array.end());
  REP(i, k) array[2] *= 2;
  cout << array[0] + array[1] + array[2] << "\n";

  return(0);
}


Measured memory_bytes: 256
n,first = map(int, input().split())
x = list(map(int, input().split()))

x.sort()
for i in range(n):
    x[i] -= first
    x[i] = abs(x[i])
import fractions
ans=x[0]
for i in x[1:]:
    ans = fractions.gcd(ans, i)

print(ans)

Measured memory_bytes: 14252
s=input()
s_list=list(s)
s_list.append('0')
for i in range(len(s)):
  if s_list[i]=='?':
    if s_list[i+1]=='D':
      if s_list[i-1]=='P':
        s_list[i]='D'
      else:
        s_list[i]='P'
    elif s_list[i+1]=='?':
      if s_list[i-1]=='P':
        s_list[i]='D'
      else :
        s_list[i]='P'
    else :
      s_list[i]='D'
    
    
s_list.pop()
a="".join(s_list)
print(a)

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

using namespace std;

string s, t;
const int maxN = 3e3 + 5;
int dp[2][maxN];
pair<int, int> par[maxN][maxN];

int main()
{
	cin >> s >> t;
	int n = s.length(), m = t.length();
	s = "0" + s;
	t = "0" + t;
	for (int i = 0; i <= m; ++i)
	{
		dp[0][i] = 0;
	}
	for (int i = 1; i <= n; ++i)
	{
		int curr = i % 2, prev = (i + 1) % 2;
		dp[curr][0] = 0;
		for (int j = 1; j <= m; ++j)
		{
			vector<int> opt;
			opt.push_back(dp[prev][j]);
			opt.push_back(dp[curr][j - 1]);
			opt.push_back( (s[i] == t[j]) ? (dp[prev][j - 1] + 1) : (dp[prev][j - 1]));
			auto it = max_element(opt.begin(), opt.end());
			dp[curr][j] = *it;
			switch(static_cast<int>(it - opt.begin()))
			{
				case 0:
				{
					par[i][j] = make_pair(i - 1, j);
					break;
				}
				case 1:
				{
					par[i][j] = make_pair(i, j - 1);
					break;
				}
				case 2:
				{
					par[i][j] = make_pair(i - 1, j - 1);
					break;
				}
			}

		}
	}

	int travI = n, travJ = m;
	string ans;

	while (travI != 0 || travJ != 0)
	{

		int tempI = par[travI][travJ].first;
		int tempJ = par[travI][travJ].second;

		if ( (tempI == travI - 1) && (tempJ == travJ - 1) && (s[travI] == t[travJ]) )	
		{
			ans.push_back( s[travI]);
		}
		travI = tempI;
		travJ = tempJ;
	}

	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 70784
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x,y;
    if(c%b==0) x=c/b;
    else x=c/b+1;
    if(a%d==0) y=a/d;
    else y=a/d+1;
    if(y>=x) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<long long> a(n,0);
	vector<long long> b(n,INT_MAX);
 
	for (int i=1; i<=n-1; i++)
		cin >> b[i];
 
	for (int i=1; i<=n; i++){
		if (i == 1)
			a[i-1] = b[i];
		else if (i == n)
			a[i-1] = b[n-1];
		else
			a[i-1] = min(b[i-1],b[i]);
	}
 
	long long sum = 0;
	for (int i=0; i<n; i++)
		sum += a[i];
 
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
def parallel?(x1, y1, x2, y2, x3, y3, x4, y4)
    a1 = (y2 - y1) / (x2 - x1) rescue Float::INFINITY
    a2 = (y4 - y3) / (x4 - x3) rescue Float::INFINITY
    return a1 == a2
end

$<.gets.to_i.times do
    puts parallel?(*$<.gets.split.map(&:to_r)) ? 'YES' : 'NO'
end

Measured memory_bytes: 6140
#include <stdio.h>
#include <string.h>
int c[20000001];
char ch[20],a[20];
int C(char x) {
  if(x=='A') return 1;
  if(x=='C') return 2;
  if(x=='G') return 3;
  return 4;
}
int search(int k, int x, int y, int t) {
  if(k==strlen(a)) {
    if(!t) c[x]=1;
    return c[x];
  }
  return search(k+1,x+C(a[k])*y,y*4,t);
}

int main() {
  int n;
  scanf("%d",&n);
  while(n--) {
    scanf("%s %s",ch,a);
    if(ch[0]=='i') search(0,0,1,0);
    else {
      if(search(0,0,1,1)) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}


Measured memory_bytes: 6724
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int[] p = new int[n];
		for(int i = 0; i < n; i++){
		    p[i] = sc.nextInt()-1;
		}
		
		// 計算
		int result = 0;
		int cnt = 0;
		boolean flg = false;
		for(int i = 0; i < n; i++){
		    if(flg){
		        result++;
		        flg = false;
		    }else if(p[i] == i){
		        flg = true;
		    }
		}
		if(flg) result++;
		
		// 出力
		System.out.println(result);
	}
}




Measured memory_bytes: 50332
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  string oka;
  
  for (int i = 0; i < N; i++) {
    cin >> oka;
    if(oka == "Y"){
    	cout << "Four" << endl;
      break;
    }
    
    if(i == N-1){
        	cout << "Three" << endl;
    }
    
  }
 
}

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - Candles
            var line = ReadLine().ToList();
            int n = line[0];
            int k = line[1];

            var x = ReadLine().ToList();
            int min = int.MaxValue;

            for (int i = 0; i <= n - k; i++)
            {
                int firstX = x[i];
                int lastX = x[i + k - 1];

                int dist = GetDistance(firstX, lastX);

                if (dist < min)
                {
                    min = dist;
                }
            }

            Console.WriteLine(min);
        }

        static int GetDistance(int firstX, int lastX)
        {
            if (lastX <= 0)
            {
                return Math.Abs(firstX);
            }
            else if (firstX >= 0)
            {
                return lastX;
            }
            else
            {
                //片方の座標がマイナスで、もう片方がプラスのケース
                //(最初にどちらの方向に行くかで2パターンが考えられる)
                int dist1 = Math.Abs(firstX) * 2 + lastX;
                int dist2 = lastX * 2 + Math.Abs(firstX);

                if (dist1 < dist2)
                {
                    return dist1;
                }
                else
                {
                    return dist2;
                }
            }
        }

        static IEnumerable<int> ReadLine()
        {
            var line = Console.ReadLine().TrimEnd();
            var array = line.Split(' ');

            foreach (var s in array)
            {
                yield return int.Parse(s);
            }
        }
    }
}

Measured memory_bytes: 19040
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef map <ll,ll> mm;
typedef vector <ll> mv;
typedef pair <ll,ll> mp;
typedef set <ll> ms;
typedef queue <ll> mq;
typedef deque <ll> mdq;
typedef stack <ll> mst;
typedef priority_queue <ll> mpq;
typedef priority_queue <ll, vector<ll>, greater<ll> > mmh;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define flush cout.flush();
#define cn continue
#define forl(i,n) for(ll i=0;i<n;i++)
#define forlr(i,n) for(ll i=n-1;i>=0;i--)
#define revstr(s) reverse(s.begin(),s.end())
void swap(ll &a,ll &b)
{
	ll tmp=a;
	a=b;
	b=tmp;
}
ll atoistring(string s)
{
	stringstream lol(s);
	ll x;
	lol>>x;
	return x;
}
// ll nck(ll N,ll K,ll mod)
// {
// 	if(N<K)
// 	{
// 		return 0;
// 	}
// 	return (((facs[N]*facsinv[N-K])%mod)*facsinv[K])%mod;
// }
ll power(ll x,ll y,ll p)
{
	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;
}
void checkmod(ll &x,ll mod)
{
	if(x>=mod)
	{
		x%=mod;
	}
}
// void checktime()
// {
// 	struct timespec ts;
// 	printf("Running Program\n");
// 	clock_gettime(CLOCK_MONOTONIC_RAW,&ts);
// 	long double st=ts.tv_nsec/(1e9)+ts.tv_sec;
// 	// Call Funcn Here
// 	clock_gettime(CLOCK_MONOTONIC_RAW,&ts);
// 	long double en=ts.tv_nsec/(1e9)+ts.tv_sec;
// 	printf("Program ended\nTime = %Lf\n",en-st);
// }
int main(void)
{
	fastio
	ll n;
	cin>>n;
	ll ans=1e18;
	for(ll i=1;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			ans=min(ans,abs(i-1)+abs((n/i)-1));
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<bitset>
#define rep(i,n) for(int i = 0;i < (n); ++i)
using namespace std;

typedef long long LL;
typedef long double LD;
const int mod = 1000000007;

LL Floor(LL a, LL b, LL x){
    LL ans = a * (x % b) - (a * x % b);
    return ans / b;
}

int main(void){
    LL a, b, n;
    cin >> a >> b >> n;

    LL ans = 0;
    if(n < b){
        ans = Floor(a, b, n);
        cout << ans << endl;
    }
    else{
        ans = Floor(a, b, b - 1);
        cout << ans << endl;
    }
}

Measured memory_bytes: 3640
mondai = input()

mondai = mondai.rstrip().split(" ")
saisyou = int(mondai[0])
saidai = int(mondai[1])
hanni = int(mondai[2])

if saidai - saisyou +1 <=hanni *2:
    for k in range(saidai - saisyou + 1):
        print(k+saisyou)
        k +=1
else:
    i=saisyou
    for i in range(hanni):
        if saisyou+i <= saidai:
            print(saisyou+int(i))
            i +=1
        else:
            i +=1
    j =saidai
    for j in range(hanni):
        if int(saidai) - int(hanni) +j+1>=int(saisyou):
            print(saidai - hanni +j+1)
            j +=1
        else:
            j +=1

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


int main(void) {

	char A[100], B[100];

	scanf("%s %s", A, B);

	if (strlen(A) > strlen(B)){
		printf("GREATER");
	}
	else if (strlen(A) < strlen(B)){
		printf("LESS");
	} else {
		for (int i = 0; i < (int) strlen(A); i++){
			if (A[i] > B[i]) {
				printf("GREATER");
				return 0;
			} else if (A[i] < B[i]) {
				printf("LESS");
				return 0;
			}
		}
		printf("EQUAL");
	}

	return 0;
}


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

using namespace std;


int main()
{
  int N; cin >> N;
  int S[N + 1][3];

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

  S[1][0] = a;
  S[1][1] = b;
  S[1][2] = c;

  for (int i = 1; i < N; i++) {
    int a, b, c; cin >> a >> b >> c;
    S[i + 1][0] = max(S[i][1], S[i][2]) + a;
    S[i + 1][1] = max(S[i][0], S[i][2]) + b;
    S[i + 1][2] = max(S[i][0], S[i][1]) + c;
  }

  cout << max({S[N][0], S[N][1], S[N][2]}) << endl;

  return 0;
}


Measured memory_bytes: 1408
//
//  main.cpp
//  atcoder_A
//
//  Created by 박다원 on 24/03/2019.
//  Copyright © 2019 박다원. All rights reserved.
//

#include <iostream>

using namespace std;

int main(int argc, const char * argv[])
{
    char c;
    cin >> c;
    
    if(c == 'A')
        cout << "T" << endl;
    else if(c == 'T')
        cout << "A" << endl;
    else if(c == 'G')
        cout << "C" << endl;
    else
        cout << "G" << endl;
    
    return 0;
}


Measured memory_bytes: 256
n,k00 = list(map(int, input().split()))

ks = [k00]
ns = [0]
k0 = k00+0
n0 = 0
while k0 >1:
    k0 = ((k0*-1)//2)*-1
    n0 += 1
    ks.append(k0)
    ns.append(n0)

for i,j in enumerate(ks):
    if n == j:
        ks1 = [1]
        for k,l in enumerate(ks[i:][:-1]):
            ks1.append(ks[i:][k] - ks[i:][k+1])
        ns1 = ns[i:]
        break
    elif n > j:
        ks1 = [n-j+1]
        for k,l in enumerate(ks[i:][:-1]):
            ks1.append(ks[i:][k] - ks[i:][k+1])
        ns1 = ns[i:]
        break

ans = 0
b1 = 1/n
for i,j in enumerate(ks1):
        ans += (ks1[i])*((1/2)**ns1[i])*(1/n)

print(ans)

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

// mod（素数だけ）の処理を忘れさせてくれるライブラリ
// https://github.com/atcoder-live/library/blob/master/mint.cpp
const int mod = 1000000007;
struct mint {
  long long x;
  mint(long long x = 0):x((x % mod + mod) % mod) {}
  mint operator-() const {return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};

int main() {

  long long N, K;
  cin >> N >> K;

  mint answer = 0;

  for (long long j = K; j <= N + 1; j++) {
    mint mn = j * (j + 1) / 2 - j;
    mint mx = N * j - mn.x;
    answer += mx.x - mn.x + 1;
  }

  cout << answer.x << endl;

  return 0;

}

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

using ll = long long;

#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 ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n; std::cin >> n;
  vector<pi> ab;
  rep(i, n) {
    int a, b; std::cin >> a >> b;
    ab.pb({b, a});
  }
  sort(rng(ab));
  bool ok = true;
  int cur = 0;
  rep(i, n) {
    if (cur > ab[i].fi-ab[i].se) ok = false;
    cur += ab[i].se;
  }
  std::cout << (ok ? "Yes" : "No") << "\n";
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
#include <limits>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
#define fi(i, n) for( int i=0 ; i<n ; i++ )
#define f(i, a, b) for( int i=a ; i<b ; i++ )
#define vi vector<int>
#define pb push_back
#define MOD 1000000007
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);

}
ll fact(ll n)
{
    ll ans = 1e14;
    for(ll i = 1; i<=sqrt(n); i++)
    {
        if(n%i==0)
        {
            ll sol = (i - 1) + (n/i - 1);
            ans = min(ans,sol);
        }
    }
    return ans;
}
int visited[200000] = {0};
vector<vector<int> > v(200000);
int dfs(int x)
{
    int ans = 0;
    if(visited[x]==0)
    {
        visited[x] = 1;
        ans++;
        int a = v[x].size();
        for(int j = 0;j<a;j++)
        {
            int data = v[x][j];
            ans = ans + dfs(data);
        }
    }
    return ans;
}
void primefactors(int n)
{
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n % i == 0)
        {
            cout << i << " ";
            n = n/i;
        }
    }

    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        cout << n << " ";

}
double fib(int n)
{
    double sol1,sol2;
    sol1 = (1 + sqrt(5))/2;
    sol2 = (1 - sqrt(5))/2;
    sol1 = pow(sol1,n);
    sol2 = pow(sol2,n);
    double ans = sol1 - sol2;
    ans = ans/sqrt(5);
    //ans = int(ans);
    return ans;
}
int digits(ll n)
{
    return floor(log10(double(n))) + 1;
}
int main()
{
    ll a,b;
    cin>>a>>b;
    ll lcm = a*b/gcd(a,b);
    cout<<lcm;


}


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

constexpr int di8[] = {0, 1, 1, 1, 0, -1, -1, -1};
constexpr int dj8[] = {1, 1, 0, -1, -1, -1, 0, 1};

int solve(){
    int h, w;
    cin >> h >> w;
    if(h == 0) return 1;
    vector<string> s(h);
    for(int i=0;i<h;i++){
        cin >> s[i];
    }
    map<string,int> cnt;
    for(int k=0;k<8;k++){
        vector<vector<bool> > used(h, vector<bool>(w));
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(used[i][j]) continue;
                int len = 0, ni = i, nj = j;
                string t;
                while(!used[ni][nj]){
                    t.push_back(s[ni][nj]);
                    used[ni][nj] = true;
                    ni = (ni+di8[k]+h)%h;
                    nj = (nj+dj8[k]+w)%w;
                }
                len = t.size();
                t += t;
                for(int l=0;l<len;l++){
                    for(int x=2;x<=len;x++){
                        cnt[t.substr(l,x)]++;
                    }
                }
            }
        }
    }
    string ans = "";
    for(auto p : cnt){
        string t = p.first;
        if(p.second >= 2){
            if(t.size() > ans.size()){
                ans = t;
            }else if(t.size() == ans.size()){
                ans = min(ans, t);
            }
        }
    }
    if(ans.empty()) ans = "0";
    cout << ans << endl;
    return 0;
}

int main(){
    while(solve()==0);
    return 0;
}



Measured memory_bytes: 31044
n = int(input())
E = []

B = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        if i+j != (n-n%2)-1:
            E.append((i,j))
            B[i][j] = 1
            B[j][i] = 1
print(len(E))
for a,b in E:
    print(a+1,b+1)

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

void solve()
{
  int k, n;
  cin>>k>>n;
  int res = 500*k;
  if(res>=n) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

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

    }
return 0;
}


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

int main(){
  string s ; cin >> s ;
  long int k ; cin >> k ;
  if(s.at(0)!='1'){
    cout << s.at(0) << endl ;
  }else{
    int cnt = 0 ;
    for(int i=0;i<s.size();i++){
      if(s.at(i)=='1'){
        cnt++ ;
      }else{
        break ;
      }
    }
    if(cnt>=k){
      cout << 1 << endl ;
    }else{
      cout << s.at(cnt) << endl ;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define rep(i, n) for(i = 0; i < (int)(n); i++)
using namespace std;

int n;
string w[100];

signed main() {
	int i, j;
	
	cin >> n;
	rep(i, n) { cin >> w[i]; }
	
	rep(i, n) {
		if (i == 0) continue;
		rep(j, i) {
			if (w[j] == w[i]) break;
		}
		if (j < i) { cout << "No" << endl; return 0; }
		if (w[i][0] != w[i - 1][w[i - 1].length() - 1]) { cout << "No" << endl; return 0; }
	}
	cout << "Yes" << endl;
	return 0;
}

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

namespace mondai0022
{
	class Program
	{
		static void Main(string[] args)
		{
			while( true ) {
				var	n	= int.Parse( Console.ReadLine() );
				if( n == 0 ) {
					break;
				}
				
				var	a	= new long[ n ];
				for( int i = 0; i < n; i++ ) {
					a[ i ]	= long.Parse( Console.ReadLine() );
				}
				
				var	max	= long.MinValue;
				for( int i = 0; i < n; i++ ) {
					long	sum	= 0;
					for( int j = i; j < n; j++ ) {
						sum	+= a[ j ];
						if( sum > max ) {
							max	= sum;
						}
					}
				}
				Console.WriteLine( max );
			}
		}
	}
}

Measured memory_bytes: 5680
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional>
#include <map>
#include <set>
#include <stack>
#include <deque>

#define INF 1000000000;
#define MOD 1000000007;
typedef long long ll;
using namespace std;

int main()
{
    string s; cin >> s;
    int section = 0;
    char now = 'a';
    for (auto c : s) {
        if (now != c) {
            section++;
            now = c;
        }
    }

    cout << section - 1 << endl;
}

Measured memory_bytes: 512
"""
奇数本の辺で成り立つ閉路があれば、全ての頂点同士を1本の辺で結ぶことができる。
そうでない場合は、奇数本の辺をたどってたどり着ける頂点同士は全て1本の辺で結ぶことができる。
奇数本の閉路があるかどうかを、どうやって判定するか？
二部グラフ判定を行う。
二部グラフ判定ってどうやるんだっけ？→となりのノードに違う色をつけていって、矛盾がなければ二部グラフ。矛盾があれば二部グラフじゃない。
"""
import sys
sys.setrecursionlimit(200000)
N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

n = len(edges)
colors = [-1]*(n+1)
def judgeBiGragh(edges):
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
if judgeBiGragh(edges):
    cnt0 = colors.count(0)
    cnt1 = colors.count(1)
    ans = cnt0*cnt1 - M
else:
    ans = choose(N,2)-M

print(ans)

Measured memory_bytes: 40528
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
#define degreeToRadian(deg) (((deg)/360)*2*M_PI)
#define radianTodegree(rad) (((rad)/2/M_PI)*360)
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; }
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;
const int MOD = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//cin.tie(0);ios::sync_with_stdio(false);
//cout << fixed << setprecision(15) << y << endl;
int main() {
  string s;
  cin >> s;

  char ch = s[0];
  bool ok = true;
  for (auto v : s) {
    if (v == ch) continue;
    ok = false;
  }

  if (!ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3584
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush, heapify

N = int(fin())
a_list = [int(elem) for elem in fin().split()]
left, right = a_list[:N], a_list[N:]

thrown_away = [False] * (2 * N)
discarded_items = []

# initialize
right_sum = sum(right)
for i, item in enumerate(right):
    if i < N:
        heappush(discarded_items, (item, i))
        thrown_away[i] = True
        right_sum -= item
    else:
        if item > discarded_items[0][0]:
            old_item, old_idx = heappop(discarded_items)
            thrown_away[old_idx] = False
            heappush(discarded_items, (item, i))
            thrown_away[i] = True
            right_sum += old_item - item


# move partitions and calculate a global maximum
left_sum = sum(left)
heapify(left)
moved_to_left = [False] * (2 * N + 1)
# dirty trick
moved_to_left[-1] = True
max_score = left_sum - right_sum
for i, item in enumerate(right[:N]):
    if not thrown_away[i]:
        # update right
        updated_idx = -1
        while moved_to_left[updated_idx] == True:
            updated_item, updated_idx = heappop(discarded_items)
        right_sum += updated_item - item
        thrown_away[updated_idx] = False
    else:
        # want to update discarded_items
        moved_to_left[i] = True
    # update left
    if item > left[0]:
        old_item = heappop(left)
        heappush(left, item)
        left_sum += item - old_item
    max_score = max(max_score, left_sum - right_sum)

print(max_score)


Measured memory_bytes: 121360
'use strict'

function Main(input) {
  input = input.trim().split('\n')
  const array = input[0].split(' ').map(s => parseInt(s))
  const N = array[0]
  const M = array[1] // 提出回数

  const rest = input.slice(1)

  const list = rest.map(s => {
    return s.split(' ')
  })

  let dp = {}
  list.forEach(data => {
    if(!dp[data[0]]) dp[data[0]] = {success: 0, fail: 0, fixed: false}
    // AC
    if(data[1] === 'AC' && !dp[data[0]].fixed) {
      dp[data[0]].success += 1
      dp[data[0]].fixed = true
    } else if(data[1] === 'WA' && !dp[data[0]].fixed) {
      dp[data[0]].fail += 1
    }
  })


  let success = 0
  let pena = 0
  for(let i in dp) {
    const tmp = dp[i]
    if (tmp.fixed) {
      success += tmp.success
      pena += tmp.fail
    }
  }


  console.log(`${success} ${pena}`)

}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 58796
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


    int a, b, c;
    cin >> a >> b >> c;
    int mn = min(a, min(b, c));
    int mx = max(a, max(b, c));
    cout << mx - mn << '\n';

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define N 2000001
#define M 10000

int B[N],C[M];

void CountingSort(int A[N], int k, int n);
  
int main(){
  
  int i,n, max=0,A[N];
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    if(A[i]>max)max=A[i];
     }
  
  CountingSort(A,max,n);

 return 0;
}   
  
void CountingSort(int A[N], int k, int n){
  
  int i, j;
  for(i=0;i<=k;i++){
    C[i]=0;
  }
  for(j=1;j<=n;j++){
      C[A[j]]=C[A[j]]+1;
      }
  for(i=1;i<=k;i++){
    C[i]=C[i]+C[i-1];
  }
  
  for(j=n;j>=1;j--){
    
    B[C[A[j]]]=A[j];
    C[A[j]]=C[A[j]]-1;
    }
  
  for(i=1;i<=n;i++){
  printf("%d",B[i]);
  if (i<n)printf(" ");
   }
  printf("\n");
}
 

Measured memory_bytes: 16268
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define GODSPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef vector<int>vi;
typedef pair<int,int>pi;
typedef vector<pi>vpi;
typedef vector<vi>vvi;
#define double long double
#define pow powl
#define sqrt sqrtl
#define cbrt cbrtl
#define floor floorl
#define ceil ceill
#define pb push_back
#define ep emplace_back
#define PB pop_back
#define pf push_front
#define ef emplace_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)-a.begin()
#define lb(a,b) lower_bound(all(a),b)-a.begin()
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) FOR(i,0,n-1) cin>>a[i]
#define in1(a,n) FOR(i,1,n) cin>>a[i]
#define ff first
#define ss second
#define out(a,n) FOR(i,0,n-1) cout<<a[i]<<" ";cout<<endl;
#define out1(a,n) FOR(i,1,n) cout<<a[i]<<" ";cout<<endl;
#define clr(a) a.clear()
#define pow2(a) (1LL<<a)
#define all(a) a.begin(),a.end()
#define all1(a) a.begin()+1,a.end()
#define rall(a) a.rbegin(),a.rend()
#define rall1(a) a.rbegin(),a.rend()
#define sz(a) ((int)a.size())
#define FOR(i,a,b) for(auto i=a;i<=b;i++)
#define NFOR(i,a,b) for(auto i=a;i>=b;i--)
const int mod=1e9+7;
int add(int a,int b){return (a%mod + b%mod)%mod;}
int sub(int a ,int b){return (a%mod - b%mod + mod)%mod;}
int mul(int a,int b){return (a%mod * b%mod)%mod;}
int power(int a,int b,int MOD){int res=1;while(b){if(b&1){res*=a;res%=MOD;}a=a*a;a%=MOD;b>>=1;}return res;}

#define trace(x) cout<<#x<<" :: "<<x<<endl;
#define trace2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define trace3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define trace4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
signed main()
{
    GODSPEED;
    vector<int>v(3);
    in(v,3);
    vector<int>p={5,5,7};
    sort(all(v));
    cout<<(v==p ? "YES" : "NO")<<endl;
    return 0;
}

Measured memory_bytes: 256
n=str(input())
k=True
kaku=n[0]
for i in n:
    if int(n[0])!=int(i):
        k=False
if k:
    print(n)
else:
    if int(n[0])>=int(n[1]) and int(n[0])>=int(n[2]):
        print(n[0]*3)
    else:
        s=int(n[0])+1
        print(str(s)*3)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
int main()
{
    int n,q;
    
    cin >> n;
    vector<ll>s(n);
    rep(i,n)cin >> s[i];
    cin >> q;
    vector<ll> t(q);
    rep(i,q)cin >> t[i];
    int ans = 0;
    rep(i,q){
        ll x = t[i];
        int itr = upper_bound(s.begin(),s.end(),x-1)- s.begin();
        if(itr >=0 && itr < n &&s[itr] == x){
            ans++;
        
        }
        
        
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  char c;
  cin >> c;
  if (c < 'a')
    cout << "A" << endl;
  else
    cout << "a" << endl;
}


Measured memory_bytes: 3652
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N, As):
    if N == 0:
        if As[0] == 1:
            return 1
        else:
            return -1

    if As[0] != 0:
        return -1

    depth = N
    mx = 2 ** depth
    prev_leaf = None

    leaf_sum = sum(As)

    ans = 0
    curr = 0
    Vs = [None] * (N + 1)
    for n in range(N + 1):
        if n == 0:
            curr = 1
            ans += 1
        else:
            # 頂点を増やせるだけ増やす
            curr2 = min(curr * 2, leaf_sum)
            # 矛盾したら終わり
            if curr2 < As[n]:
                return -1
            # 頂点全部足す
            ans += curr2
            # 次に残れる頂点
            curr = curr2 - As[n]
            # 使った葉のぶんを引く
            leaf_sum -= As[n]

    return ans


def main():
    N = int(input())
    As = list(map(int, input().split()))
    print(solve(N, As))

    
main()


Measured memory_bytes: 22316
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

static const int INTINF = (2147483647);
static const ll LLINF = (9223372036854775807);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Printer{
    template<class T>
    void print(vector<T> v){
        rep(i, v.size()){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class T>
    void print(vector<vector<T> > vv){
        rep(i, vv.size()){
            rep(j, vv[i].size()){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void print(pair<int, int> p){
        cout << "(" << p.first << ", " << p.second << ")" << endl;
    }
};

//--global--//



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

std::vector<std::vector<long long>> comb(int n, int r) {
  std::vector<std::vector<long long>> v(n + 1,std::vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

void calcSosu(bool *sosu){
    rep2(i, 2, 101){
        bool ok = true;
        rep2(j, 2, i){
            if(i%j == 0)ok = false;
        }
        if(ok)sosu[i] = true;
    }
}

int num(int m, int *cnt){
    int res = 0;
    rep(i, 101){
        if(cnt[i] >= m-1){
            res++;
        }
    }
    return res;
}

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//

    bool sosu[101];
    fill(sosu, sosu+101, false);
    int n;
    cin >> n;
    calcSosu(sosu);

    int cnt[101];
    fill(cnt, cnt+101, 0);
    rep2(i, 2, n+1){
        int tmp = i;
        rep(j, 101){
            if(sosu[j]){
                while(tmp % j == 0){
                    cnt[j]++;
                    tmp /= j;
                }
            }
        }
    }

    int tmp15 = 0;
    int fivefive = 0;
    int five = 0;
    int three = 0;
    rep(i, n+1){
        if(cnt[i] >= 14)tmp15++;
        if(cnt[i] >= 24)fivefive++;
        if(cnt[i] >= 4)five++;
        if(cnt[i] >= 2)three++;
        //cout << cnt [i] << endl;
    }
    three -= five;
    // cout << "res" << endl;

    // cout << num(75, cnt) <<endl;
    // cout << num(25, cnt)*(num(3, cnt)-1) <<endl;
    // cout << num(15, cnt)*(num(5, cnt)-1) <<endl;
    // cout << num(5, cnt)*(num(5, cnt)-1)*(num(3, cnt)-2) <<endl;
    cout << num(75, cnt)+num(25, cnt)*(num(3, cnt)-1)+num(15, cnt)*(num(5, cnt)-1)+num(5, cnt)*(num(5, cnt)-1)*(num(3, cnt)-2)/2 << endl;


    
    
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
ans = 1000
for i in range(n-1):
    x = ans // a[i]
    if a[i] < a[i+1]:
        ans -= x * a[i]
        ans += x * a[i+1]
print(ans)

Measured memory_bytes: 65584
import copy
n = int(input())
numS = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
numH = copy.copy(numS)
numC = copy.copy(numS)
numD = copy.copy(numS)
for i in range(n):
  sym, num = list(input().split())
  num = int(num)
  if sym == "S":
    numS.remove(num)
  elif sym == "H":
    numH.remove(num)
  elif sym == "C":
    numC.remove(num)
  else:
    numD.remove(num)
for s in range(len(numS)):
  print("S " + str(numS[s]))
for h in range(len(numH)):
  print("H " + str(numH[h]))
for c in range(len(numC)):
  print("C " + str(numC[c]))
for d in range(len(numD)):
  print("D " + str(numD[d]))


Measured memory_bytes: 6340
import sys

inputs = []
for _ in range(5):
    x = int(sys.stdin.readline())
    if x % 10 == 0:
        m = 0
    else:
        m = 10 - (x % 10)
    inputs.append((m, x))

inputs.sort()

ret = 0
for m, x in inputs[:-1]:
    ret += m + x
ret += inputs[-1][1]

print(ret)

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, f, n) for (int i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;

int main() {
    ll N, K;
    cin >> N >> K;

    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> B(N, 0);
    vector<ll> S(N, 0);
    vector<ll> E(N, 0);

    for (ll k = 0; k < K; k++) {
        bool flg = true;
        rep(i, N) {
            if (A[i] != N) {
                flg = false;
            }
        }
        // cout << "flg:" << flg << endl;
        if (flg) break;

        rep(i, N) {
            B[i] = 0;
            S[i] = 0;
            E[i] = 0;
        }

        for (ll i = 0; i < N; i++) {
            ll s = max(0LL, i - A[i]);
            ll e = min(i + A[i], N - 1);
            S[s]++;
            E[e]++;
        }

        // cout << "S: ";
        // rep(i, N) { cout << S[i] << " "; }
        // cout << endl;

        // cout << "E: ";
        // rep(i, N) { cout << E[i] << " "; }
        // cout << endl;

        ll now = 0LL;
        for (ll i = 0; i < N; i++) {
            now += S[i];
            B[i] = now;
            now -= E[i];
        }
        // rep(i, N) cout << B[i] << " ";
        // cout << endl;

        rep(i, N) A[i] = B[i];
    }

    rep(i, N) cout << A[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 9592
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n;
  cin >> n;
  int a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  pr(a[n-1]-a[0]);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    double a, b, x;
    cin >> a >> b >> x;
    double s = x / a;
    double ans = 0;
    auto f = [&](double theta) {
        if(theta > M_PI / 2.0) {
            return 0.0;
        }
        double ret;
        if(a * tan(theta) <= b) {
            ret = a * a * b - a * a * a * tan(theta) / 2.0;
        } else {
            ret = b * b / tan(theta) * a / 2.0;
        }
        return ret;

    };
    double ok = M_PI / 2.0;
    double ng = 0.0;
    rep(i, 100) {
        double mid = (ok + ng) / 2.0;
        if (f(mid) < x) ok = mid;
        else ng = mid;
    }
    cout << ok * 180 / M_PI << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int convert(char *str)
{
    int ans;
    
    ans = (str[1] == '#');
    switch (str[0]){
      case 'D':
        ans += 2;
        break;
      
      case 'E':
        ans += 4;
        break;
      
      case 'F':
        ans += 5;
        break;
      
      case 'G':
        ans += 7;
        break;
      
      case 'A':
        ans += 9;
        break;
      
      case 'B':
        ans += 11;
        break;
    }
    
    return (ans);
}

int n, m;
int T[50000], S[50000];

int searchPath(int vertex, int cur)
{
    int ans;
    
    if (cur == 0){
        return (vertex == -1);
    }
    if (vertex < 0 || vertex >= n){
        return (0);
    }
    
    ans = 0;
    if (T[vertex] == S[cur - 1]){
        ans |= searchPath(vertex - 1, cur - 1);
    }
    if ((T[vertex] + 1) % 12 == S[cur - 1]){
        ans |= searchPath(vertex - 2, cur - 1);
    }
    if ((T[vertex] + 11) % 12 == S[cur - 1]){
        ans |= searchPath(vertex + 1, cur - 1);
    }
    
    return (ans);
}

int main(void)
{
    int t;
    int i, j;
    char in[4];
    
    scanf("%d", &t);
    
    while (t--){
        scanf("%d%d", &n, &m);
        
        for (i = 0; i < n; i++){
            scanf("%s", in);
            T[i] = convert(in);
        }
        for (i = 0; i < m; i++){
            scanf("%s", in);
            S[i] = convert(in);
        }
        
        if (searchPath(n - 1, m) | searchPath(n - 2, m)){
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    
    return (0);
}

Measured memory_bytes: 2724
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
long long read() {
    register long long x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f ^= 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
#define N 100005
int n;
long long sum, a[N], b[65], ans;
void insert(long long x) {
    for (register int i = 60; ~i; --i)
        if (!(sum >> i & 1))
            if (x >> i & 1) {
                if (!b[i])
                    return b[i] = x, void(0);
                x ^= b[i];
            }
    for (register int i = 60; ~i; --i)
        if (sum >> i & 1)
            if (x >> i & 1) {
                if (!b[i])
                    return b[i] = x, void(0);
                x ^= b[i];
            }
}
int main() {
    n = read();
    for (register int i = 1; i <= n; ++i) a[i] = read(), sum ^= a[i];
    for (register int i = 1; i <= n; ++i) insert(a[i]);
    for (register int i = 60; ~i; --i)
        if (!(sum >> i & 1))
            if (!(ans >> i & 1))
                ans ^= b[i];
    for (register int i = 60; ~i; --i)
        if (sum >> i & 1)
            if (!(ans >> i & 1))
                ans ^= b[i];
    printf("%lld\n", ans + (sum ^ ans));
}

Measured memory_bytes: 896