akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
struct C{
	P p;D r;
	C(P p,D r):p(p),r(r){}
};
D eps=1e-9,PI=acos(-1);
bool eq(D a,D b){return abs(a-b)<eps;}
bool eq(P a,P b){return abs(a-b)<eps;}
int sig(D a){return eq(a,0)?0:(a>0?1:-1);}
int large(D a,D b){return eq(a,b)?0:(a>b?1:-1);}
D dot(P a,P b){return real(conj(a)*b);}
P perp(L l,P p){
	D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc);
	return l.fs+t*(l.fs-l.sc);
}
vector<L> tanCP(C c,P p){
	int x=large(c.r,abs(p-c.p));
	vector<L> ret;
	if(x==1) return ret;
	if(x==0){
		ret.pb(L(p,p+(c.p-p)*P(0,1)));
		return ret;
	}
	D theta=acos(c.r/abs(p-c.p));
	ret.pb(L(p,c.p+(p-c.p)/abs(p-c.p)*polar(c.r,theta)));
	ret.pb(L(p,c.p+(p-c.p)/abs(p-c.p)*polar(c.r,-theta)));
	return ret;
}
vector<L> intan(C a,C b){
	P p=(a.r*b.p+b.r*a.p)/(a.r+b.r);
	return tanCP(a,p);
}
vector<L> outtan(C a,C b){
	if(eq(a.r,b.r)){
		vector<L> ret;
		P p=(a.p-b.p)/abs(a.p-b.p)*polar(a.r,PI/2);
		ret.pb(L(a.p+p,b.p+p));
		ret.pb(L(a.p-p,b.p-p));
		return ret;
	}
	P p=(a.r*b.p-b.r*a.p)/(a.r-b.r);
	return tanCP(a,p);
}
inline D dLP(L l, P p) { return abs(perp(l,p)-p);}
int iCL(C c,L l){
	D d=dLP(l,c.p);
	return eq(d,c.r)?1:(d<c.r?2:0);
}
typedef pair<P,int> Pp;
L BL;
bool compBLp(Pp &aa,Pp &bb){
	P a=aa.fs,b=bb.fs;
	return dot(BL.sc-BL.fs,a-BL.fs)<dot(BL.sc-BL.fs,b-BL.fs);
}
bool can[1<<16];
int N;
int dp[1<<16];
vector<C> cs;
vector<L> ls;
int main(){
	cin>>N;
	rep(i,N){
		int x,y,r;
		cin>>x>>y>>r;
		cs.pb(C(P(x,y),r));
	}
	rep(i,N) rep(j,i){
		vector<L> vl=intan(cs[i],cs[j]);
		ls.insert(ls.end(),all(vl));
		vl=outtan(cs[i],cs[j]);
		ls.insert(ls.end(),all(vl));
	}
	for(L l:ls){
		vector<Pp> ps;
		rep(i,N){
			if(iCL(cs[i],l)>=1) ps.pb(Pp(perp(l,cs[i].p),i));
		}
		BL=l;
		sort(all(ps),compBLp);
		int o=-1;
		int K=ps.size();
		rep(i,K) if(ps[i].sc==0) o=i;
		if(o==-1) continue;
		int x=1;
		rep(i,o) x|=(1<<ps[i].sc);
		can[x]=1;
		x=1;
		for(int i=o+1;i<K;i++) x|=(1<<ps[i].sc);
		can[x]=1;
	}
	can[0]=1;
	rep(i,N) can[1|(1<<i)]=1;
//	rep(i,1<<N) printf("can[%d]=%d\n",i,can[i]);
//	puts("");
	rep(i,1<<N){
		if(!can[i]) continue;
		int a=i;
		int j=a;
		do{
			can[j]=1;
			j=(j-1)&a;
		}while(a!=j);
	}
//	rep(i,1<<N) show(can[i]);
	rep(i,1<<N) dp[i]=1e9;
	dp[0]=0;
	rep(i,1<<N){
		int a=(1<<N)-1-i;
		int j=a;
		do{
			if(can[j]) chmin(dp[i|j],dp[i]+1);
			j=(j-1)&a;
		}while(a!=j);
	}
	cout<<dp[(1<<N)-1]<<endl;
}

Measured memory_bytes: 3668
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1LL<<50
#define fst first
#define snd second
#define pb push_back
#define int long long
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(int itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(int itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define debug(x)  cout << #x << " = " << (x) << endl;
typedef long long ll;
typedef pair<ll,ll> P;

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

  int n;
  cin >> n;
  
  int a[3*n];
  REP(i,3*n) cin >> a[i];
  
  sort(a,a+3*n);
  
  ll ans = 0;
  REP(i,n){
    ans += a[3*n-2-i*2];
  }
  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2560
n = int(input())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))
xlst = []
ylst = []
for a, b in zip(alst, blst):
    if a < b:
        xlst.append(b - a)
    if a > b:
        ylst.append(a - b)

total = sum(xlst)
ans = len(xlst)
ylst.sort(reverse=True)
if total == 0:
    print(ans)
else:
    for y in ylst:
        total -= y
        ans += 1
        if total <= 0:
            print(ans)
            break
    else:
        print(-1)

Measured memory_bytes: 83248
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
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);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

map<string,ll> mp;
template<class Type>
Type solve(Type res = Type()){
    ll N; cin >> N;
    vector<string> s(N);
    for(auto& in:s){
        cin >> in;
        sort(in.begin(),in.end());
        mp[in]++;
    }
    
    for(int i = 0; i < N;i++){
        res += mp[s[i]]-1;
    }
    res /= 2;
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A; int V; int B; int W; int T;
  cin >> A >> V >> B >> W >> T;
  
  string hantei="NO";
  
//  if(W >= V && abs(A-B)/(V-W) >= T){
  int distance=abs(A-B);
  double speed=abs(V-W);
  double Ta=distance/speed;
  if(speed==0){
    hantei="NO";
  }else if(V >= W && T>=Ta){
    hantei="YES";
  }
    
  
  cout << hantei << endl;
}


Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main(void){
    int a, b, c, d, e, k;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cin >> e;
    cin >> k;
    if (e - a <= k) cout << "Yay!" << endl;
    else cout << ":(" << endl;
}


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

using namespace std;

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> vec(h);
  for (auto &v : vec)
    cin >> v;

  vector<int> hidx, widx;
  for (int i = 0; i < h; ++i) {
    bool flag = false;
    for (int j = 0; j < w; ++j)
      if (vec[i][j] == '#')
        flag = true; 
    if (flag)
      hidx.push_back(i);
  }

  for (int i = 0; i < w; ++i) {
    bool flag = false;
    for (int j = 0; j < h; ++j)
      if (vec[j][i] == '#')
        flag = true;
    if (flag)
      widx.push_back(i);
  }

  for (auto &i : hidx) {
    for (auto &j : widx)
      cout << vec[i][j];
    cout << endl;
  }
}


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

using namespace std;

int main() {
    int n, ans = 1e5;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int k = 0, in;
        cin >> in;
        while (in % 2 == 0) {
            in /= 2;
            ++k;
        }
        ans = min(ans, k);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int msk[15];

void f(int pos) {
	if (pos < 0) {
		for (int i = n - 1; i >= 0; i--) putchar(msk[i] + 'a');
		puts(""); return;
	}
	int max_val = 0;
	for (int i = n - 1; i > pos; i--) {
		max_val = max(max_val, msk[i]);
	}
	for (int i = 0; i <= max_val + 1; i++) {
		msk[pos] = i;
		f(pos - 1);
	}
}

void doit(int k) {
	msk[k - 1] = 1;
	f(k - 2);
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) putchar('a');
	puts("");
	for (int i = 1; i < n; i++) {
		doit(i);
	}
	return 0;
}

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

typedef long long ll;

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n;
	cin>>n;

	map<string, ll> wow;
	string a[110];

	bool yes = 1;
	ll idx = 0;

	while(n--) {

		cin>>a[idx];

		if(idx > 0) {
			if(wow.count(a[idx]) > 0) yes = 0;
			if(a[idx][0] != a[idx-1][a[idx-1].size()-1]) yes = 0;
		}

		wow[a[idx]] = 1;

		idx++;

	}

	if(yes) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		
	Scanner scan = new Scanner(System.in);
		        int i=1;
		        while(true) {
		            int x=scan.nextInt();
		        
		        if(x==0) break;
		        System.out.println("Case "+i+":"+" "+x);
		        i++;
		        }
		        
		    
		
	}

}



Measured memory_bytes: 41784
import math

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

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

x=[]
for i in range(n):
  x.append(list(map(int,input().split())))


ans = 0
for i in range(n):
  for j in range(n-i-1):
    a = i
    b = i+j+1
    t = 0
    for k in range(d):
      t += math.pow(abs(x[a][k] - x[b][k]),2)

    t = math.sqrt(t)
    if(is_integer_num(t)):
      ans += 1

print(ans)

Measured memory_bytes: 3064
import random
def dice(a,b,c,d,e,f,l):
    if l == "N":
        return [b,f,c,d,a,e]
    if l == "S":
        return [e,a,c,d,f,b]
    if l == "E":
        return [d,b,a,f,e,c]
    if l == "W":
        return [c,b,f,a,e,d]
d = list(map(int, input().split()))
s = ["W","N","E","S"]
a,b,c,g,e,f = map(int ,input().split())
j = 0
while j <= 10000:
    k = random.randrange(4)
    d = dice(d[0],d[1],d[2],d[3],d[4],d[5],s[k])
    if d[0] == a and d[1] == b and d[2] == c and d[3] == g and d[4] == e and d[5] == f:
        print("Yes")
        break
    if j == 10000:
        print("No")
    j += 1



Measured memory_bytes: 8176
def sget; gets.chomp; end
def iget; sget.to_i; end
def saget; gets.chomp.split; end
def iaget; saget.map {|a| a.to_i }; end

N, K, X, Y = 4.times.map { iget }
puts [K, N].min * X + [N-K, 0].max * Y

Measured memory_bytes: 1788
N,M=map(int,input().split())
SC=[list(map(int,input().split())) for i in range(M)]
ans='0'*N
x=[]
for s,c in SC:
  if s==1 and c==0 and N!=1:
    print(-1)
    exit(0)
  if s not in x:
    ans=ans[:s-1]+str(c)+ans[s:]
    x.append(s)
  else:
    if ans[s-1]==str(c):
      continue
    else:
      print(-1)
      exit(0)
if ans[0]=='0' and N>1:
  ans='1'+ans[1:]
print(ans)

Measured memory_bytes: 3064
// 課題4_3 AtCoder Beginner Contest 099 B - Stone Monument
// nk777
 
#include<stdio.h>

// プロトタイプ宣言
int sum(int last);
 
int main(void){
    // 西側の塔(低い方)の見えてるlenW m,東側の塔lenE m, 結果の格納ans
    int lenW, lenE, ans;

    // lenW, lenEを受け取る
    scanf("%d %d", &lenW, &lenE);

    // 西側の塔の地面からの高さ-西の見えてる高さ
    ans = sum(lenE - lenW - 1) - lenW;

    printf("%d\n", ans);
    
    return 0;
}

// 関数の定義
// 1から入力された整数までの和を求める
int sum(int last){
    if (last == 1){
        return 1;
    } else {
        return last + sum(last - 1);
    }
}

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

int main(){
    int n;
    int m;
    int r;
    char s;
    cin>>n;
    int card[4][13]={};
    for(int i=0; i<n;i++){
        cin>>s>>m;
    if(s=='S')r=0;
    if(s=='H')r=1;
    if(s=='C')r=2;
    if(s=='D')r=3;
        card[r][m-1]=1;
    }
    for(int i=0; i<4;i++){
        for(int t=0; t<13; t++){
            if(card[i][t]==0){
                if(i==0)cout<<"S "<<t+1<<endl;
                if(i==1)cout<<"H "<<t+1<<endl;
                if(i==2)cout<<"C "<<t+1<<endl;
                if(i==3)cout<<"D "<<t+1<<endl;
            }
        }
    }
    
    return 0;
}

Measured memory_bytes: 3072
object Main extends App {                                                                                                                                      import scala.util.matching.Regex
  val sc = new java.util.Scanner (System.in)
  val s:String = sc.nextLine
  val pattern:Regex = "(hi)+".r
  val result = s match {
    case pattern(_) => println("Yes")
    case _ => println("No")
  }
}

Measured memory_bytes: 27460
package main

import (
	"bufio"
	"fmt"
	"os"
)

func readLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 100000)
	sc.Buffer(buf, 100000+1024)
	sc.Split(bufio.ScanWords)
	input := readLine(sc)

	blackCount, whiteCount := 0, 0

	for i := 0; i < len(input); i++ {
		if i%2 == 0 {
			if input[i] == '0' {
				whiteCount++
			} else {
				blackCount++
			}
		} else {
			if input[i] == '0' {
				blackCount++
			} else {
				whiteCount++
			}
		}
	}
	if blackCount <= whiteCount {
		fmt.Println(blackCount)
	} else {
		fmt.Println(whiteCount)
	}
}


Measured memory_bytes: 896
#define _CRT_SECURE_NO_DEPRECATE
 #pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
 #define pii pair<int, int>
 #define mod 1000000007
 #define mp make_pair
 #define pi acos(-1)
 #define eps 0.00000001
 #define mst(a,i) memset(a,i,sizeof(a))
 #define all(n) n.begin(),n.end()
 #define lson(x) ((x<<1))  
 #define rson(x) ((x<<1)|1) 
 #define inf 0x3f3f3f3f
 typedef long long ll;
 typedef unsigned long long ull;
 using namespace std;
 const int maxn = 1e5 + 5;
 class node {
 public:
     int u, v, w;
     node(int a, int b, int c) :u(a), v(b), w(c) {};
 };
 int fa[maxn];
 int getf(int i) { return i == fa[i] ? i : fa[i] = getf(fa[i]); }
 vector<node>edge;
 bool cmp(const node&a, const node&b){return a.w < b.w;}
 class T {
 public:
     int value, id;
     bool operator<(const T &a){return value < a.value;}
 };
 T sx[maxn], sy[maxn];
 int main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     int i, j, k, m, n, ta, tb;
     cin >> n;
     for (int i = 1; i <= n; ++i)
         fa[i] = i;
     for (int i = 1; i <= n; ++i)
     {
         cin >> sx[i].value >> sy[i].value;
         sx[i].id = sy[i].id = i;
     }
     sort(sx + 1, sx + n + 1);
     sort(sy + 1, sy + 1 + n);
     for (int i = 1; i < n; ++i)
     {
         edge.push_back(node(sx[i].id, sx[i + 1].id, sx[i+1].value - sx[i].value));
         edge.push_back(node(sy[i].id, sy[i + 1].id, sy[i+1].value - sy[i].value));
     }
     sort(all(edge), cmp);
     ll ans = 0;
     for (int i = 0; i <edge.size(); ++i)
     {
         if (getf(edge[i].u) != getf(edge[i].v))
         {
             ans += edge[i].w;
             fa[getf(edge[i].u)] = getf(edge[i].v);
         }
     }
     cout << ans << endl;
     return 0;
 }

Measured memory_bytes: 6900
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int

struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
ll euclidean_gcd(ll a, ll b) {
  if(a < b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
ll euclidean_lcm(ll a, ll b) {
  return a/euclidean_gcd(a,b)*b;
}

ll binary(ll bina){
    ll ans = 0;
    for (ll i = 0; bina>0 ; i++)
    {
        ans += bina%2;
        bina = bina/2;
    }
    return ans;
}
void revStr(char* str){
	int size = strlen(str);
	int i,j;
	char tmp = {0};
	
	for(i = 0, j = size - 1; i < size / 2; i++, j--){
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
	return;	
}

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(void){
  ll n;
  cin >> n;
  ll d[n],e[n];
  ll a=0;
  rep(i,n){
    cin >> d[i] >> e[i];
    if(d[i]==e[i])a++;
    else a=0;
    if(a==3){
      cout << "Yes";
      return 0;
    }
  }
  cout << "No";
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll m=a*c;
    ll n=a*d;
    ll o=b*c;
    ll p=b*d;
    ll arr[4]={m,n,o,p};
    cout<<*max_element(arr,arr+4)<<endl;
}


Measured memory_bytes: 3648
#include<stdio.h>
#include<math.h>

int main(){
    int n;
    float i,x1, y1, x2, y2, x3, y3, xp, yp,a,b,c,a2,b2,c2,s,S,R;
    scanf("%d",&n);
for(i=0;i<n;i++){
    scanf("%f %f %f %f %f %f",&x1,&y1,&x2,&y2,&x3,&y3);
    
   	    a2=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
   	    b2=(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3);
    	c2=(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);
    	a=sqrt(a2);
        b=sqrt(b2);
        c=sqrt(c2);
    	s=(a+b+c)/2;
     S=sqrt(s*(s-a)*(s-b)*(s-c));
     R=(a*b*c)/(4*S);
     xp=(a2*(b2+c2-a2)*x3+b2*(a2+c2-b2)*x2+c2*(a2+b2-c2)*x1)/(16*S*S);
     yp=(a2*(b2+c2-a2)*y3+b2*(a2+c2-b2)*y2+c2*(a2+b2-c2)*y1)/(16*S*S);
     printf("%.3f %.3f %.3f\n",xp,yp,R);
    }
return 0;
}

Measured memory_bytes: 648
import java.util.*;
import java.lang.*;

class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double p = 0;
        double n = 0;

        if(N == 1){
            p = 1;
        } else if(N % 2 == 0){
            p = 0.5;
        } else if(N % 2 == 1){
            n = (N - 1) / 2;
            p = ((double)N - n) / N;
        }

        System.out.println(p);


    }
}






Measured memory_bytes: 21844
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;

#define REP(i,n) for (ll i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long ll;

int main ()
{
    string S; cin >> S;
    ll ans = 0;
    ll wcnt = 0;
    ll rwcnt = 0;
    REP(i,S.size()) {
        if (S[i] == 'W') {
            wcnt++;
        }
    }
    reverse(S.begin(), S.end());
    REP(i,S.size()) {
        if (S[i] == 'W') {
            wcnt--;
            rwcnt++;
        } else {
            ans += rwcnt;
        }
    }

    cout << ans << endl;

    return 0;
}


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

const int MAXH = 1e5 + 5;
const int MAXW = 1e5 + 5;
const int MOD = 1e9 + 7;

int fact[ MAXH + MAXW ];

int int_pow( int x, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * x % MOD;
        x = 1LL * x * x % MOD;
        p >>= 1;
    }
    return res;
}

int mod_inv( int x ){
    return int_pow( x, MOD - 2 );
}

int get_ways( int h, int w ){
    return 1LL * fact[ h + w - 2 ] * mod_inv( fact[ h - 1 ] ) % MOD * mod_inv( fact[ w - 1 ] ) % MOD;
}

void solve(){
    for( int i = fact[ 0 ] = 1; i < MAXH + MAXW; ++i )
        fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD;

    int H, W, A, B; cin >> H >> W >> A >> B;
    int ans = 0;

    for( int i = B + 1; i <= W; ++i )
        ( ans += 1LL * get_ways( H - A, i ) * get_ways( A, W - i + 1 ) % MOD ) %= MOD;

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    solve();
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9
typedef pair<ll,mp> mmp;

int dx[]={1,-1,0,0};
int dy[] = {0,0,1,-1};
int main(){
	int h,w;
	cin>>h>>w;
	vector<vector<int> > map(h+2,vector<int>(w+2,inf) );
	vector<vector<bool> > used(h+2,vector<bool>(w+2,false) );
	queue<mmp> q;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++){
			char a;
			cin>>a;
			if(a=='#'){
				map[i][j] = 0;
				q.push(mmp(0,mp(i,j) ) );
			}else used[i][j] = true;
		}
	
	while(!q.empty()){
		mmp tmp = q.front();
		q.pop();
		int x = tmp.second.first;
		int y = tmp.second.second;
		int c = tmp.first;
		map[x][y] = c;
		for(int i=0;i<4;i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx<1||nx>h||ny<1||ny>w)continue;
			if(used[nx][ny]){
				q.push(mmp(c+1,mp(nx,ny) ) );
				used[nx][ny] = false;
			}
		}
	}
	int  res = 0;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++) res = max(res,map[i][j]) ;
	cout<<res<<endl;


	return 0;
}


Measured memory_bytes: 28596
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;

vector< pair<int,int> > e;
int N;

int solve(long long k){
	
	if(k==0) return true;
	
	long long sum = 0;
	priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> >  > Q;
	for(int i = 0 ; i < k ; i++){
		int out = e[i].first , in = e[i].second;
		sum += out;
		Q.push(make_pair(in,out));
	}
	
	while(Q.size() && Q.top().first * k < sum){ sum -= Q.top().second; Q.pop(); }
	if( Q.size() >= k) return true;
	
	for(int i = k ; i < N ; i++){
		int out = e[i].first , in = e[i].second;
		Q.push(make_pair(in,out));
		sum += out;
		while(Q.size() && Q.top().first * k < sum){ sum -= Q.top().second; Q.pop(); }
		if( Q.size() >= k) return true;
	}
	
	return false;
}

int main(){
	scanf("%d",&N);
	for(int i = 0 ; i < N ; i++){
		int a,b;
		scanf("%d%d",&a,&b);
		e.push_back(make_pair(a,b));
	}
	sort(e.begin(),e.end());
	long long l = 0 , r = N;
	while(l!=r){
		long long m = (l+r+1)/2;
		if( solve(m) ){
			l = m;
		}else{
			r = m-1;
		}
	}
	printf("%d\n",r);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vector< ll > >;
using vpi = vector<pair<ll,ll> >;
using pi = pair<ll,ll>;
using st = set<ll>;
using kiwi = queue<ll>;
using mp = map<ll,ll>;
using ump = unordered_map<ll,ll>;
#define MOD 1000000007
const ll mx = 1e5+123;
#define REP(i,n) for (ll i=1;i<=n;++i)

#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
    fastio;
    ///freopen("input.txt","r",stdin);
    ///freopen("output.txt","w",stdout);
    ll n; cin>>n;
    if(n>=400&&n<600){
        cout<<8<<endl;
    }
        else if(n>=600&&n<800){
        cout<<7<<endl;
    }
        else if(n>=800&&n<1000){
        cout<<6<<endl;
    }
        else if(n>=1000&&n<1200){
        cout<<5<<endl;
    }
        else if(n>=1200&&n<1400){
        cout<<4<<endl;
    }
        else if(n>=1400&&n<1600){
        cout<<3<<endl;
    }
        else if(n>=1600&&n<1800){
        cout<<2<<endl;
    }
        else if(n>=1800&&n<2000){
        cout<<1<<endl;
    }

return 0;
}


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

int main()
{
	int n, k;
	cin >> n >> k;
	int a;
	map<int, int> mp;
	for (int i = 0; i < n; i++){
		cin >> a;
		mp[a]++;
	}

	vector<int> v;
	int now = mp.size();

	for (auto x : mp){
		v.push_back(x.second);
	}

	sort(v.begin(), v.end());

	long long res = 0;
	int idx = 0;
	while (now-idx > k){
		res += v[idx];
		idx++;
	}

	cout << res << endl;
}


Measured memory_bytes: 10748
N,M=map(int,input().split())
X=input().split()
X=[int(i) for i in X]
X.sort()
Y=[]
for i in range(1,M):
	Y.append(X[i] - X[i-1])
Y.sort(reverse=True)
ans=0
if N < M:
	for i in range(N-1,len(Y)):
		ans += Y[i]
print(ans)

Measured memory_bytes: 15760
n,x,y = map(int, input().split())
t = [0 for i in range(n)]
x = x-1
y = y-1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    b = abs(i-j)
    if a < b:
      t[a-1] += 1
    else:
      t[b-1] += 1

for k in range(0,n-1):
  print(int(t[k]))

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
const int A = 3e2 + 2;
const int mod = 1e9 + 7;
ll ans[A][A], fuel[A][A];
int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m, l;
    cin >> n >> m >> l;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            ans[i][j] = fuel[i][j] = 1e18;
    }
    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        if (l < c) continue;
        fuel[x][y] = fuel[y][x] = c;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (i != j && fuel[i][j] <= l)
                ans[i][j] = 1;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j]);
    }
    int q;
    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        cout << (ans[x][y] == 1e18 ? -1 : ans[x][y] - 1) << '\n';
    }
    return 0;
}

Measured memory_bytes: 5056
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    
    vector<int> X(N);
    for(int i=0;i<N;++i)cin>>X[i];
    
    int ans=INT_MAX;
    for(int i=1;i<=100;++i){
        int cost=0;
        for(const int &x:X)cost+=(x-i)*(x-i);
        ans=min(ans,cost);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
n,y=map(int,input().split())
res10000=-1
res5000=-1
res1000=-1
for a in range(n+1):
  for b in range(n+1-a):
    if 10000*a+5000*b+1000*(n-a-b) == y:
      res10000=a
      res5000=b
      res1000=n-a-b

print(res10000, res5000, res1000)

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

int n,k;
int can[10],num[6],p=0,minnum;

void getnum(int l,int ok){
	if (l==0) return;
	if (ok){
		num[l]=minnum;
		getnum(l-1,1);
		return;
	}
	if (num[l]==10){
		num[l]=minnum;
		num[l+1]++;
		if (num[l+1]<10 && !can[num[l+1]]){
			getnum(l-1,1);
		}
		else getnum(l+1,ok);
		return;
	}
	if (!can[num[l]]) getnum(l-1,ok);
	else{
		int j=num[l]+1;
		while (j<10 && can[j]) j++;
		if (j==10){
			num[l]=minnum;
			num[l+1]++;
			if (num[l+1]<10 && !can[num[l+1]]){
				getnum(l-1,1);
			}
			else getnum(l+1,ok);
		}
		else{
			num[l]=j;
			getnum(l-1,1);
		}
	}
} 

void solve(){
	while (n){
		num[++p]=n%10;
		n/=10;
	}
	getnum(p,0);
	int j=5;
	while (num[j]==0) j--;
	for (;j>0;j--) cout<<num[j];
	cout<<endl;
}

int main(){
	cin>>n>>k;
	memset(can,0,sizeof can);
	for (int i=1;i<=k;i++){
		int u;
		cin>>u;
		can[u]=1;
	}
	minnum=10;
	memset(num,0,sizeof num);
	for (int i=0;i<10;i++){
		if (!can[i]){
			minnum=i;
			break;
		}
	}
	solve();
	return 0;
} 

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        n: usize,
    }

    let mut ans = 0;

    for i in 1..=n {
        if i.to_string().len() % 2 != 0 {
            ans += 1;
        }
    }

    println!("{}", ans);
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


Measured memory_bytes: 2176
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args ) {
    Scanner sc = new Scanner(System.in);
     int start=sc.nextInt();
     int end = sc.nextInt();
     int devide=sc.nextInt();
     int j = 0;
     for(int i=start;i<=end;i++){
       if(i%devide==0){
         j=j+1; 
       }
     }
     System.out.println(j);
  }
}

Measured memory_bytes: 26976
N,A,B=map(int,raw_input().split())
S = raw_input()
for cha	in S:
    if cha == 'a' and (A+B) > 0:
	A = A-1
	print 'Yes'
        pass
    elif cha == 'b' and B > 0 and (A+B)>0:
        B = B-1
	print 'Yes'
        pass
    elif cha == 'c':
	print 'No'
        pass
    else:
	print 'No'
        pass

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] inp = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int a = inp[0];
            int b = inp[1];
            int ans = (b - 1) / (a - 1);
            int amari = (b - 1) % (a - 1);

            if (amari > 0)
            {
                Console.WriteLine(ans+1);
            }
            else
            {
                Console.WriteLine(ans);
            }
        }
    }
}

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

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

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

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

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#if __cplusplus >= 201402L
#include <shared_mutex>
#endif

using namespace std;

char s[200001];

int main() {
    scanf("%s", s);

    long long mp[26] = {0};

    long long n = 0;
    for (auto c : s) {
        if (c != '\0') {
            mp[c - 'a']++;
            n++;
        } else break;
    }

    long long res = n * (n - 1) / 2 + 1;
    for (auto x : mp) {
        res -= (x - 1) * x / 2;
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;


const long long INFLL = 1LL << 60;
const int INFI = 1000000000;

int main(){
    int N; cin >> N;
    vector<int> v(N+2); v[0] = 0; v[N+1]=0;
    long long S = 0;
    for(int i=1;i<N+1;i++){
        cin >> v[i];
        S+=abs(v[i]-v[i-1]);
    }
    S+=abs(v[N+1]-v[N]);

    for(int i=1;i<=N;i++){
        long long ans=S;
        if((v[i+1]-v[i])*(v[i]-v[i-1])>=0) cout << ans << endl;
        else{
            ans-=(abs(v[i+1]-v[i]) + abs(v[i]-v[i-1]));
            ans+=abs(v[i+1]-v[i-1]);
            cout << ans << endl;
        }
    }
}


Measured memory_bytes: 1664
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, m, x, y, sum, mx, a[100005], s[200005];
int main() {
	ll i;
	cin >> n >> m;
	for(i=1; i<=n; i++) scanf("%lld", &a[i]);
	for(i=1; i<n; i++) {
		x = a[i]; y = a[i+1];
		if(x > y) y += m;
		sum += y-x;
		if(y-x <= 1) continue;
		s[x+2]++;
		s[y+1] -= y-x;
		s[y+2] += y-x-1;
	}
	for(i=1; i<2*m+1; i++) s[i] += s[i-1];
	for(i=1; i<2*m+1; i++) s[i] += s[i-1];
	for(i=1; i<=m; i++) mx = max(mx, s[i] + s[i+m]);
	cout << sum - mx;
	return 0;
}

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

public class Main {
	public static void main(String[] args){
		int a=0;
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			String line = null;
			try {
				line = reader.readLine();
			} catch (IOException e) {
				// TODO ????????????????????? catch ????????????
				System.out.println(e);
			}
			a = Integer.parseInt(line);
			a=a*a*a;
			System.out.println(a);
			
    }
}

Measured memory_bytes: 24152
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include <memory>
#include <deque>
#include <set>
#include <unordered_set>
#include <cmath>
#include <list>
#include <cassert>
#include <cstring>

using namespace std;

using big = long long;

const int N = 20000;

big a[N];


int main() {
	std::ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a[i] += x;
  }
  for (int i = 0; i < n; ++i) {
    int x;
    
    cin >> x;
    a[i] -= x;
  }
  big s = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] > 0) {
      s += a[i];
      a[i] = 0;
    }
  }
  s *= 2;
  for (int i = 0; i < n; ++i) {
    if (a[i] < 0) {
      big v = min(-a[i] / 2 * 2, s);
      a[i] += v;
      s -= v;
    }
  }
  if (s <= 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
    
#define all(a) a.begin(), a.end()
#define forn(l, r) for(int i = l; i < (r); ++i)
#define F first
#define S second
#define $ ios::sync_with_stdio(0);
//#define int long long int
    
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ii = pair<int, int>;
using vi = vector<int>;
using graph = vector<vi>;
using ordered_mset = tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update>;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
//const ll INFLL = (ll)1e17;
const int MAXN = 112345;
const double pi = 3.14159265359;
const double eps = 0.00000001;

int mat[3][MAXN];
int dp[3][MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            scanf("%d", &mat[j][i]);
        }
    }
    for (int j = 0; j < 3; ++j) {
        dp[j][0] = mat[j][0];
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            int res = 0;
            for (int k = 0; k < 3; ++k) if (j != k) {
                res = max(res, dp[k][i - 1]);
            }
            dp[j][i] = res + mat[j][i];
        }
    }
    int ans = 0;
    for (int j = 0; j < 3; ++j) {
        ans = max(ans, dp[j][n - 1]);
    }
    printf("%d\n", ans);
}

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

int main(){
	int r;
	cin >> r;
	if(r < 1200) cout << "ABC" << endl;
	else if (r < 2800) cout << "ARC" << endl;
	else cout << "AGC" << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == -1)
                break;
            double x = 1;
            double y = 0;
            for (int i = 1; i < n; i++) {
                float d =(float) Math.sqrt(x * x + y * y);
                double dx = -y / d;
                double dy = x / d;
                x += dx;
                y += dy;
            }
            System.out.printf("%.2f\n%.2f\n", x, y);
        }
    }

}


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

int main(){
  int A, B;
  cin >> A >> B;
  int ans = 0;
  for(int i = A; i <= B; i++){
    string s = to_string(i);
    if(s[0] == s[4] && s[1] == s[3]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3192
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

const long long MOD = 4294967291LL;
const long long INF = 1e18;

int GCD(int a, int b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp, long long mod = MOD) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % mod;
       base = base * base % mod;
    }
    return tot;
}
long long mult_mod(long long base, long long exp, long long mod = MOD) {
    long long tot = 0;
    for(;exp > 0;exp >>= 1){
       if((exp & 1) == 1) tot = (tot + base) % mod;
       base = base * 2 % mod;
    }
    return tot;
}

struct chash {
    static uint64_t splitmix64(uint64_t x) {x += 0x8e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf54876d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);}
    size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);}
    size_t operator()(pair<uint64_t,uint64_t> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);}
};

vector<int> pos[27];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    string s, t; cin >> s >> t;

    for(int i = 0; i < 26; ++i)
        for(int j = 0; j < s.size(); ++j)
            if(i == s[j] - 'a')
                pos[i].push_back(j);

    long long repeat = 0;
    int cur = -1;

    for(auto ch : t){

        if(pos[ch - 'a'].empty()){
            cout << -1;
            return 0;
        }

        auto it = lower_bound(pos[ch - 'a'].begin(), pos[ch - 'a'].end(), cur + 1);

        if(it == pos[ch - 'a'].end()){
            cur = pos[ch - 'a'][0];
            ++repeat;
        } else {
            cur = *it;
        }

    }

    cout << repeat * s.size() + cur + 1;

    return 0;
}


Measured memory_bytes: 1228
import java.util.Scanner;

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

        String s = scanner.nextLine();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if('a' <= c && c <= 'z')
                c -= 'a' - 'A';
            else if('A' <= c && c <= 'Z')
                c += 'a' - 'A';
            System.out.print(c);
        }
        System.out.println();
    }
}



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

int main(void){
	int n,m,p;

	while(cin>>n>>m>>p && (n || m || p)){
		int x[104],sum=0;

		for(int i=0;i<n;i++){
			cin>>x[i];
			sum += x[i] * 100;
		}

		sum = (int)(sum * ((100.0 - p) / 100.0));

		if(x[m-1] == 0){
			cout<<"0\n";
		}
		else{
			cout<<sum/x[m-1]<<endl;
		}
	}

	return 0;
}

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

int main(){

    int n,k;
    cin>> n>>k;

    vector<int> l(n);

    rep(i,n) cin >> l[i];

    sort(l.begin(),l.end(),greater<int>());

    int ans=0;

    rep(i,k){
        ans+=l[i];
    }

    cout << ans <<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <utility> //pair

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {

    ll n;
    cin >> n;

    vector<ll> a(n);

    FOR(i, 0, n){
        cin >> a[i];
        a[i] = a[i] -(i+1);
    }

    sort(a.begin(),a.end());

    ll b,b1,b2;
    ll ans=0;
    ll ans1=0,ans2=0;
    if(n%2!=0){
        b = a[n/2]; //中央値
        FOR(i, 0, n){
            ans += abs(a[i]-b);
        }
    }else{
        b1 = a[n/2];
        b2 = a[n/2-1];
        FOR(i, 0, n){
            ans1 += abs(a[i]-b1);
            ans2 += abs(a[i]-b2);
        }
        ans = min(ans1,ans2);
    }

    cout <<  ans <<  endl;

    return 0;
}



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

int TagLinerSearch(int S[],int n, int value){
    S[n] = value;
    int i = 0;
    // reduce the num of compare in for
    while(1){
        if(S[i]==value) break;
        i++;
    }
    return ((i==n)?0:1);
}

int main(){

//    for(int i=0;cin>>ch;++i){
//        printf("%c",ch);
//    }
//    while(cin>>ch)cout<<ch;
    int n,q;
    int S[10000+1];
    int sum = 0;
    int T;
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&S[i]);
    scanf("%d",&q);
    for(int i=0;i<q;++i){
        scanf("%d",&T);
        sum += TagLinerSearch(S,n,T);
    }
    printf("%d\n",sum);
	return 0;
}



Measured memory_bytes: 3216
from collections import defaultdict
N = int(input())
L = defaultdict(int)
for s in input().split():
  L[int(s)] += 1
U = sorted(list(L.keys()), reverse=True)
cnt = 0
for i, a in enumerate(U):
  for j, b in enumerate(U[i+1:]):
    for c in U[i+j+2:]:
      cnt += (L[a] * L[b] * L[c]) if a < b + c else 0
print(cnt)

Measured memory_bytes: 9468
// Trained?
#include <cmath>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; i++) cin >> a[i], a[i]--;

    int x = -1;
    int idx;
    for (int i = 0; i < N; i++) {
        idx = a[idx];
        if (idx == 1) {
            x = i + 1;
            break;
        }
    }
    cout << x << endl;
}

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

namespace AtCoder.Abc
{
    class QuestionM
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var num_NK = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            int result = 0;
            var num_M = num_NK[0];

            do
            {
                num_M = num_M / num_NK[1];

                result++;

            } while (num_M != 0);


            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}

Measured memory_bytes: 11348
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int N; cin >>N;
  vector<ll> A(N),B(N),C(N); rep(i, N) cin >>A[i]; rep(i, N) cin >>B[i]; rep(i, N) cin >>C[i];
  vector<ll> left(N+1); // left[i] := Aに、Bの[0, i) の範囲を加えたものからN個取った総和の最大値
  vector<ll> right(N+1);// right[i]:= Cに、Bの[i, N) の範囲を加えたものからN個取った総和の最小値
  // 最終的に求めたいのはleft[i]-right[i]の最大値
  ll sum = 0;  rep(i, N) sum += A[i]; left[0] = sum;
  sum = 0;     rep(i, N) sum += C[i]; right[N] = sum;
  // まずleftを埋めていく
  priority_queue<ll, vector<ll>, greater<ll>> pq1; rep(i, N) pq1.push(A[i]);
  sum = left[0];
  rep(i, N){
    sum += B[i]; pq1.push(B[i]); // とりあえず新しいやつを突っ込む
    sum -= pq1.top(); pq1.pop(); // その中で一番小さいものを捨てる
    left[i+1] = sum;
  }
  // 次にrightを埋めていく
  priority_queue<ll> pq2; rep(i, N) pq2.push(C[i]);
  sum = right[N];
  rep(i, N){
    sum += B[N-1-i]; pq2.push(B[N-1-i]); // とりあえず新しい奴を突っ込む
    sum -= pq2.top(); pq2.pop(); // その中で一番大きいものを捨てる
    right[N-1-i] = sum;
  }
  ll res = -INF;
  rep(i, N+1){
    chmax(res, left[i] - right[i]);
  }
  cout <<res <<endl;
}

Measured memory_bytes: 6516
#include <bits/stdc++.h>
using namespace std;
int N, A, B;
int main()
{
    scanf("%d%d%d", &N, &A, &B);
    int Max = min(A, B);
    int Min;
    if(A + B <= N) Min = 0;
    else Min = A + B - N;
    printf("%d %d\n", Max, Min);
    return 0;
}


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

#define ll long long 
#define mkp make_pair 
#define fi first 
#define se second

using namespace std ;

int z ;

int	 main ( ) {

	vector<int>vc;

	int x = 0 ;
	vc.push_back(x);
	int n ;
	cin >> n ;
	string s ;
	cin >> s ;
	for(int i = 0 ; i < n ; i ++ ){
		if( s[i] == 'I' ){
			x ++ ;
			vc.push_back(x);
		}
		else{
			x -- ;
			vc.push_back(x);
		}
	}

	sort(vc.begin(),vc.end());

	cout << vc[vc.size()-1] ;
	
}


Measured memory_bytes: 256
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    else:
        cnt = 0
        for i in range(1,n-1):
            for j in range(i+1,n):
                for k in range(j+1,n+1):
                    if i + j + k == x:
                        cnt += 1
        print(cnt)


Measured memory_bytes: 5596
S = input()
T = input()
# S = "abc"
# T = "abcd"
Check = "NG"
# print(T[0:len(S)])
if len(S) + 1 == len(T):
    if S == T[0:len(S)]:
        if ord(T[len(S)]) >= 97 and ord(T[len(S)]) <= 122:
            Check = "OK"
if Check == "OK":
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9072
package main

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

func main() {
    var input []string
    sc := bufio.NewScanner(os.Stdin)
    for sc.Scan() {
        input = append(input, sc.Text())
    }   

    A, _ := strconv.Atoi(input[0])
    B, _ := strconv.Atoi(input[1])
    C, _ := strconv.Atoi(input[2])
    X, _ := strconv.Atoi(input[3])

    var count int 
    for i := 0; i <= A; i++ {
        for j := 0; j <= B; j++ {
            for k := 0; k <= C; k++ {
                if 500*i+100*j+50*k == X { 
                    count++
                }   
            }   
        }   
    }

    fmt.Println(count)
}

Measured memory_bytes: 640