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

/*Q5.
Chocolate brands were ranked according to which had the best taste. There were 10^30 chocolate brands in total.
Two judges ranked the chocolates in the increasing order of taste. The ranks given are unique (1 to 10^30 by each judge). 
The final score is the product of the scores given by the two judges. You have to process Q queries. 
Our chocolate of interest had ranks Xi and Yi given by the two judges. 
You have to determine the maximum number of participants whose score is less than the score of our brand in each case.

Constraints:
1 <= Q <= 100
1 <= Xi,Yi <= 10^9 (1<= i <= Q)

Input:
First line contains Q
Next Q lines contain Xi and Yi

Output: 
Maximum number of brands having a score less than our brand. 
https://arc094.contest.atcoder.jp/tasks/arc094_b */

typedef long long ll;
typedef long double ld;

int main()
{
	ll a,b,q;
	cin >> q;
	while(q--)
	{
		cin >> a >> b;
		if(a>b) swap(a,b);
		if(a==b) cout << (2*a-2) << '\n';
		else if(a+1==b) cout << (2*a-2) << '\n';
		else
		{
			ld c = sqrt((ld)a*(ld)b);
			ll c1=c;
			if(c1==c) c1--;
			if((c1*(c1+1))>=(a*b)) cout << (2*c1-2) << '\n';
			else cout << (2*c1-1) << '\n';

		}
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
s = [a[0] for _ in range(n)]
t = [a[0] for _ in range(n)]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    t[i] = t[i - 1] + a[i]
x, y = 0, 0
ans1, ans2 = 0, 0
for i in range(n):
    ss = s[i] + x
    tt = t[i] + y
    if i % 2 == 0:
        if ss <= 0:
            x += abs(ss) + 1
            ans1 += abs(ss) + 1
        if tt >= 0:
            y -= abs(tt) + 1
            ans2 += abs(tt) + 1
    else:
        if ss >= 0:
            x -= abs(ss) + 1
            ans1 += abs(ss) + 1
        if tt <= 0:
            y += abs(tt) + 1
            ans2 += abs(tt) + 1
print(min(ans1, ans2))

Measured memory_bytes: 16064
#include <iomanip>
#include <iostream>
#include <string>
using namespace std;
int main(void) {
  string s, p;
  cin >> s >> p;
  s += s;
  for(int i = 0; i < s.length(); i++) {
    if(p == s.substr(i, p.length())) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

  return 0;
}



Measured memory_bytes: 3212
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int n, a;
vector<int> ac[100000];

int solve(int v) {
	vector<pair<int, int>> p;
	REP(i, ac[v].size()) p.push_back(MP(solve(ac[v][i]), ac[v][i]));
	sort(ALL(p));
	reverse(ALL(p));
	int res = 0;
	REP(i, p.size()) res = max(res, p[i].first + i + 1);
	return res;
}

int main(int argc, char **argv) {
	cin >> n;
	FOR(i, 1, n) {
		cin >> a;
		--a;
		ac[a].push_back(i);
	}
	cout << solve(0) << endl;
	return 0;
}


Measured memory_bytes: 15104
a,b,x=map(int,input().split())
h=x/a**2
#print(h)


import math
#print(math.degrees(math.atan2(0,1)))

if b-x/a**2>=x/a**2:
  print(math.degrees(math.atan2(b,2*x/(a*b))))
else:
  print(math.degrees(math.atan2(2*b-2*x/(a**2),a)))



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

int main(){
    while(true){
        bool ju = true;
        string s;
        stack <char> box;
        getline(cin,s); if(s == ".") break;
        for(int i=0;i<s.size();i++){
            if(s[i] == '(' || s[i] == '[') box.push(s[i]);
            else if(s[i] == ')'){
                if(box.empty() || box.top()!= '(') ju = false;
                else box.pop();
            }
            else if(s[i] == ']'){
                if(box.empty() || box.top()!= '[') ju = false;
                else box.pop();
            }
            if(!ju) break;
        }
        cout << ((ju&&box.empty())? "yes" : "no") << endl;
    }
}

Measured memory_bytes: 1180
#include <iostream>
#define SENTINEL 1000000001;
using namespace std;

int comp = 0;

void merge(int S[], int left, int mid, int right){
  int nl = mid-left;
  int nr = right-mid;
  int L[nl+1],R[nr+1];
  L[nl] = SENTINEL; R[nr] = SENTINEL;

  for(int i=0;i<nl;i++) L[i]=S[left+i];
  for(int i=0;i<nr;i++) R[i]=S[mid+i];
  int il = 0;
  int ir = 0;
  int is = 0;
  for(int i=0;i<right-left;i++){
    comp++;
    if(L[il]<=R[ir]){
      S[left+is] = L[il];
      il++;
    }else if(L[il]>R[ir]){
      S[left+is] = R[ir];
      ir++;
    }
    is++;
  }
}

void merge_sort(int S[], int left, int right){
  int mid = (left+right)/2;
  if(left + 1 < right){
    merge_sort(S,left,mid);
    merge_sort(S,mid,right);
    merge(S,left,mid,right);
  }
}

int main(){
  int n; cin>>n;
  int S[n];
  for(int i=0;i<n;i++){
    cin>>S[i];
  }
  merge_sort(S,0,n);
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<S[i];
  }
  cout<<endl<<comp<<endl;
}

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

double powNum(double a)
{
    return a * a;
}

int main()
{
    double a, b, h, m;
    cin >> a >> b >> h >> m;

    double hourDeg = h / 12.0 * (2.0 * M_PI) + m / 60.0 * 30.0 * (2.0 * M_PI) / 360.0, minDeg = m / 60.0 * (2.0 * M_PI);

    double hourPosX = a * sin(hourDeg), hourPosY = a * cos(hourDeg);

    double minPosX = b * sin(minDeg), minPosY = b * cos(minDeg);

    cout << setprecision(12) << fixed;
    cout << sqrt(powNum(hourPosX - minPosX) + powNum(hourPosY - minPosY)) << endl;
}

Measured memory_bytes: 4124
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b){return (1ll*a*b)/gcd(a, b);}
#define MOD 100000000;
#define EPS 0.001
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a,b;
    cin>>a>>b;
    cout<<max(0,a-b*2);
}


Measured memory_bytes: 256
import java.util.Scanner;

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

        boolean flag=false;
        for (int a = 0; a <= A; a=a+4) {
            for(int b=0;b<=A;b=b+7){
                if (a+b==A){
                    flag=true;
                }
            }
        }
        if (flag==false){
            System.out.println("No");
        }else {
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 23124
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	Scanner scan=new Scanner(System.in);
	int n,b,f,r,v;
	n=scan.nextInt();
	int a[][][]=new int[4][3][10];
	for(int i=0;i<n;i++)
	    {
		b=scan.nextInt();
		f=scan.nextInt();
		r=scan.nextInt();
		v=scan.nextInt();
		a[b-1][f-1][r-1]+=v;
	    }
	for(int i=0;i<4;i++)
	    {
		for(int j=0;j<3;j++)
		    {
			for(int k=0;k<10;k++)
			    {
				System.out.print(" "+a[i][j][k]);
			
			    }
			System.out.println();
		
		    }
		if(i<3)
			    {
			
				System.out.print("####################");
				System.out.println();
			    }
	    }
    }
}

Measured memory_bytes: 21064
#include<iostream>

using namespace std;

int main() {

	int K;
	int A, B;
	cin >> K;
	cin >> A >> B;

	bool hikyori = false;
	for (int i = A; i <= B; i++) {
		if (i % K == 0) {
			hikyori = true;
			break;
		}
	}

	if (hikyori) {
		cout << "OK" << endl;
	}
	else {
		cout << "NG" << endl;
	}
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
using namespace std;
const int SIZE=2017;
const int SEGSIZE=1<<16;
const int INF=1<<29;
const LL p=1e9+7;
bool maps[SIZE][SIZE];
int N,M;
int DP[SIZE][SIZE];
int solve(int i,int j){
	if(i==0 or j==M or i==N) return 0;
	if(DP[i][j]) return DP[i][j];
	if(((maps[i][j]^maps[i-1][j])==(maps[i][j+1]^maps[i-1][j+1]))) 
		return DP[i][j]=solve(i,j+1)+1;
	return DP[i][j]=1;
}
int solve2(int x){
	int maxim=0;
	Vpr st;
	REP(i,N+1){
		int val=solve(i,x);
		int last=i;
		while(!st.empty() && st.back().first>val){
			maxim=max(maxim,st.back().first*(i-st.back().second+1));
			last=st.back().second;
			st.pop_back();
		}
		st.PB(pr(val,last));
	}
	return maxim;
}
int main(){
	string s;
	cin >>N >> M;
	REP(i,N){
		cin >> s;
		REP(j,M){
			maps[i][j]=s[j]=='.';
			
		}		
	}

	int maxim=max(N,M);
	REP(i,M){
		
		maxim=max(maxim,solve2(i));
	}
	//REP(i,N) REP(j,M) 	cout << i << " " << j << " " << solve(i,j) << endl;

	cout << maxim << endl;
}

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

int main(void){

	double r;
	double s,l;

	scanf("%lf",&r);

	s=(double)r*r*M_PI;
	l=(double)2*r*M_PI;

	printf("%lf %lf\n",s,l);

	return 0;

}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n , m , c;
  cin >> n >> m >> c;
  vector <int> b(m);
  for ( int i=0 ; i<m ; i++){
    cin >> b.at(i);
  }
  int ans = 0 ;
  for ( int i=0 ; i<n ; i++){
     vector <int> a(m);
    int sum=0 ;
    for ( int j=0 ; j<m ; j++){
      cin >> a.at(j) ;
      sum += a.at(j)*b.at(j); 
    }
    if ( sum+c>0){
      ans ++ ;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3648
N = int(input())
Ai = list(map(int, input().split()))
p = 1
i = 0
if 0 in Ai:
    print("0")
else:
    while i <= N - 1:
        p = p * Ai[i]
        if p > 10 ** 18:
            print("-1")
            break
        if i == N - 1:
            print(p)
            break
        i += 1

Measured memory_bytes: 21648
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(2)]

ans = 0
for i in range(n):
    ans = max(ans, sum(a[0][:i + 1:]) + sum(a[1][i::]))
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
int main(){
  int i,j,h,w,a[30][30],b[30][30],s1,s2,g1,g2,x,y,ans=0,k,l;
  char s;
  const int INF=(1<<29);
  queue<int> q1;
  queue<int> q2;
  scanf("%d %d\n",&h,&w);
  for(i=0;i<=h;i++){
    for(j=0;j<=w;j++){
      a[i][j]=1;
    }
  }
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      scanf("%c",&s);
      if(s=='.'){
        a[i][j]=0;
      }
    }
    scanf("\n");
  }
  for(s1=1;s1<=h;s1++){
    for(s2=1;s2<=w;s2++){
      for(g1=1;g1<=h;g1++){
        for(g2=1;g2<=w;g2++){
          if(a[s1][s2]==1 || a[g1][g2]==1){
            continue;
          }
          if(s1==g1 && s2==g2){
            continue;
          }
          for(i=1;i<=h;i++){
            for(j=1;j<=w;j++){
              b[i][j]=INF;
            }
          }
          b[s1][s2]=0;
          q1.push(s1),q2.push(s2);
          while(!q1.empty()){
            x=q1.front(),y=q2.front();
            q1.pop(),q2.pop();
            if(a[x+1][y]==0 && b[x+1][y]>b[x][y]+1){
              q1.push(x+1),q2.push(y);
              b[x+1][y]=b[x][y]+1;
            }
            if(a[x-1][y]==0 && b[x-1][y]>b[x][y]+1){
              q1.push(x-1),q2.push(y);
              b[x-1][y]=b[x][y]+1;
            }
            if(a[x][y+1]==0 && b[x][y+1]>b[x][y]+1){
              q1.push(x),q2.push(y+1);
              b[x][y+1]=b[x][y]+1;
            }
            if(a[x][y-1]==0 && b[x][y-1]>b[x][y]+1){
              q1.push(x),q2.push(y-1);
              b[x][y-1]=b[x][y]+1;
            }
          }
          if(ans<b[g1][g2] && b[g1][g2]!=INF){
            ans=b[g1][g2];
          }
        }
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <queue>
#include <deque>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <bitset>

#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x, y) memset(x, y, sizeof(x))
#define pb push_back
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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 (a > b) {
      a = b;
      return 1;
   }
   return 0;
}

using namespace std;
using ll = long long;

const int kInf = 2e9;
const ll kLInf = 2e18;

int gcd (int a, int b) {
   return b ? gcd(b, a % b) : a;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

map<string, int> dict;
int N;
string S;
int main()
{
   cout << fixed << setprecision(10);
   cin >> N;
   int max = 0;
   REP(i, N) {
      cin >> S;
      dict[S]++;
      if (dict[S] > max) {
         max = dict[S];
      }
   }
   for (auto itr = dict.begin(); itr != dict.end(); itr++) {
      if (itr->second == max) {
         cout << itr->first << endl;
      }
   }
   return 0;
}



Measured memory_bytes: 25216
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>

using namespace std;

#define ll long long
#define rep(i, n) for (ll i = 1; i < (n+1); i++)
#define req(j, n) for (ll j = 1; j < (n+1); j++)
#define rer(k, n) for (ll k = 1; k < (n+1); k++)


int main()
{
    ll R;
    float ans;
    cin >> R;
    ans = 2 * 3.14 * R;
    cout << ans << endl;
}

Measured memory_bytes: 3228
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;

void solve() {
  string s;
  cin >> s;
  if(s[0] != '<') s = "<" + s;
  ll ret = 0;
  for(int i = 0; i < sz(s);) {
    int j = i+1;
    while(j < sz(s) && s[i] == s[j]) j++;
    ll inc = j-i;
    i = j;
    j = i+1;
    while(j < sz(s) && s[i] == s[j]) j++;
    ll dec = j-i;
    if(inc <= dec) {
      ret += inc * (inc-1)/2;
      ret += dec * (dec+1)/2;
    }
    else {
      ret += inc * (inc+1)/2;
      ret += dec * (dec-1)/2;
    }
    i = j;
  }
  cout << ret << "\n";
}

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


Measured memory_bytes: 1308
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <map>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }

    map<int,int> mp;
    for(int i=0; i<N; i++) {
        mp[A[i]]++;
    }

    int64_t ans =0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        int64_t val = itr->second;
        ans += val*(val-1)/2;
    }

    for(int i=0; i<N; i++) {
        int64_t tmp = mp[A[i]];
        cout << ans - (tmp-1) << endl;
    }
    return 0;
}


Measured memory_bytes: 9728
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main() {
	int N,p=0,te=0,B,j;
	cin >> N;
	vector<int> A(N,0),D(N,1);
	vector<int> E(200, 0);
	ll count = 0,mul=1;
	for (int i = 2; i <= 1000; i++) {
		for (j = 2; j < i; j++) {
			if (!(i % j))
				break;
		}
		if (i == j) {
			E[p] = i;
			p++;
		}
	}
	int prime[p] = { 0 };
	int C[N+1][p] = { 0 };
	vector<int> BP(N,1);
	int bpc = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B = A[i];
		for (int j = 0; j < p; j++) {
			while (!(B% E[j])) {
				B/=E[j];
				te++;
				C[i+1][j]++;
				//cout << "B:" << B << endl;
			}
			if (te) {
				if (prime[j] < te) {
					prime[j] = te;
				}
			}
			te = 0;
		}
		if (B > 999) {
			D[i] = B;
			for (int k = 0; k <= bpc; k++) {
				if (B == BP[k])
					break;
				if (k == bpc) {
					BP[bpc] = B;
					bpc++;
					break;
				}
			}
		}
	}
	int x;
	for (int i = 0; i < N; i++) {
		mul = 1;
		for (int j = 0; j < p; j++) {
			x = (prime[j] - C[i+1][j]);
			if (x) {
				for (int k = 0; k < x; k++) {
					mul *= E[j];
					if (mul > mod)
						mul = mul % mod;
				}
			}
		}
		for (int j = 0; j < bpc; j++) {
			if (D[i] != BP[j]) {
				mul *= BP[j];
				if (mul > mod)
					mul = mul % mod;
			}
		}
		count += mul;
		//cout << "mul:" << mul << endl;
		if (count > mod)
			count = count % mod;
	}
	cout << count << endl;
}

Measured memory_bytes: 6912
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string a,b;
    cin >> a >> b;
    for(int i = 0;i < b.size();i++)cout << a[i] << b[i];
    if(a.size()!=b.size())cout << a[a.size()-1];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
def roop(i,K):
    n=i
    ma=[-1]*N
    ma[n]=0
    point=0
    maxp=-10**30
    cnt=0
    isroop=False
    while cnt<K:
        cnt+=1
        n=P[n]
        point+=C[n]
        ma[n]=point
        maxp=max(maxp,point)
        if n==i:
            isroop=True
            break
    if not isroop:
        return maxp
    
    allpoint=(K//cnt)*point
    K%=cnt
    lastpoint=0
    j=0
    n=i
    lastp=0
    while(j<K):
       j+=1
       n=P[n]
       lastp+=C[n]
       lastpoint=max(lastpoint,lastp)
    return max([allpoint+lastpoint,allpoint-point+maxp,maxp])

N,K=map(int,input().split())
P=list(map(lambda x:int(x)-1,input().split()))
C=list(map(int,input().split()))

ans=-10**30
for i in range(N):
    ans=max(ans,roop(i,K))
print(ans)

Measured memory_bytes: 73364
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    string S; cin >> S;
    int len = S.length();
    int s = 0, ans = len;
    for(int i = 0; i < len; i++){
        if(S[i] == 'T'){
            if(s>0){
                s--; ans-=2;
            }
        }else{
            s++;
        }
    }
    cout << ans << endl;    
    return 0;
}

Measured memory_bytes: 640
'''
5乗なのでグラフは十分疎である
AとBが連続する整数(B = A-1)だった時の値で絞り込む
A^5-(A-1)^5 の値はA=120で今回のX=10^9を超える
同様に下限はA=-119である
その時のBの範囲も、与式>=1によりA-B>0だから同様の範囲だろうと推測できる
'''

X = int(input())
for i in range(-120, 120):
    for j in range(-120,120):
        if i**5 - j**5 == X:
            print(i, j)
            break
    else:
        continue
    break

Measured memory_bytes: 9136
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		// メソッドごとのテスト
//		String str = "abcdef";
//		print(str, 2, 3); // cd
//		// 置換
//		System.out.println(replace(str, "xyz", 0, 2)); // xyzdef
//		// 反転
		// cbade
//		System.out.println(reverse(str, 0, 2)); // cbadef

		String str = sc.next();
		Integer q = sc.nextInt();
		for(int i=0; i<q; i++) {
			String func = sc.next();
			if(func.equals("replace")) {
				Integer arg1 = sc.nextInt();
				Integer arg2 = sc.nextInt();
				String arg3 = sc.next();
				str = replace(str, arg3, arg1, arg2);
			} else if(func.equals("reverse")) {
				Integer arg1 = sc.nextInt();
				Integer arg2 = sc.nextInt();
				str = reverse(str, arg1, arg2);
			} else if(func.equals("print")) {
				Integer arg1 = sc.nextInt();
				Integer arg2 = sc.nextInt();
				print(str, arg1, arg2);
			}
		}

		sc.close();

	}

	private static void print(String str, Integer start, Integer end) {
		System.out.println(str.substring(start, end+1));
	}

	private static String reverse(String str, Integer start, Integer end) {
		StringBuffer sb = new StringBuffer(str);
		String reversingStr = sb.substring(start, end+1);
//		System.out.println("逆にする文字列 : " + reversingStr);
		StringBuffer sb2 = new StringBuffer(reversingStr);
		String reversedStr = sb2.reverse().toString();
//		System.out.println("逆にした文字列 : " + reversedStr);
		String resultStr = sb.replace(start, end+1, reversedStr).toString();
		return resultStr;
	}

	private static String replace(String str, String replaceStr, Integer start, Integer end) {
		StringBuffer sb = new StringBuffer(str);
		sb.replace(start, end+1, replaceStr);
		String ret = sb.toString();
		return ret;
	}


}


Measured memory_bytes: 29412
#include <iostream>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <map>

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

using namespace std;

typedef long long int lli;

lli memo[100][100];

lli nCr(int n, int r) {
    if (memo[n][r]) return memo[n][r];
    if (r == 0 || r == n) return 1;
    return memo[n][r] = nCr(n - 1, r) + nCr(n - 1, r - 1);
}

int main () {
    int N, A, B;
    cin >> N >> A >> B;
    map<lli, int> v;
    REP (i, 0, N) {
        lli vi;
        cin >> vi;
        v[vi]++;
    }
    lli sum = 0;
    int cnt = 0;
    lli res = 0;

    for (int i = A; i <= B; i++) {
        int c = 0;
        lli t = 0;
        lli p = 0;
        for (auto it = v.rbegin(); it != v.rend(); it++) {
            if (c < i && c + it -> second >= i) {
                t = nCr(it -> second, i - c);
                p += it -> first * (i - c);
                c = i;
                break;
            }
            c += it -> second;
            p += it -> first * it -> second;
        }
        if (cnt == 0) {
            sum = p;
            cnt = i;
            res = t;
        }
        else if (sum * i == p * cnt) {
            res += t;
        }
        else if (sum * i < p * cnt) {
            sum = p;
            cnt = i;
            res = t;
        }
    }
    cout << fixed << setprecision(10) << (double)sum / cnt << endl;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
H,W=map(int,input().split())
a=[]
for i in range(H):
    a.append(map(str,input().split()))

for i in range(0,W+2):
    print("#",end="")
print()

for i in a:
    print("#",end="")
    for j in i:
        print(j,end="")
    print("#")

for i in range(0, W+2):
      print("#",end="")
print()

Measured memory_bytes: 3060
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;




int main()
{
  int n, m, x, y; //かっている数//最大100
  cin >> n >> m >> x >> y ;

  vector<long>xx(n);
  vector<long>yy(m);
  for (int i = 0; i < n; ++i) {
    cin >> xx[i];
  }
  for (int i = 0; i < m; ++i) {
    cin >> yy[i];
  }

  sort(xx.begin(), xx.end(), [](long & l, long & r) {return l > r;});
  sort(yy.begin(), yy.end(), [](long & l, long & r) {return l < r;});



  bool ans = false;

  for (int z = x + 1; z <= y; ++z) {
    cerr << z <<endl;
    cerr << xx[0] << " z:y " <<yy[0] <<endl;
    if (xx[0] < z && yy[0] >= z)ans = true;
  }


  cout << (!ans ? "War" : "No War");

  return 0;
}



























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

const int maxn = 1e6 + 3;

int n, q, c[maxn], l[maxn], r[maxn], o[maxn], pc[maxn], ans[maxn];
int bits[maxn];

int query(int k) {
    int ans = 0;
    for(int i = k + 1; i >= 1; i -= i & -i)
        ans += bits[i];
    return ans;
}

void modify(int k, int v) {
    for(int i = k + 1; i < maxn; i += i & -i)
        bits[i] += v;
}

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i)
        scanf("%d", c + i);
    for(int i = 0; i < q; ++i) {
        scanf("%d%d", l + i, r + i);
        o[i] = i;
    }
    std::sort(o, o + q, [](int i, int j) {
        return r[i] < r[j];
    });
    for(int cr = 1, i = 0; cr <= n; ++cr) {
        if(pc[c[cr]])
            modify(pc[c[cr]], -1);
        modify(cr, 1);
        pc[c[cr]] = cr;
        while(i < q && r[o[i]] == cr) {
            ans[o[i]] = query(cr) - query(l[o[i]] - 1);
            i += 1;
        }
    }
    for(int i = 0; i < q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Measured memory_bytes: 17460
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20

S=input()
N=len(S)
dests = [-1]
for i in range(N-1):
    if S[i] == "R" and S[i+1] == "L":
        dests.append(i)
M = len(dests)

# i<-[0,N)について、d<iなるmax d のをl, i<=dなる最小をr
l = -1
li = 0
r = dests[1]
ri =1 
dests.append(N)
ans = [0 for _ in range(N)]
for i in range(N):
    if i > r:
        ri+=1
        r = dests[ri]
    if dests[li+1] < i:
        li+=1
        l = dests[li]
    if S[i] == "R":
        d = r
    else:
        d = l
    p = abs(d-i)%2
    ans[p + d] += 1
print(" ".join(map(str,ans)))

Measured memory_bytes: 14764
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
 
const inputlist = input.split(' ');
 
const a = Number(inputlist[0]);
 
const b = Number(inputlist[1]);
 
const k = Number(inputlist[2]);
 
const arr = [];

let e = 0;

if (a>b) {
  e = b;
} else {
  e = a;
}
 
for (let i=1;i<=e;i++) {
  if (a % i === 0 && b % i === 0) {
    arr.push(i);
  }
}

const f = arr.length - k;
 
console.log(arr[f]);

Measured memory_bytes: 7372
s = input()
t = input()

before = [-1] * 26
after = [-1] * 26

for i, j in zip(s, t):
    si = ord(i) - ord('a')
    ti = ord(j) - ord('a')

    if before[si] != -1 or after[ti] != -1:
        if before[si] != ti or after[ti] != si:
            print("No")
            exit()

    before[si] = ti
    after[ti] = si
print("Yes")


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define double long double
#define ll long long
#define INF LLONG_MAX/3
#define P pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
#define ggr getchar();getchar();return 0;
using namespace std;
int n,k,a[110];
int dp[100010];
signed main(){
    cin>>n>>k;
    int mi=INF;
    rep(i,n){
        cin>>a[i];
        mi=min(mi,a[i]);
    }
    rep(i,mi)dp[i]=2;
    for(int i=mi;i<=k;i++){
        rep(j,n){
            if(i-a[j]>=0&&dp[i-a[j]]==2){
                dp[i]=1;
                goto kaage;
            }
        }
        dp[i]=2;
        kaage:;
    }
    if(dp[k]==1)puts("First");
    else puts("Second");
    ggr;
}

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

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0), cout.tie(0);

 string s;
 cin >> s;

 if(s=="ABC"){
 	cout << "ARC" << "\n";
 } else {
 	cout << "ABC" << "\n";
 }

}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

int gcd(int x, int y) {
    if (y==0) return x;
    // cout << x << " " << y << endl;
    return gcd(y, x%y);
}

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

    int x, y; cin >> x >> y;
    if (y>x) swap(x, y);
    cout << gcd(x, y) << endl;
}


Measured memory_bytes: 3232
import math

N = int(input())
A = list(map(int ,input().split()))
MOD = math.floor(1e9+7)

sum = 0
for i in range (N):
    sum += A[i] % MOD

ans = 0
for i in range(N):
    sum -= A[i]
    ans += (A[i] * sum) % MOD

ans = ans % MOD
print(ans)

Measured memory_bytes: 32848
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = ll(1e9 + 7);

vector<vector<ll>> dp;

void solve(const string &S, const int slen) {
    for (int i = 0; i < slen ;i++) {
        for (int j = 0; j < 13; j++) {
            char c = S[i + 1];
            if (c == '?') {
                for (int d = 0; d <= 9; d++) {
                    int nj = (10 * j + d) % 13;
                    dp[i + 1][nj] = (dp[i + 1][nj] + dp[i][j]) % MOD;
                }
            } else {
                int d = c - '0';
                int nj = (10 * j + d) % 13;
                dp[i + 1][nj] = (dp[i + 1][nj] + dp[i][j]) % MOD;
            }
        }
    }
}

int main(void) {
    string S;
    cin >> S;

    int slen = (int) S.size();

    S = " " + S;

    dp.resize(slen + 1, vector<ll>(13, 0LL));
    dp[0][0] = 1LL;

    solve(S, slen);

    // for (int i = 0; i <= slen; i++) {
    //     for (int j = 0; j <= 12; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    cout << dp[slen][5] << endl;

    return 0;
}


Measured memory_bytes: 13692
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=998244353,MAX=1e7+2;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    string s;
    cin>>s;
    int n=sz(s),res=0;
    lp(i,0,n){
        int cnt=0;
        lp(j,i,n){
            if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T')
                cnt++;
            else
                break;
        }
        res=max(res,cnt);
    }
    cout<<res;
}

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

#define ll long long int
#define str string
#define ALL(a)  (a).begin(),(a).end()
#define P pair<ll,ll>

using Graph = vector<vector<int>>;

const int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
ll INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Min = INFL, Max = -1;
ll a, b, c, n, sum, A[500010], B[500000], rui[500000], dp[5000];
str S, T, U; bool check = true;	vector<ll> v;



int main() {
	//Code Line
	cin >> n;
	for (int i = 4; i <= 18; i += 2) {
		if (i * 100 <= n && n < (i + 2) * 100) {
			a = i / 2; break;
		}
	}
	cout << 10 - a << endl;


	return 0;
}


Measured memory_bytes: 3632
import sys
rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

li = [ri() for _ in range(6)]
print(':(' if li[4] - li[0] > li[5] else 'Yay!')














Measured memory_bytes: 9112
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef vector<pair<ll,ll> > vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int INF=1e9+7;

int main(){
  ll n,sum=0;cin>>n;
  vll ans(n,-1),d(n);vvb g(n,vb(n,false));
  priority_queue<ll> c;
  rep(i,0,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    g[a][b]=true;g[b][a]=true;
  }
  rep(i,0,n){
    int C;cin>>C;
    c.push(C);
    d[i]=C;
  }
  queue<ll> q;
  q.push(0);
  ans[0]=c.top();c.pop();
  while(!q.empty()){
    ll now=q.front();q.pop();
    rep(i,0,n){
      if(g[now][i]&&ans[i]==-1){
        ans[i]=c.top();c.pop();
        q.push(i);

      }
    }
  }
  sort(d.begin(),d.end());
  rep(i,0,n-1){
    sum+=d[i];
  }
  cout<<sum<<endl;
  rep(i,0,n){
    cout<<ans[i]<<" ";
  }
  cout<<endl;
}


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

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

    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll i = 0;i < n;i++){
        cin >> a[i];
        a[i]--;
    }
    vector<ll> num(n);
    for (ll i = 0;i < n;i++){
        num[a[i]]++;
    }
    ll t = 0;
    for (ll i = 0;i < n; i++){
        if (num[i] > 0){
            t++;
        }
    }

    sort(num.begin(), num.end());
    
    ll ans = 0;
    ll i = 0;
    while (t > k){
        if (num[i] > 0){
            ans += num[i];
            num[i] = 0;
            t--;
        }
        i++;
    }
    cout << ans << endl;    
}

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll w,h,n; cin>>w>>h>>n;
    ll ans,x1=0,x2=w,y1=0,y2=h;
    rep(i,n){
        ll x,y,a;
        cin>>x>>y>>a;
        if(a==1) x1=max(x1,x);
        if(a==2) x2=min(x2,x);
        if(a==3) y1=max(y1,y);
        if(a==4) y2=min(y2,y);
    }
    if(x1>=x2||y1>=y2) ans=0;
    else ans=(x2-x1)*(y2-y1);
    cout<<ans<<endl;
    return 0;
}

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

using ll = long long;
// #define int long long

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
/***** MAIN *****/
signed main() {
  int n, a, b;
  cin >> n >> a >> b;
  if((b-a)%2 == 0) cout << "Alice";
  else cout << "Borys";
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int mod = 1000000007;


int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n;
  ll d;
  cin>>n>>d;
  int ret = 0;
  while(n--){
    ll x,y;
    cin>>x>>y;
    if(x*x+y*y<=d*d)ret++;
  }
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 3632
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))

dis = (c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2

if dis > (c1[2] + c2[2]) ** 2:
  print(4)
elif dis == (c1[2] + c2[2]) ** 2:
  print(3)
elif dis > (c1[2] - c2[2]) ** 2:
  print(2)
elif dis == (c1[2] - c2[2]) ** 2:
  print(1)
else:
  print(0)
  


Measured memory_bytes: 5596
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int k = sc.nextInt();
        if (k >= (1 << m)) {
            System.out.println(-1);
            return;
        }
        if (m == 1) {
            if (k == 0) {
                System.out.println("0 0 1 1");
            } else {
                System.out.println(-1);
            }
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < (1 << m); i++) {
            if (i == k) {
                continue;
            }
            sb.append(i).append(" ");
        }
        sb.append(k).append(" ");
        for (int i = (1 << m) - 1; i >= 0; i--) {
            if (i == k) {
                continue;
            }
            sb.append(i).append(" ");
        }
        sb.append(k);
        System.out.println(sb);
     }
}

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

int main() {
  int X;
  cin >> X;
  
  int y = 0;
  int z = X;
  while (X != 0) {
    y += X%10;
    X /=10;
  }
  
  if (z%y == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  
}


Measured memory_bytes: 256
class Light
  def initialize(p_bool, connects)
    @p = p_bool
    @connects = connects
  end

  def shine?(switch_status)
    @connects.map { |a| switch_status[a - 1] }.inject(0, :+) % 2 == @p
  end
end

N, M = gets.chop.split.map(&:to_i)

connects = []
M.times do
  line = gets.chop.split.map(&:to_i)
  line.shift
  connects << line.to_a
end

pr = gets.chop.split.map(&:to_i)

lights = []
connects.each do |c|
  lights << Light.new(pr.shift, c)
end

ans = 0
0.upto(2**N - 1) do |binary_status|
  switch_status = [*(0..(N - 1))].map { |i| binary_status[i] }
  ans += 1 if lights.all? { |light| light.shine?(switch_status) }
end

puts ans


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

#define EPS 1e-10
#define INF 1000000000

typedef struct {
	int x1, y1, x2, y2;
} Line;

Line line[102][3];

int rel_s_s(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double *x, double *y) {
	const double dn = (x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1);
	const double nm = (x3 - x1) * (y4 - y3) - (x4 - x3) * (y3 - y1);

	if (fabs(dn) < EPS)
		return 2;
	else
		if (fabs(nm / dn - 0.5) < 0.5 + EPS && fabs(((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)) / dn - 0.5) < 0.5 + EPS) {
			*x = x1 + nm / dn * (x2 - x1);
			*y = y1 + nm / dn * (y2 - y1);
			return 0;
		} else
			return 6;
}

int main(void) {
	int n, t[103], v[102];

	scanf("%d", &n);

	t[0] = -100;
	t[1] = 0;
	t[n + 2] = INF;
	v[0] = 0;
	v[n + 1] = 0;
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		t[i + 1] = t[i] + tmp;
	}
	for (int i = 1; i <= n; i++)
		scanf("%d", v + i);

	for (int i = 0; i <= n + 1; i++) {
		line[i][0] = (Line){0, v[i] + t[i], t[i], v[i]};
		line[i][1] = (Line){t[i], v[i], t[i + 1], v[i]};
		line[i][2] = (Line){t[i + 1], v[i], t[n + 1], v[i] + t[n + 1] - t[i + 1]};
	}

	double cur_x = 0, cur_y = 0;
	int cur_idx = 0;
	int cur_type = 2;
	double sum = 0;
	while (cur_x < t[n + 1]) {
		const Line l = line[cur_idx][cur_type];
		double x, y;
		double min_x = l.x2, min_y = 0;
		int min_idx = 0, min_type = 0;

		if (cur_type == 0) {
			sum += (cur_y + l.y2) * (l.x2 - cur_x) / 2.;

			cur_x = l.x2;
			cur_y = l.y2;
			cur_type = 1;
		} else if (cur_type == 1) {
			for (int i = cur_idx + 1; i <= n + 1; i++) {
				const Line m = line[i][0];
				int rel = rel_s_s(l.x1, l.y1, l.x2, l.y2, m.x1, m.y1, m.x2, m.y2, &x, &y);
				if (rel == 0)
					if (x < min_x) {
						min_x = x;
						min_idx = i;
					}
			}

			if (min_x < l.x2) {
				cur_idx = min_idx;
				cur_type = 0;
			} else
				cur_type = 2;

			sum += cur_y * (min_x - cur_x);

			cur_x = min_x;
		} else {
			for (int type = 0; type <= 1; type++)
				for (int i = cur_idx + 1; i <= n + 1; i++) {
					const Line m = line[i][type];
					int rel = rel_s_s(l.x1, l.y1, l.x2, l.y2, m.x1, m.y1, m.x2, m.y2, &x, &y);
					if (rel == 0)
						if (x < min_x) {
							min_x = x;
							min_y = y;
							min_idx = i;
							min_type = type;
						}
				}

			sum += (cur_y + min_y) * (min_x - cur_x) / 2.;

			cur_x = min_x;
			cur_y = min_y;
			cur_idx = min_idx;
			cur_type = min_type;
		}
	}

	printf("%f\n", sum);

	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
	int a, b, c, i, d;
	scanf("%d %d %d", &a, &b, &c);
	for(i=a; i<=b; i++){
		if(c%i==0){
			d++;
		}
	}
	printf("%d\n", d);
		
	return 0;
}

Measured memory_bytes: 596
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int n;
string s;
int cur;

int num(){
	int res=0;
	while(isdigit(s[cur])){
		res=res*10+s[cur]-'0';
		cur++;
	}
	return res;
}

int f(){
	assert(s[cur]=='[');
	cur++;
	if(isdigit(s[cur])){
		int res=num();
		cur++;
		return (res+1)/2;
	}else{
		vi v;
		while(s[cur]=='['){
			v.pb(f());
		}
		cur++;
		int res=0;
		sort(v.begin(),v.end());
		rep(i,(sz(v)+1)/2)res+=v[i];
		return res;
	}
}

void main2(){
	cur=0;
	cout<<f()<<endl;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>n;
	while(n--){
		cin>>s;
		s+="#";
		main2();
	}
}

Measured memory_bytes: 1312
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# Dかそれぞれのqueryで固定なのでこの問題は解ける
H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()
# piece[0]からpiece[1]まで
# 4 → 6　→ 8
piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]

# 飛ばし累積和
x_plus = []
y_plus = []
for i in range(D):
    list_x = [0]
    list_y = [0]
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
        list_x.append(list_x[-1] + opt_x)
        list_y.append(list_y[-1] + opt_y)
    list_x.pop(0)
    list_y.pop(0)
    x_plus.append(list_x)
    y_plus.append(list_y)

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    mul = (start - 1) % D
    if D == 1:
        x_point = x_plus[0][goal - 1] - x_plus[0][start - 1]
        # 書き間違い!!
        y_point = y_plus[0][goal - 1] - y_plus[0][start - 1]
    else:
        x_point = x_plus[mul][(goal - mul) // D] - x_plus[mul][(start - mul) // D]
        y_point = y_plus[mul][(goal - mul) // D] - y_plus[mul][(start - mul) // D]
    return x_point + y_point

for i in range(Q):
    print(past_exam(piece[i]))

Measured memory_bytes: 121688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl


int main() {
    int N, M;  cin >> N >> M;
    vector<int> a(M);  rep(i, M) cin >> a[i];
    vector<int> s(N+1, 0);
    rep(i, M) {
        s[a[i]]++;
    }

    ll dp[N+1];
    rep(i, N+1) dp[i] = 0;

    dp[0] = 1;
    if (s[1] == 0) dp[1] = dp[0];

    REP(i, 2, N+1) {
        if (s[i] == 0) {
            dp[i] = dp[i-1] % MOD + dp[i-2] % MOD;
        }
    }
    print(dp[N] % MOD);
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	
	int N,A,B,C,D;
	scanf("%d %d %d %d %d\n",&N,&A,&B,&C,&D);
	int i;
	int S[N+1];
	char w;
	for(i=1; i < N+1; i++)
	{
		scanf("%c",&w);
		if(w=='#') S[i] = 1;
		else if(w=='.') S[i] = 2;
	}
	int ans = 0;
	if(C < D)
	{
		for(i = A; i < D; i++)
		{
			if(S[i] == 1 && S[i+1] == 1)
			{
				printf("No");
				return 0;
			}
		}
		printf("Yes");
	}
	else if(D < C)
	{
		for(i = A; i < C; i++)
		{
			if(S[i] == 1 && S[i+1] == 1)
			{
				ans = 1;
			}
		}
		for(i = B; i <= D; i++)
		{
			if(S[i] == 2 && S[i+1] == 2 && S[i-1] == 2 && ans == 0) ans = 2;
		}
		if(ans == 0) ans = 1;
	}
	if(ans == 2) printf("Yes");
	else if(ans == 1) printf("No");
	//printf("C = %d, D = %d, ans = %d\n",C,D,ans);
	return 0;
}


Measured memory_bytes: 896
N = gets.chomp.to_i
sides = {}
(N-1).times do |i|
  a, b, c = gets.chomp.split(' ').map(&:to_i)
  sides[a] ||= {}
  sides[b] ||= {}
  sides[a][b] = c
  sides[b][a] = c
end

qs = []
Q, K = gets.chomp.split(' ').map(&:to_i)
Q.times do
  qs.push gets.chomp.split(' ').map(&:to_i)
end

cost = []
cost[K] = 0

g = [[K, 0]]
while g.length > 0
  node, dis = g.shift
  sides[node].each do |k, v|
    b = k
    c = v
    unless cost[b]
      cost[b] = dis + c
      g.push [b, cost[b]]
    end
  end
end

qs.each do |q|
  print "#{cost[q[0]] + cost[q[1]]}\n"
end

Measured memory_bytes: 62968