akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    string s;cin>>s;
    int n=s.size();
    s="x"+s;
    
    bool f=true;
    if(s[n]=='1') f=false;
    for(int i=1;i<n;i++){
        if(s[i]!=s[n-i]) f=false;
    }
    if(s[1]=='0') f=false;
    if(!f){
        cout<<-1<<endl;
        return 0;
    }

    int nw=n;
    for(int i=n-1;i>0;i--){    
        cout<<nw<<' '<<i<<endl;
        if(s[i]=='1') nw=i;
    }

    return 0;
}


Measured memory_bytes: 1664
K=int(input())
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a=l[K-1]
print(a)


Measured memory_bytes: 2940
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main() {
  int L, R;

  cin >> L >> R;

  int ans = 0;

  for (int i=L; i<=R; i++) {
    string s = to_string(i);
    string t = s;
    reverse(t.begin(), t.end());
    ans += s == t;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	int n,m;
	string u[256];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>u[i];
	bool door=true;
	string a;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>a;
		bool t=false;
		for(int j=0;j<n;j++){
			if(u[j]==a){
				t=true;
				if(door==true){
					cout<<"Opened by "<<a<<endl;
					door=false;
				}
				else{
					cout<<"Closed by "<<a<<endl;
					door=true;
				}
			}
		}
		if(t==false)
			cout<<"Unknown "<<a<<endl;
	}
    return 0;
}

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

using namespace std;

#define INF ((int64_t)2e18)
#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 3;

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int l;

  cin >> l;

  double a = l / 3.0;

  cout << fixed << setprecision(9);
  cout << a * a * a << endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0;i<n;i++) {
    cin>>a.at(i);
  }
  double p=0;
  for (int x:a) {
    p+=1.0/x;
  }
  cout<<1.0/p<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int a;
	int sum = 0;
	cin >> a;
	int s[10];
	for (int i = 0; i < a; i++)
	{
		cin >> s[i];
	}
	for (int i = 0; i < a-1; i++)
	{
		if (s[i] > s[i + 1])
		{
			swap(s[i], s[i + 1]);
		}
	}
	for (int i = 0; i < a - 1; i++)
	{
		sum = sum + s[i];
	}
	sum = sum + s[a - 1]/2;
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n;
	map<ll, int> mp1;
	map<ll, int> mp2;
	rep(i, n) {
		int a; cin >> a;
		mp1[a]++;
	}
	cin >> m;
	rep(i, m) {
		int a; cin >> a;
		mp2[a]++;
	}
	bool elf = true;
	for (auto& c : mp2) {
		if (mp1[c.first] < c.second) elf = false;
	}
	dunk(elf ? "YES" : "NO");
	return 0;
}


Measured memory_bytes: 25216
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
typedef long long ll;
#define mp make_pair
ll ans;
int d,n;
int main()
{
	cin>>d>>n;
	int p=0;
	if(d==0){
		p=1;
	}
	if(d==1){
		p=100;
	}
	if(d==2){
		p=10000;
	}
	for(int i=0;i<n;i++){
		ans+=p;
	}
	if(n==100){
		ans+=p;
	}
	cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 5005
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
const int n=read(),mod=read();
int dp[N],w[N],ans;
#define ck(x) (x>=mod?x-mod:x)
int main(){
	w[2]=1;
	for(int l=3,r=n;l<=r;++l,--r){
		w[l]=w[r]=w[l-1]+1;
	}
	dp[n]=1;
	for(int i=2;i<=n;++i){
		for(int j=n-w[i];j>=1;--j){
			dp[j]=ck(dp[j]+dp[j+w[i]]);
		}
	}
	for(int i=1;i<=n;++i){
		ans=(ans+1LL*i*dp[i])%mod;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3760
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

//制定了间隔g的插入排序
void insertionSort(int A[], int n, int g) {
	for ( int i = g; i < n; i++) {
		int v = A[i];
		int j = i - g;
		while( j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = v;
	}
} 

void shellSort(int A[], int n) {
	//生成数列G={1, 4, 13, 40, 121, 364, 1093, ...}
	for ( int h = 1; ; ) {
		if ( h > n ) break;
		G.push_back(h);
		h = 3*h + 1;
	} 
	
	for ( int i = G.size()-1; i >= 0; i--) {
	    //按逆序指定G[i] = g
	    insertionSort(A, n, G[i]);
	}
}

int main() {
	cin >> n;
	//使用速度更快的scanf函数进行输入
	for ( int i = 0; i < n; i++ ) scanf("%d", &A[i]);
	cnt = 0;
	
	shellSort(A, n);
	
	cout << G.size() << endl;
	for ( int i = G.size() - 1; i >= 0; i--) {
		printf("%d", G[i]);
		if (i) printf(" ");
	}
	printf("\n");
	printf("%d\n", cnt);
	for ( int i = 0; i < n; i++ ) printf("%d\n", A[i]);
	
	return 0;
}


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

int main() {
  int n;
  int bus_stop[]={0,1,2,3,4,5,6,7,8,9,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9};
  cin>> n;
  while(n--) {
    int get, off;
    cin>> get>> off;
    int i;
    for((get<6 && get>off) ? i=(15-get):i=get; bus_stop[i]!=off; i++) {
      cout<< bus_stop[i]<< ' ';
    }
    cout<< off<< endl;
  }
}

Measured memory_bytes: 1160
#include<iostream>
using namespace std;
int main()
{
	long long int N,k,i,j,ans=0;
  	cin>>N>>k;
  	long long int start_value=0;
      	long long int end_value=0;
      	for(j=0;j<k;j++)
        {
        	start_value+=j;
          	end_value+=N-j;
          
        }
        ans+=end_value-start_value+1;
        start_value+=k;
        end_value=end_value+N-k;
    	 //ans=ans%1000000007;
    	 //cout<<start_value<<endl;
    	 //cout<<end_value<<endl;
  	
  	for(i=k+1;i<=N+1;i++)
    {
        ans+=end_value-start_value+1;
    	 ans=ans%1000000007;
    	start_value=start_value+i;
    	end_value=end_value+N-i;
      	
    	 //cout<<start_value<<endl;
    	 //cout<<end_value<<endl;
    	 //cout<<ans<<endl;
    }
   
  	cout<<ans<<endl;


	return 0;
}

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

int main(){
    int a,h,N;
    cin >> N;
    a=N;h=0;
    while(a>9){
      h+=(a%10);
      a/=10;
    }
    h+=a;
    if(N%h==0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int mod = 998244353;
const int IMAX = 100000;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}

ll dp[3001];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N, S;
	cin >> N >> S;

	int A[3000];
	rep(i, N) cin >> A[i];
	sort(A, A + N);

	ll k2 = modpow(2, mod - 2);
	dp[0] = modpow(2, N);
	int s = 0;
	rep(i, N) {
		s = min(S - A[i], s + A[i]);

		if (S >= A[i]) dp[S] = (dp[S] + dp[S - A[i]] * k2) % mod;
		for (int j = s; j >= A[i]; j--) {
			dp[j] = (dp[j] + dp[j - A[i]] * k2) % mod;
		}
	}

	co(dp[S] % mod);

	Would you please return 0;
}

Measured memory_bytes: 3612
ls = []
for i in range(5):
  ls.append(int(input()))
k = int(input())
a = []
for i in range(5):
  for j in range(i+1, 5):
    a.append(abs(ls[i] - ls[j]) <= k)
if all(a):
  print('Yay!')
else:
  print(':(')


Measured memory_bytes: 2940
import std.stdio,std.conv,std.string,std.algorithm,std.array,std.math;
void main(){
  auto s=readln().chomp().split().map!(to!int);
  int a,b,c,d;
  a=s[0];
  b=s[1];
  c=s[2];
  d=s[3];
  if(abs(c-a)<=d)
    writeln("Yes");
  else if(abs(b-a)<=d && abs(c-b)<=d)
    writeln("Yes");
  else
    writeln("No");
}

Measured memory_bytes: 256
import math 
a, b, x = map(int, input().split())

tan = 0
if (x < (a**2*b)/2):
    tan1 = 2 * x / (a * (b**2))
    print(90-math.degrees(math.atan(tan1)))
else:
    tan2 = 2 * ((a**2) * b - x) / (a**3)
    print(math.degrees(math.atan(tan2)))

Measured memory_bytes: 3444
#include<bits/stdc++.h> 
#define ll long long int
#define MOD 1000000007
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

vector <ll> h,dp;
ll n,k;
ll rec(ll idx)
{ll ans;
    if(dp[idx]!=-1) return dp[idx];
    if(idx>=n)return MOD; 
    if(idx==n-1)return 0;
    if(idx<n)
    {ans=MOD;
        for(ll i=1;i<=k;i++)
        {
            if(idx+i<n)
            ans=min(ans,rec(idx+i)+abs(h[idx]-h[idx+i]));
            // cout<<ans<<"\n";
        }
        return dp[idx]=ans;
    }

}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    ll c,a;
    cin>>n>>k;
    for(ll i=0;i<n;i++)
    {
        cin>>a;
        h.push_back(a);
    }
    h.push_back(MOD);
    vector<ll> v(n,-1);
    dp=v;
    c=rec(0);
    cout<<c;
}


Measured memory_bytes: 7412
#include<stdio.h>

int main(void){
  int a, b, s;
  scanf("%d %d", &a, &b);

  s = a + b;

  if( a % 3 == 0 || b % 3 == 0 || s % 3 == 0 ) printf("%s\n", "Possible");

  else printf("%s\n", "Impossible");

}

Measured memory_bytes: 128
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

S = raw_input()
ans = [0] * len(S)
S = S + "R"
pos1 = 0
posR = 0
c_pre = 'R'
for i in range(len(S)):
    c = S[i]
    if c_pre == 'L' and c == 'R':
        n1 = (posR - pos1) / 2 + 1 + (i - 1 - posR) / 2
        n2 = i - pos1 - n1
        ans[posR] += n1
        ans[posR + 1] += n2
        pos1 = i
    if c_pre == 'R' and c == 'L':
        posR = i - 1
    c_pre = c
print " ".join(map(str, ans))

Measured memory_bytes: 7276
#include <iostream>

int main(int argc, char const *argv[]) {
  int times=0,s,m,h;
  std::cin >> times;

  h = times/3600;
  m = (times%3600)/60;
  s = times % 3600 % 60;

  std::cout << h << ":" << m << ":" << s << std::endl;
  return 0;
}

Measured memory_bytes: 3108
#include<iostream>
using namespace std;
int main(){
  int x,y;
  cin>>x>>y;
  int flag=0;
  for(int i=0;i<=x;i++){
    int a,b;
    a=i;
    b=x-i;
    if(a*2+b*4==y){
      flag=1;
      cout<<"Yes"<<endl;
      break;
    }
  }
  if(flag==0){
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3564
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

get_chars(Xs) :-
    get_string(S),
    string_chars(S, Xs).

get_numbers(0, []).
get_numbers(N, [X|Xs]) :- 
    get_number(X), 
    N2 is N - 1, 
    get_numbers(N2, Xs).

put_numbers([]).
put_numbers([X|Xs]) :-
    writeln(X),
    put_numbers(Xs).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)
    sub_string

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==

    between(L,U,X): L <= X <= U
    nth0(I, Xs, Y), nth1(I, Xs, Y): (Xs,Y) -> I, (I, Xs) -> Y 

    sort(Key, Order, List, Sorted): Keyは通常0?, Orderは=なしが重複削除，=は重複保持
*/

f([], Y, Y).
f([X|Xs], Y, -1) :- Y * X > 1000000000000000000, !.
f([X|Xs], Y, Z) :- Y2 is X * Y, f(Xs, Y2, Z).

g([]).
g([X|Xs]) :- X \= 0, g(Xs).

main :-
    get_number(N),
    get_numbers(N, Xs),
    (\+ g(Xs) -> writeln("0") ; (f(Xs, 1, Z) , writeln(Z))).


Measured memory_bytes: 15540
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int h, w, n;
char m[1002][1002];
int d[1002][1002];
char nc[10] = {'S', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

void dfs(int x, int y, char goal, int depth) {
    if (d[x][y] > depth) {
        d[x][y] = depth;
        if (m[x][y] != 'X') {
            dfs(x + 1, y, goal, depth + 1);
            dfs(x - 1, y, goal, depth + 1);
            dfs(x, y + 1, goal, depth + 1);
            dfs(x, y - 1, goal, depth + 1);
        }
    }
}

int main(void) {
    cin >> h >> w >> n;
    string temp;
    for (int i = 0; i < 1002; i++)
        for (int j = 0; j < 1002; j++)
            m[i][j] = 'X';
    pair<int, int> pos[10];
    for (int y = 0; y < h; y++) {
        cin >> temp;
        for (int x = 0; x < w; x++) {
            m[x + 1][y + 1] = temp[x];
            for (int i = 0; i < 10; i++) {
                if (m[x + 1][y + 1] == nc[i])
                    pos[i] = make_pair(x + 1, y + 1);
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int x = 0; x < 1002; x++) {
            for (int y = 0; y < 1002; y++) {
                d[x][y] = 1000000;
            }
        }
        dfs(pos[i].first, pos[i].second, nc[i + 1], 0);
        res += d[pos[i + 1].first][pos[i + 1].second];
    }
    cout << res << endl;
}


Measured memory_bytes: 14800
#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string s, strCopy;
    while (getline(cin, s)) {
        for(int j=0 ; j<26 ; j++){
            for(int i=0 ; i<s.size() ; i++){
                if(s[i]>='a' && s[i]<='z'){
                    s[i] = (s[i]=='z')? 'a' : s[i] + 1;
                }
            }
            if( s.find( "the" ) != string::npos ||
                s.find( "this" ) != string::npos ||
                s.find( "that" ) != string::npos){
                cout << s << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1176
N, M = map(int, input().split())

div = [(1, M), (M, 1)]
for i in range(2, int(M ** 0.5) + 1):
    if M % i == 0:
        div.append((i, M // i))
        if i * i != M:
            div.append((M // i, i))

ans = 1
for num, cnt in div:
    if cnt >= N:
        ans = max(ans, num)

print(ans)


Measured memory_bytes: 3188
# encoding:utf-8

import copy
import numpy as np
import random
# import headpq

n,m = map(int,input().split())

x = [int(i) for i in input().split()]

x_sorted = sorted(x)
dif_list = []
for i in range(m-1):
    dif_list.append(x_sorted[i+1]-x_sorted[i])

dif_list = sorted(dif_list)
answer = 0
for i in range((m-1)-(n-1)):
    answer += dif_list[i]

print(answer)


Measured memory_bytes: 23096
#pragma region includes, macros
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <stdlib.h>
#include <cassert>
#include<iomanip>

using namespace std;
 
typedef int64_t i64;
typedef pair<i64, i64> P;

template<class T>
const T INF = numeric_limits<T>::max();
template<class T>
const T SINF = numeric_limits<T>::max() / 10;
static const i64 MOD = 1000000007;

//int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
//int dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//int dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//int dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

struct edge {
	i64 from, to, cost;
	edge(i64 to, i64 cost) : from(-1), to(to), cost(cost) {}
	edge(i64 src, i64 to, i64 cost) : from(src), to(to), cost(cost) {}
};

// 多重vectorを可変引数テンプレートで http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}
//

#pragma endregion

int main(){
    cout<<std::defaultfloat<<std::setprecision(6);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	i64 n, k;
    cin >> n >> k;
    vector<i64> p(n);
    for(i64 i = 0; i < n; ++i) cin >> p[i];
    vector<i64> wa(n + 1);
    for(i64 i = 0; i < n; ++i) wa[i + 1] = wa[i] + p[i];
    i64 ans = 0;
    for(i64 i = 0; i < n - k + 1; ++i){
        ans = max(ans, wa[i + k] - wa[i] + k);
    }
    cout <<  std::setprecision(10) << ((long double)ans) / 2.0L << endl;
}

Measured memory_bytes: 3456
from itertools import product
xyh = []
xyh0 = []
N=int(input())
for _ in range(N):
    tmp1, tmp2, tmp3 = map(int, input().split())
    if tmp3 > 0:
        xyh.append((tmp1, tmp2, tmp3))
    else:
        xyh0.append((tmp1, tmp2, tmp3))
ans = None
for cx, cy in product(range(101), repeat=2):
    H = None
    H_lower = 1
    H_upper = 10**100
    is_ok = 1
    for x, y, h in xyh:
        if H is None:
            H = abs(x-cx)+abs(y-cy)+h
        else:
            if H != abs(x-cx)+abs(y-cy)+h:
                is_ok = 0
                break
    if not is_ok or H is None:
        continue
    for x, y, h in xyh0:
        H_upper = min(H_upper, abs(x-cx)+abs(y-cy))
    if H > H_upper or H < H_lower:
        continue
    ans = (cx, cy, H)
    break

print(*ans)

Measured memory_bytes: 73728
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*
        PEOPLE'S LIVES DON'T END WHEN THEY DIE.
        IT ENDS WHEN THEY LOSE FAITH
                                     -ITACHI UCHIHA
        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
void solve()
{
    ll n,m;cin>>n>>m;
    cout<<(n*(n-1)/2)+(m*(m-1)/2)<<"\n";
}
int main()
{
   fastio
   solve();
  return 0;
}


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

//Author: Varun Goyal (@govarun)

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef GOVARUN
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define f(i, n) for(int i=0;i<(n);++i)
#define fa(i, a, n) for(int i=(a);i<=(n);++i)
#define fd(i, a, n) for(int i=(a);i>=(n);--i)
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define endl '\n'
typedef long double ld;
typedef long long ll;
typedef vector<ll> vl;      typedef vector<int> vi;
typedef vector<vl> vvl;     typedef vector<vi> vvi;
typedef pair<ll, ll> pll;   typedef pair<int, int> pii;
inline bool EQ(double a, double b) {return fabs(a-b) < 1e-9;}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*(b/gcd(a, b));}
ll binexp(ll a, ll b, ll mod){ll ans = 1;while(b){if(b&1) ans = ans*a%mod; b/=2;a=a*a%mod;}return ans;}
ll inverse(ll a, ll p, ll mod){return binexp(a, p-2, mod);}
// bool sortbysec(const pll &a, const pll &b){return (a.second < b.second);} 
void createadj(vvl& adj, ll m){ll x, y; f(i, m){cin>>x>>y;x--, y--;adj[x].pb(y);adj[y].pb(x);}}

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
void pre(){

}
void solve() {
    int k; cin >> k;
    for (int i = 0; i < k; ++i) cout << "ACL";
    
}

int main(){
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    #ifdef GOVARUN
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    #define GOVARUN 0
    #endif
    int TC = 1;
    // cin >> TC;
    pre();
    while(TC--){    
        solve();
        cout << "\n";
    }
    return 0;
}



Measured memory_bytes: 3584
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define mod (1e9 + 7)
#define pb push_back
#define ll long long int
using namespace std;
typedef pair<int,int> pii;

int main(){

  int a,b;
  cin>>a>>b;
  
  if((a+b)%2==0) cout<<(a+b)/2<<endl;
  else cout<<"IMPOSSIBLE"<<endl;
  
  return 0;
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func check(e error) {
	if e != nil {
		log.Fatalf("error: %v", e)
	}
}

func digitSum(num int) (sum int) {
	strN := strconv.Itoa(num)
	for i := 0; i < len(strN); i++ {
		add, err := strconv.Atoi(strN[i : i+1])
		check(err)
		sum += add
	}
	return
}

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	input := strings.Split(stdin.Text(), " ")

	n, err := strconv.Atoi(input[0])
	check(err)
	a, err := strconv.Atoi(input[1])
	check(err)
	b, err := strconv.Atoi(input[2])
	check(err)

	var sum int
	for i := 1; i <= n; i++ {
		if dsum := digitSum(i); a <= dsum && dsum <= b {
			sum += i
		}
	}

	fmt.Println(sum)
}

Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
A = [0] + A

from collections import Counter

L1 = [i+a for i, a in enumerate(A)][1:]
L2 = [i-a for i, a in enumerate(A)][1:]

C1 = Counter(L1)
C2 = Counter(L2)
C = Counter(L1+L2)

ans = 0
for k in C.keys():
    ans += C1[k]*C2[k]
print(ans)

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

int main() {
  int N;
  cin >> N;
  int t=N;
  int sum=0;

  for(int i=0;i<9;i++){
    int a = t%10;
    sum+=a;
    t = t/10;
    if (t==0){
      break;
    }

  }
//cout << sum << endl;
if(N%sum==0){
  cout << "Yes" << endl;
}
else{
  cout << "No" << endl;
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int n;
ll a,b,c,d,f[N<<1],invf[N<<1];
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
ll C(ll n,ll m)
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
int main()
{
    f[0]=invf[0]=1;
    for(int i=1;i<N<<1;i++)
        f[i]=f[i-1]*i%mod,invf[i]=qpow(f[i],mod-2);
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    a=a*qpow(100,mod-2)%mod;b=b*qpow(100,mod-2)%mod;d=100*qpow(100-c,mod-2)%mod;
    a=a*d%mod;b=b*d%mod;
    ll ans=0;
    for(int i=n;i<n*2;i++)
        ans=(ans+(qpow(a,n)*qpow(b,i-n)%mod+qpow(b,n)*qpow(a,i-n)%mod)*C(i-1,n-1)%mod*d%mod*i%mod)%mod;
    printf("%lld\n",ans);
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

string s;
int n,m;
vector<int> ans;
int main(){
    cin>>n>>m;
    cin>>s;
    int cur=n;
    while(cur!=0){
        int nx=-1;
        for(int i=m;i>0;--i)if(cur-i>=0){
            if(s[cur-i]=='0'){
                nx=i;
                cur=cur-i;
                break;
            }
        }
        if(nx!=-1) ans.pb(nx);
        else{
            cout<<-1<<endl;
            return 0;
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto it:ans) cout<<it<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 1144
from collections import deque
n = int(input())

a = 0
b = 0
tm = 0
while a < n:
    tm += 1
    b = a
    a += 26 ** tm

def base_10_to_n(x, n, tm):
    A = deque([])
    while x > 0:
        A.appendleft(x%n)
        x = int(x/n)
    if len(A) < tm:
        for i in range(tm - len(A)):
            A.appendleft(0)
    else:
        pass
    return A
    
#print(n-b-1)
L = base_10_to_n(n - b - 1, 26, tm)

#print(a)
#print(L)
ans = ''
for i in L:
    ans += chr(i + 97)
print(ans)

Measured memory_bytes: 9356
#include<stdio.h>

int main(){
	int min=100000;
	int N,T;
	scanf("%d%d",&N,&T);
	for(int i=0;i<N;i++){
		int c,t;
		scanf("%d%d",&c,&t);
		if(t<=T && c<min)min=c;
	}
	if(min==100000)printf("TLE\n");
	else printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
//	f(n,k) = (f(n-1,k) + k) Mod n (ただし、f(1,k) = 0)
	
	static int[] dp;
	static int f(int n,int k){
		dp[1]=0;
		for (int i = 2; i < dp.length; i++) {
			dp[i] = (dp[i-1]+k)%i;
		}
		return dp[n-1];
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		if(true){
			// yosefusu
			while(true){
				int n = sc.nextInt();	
				int k = sc.nextInt();	
				int m = sc.nextInt()-1;
				if(n+k+m<=0)break;
				dp=new int[n];
				Arrays.fill(dp, -1);
				int f = f(n,k);
				System.out.println(((f+m+1+n)%n+1));
			}
			return;
		}
		while(true){
			int n = sc.nextInt();	
			int k = sc.nextInt();	
			int m = sc.nextInt()-1;
			if(n+k+m<=0)break;
			List<Integer>list= new LinkedList<Integer>();
			for (int i = 0; i < n; i++) {
				list.add(i);
			}
			int cur = m;
			list.remove(cur);
			cur--;

			for (int j = 0; j < n-2; j++) {
//				for (int i = 0; i < k; i++) {
//					cur = (cur+1)%list.size();
//				}
				cur = (list.size()+cur+k%list.size())%list.size();
				list.remove(cur);
				cur--;
			}
			System.out.println(list.get(0)+1);
		}

	}

}

Measured memory_bytes: 23248
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rfor(i,a,b) for(ll (i) = (a); (i) > (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(a) cout << (a) << endl;
#define all(x) (x).begin(),(x).end()

ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    for (ll d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

int main()
{
    ll n,k,ans = 0;
    cin >> n >> k;
    if(k % 2 == 0){
        ll cnt1 = 0,cnt2 = 0;
        rep1(i, n){
            if(i % k == 0)++cnt1;
            else if(i % k == k / 2)++cnt2;
        }
        ans = cnt1 * cnt1 * cnt1 + cnt2 * cnt2 * cnt2;
    }else{
        ll cnt = 0;
        rep1(i, n){
            if(i % k == 0)++cnt;
        }
        ans = cnt * cnt * cnt;
    }
    pf(ans)
    return 0;
}


Measured memory_bytes: 256
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin >> n;
  int count = 0;
  vector<int>a(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  rep(i,n-1){
    if(a.at(i) == a.at(i+1))count++;
  }
    cout << n - count << endl;
}

Measured memory_bytes: 256
// edpc_b
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#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 REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (int)(2e9)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int N, K;
vector<int> H;
vector<int> memo;

int dp_func(int i){

    if (i == N-1) return 0;

    if (memo[i] != -1) return memo[i];

    int tmp = INF;
    REPN(k, 1, K+1) {
        if (i + k >= N) break;
        tmp = min(tmp, dp_func(i+k) + abs(H[i] - H[i+k]));
    }

    return memo[i] = tmp;
};


int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    cin >> N >> K;
    H.assign(N, 0);
    REP(i, N) cin >> H[i];

    memo.assign(N, -1);

    int ans = dp_func(0);
    print(ans);

    return 0;
}



Measured memory_bytes: 5760
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split("[\\s]+");
        int D = Integer.parseInt(inputs[0]);
        int N = Integer.parseInt(inputs[1]);
        int num = 1;
        for(int i = 0; i < D; i++) {
          num = num * 100;
        }
        if(N == 100) {
            N += 1;
        }
        System.out.println(num * N);
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<cmath>
#include<iomanip>
#include <cstdio>
using namespace std;

int main()
{
	int a, b, h, m;
	double xita, ans;
	cin >> a >> b >> h >> m;
	xita = abs(h * 30.0 +m * 0.5 - 6.0 * m);
	
	ans = sqrt(a * a + b * b - 2.0 * a * b * cos(1.0*xita * acos(-1) / 180.0));
	cout <<fixed<<setprecision(20) <<ans << endl;
	
	return 0;
 } 

Measured memory_bytes: 4184
#include <bits/stdc++.h>
using namespace std;
#define  ft   ios_base::sync_with_stdio(false);cin.tie(NULL);
#define  pb   push_back
#define  ll   long long
#define  pi   pair<int,int>
#define  F    first
#define  S    second
const int N=2e5+3;
string s,p;
//map<string,int>mp;
//vector<int,int>v;

int main()
{
    ft
    int t,i,j,n,m;
    cin>>s;
    for(char c:s)
    {
        if(c==',')
        {
            cout<<" ";
        }
        else
        {
            cout<<c;
        }
    }
    return 0;
}


Measured memory_bytes: 256
# AGC017A - Biscuits
def main():
    N, P, *A = map(int, open(0).read().split())
    total = sum(i % 2 for i in A)
    if total == 0:  # all numbers are even
        flg = P == 0
        print(2 ** N if flg else 0)
    else:
        print(2 ** (N - 1))


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
  int n, p[10], ans = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> p[i];
    ans += p[i];
  }
  sort(p, p + n, greater<int>());
  ans -= p[0] / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int l[n];
  int max=0;
  int index;
  for(int i=0;i<n;i++){
    cin>>l[i];
    if(l[i]>max){
      max = l[i];
      index = i;
    }
  }
  
  int sum = 0;
  for(int i=0;i<n;i++){
    if(i==index){
      continue;
    }else{
      sum += l[i];
    }
  }
  
  if(max < sum){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  if(s.size() == 3){
    cout << s.at(2) << s.at(1) << s.at(0) << endl;
  }
  else{
    cout << s << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import numpy as np
n = int(input())
SP=[]
SPs=[]
for i in range(n):
    SP=[i]
    for j in input().split():
        SP.append(j)
    SPs.append(SP)
SPs=np.array(SPs)

SPs2=SPs[SPs[:,2].astype(int).argsort(kind="mergesort")[::-1],:]
SPs3=SPs2[SPs2[:,1].argsort(kind="mergesort"),:][:,0]

for i in range(n):
    print(int(SPs3[i])+1)


Measured memory_bytes: 12512
#include <stdio.h>
#include <math.h>
double point[100][3];
int check(int i,int j,int k,int n) {
	double x1,x2,x3,y1,y2,y3,xp,yp,ax,ay,bx,by,cx,cy,a,b;
	int x,ans;

	x1=point[i][0];y1=point[i][1];
	x2=point[j][0];y2=point[j][1];
	x3=point[k][0];y3=point[k][1];
	ax=x2-x1; ay=y2-y1;
	bx=x3-x1; by=y3-y1;
	ans=0;

	for(x=0;x<n;x++){
		if(point[x][2]<1 || x==i || x==j || x==k)continue;
		xp=point[x][0];yp=point[x][1];
		cx=xp-x1; cy=yp-y1;
		if(by!=0){
			a=(cx*by-cy*bx)/(ax*by-ay*bx);
			b=(cy-a*ay)/by;
		}
		else{
			a=cy/ay;
			b=(cx-a*ax)/bx;
		}
		if(a>=0 && b>=0 && a+b<=1){ans++;point[x][2]=0;}
	}

	return ans;
}
int main(void){
	int i,j,k,n,ans;
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		ans=0;
		for(i=0;i<n;i++){scanf("%lf,%lf",&point[i][0],&point[i][1]);point[i][2]=1;}

		for(i=0;i<n-2;i++){if(point[i][2]<1)continue;
		for(j=i+1;j<n-1;j++){if(point[j][2]<1)continue;
		for(k=j+1;k<n;k++){if(point[k][2]<1)continue;
		ans+=check(i,j,k,n);
		}
		}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000005
#define MOD 1000000007 
#define N 100005
#define M 1000000
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

int mx,dia,n;
int sub[N],dad[N];
vector<int> v[N];

void dfs(int node,int ata,int dst) {

	dad[node]=ata;
	sub[node]=1;

	if(dst>mx) {

		mx=dst;
		dia=node;

	}

	for(auto x:v[node]) {

		if(x==ata) continue ;

		dfs(x,node,dst+1);

		sub[node]+=sub[x];

	}

}

vector<int> ans;
vector<int> cur;
int val;

void dfs2(int node,int ata) {

	int leaf=0;
	int non=0;

	for(int x:v[node]) {

		if(x==ata) continue ;

		leaf+=(sub[x]==1);
		non+=!(sub[x]==1);

	}

	if(non>1) return ;

	if(non) {

		int tut=++val;

		for(int i=1;i<=leaf;i++) {

			cur.pb(++val);

		}

		cur.pb(tut);

		for(int x:v[node]) {

			if(x==ata || sub[x]==1) continue ;

			dfs2(x,node);

		}
	
	}
	else {

		int tut=++val;

		for(int i=1;i<leaf;i++) {

			cur.pb(++val);

		}

		cur.pb(tut);
		cur.pb(++val);

		if(!sz(ans)) ans=cur;
		else umin(ans,cur);

	}

}

void solve(int node) {

	cur.clear();
	val=0;

	dfs(node,0,0);

	dfs2(node,0);

}

int main() {

	int root=1;

	scanf("%d",&n);

	for(int i=1;i<n;i++) {

		int x,y;

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

		if(sz(v[x])>1) root=x;
		if(sz(v[y])>1) root=y;

	}

	vector<int> cd;

	mx=0;
	dfs(root,0,0);

	cd.pb(dia);

	mx=0;
	dfs(dia,0,0);

	cd.pb(dia);

	solve(cd[0]);
	solve(cd[1]);

	dfs(root,0,0);

	solve(dad[cd[0]]);
	solve(dad[cd[1]]);

	if(ans.empty()) printf("-1");
	else for(auto x:ans) printf("%d ",x);

}	

Measured memory_bytes: 15736
//Himanshu Manwani..
//coin problem - i
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ul unsigned long int
#define ld long double
#define f(t) for(ll i =0;i<t;i++)
#define vi vector<int>
#define vl vector<ll>
#define pri pair<int,int>
#define mpi map<int,int>
#define prl pair<ll,ll>
#define mp make_pair
#define mpl map<ll,ll>
#define umpl unordered_map<ll,ll>
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define inf 2e18
#define EPS 1e-3
#define PI 3.1415926535897932385
const double h = 1e-6;
const int MAX_  = 100005;

inline ll mul(ll a, ll b){ return (a * 1ll * b) % MOD; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += MOD; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > MOD) c -= MOD; return c; }
 //////////////////////*********CODE***********/////////////////////
 //////////////////////////////////////////////////////////////////

int main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout.precision(11);
    cout << fixed;
    int n;
    cin>>n;
    vector<double> dp(n+1);
    dp[0] = 1;
    double pro;
    for(int c = 0;c<n;c++)      //c -> coin
    {
        cin>>pro;
        for(int i = c+1;i>=0;i--)
        {
            if(i==0)
            {
                dp[i] = dp[i]*(1-pro);
            }
            else
            {
                dp[i] = dp[i-1]*pro + dp[i] * (1-pro) ;
            }
        }
    }
    int xx = n/2 -1;
    double ans = 0.0;
    //f(n+1)cout <<dp[i]<< "  ";
    for(int i =xx;i<=n;i++)
    {
        if(i*2 > n)
        {
            ans += dp[i];
        }
    }cout << ans;
    
    return 0;
 }

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

using namespace std;

const int N = 1234567;

int a[N];
int d[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  a[n] = a[0];
  int mx = 0;
  for (int i = 0; i < n; i++) {
    d[i] = a[i + 1] - a[i];
    mx = max(mx, d[i]);
  }
  int ops = mx;
  for (int i = 0; i < n; i++) {
    if ((ops - d[i]) % n != 0) {
      puts("NO");
      return 0;
    }
  }
  long long total = 0;
  for (int i = 0; i < n; i++) {
    total += a[i];
  }
  long long z = n * 1LL * (n + 1) / 2;
  long long need = ops * z;
  long long useless = n * z;
  if (need > total || (total - need) % useless != 0) {
    puts("NO");
    return 0;
  }
  puts("YES");
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> T(N);
  for (auto & t : T)
    cin >> t;
  auto sum = accumulate(T.begin(), T.end(), 0);
  int M;
  cin >> M;
  for (int i = 0; i < M; ++i)
  {
    int P, X;
    cin >> P >> X;
    cout << sum + X - T[P - 1] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
icase=0
if icase==0:
    n,x=map(int,input().split())
    l=list(map(int,input().split()))
    d=0
    for i in range(n):
        d=d+l[i]
        if d>x:
            print(i+1)
            break
    if d<=x:
        print(n+1)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long INF = 1e9 + 7;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	vector<int> p(3);
	cin >> p[0] >> p[1] >> p[2];
	sort(p.begin(), p.end());
	cout << p[0] + p[1] << endl;
	return 0;
}

Measured memory_bytes: 256
function Main(input) {
	//input = input.split("\n");
	//tmp1 = parseInt(input[0]);
	//tmp2 = input[1].split(" ");

	var input = parseInt(input);
	var ans = 0;

	for (i = 0; i <= input; i++) {
		ans += i;
	}

	console.log('%d', ans);

}

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

Measured memory_bytes: 7372
#include <iostream>
using namespace std;
int main(){
    int N,max=0;std::cin>>N;
    unsigned long long int sum=0;
    int p[10];
    for(int i=0; i<N; i++){
        cin>>p[i];
        sum+=p[i];
        if(max<p[i])
            max=p[i];
    }
    cout<<sum-(max/2);
    return 0;
}

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

#define int long long
const int MOD=1e9+7;
int pw(int n,int k){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}
std::vector<int> Factorial(5e6),Finverse(5e6);
inline void Cinit(){// limit is 5e6 /// write pw /// this takes 792ms at AtCoder
  Factorial[0]=1;
  for(int i=1;i<5e6;i++)Factorial[i]=(Factorial[i-1]*i)%MOD;
  for(int i=0;i<5e6;i++)Finverse[i]=pw(Factorial[i],MOD-2);
}
int nCk(int n,int k){
  if(n<k)return 0;if(k<0)return 0;
  if(!Factorial[0])Cinit();
  int res=Factorial[n];
  (res*=Finverse[k])%=MOD;
  (res*=Finverse[n-k])%=MOD;
  return res;
}
void f(int &a){
  a%=MOD;if(a<0)a+=MOD;
}
void tasu(int &a,int b){
  f(a+=b);
}
void hiku(int &a,int b){
  f(a-=b);
}
int seki(int a,int b){
  f(a);f(b);
  return a*b%MOD;
}

struct wall{int r,c;};
bool cmp(wall a,wall b){return a.r+a.c<b.r+b.c;}
int dp[3001][2],ans;//dp[i][j]:最後に訪れた壁がiで偶奇j個目の時の通り数

signed main(){
  int h,w,n;cin>>h>>w>>n;
  vector<wall> v(n);
  for(int i=0;i<n;i++){
    int r,c;cin>>r>>c;
    v[i]={r,c};
  }
  v.push_back({1,1});//スタートに壁があると考えると求めるものが壁を通る道の数1つになって簡単
  sort(v.begin(),v.end(),cmp);

  dp[0][1]=1;//(1,1)を0つ目の壁として通るパターンは1通り
  for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
      for(int k=0;k<2;k++)
        tasu(dp[i][k],seki(dp[j][k^1],nCk(v[i].r-v[j].r+v[i].c-v[j].c,v[i].r-v[j].r)));

  for(int i=0;i<=n;i++)
    for(int k=0;k<2;k++)
      if(k)tasu(ans,seki(dp[i][k],nCk(h-v[i].r+w-v[i].c,h-v[i].r)));
      else hiku(ans,seki(dp[i][k],nCk(h-v[i].r+w-v[i].c,h-v[i].r)));

  cout<<ans<<endl;
}


Measured memory_bytes: 78464
N = int(input())
X = list(map(int,input().split()))
M = max(X)
m = min(X)
ans = 10**6
for i in range(m,M+1) :
    p = list(map(lambda x : (x - i)**2 ,X))
    s = sum(p)
    ans = min(ans,s)
print(ans)

Measured memory_bytes: 9132
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
    int a,n,k,aa,bb;
    scanf("%d",&n);
    char s[n+1];
    scanf("%s",s);
    scanf("%d",&k);
    k-=1;
    for(a=0;a<n;a++){
        aa=s[k];
        bb=s[a];
        if(aa==bb){
            printf("%c",s[a]);
        }else{
            printf("*");
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

ll gcd(ll a, ll b){
    ll r,temp;
    if (a < b){
        temp = a;
        a = b;
        b = temp;
    }
    while ( (r = a % b) != 0){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    ll A,B;
    cin >> A >> B;
    ll ans = 1;
    ll X = gcd(A,B);
    vector<bool> vec(1000001);
    rep(i,1000001){
        vec[i] = true;
    }
    vec[0] = false;
    vec[1] = false;
    for (ll i = 2; i < 1000001; i++){
        if (vec[i]){
            for (ll j = 2 * i; j < 1000001; j += i){
                vec[j] = false;
            }
        }
    }
    /*int X;
    cin >> X;
    if (vec[X]) cout <<"Yes"<<endl;*/
    for (ll i = 1; i < 1000001; i++){
        if (vec[i]){
            if (A % i == 0 && B % i == 0){
                ans++;
                while (X % i == 0){
                    X /= i;
                }
            }
        }
    }
    if (X >= 1000001){
        ans++;
    }
    cout << ans << endl;
}


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





int main(){
  



  int n,k;
  cin>>n>>k;
  
  vector<int> data(n);
  
  for (int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    data.at(i)=tmp;
  }
  
  
  vector<int> count(200001,0);
  
  for (int i=0;i<n;i++){
    count.at(data.at(i))++;
  }
  
  sort(count.begin(),count.end());
  
  int plusindex;
  
  for (int i=0;i<=200000;i++){
    if (count.at(i)>0){
    plusindex=i;
      break;
    }
  }
  
  int kinds=200000-plusindex+1;
  
  int answer=0;
  
  if (kinds<=k){
    answer=0;
  }
  
  else {
    for (int i=plusindex;i<=200000-k;i++){
      answer+=count.at(i);
    }
  }
  
  cout<<answer<<endl;
  
    
    
  
    
    
    

      
  
    

  
  
    
  
  
  
}

Measured memory_bytes: 1792
s = list(input())
cnt1 = 0
cnt2 = 0
for i in range(len(s)):
    if i%2 == 0:
        if s[i] =="0":
            cnt2 += 1
        else: cnt1 += 1
    elif i%2 == 1:
        if s[i] =="0":
            cnt1 += 1
        else: cnt2 += 1
print(min(cnt1,cnt2))


Measured memory_bytes: 3956