akhauriyash/Code-Regression huggingface dataset:
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Stack, Queue, PriorityQueue, Set}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N = in.next().toInt
  val S = in.next()

  // val a = new Array[Int](N)

  val ans = Set[String]()

  var dp = Set[String]()

  for (c <- S) {
    val next = Set[String]()
    next += c.toString
    for (s <- dp) {
      s.length match {
        case 2 =>
          ans += s + c
          next += s
        case _ =>
          next += s + c
          next += s
      }
    }

    dp = next
  }


  println(ans.size)
}

object Sub {
  def print2DimArray[A](mat: Array[Array[A]]): Unit = {
    mat.foreach(lin => println(lin.deep))
  }
}

class InputReader(stream: InputStream) {
  private[this] val reader = new BufferedReader(new InputStreamReader(stream))
  private[this] var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 117128
#include<bits/stdc++.h>
using namespace std;
int  main (){
  int n;
  int a=0,b=0,c=1000000000;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    b=max(a,b);
    c=min(a,c);
  }
  cout<<b-c<<"\n";
  return(0);
}


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

#define pb push_back
#define all(a) begin(a), end(a)
#define deb(x) cout << #x << " = " << x << endl
#define debu(x, y) cout << "( " << #x << ", " << #y << " ) = ( " << x << ", " << y << " )" << endl
#define int long long

typedef long long ll;
ll mod=1000000007;
int s;

int fun(int a) {
    if(a < 3) {
        return -1;
    }
    int val = 0;
    for(int i=3; i<=s; i++) {
        if(a-i < 3) break;
        val += fun(a-i);
        val++;
    }
    return val;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;

    int ans = 0;

    if( s < 3 ) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> dp(2005, 1);
    for(int i=0; i<3; i++) {
        dp[i] = 0;
    }
    for(int i=4; i<=s; i++) {
        for(int j=3; j<i; j++) {
            if(i-j < 3 && j != i) continue;
            dp[i] = (dp[i] + dp[j])%mod;
        }
    }


    cout << dp[s] << endl;

    return 0;
}


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

int l[8];

int bitcount(int a){
  int ret=0;
  while(a>0){
    ret+=a%2;
    a/=2;
  }
  return ret;
}

int get(int a){
  int ret=0;
  for(int i=0;a>0;a/=2,++i){
    if(a%2==1){
      ret+=l[i];
    }
  }
  return ret;
}


int main(){

  int N,A,B,C;
  
  std::cin>>N>>A>>B>>C;
  
  for(int i=0;i<N;++i){
    std::cin>>l[i];
  }
  
  std::sort(l,l+N);
  
  int ans=99999999;


  for(int a=1;a<(1<<N);++a){
    for(int b=1;b<(1<<N);++b){
      if((a&b)>0)continue;
      for(int c=1;c<(1<<N);++c){
	if((b&c)>0||(a&c)>0)continue;
	int cur=bitcount(a)+bitcount(b)+bitcount(c)-3;
	cur*=10;
	cur+=std::abs(get(a)-A)+std::abs(get(b)-B)+std::abs(get(c)-C);
	ans=std::min(ans,cur);
      }   
    }
  }
  std::cout<<ans<<std::endl;
  return 0;
}


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

int main() {
    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());
        
    if(s < t) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
   
      long long n,i,j,k,sum=0,count=0,ans=0,x=0,y=0,l,r,m;
     string s;
     cin>>s;
     n=s.length();
     for(i=0;i<n;i++)
     {
         k=int(s[i]-'0');
         ans+=k;
     }
     if(ans%9==0)
     cout<<"Yes";
     else
     cout<<"No";
     
     

	return 0;
}

Measured memory_bytes: 3720
#include<iostream>
#include<stack>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int n;
	cin>>n;
	int p[n];
	string res="";
	stack<int> st;
	rep(i,n)cin>>p[i];
	st.push(-1);
	bool check=false;
	int cnt=1;
	rep(i,n){
		int tmp=st.top();
		st.pop();
		if(tmp==-1){
			st.push(-1);
			while(cnt<=p[i]){
				st.push(cnt);
				cnt++;
				res+="(";
			}
			res+=")";
		}else{
			if(tmp<p[i]){
				while(cnt<=p[i]){
					st.push(cnt);
					cnt++;
					res+="(";
				}
				res+=")";
			}else if(tmp>p[i]){
				check=true;
				break;
			}else{
				res+=")";
			}
		}
		if(st.top()!=-1)st.pop();
	}
	if(check)cout<<":("<<endl;
	else cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3740
N,M=map(int,input().split())
L=[[0 for i in range(4)]for i in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    L[i][0]=i
    L[i][1]=a
    L[i][2]=b
L2=sorted(L,key= lambda x: (x[1],x[2]))

c=0
t=0
for i in range(M):
    if(L2[i][1]!=c):
        c=L2[i][1]
        t=1
    L2[i][3]=t
    t+=1

L3=sorted(L2,key= lambda x: (x[0]))

for i in range(M):
    print('{0:06d}'.format(L3[i][1]),'{0:06d}'.format(L3[i][3]),sep="")

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

void Knapsack_1(vector<int> &weight, vector<int> &val, int maxCap)
{
	int n = weight.size();
	
	// It's very important to make DP as long long
	vector<vector<long long>> dp(n + 1, vector<long long>(maxCap + 1, 0));

	/* dp[n][cap] represents the maximum value that you can get from the first 'n' items
	 * with a knapsack of capactiy 'cap'
	 */

	// No elements to choose from 
	for(int cap = 0; cap <= maxCap; cap++)
		dp[0][cap] = 0;
	
	// The knapsack has zero capacity
	for(int i = 0; i <= n; i++)
		dp[i][0] = 0;

	for(int i = 1; i <= n; i++)
	{
		for(int cap = 0; cap <= maxCap; cap++)
		{
			long long take_it = 0, leave_it = 0;

			if(weight[i-1] <= cap)
				take_it = val[i-1] + dp[i-1][cap - weight[i-1]];

			leave_it = dp[i-1][cap];

			dp[i][cap] = max(take_it, leave_it);
		}
	}

	cout << dp.back().back() << endl;
}

int main()
{
	int n, maxCap;
	cin >> n >> maxCap;

	vector<int> weight(n), val(n);

	for(int i = 0; i < n; i++)
		cin >> weight[i] >> val[i];

	Knapsack_1(weight, val, maxCap);
	return 0;
}





Measured memory_bytes: 80256
/*
	Author: zxy_hhhh
	date: 2020/05/23
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<iostream>
#define ll long long
inline ll rd() {
	ll _x=0;int _ch=getchar(),_f=1;
	for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
	if (_ch=='-'){_f=0;_ch=getchar();}
	for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
	return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 505
int f[maxn][maxn];
int n;
int p[maxn*maxn];
bool vis[maxn][maxn];
int hx[4]={0,0,-1,1};
int hy[4]={1,-1,0,0};
void bfs(int pos) {
	std::deque< std::pair<int,int> > que;
	que.push_back(std::make_pair((pos-1)/n+1,(pos-1)%n+1));
	while(!que.empty()) {
		std::pair<int,int> now=que.front();que.pop_front();
		if (!vis[now.first][now.second]) {
			for(int k=0;k<4;k++) {
				int x=now.first+hx[k],y=now.second+hy[k];
				if (f[x][y]>f[now.first][now.second]) 
					f[x][y]=f[now.first][now.second],que.push_front(std::make_pair(x,y));
			}
		}
		else {
			for(int k=0;k<4;k++) {
				int x=now.first+hx[k],y=now.second+hy[k];
				if (f[x][y]>1+f[now.first][now.second]) 
					f[x][y]=f[now.first][now.second]+1,que.push_back(std::make_pair(x,y));
			}

		}
	}
}
int main() {
	n=rd();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			f[i][j]=std::min(std::min(i-1,j-1),std::min(n-i,n-j));
			vis[i][j]=1;
		}
	}
	int cnt=0;
	for(int i=1;i<=n*n;i++) {
		p[i]=rd();
		int x=(p[i]-1)/n+1,y=(p[i]-1)%n+1;
		vis[x][y]=0;
		bfs(p[i]);
		cnt+=f[x][y];
		// for(int a=1;a<=n;a++) {
		// 	for(int b=1;b<=n;b++) {
		// 		wrt(f[a][b],' ');
		// 	}
		// 	putchar('\n');
		// }
		// putchar('\n');
	}
	wrt(cnt,'\n');
}

Measured memory_bytes: 6028
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef unsigned long long ll;
typedef pair<ll,int> P;

int main(){
  vector<ll> V;
  ll N,temp;
  ll K,ans=0,count1=0,count2=0;

  cin>>N>>K;

  for(ll i=0;i<N;i++){
    cin>>temp;
    V.push_back(temp);
  }
  //cout<<V[0]<<endl;
  for(ll i=0;i<N;i++,count1=0,count2=0){
    for(ll j=0;j<i;j++){
      if(V[i]>V[j]) count1++; 
    }

    for(ll k=i+1;k<N;k++){
      if(V[i]>V[k]) count2++;
    }
    //cout<<V[i]<<" "<<count1<<" "<<count2<<endl;
    ans+=(count2*K)%MOD;
    ans+=(count2+count1)*((K*(K-1)/2)%MOD);
    ans%=MOD;
  }
  ans%=MOD;
  cout<<ans<<endl;
}


Measured memory_bytes: 256
"use strict";

function main(arg) {
    const A = arg.split("\n")[0].split(" ")[0];
    const B = arg.split("\n")[0].split(" ")[1];
    if(A <=8 && B <=8) {
        console.log("Yay!");
    } else {
        console.log(":(");
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a1,a2,a3;
	cin>>a1>>a2>>a3;
	if((a1+a2+a3)>=22)
	    cout<<"bust"<<"\n";
	else
	    cout<<"win"<<"\n";
  return 0;  
}

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

int main() {
    string s,s1,s2;
    cin >> s;
    for(int i=s.length()-2;i>=2;i-=2){
        s1=s.substr(0,i/2);
        s2=s.substr(i/2,i/2); //i/2番目からi/2個分r取り出し
        if(s1==s2){
            cout << i << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
 int d;
 long int S;
 while (cin >> d) {
  S = 0;
  for (int i=1; i<600/d; ++i) {
   S += i*i*d*d*d;
  }
  cout << S << endl;
 }
}


Measured memory_bytes: 1160
#include "bits/stdc++.h"

struct statement
{
  int a, b;
  std::string op;

  int print() const
  {
    if (op == "+")
    {
      printf("%d\n", a + b);
    }
    else if (op == "-")
    {
      printf("%d\n", a - b);
    }
    else if (op == "*")
    {
      printf("%d\n", a * b);
    }
    else if (op == "/")
    {
      printf("%d\n", a / b);
    }
    else if (op == "%")
    {
      printf("%d\n", a % b);
    }
    else
    {
      return 1;
    }
    return 0;
  }
};

int main()
{
  auto v = std::vector<statement>{};

  int a, b;
  std::string op;

  while (std::cin >> a >> op >> b)
  {
    auto s = statement{};
    s.a = a;
    s.b = b;
    s.op = op;
    v.push_back(s);
  }

  for (auto s : v)
  {
    auto has_finished = s.print();
    if (has_finished)
    {
      break;
    }
  }
  return 0;
}



Measured memory_bytes: 3196
white, black = map(int,input().split())
white -= 1
black -= 1

grid = [['#' for i in range(100)] for j in range(100)]
for i in range(1, 99):
    for j in range(50, 99):
        grid[i][j] = "."

a = 3
b = 3
while True:
    if white == 0:
        break
    grid[a][b] = "."
    white -= 1
    a += 2
    if a > 93:
        a = 3
        b += 2
    
 
c = 3
d = 53
while True:
    if black == 0:
        break
    grid[c][d] = "#"
    black -= 1
    c += 2
    if c > 93:
        c = 3
        d += 2
    

print(100, 100)
for i in grid:
    print("".join(i))

Measured memory_bytes: 3188
n, a = map(int, input().split())
x = list(map(int, input().split()))

x_max = max(x)
y = [i-a for i in x]


def ave_comb():
    dp = [[0 for d in range(2*n*x_max+1)] for c in range(n+1)]
    for i in range(n+1):
        dp[i][n*x_max] = 1

    for i in range(1, n+1):
        for j in range(1, 2*n*x_max+1):
            if 0 <= j - y[i-1] <= 2 * n * x_max:
                dp[i][j] = dp[i-1][j-y[i-1]] + dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][n*x_max] - 1


def main():
    print(ave_comb())


if __name__ == '__main__':
    main()


Measured memory_bytes: 5740
#include <cstdio>
#include <algorithm>

typedef long long ll;

using namespace std;

int main() {
    ll n, a, b, prev, now, cnt = 0;
    scanf("%lld%lld%lld%lld", &n, &a, &b, &prev);
    for (ll i = 1; i < n; ++i) {
        scanf("%lld", &now);
        cnt += min(b, a * (now - prev));
        prev = now;
    }
    printf("%lld\n", cnt);
    return 0;
}


Measured memory_bytes: 128
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

n = int(input())
h = [0] + list(map(int, input().split()))

INF = 10**15

dp = [INF]*(n+5)
dp[0] = 0
dp[1] = 0
dp[2] = abs(h[2]-h[1])

for i in range(3,n+1):
    dp[i] = min([dp[i-2] + abs(h[i] - h[i-2]),dp[i-1] + abs(h[i] - h[i-1]) ])

print(dp[n])


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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
using P = pair<int,int>;
//Write From this Line

int main()
{
	int n;
	cin >> n;
	vector<ll> dp(1010,1);
	vector<int> a(n), b(n);
	rep(i,n) cin >> a[i] >> b[i];
	rep(i,n){
		if(i == 0) continue;
		dp[i] = (a[i-1] * dp[i-1] + a[i] - 1) / a[i];
		dp[i] = max(dp[i], (b[i-1] * dp[i-1] + b[i] - 1) / b[i]);
	}
	cout << (a[n-1] + b[n-1]) * dp[n-1]  << endl;
}


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

using namespace std;
constexpr long long MOD = 1000000007;

int main(void) {
    int N, M;
    set<int> a;
    vector<int> dp(100010,0);
    cin >> N >> M;
    for (int i=0;i<M;i++) {
        int q;
        cin >> q;
        a.insert(q);
    }

    dp[0] = 1; dp[1] = 1;
    for (int i=2;i<=N;i++) {
        if (a.find(i) != a.end()) continue;
        dp[i] = dp[i-2] + dp[i-1];
        if (a.find(i-2) != a.end()) dp[i] -= dp[i-2];
        if (a.find(i-1) != a.end()) dp[i] -= dp[i-1];
        dp[i] %= MOD;
    }
    cout << dp[N] << endl;

    return 0;
}

Measured memory_bytes: 5376
H, W = gets.chomp.split(" ").map(&:to_i)
S = [Array.new(W+2, '#')]
H.times{
  S << gets.chomp.chars.unshift('#').push('#')
}
S << Array.new(W+2, '#')

c_w = S.inject(0){|r, s|
  r + s.count{|c| c == '.'}
}
bef = [[1, 1]]
S[1][1] = '#'
cnt = 1
until bef.empty? do
  nxt = []
  bef.each{|x, y|
    (S[x-1][y] = '#'; nxt << [x-1, y]) if S[x-1][y] == '.'
    (S[x+1][y] = '#'; nxt << [x+1, y]) if S[x+1][y] == '.'
    (S[x][y-1] = '#'; nxt << [x, y-1]) if S[x][y-1] == '.'
    (S[x][y+1] = '#'; nxt << [x, y+1]) if S[x][y+1] == '.'
  }
  bef = nxt
  cnt += 1
  break if bef.include?([H, W])
end

puts bef.include?([H, W]) ? c_w - cnt : -1


Measured memory_bytes: 2172
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        mut x: isize,
        mut k: isize,
        d: isize,
    }

    x = isize::abs(x);
    let num = std::cmp::min(k, x / d);
    k -= num;
    x -= d * num;

    println!("{}", if k % 2 == 0 { x } else { d - x });
}


Measured memory_bytes: 2188
//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
 
const int maxn=1e6+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;
 
ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));}
ll arr[maxn];
ll lc=1;
ll mx[maxn] ;
ll ans;
ll ted;
void primeFactors(int n)  
{  
	ted = 0 ;
    while (n % 2 == 0)  
    {  
        ted++; 
        n = n/2; 
    }
    mx[2] = max(mx[2] , ted);
	ted = 0 ;  
    for (int i = 3; i*i <= n; i = i + 2)  
    {  
    	ted = 0 ;
        while (n % i == 0)  
        {  
            ted++; 
            n = n/i;  
        }
        mx[i] = max(mx[i] , ted);  
    }  
    if (n > 2){
        mx[n] = max(mx[n] , 1LL);
    }  
         
}    
int main()  
{  
    ll n;
    cin >> n; 
    for(int i = 0 ; i < n ; i++){
        cin >> arr[i];
    }     
 
    for(int i = 0 ; i < n ; i++){
        primeFactors(arr[i]);
    }
 
    for(int i = 0 ; i < maxn ; i++){
        if(mx[i]!=0){
            lc= lc*poww(i , mx[i] , 1e18);
            lc%=mod;
        }
    }
    for(int i = 0 ; i < n ;i++){
        ans+=lc*poww(arr[i] , mod-2, mod);
        ans%=mod;
    }  
    cout<<ans;
    return 0;  
}  

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

const int N = 1e5 + 100;
int vt[N], up[22][N];

void solve() {
    int n, L, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> vt[i];
    }

    cin >> L;

    int rh = 1;
    for (int l = 1; l <= n; l++) {
        while (rh <= n && vt[rh] - vt[l] <= L)
            rh++;
        int r = rh - 1;
        up[0][l] = r;
    }

    for (int lvl = 1; lvl < 22; lvl++) {
        for (int v = 1; v <= n; v++) {
            up[lvl][v] = up[lvl - 1][up[lvl - 1][v]];
        }
    }

    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        if (l > r)
            swap(l, r);

        int left = 1, right = r - l, ans = r - l;
        while (left <= right) {
            int mid = (left + right) >> 1;

            int v = l;
            for (int lvl = 21; lvl >= 0; lvl--)
                if (mid & (1 << lvl))
                    v = up[lvl][v];

            if (v >= r) {
                ans = mid;
                right = mid - 1;
            }
            else
                left = mid + 1;
        }

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

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(20);
    solve();
    return 0;
}


Measured memory_bytes: 9856
#include <bits/stdc++.h>
#define ll long long
#define uint unsigned long long
#define db double
#define ls x << 1
#define rs x << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n, L, x[200010], dp[200010][20];
 
int main()
{
	n = read();
	rep(i, 1, n) x[i] = read();
	L = read();
    x[n + 1] = 2e9;
    rep(i, 1, n) 
    	dp[i][0] = lower_bound(x + 1, x + n + 2, x[i] + L + 1) - (x + 1);
    int p;

    for(p = 1; (1 << p) <= n; p ++)
        rep(k, 1, n)
            dp[k][p] = dp[dp[k][p - 1]][p - 1];
    int q = read();
    while(q --)
    {
        int a, b;
        a = read();
        b = read();
        if(a > b) swap(a, b);
        int ans = 0;
        rrep(i, p - 1, 0)
            if(dp[a][i] < b)
            {
                ans += (1 << i);
                a = dp[a][i];
            }
        while(a < b) ans ++, a = dp[a][0];
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 11008
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
num_dic = {}
for i in A:
    if i not in num_dic:
        num_dic[i] = 1
    else:
        num_dic[i] += 1
ans = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    if not b in num_dic:
        print(ans)
        continue
    else:
        if c in num_dic:
            ans -= num_dic[b] * b
            ans += num_dic[b] * c
            num_dic[c] += num_dic[b]
            num_dic[b] = 0
        else:
            ans -= num_dic[b] * b
            ans += num_dic[b] * c
            num_dic[c] = num_dic[b]
            num_dic[b] = 0
        print(ans)

Measured memory_bytes: 85328
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define lla(s) s.rbegin(),s.rend()
#define pcnt(b) __builtin_popcount(b)
#define vi vector<int>
#define vvi vector<vector<int>>
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const ll INF = 1e18;

int G[100010]={};


int pw(int a, int st) {
    if (st == 0) return 1;
    int b = pw(a, st / 2);
    b = (b * b) % MOD;
    if (st % 2)
        return (a * b) % MOD;
    return b;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    rrep(i,k,1){
        int tmp = pw(k/i,n)%MOD;
        for(int j = i + i;j <= k;j+=i){
            tmp = (tmp-G[j])%MOD;
        }
        G[i] = tmp%MOD;
    }
    int ans = 0;
    rep(i,1,k+1){
        ans += i*G[i]%MOD;
        ans%=MOD;
    }
    cout<<ans<<endl;
}

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

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

graph = [[] for _ in range(N+1)]
for a,b in zip(AB,AB):
    graph[a].append(b)
    graph[b].append(a)

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

stack = [1]
parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

print(' '.join(map(str,val[1:])))

Measured memory_bytes: 85876
n = int(input())
a = list(map(int, input().split()))

abs_a = list(map(abs, a[:]))
s = sum(abs_a[:])
m = len([i for i in a if i < 0])
if m % 2 == 0:
  print(s)
else:
  print(s - 2 * min(abs_a))

Measured memory_bytes: 14332
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 準備
            List<char> lstA = "ACGT".ToList();

            // 入力
            List<char> lstS = System.Console.ReadLine().Trim().ToList();

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            for (int i = 0; i < lstS.Count; i++)
            {
                if (lstA.Contains(lstS[i])) { lstS[i] = '1'; }              // 文字列内のACGTを1に
                else { lstS[i] = '0'; }                                     // それ以外を0に
            }
            string sCng = string.Join("", lstS);
            List<string> sOut = sCng.Split('0').ToList();                   // 文字列を0で分割
            sOut.Sort(delegate (string mca1, string mca2) { return (int)(mca2.Length - mca1.Length); });        // 文字列長の降順

            // 出力
            System.Console.WriteLine("{0}", sOut[0].Length.ToString());     // 一番長いの

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 13280
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
#define No cout<<"No"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int n;
    cin>>n;
    ll a[n];
    rep(i,n){
        cin>>a[i];
    }
    vector<ll> b;
   
    for(int i=n-1;i>=0;i-=2){
        b.push_back(a[i]);
        }
    for(int i=(n%2==0?0:1);i<n;i+=2){
        b.push_back(a[i]);
    }
    rep(i,n-1){
        cout<<b[i]<<' ';
    }
    cout<<b[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 5488
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    let s: String = iter.next().unwrap().parse().unwrap();
    let split: Vec<_> = s.split("").collect();
    let split: Vec<_> = split[1..split.len() - 1].to_vec();

    if split[2] == split[3] && split[4] == split[5] {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

// 文字列からi番目までにACが表れた数の累積和配列を作る。
// あとは、sum_pile[a] - sum_pile[b] を順に出力。

int main(){
    int N,Q;
    cin >> N >> Q ;
    string S;
    cin >> S ;
    vector<long long int> sum_pile(N+1);
    int temp = 0;
    sum_pile[0] = 0;
    for(int i = 1;i < N;i++){ // 累積和配列の作成

        if(S[i] == 'C'){
            if(S[i-1] == 'A'){
                temp += 1;
                sum_pile[i] = temp;
                continue;
            }
        }

    sum_pile[i] = temp;

    }

    int l,r;
    for(int j = 0;j < Q;j++){
        cin >> l >> r;
        cout << sum_pile[r-1] - sum_pile[l-1] << endl;
    }

}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;

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

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

int main()
{

    int mx = 2000001;
    VL isPrime(mx, true);
    isPrime[0] = false;
    isPrime[1] = false;
    rep(i, mx)
    {
        if (isPrime[i] == false)
            continue;
        for (int j = 2 * i; j < mx; j += i)
        {
            isPrime[j] = false;
        }
    }
    VL primes;
    rep(i, mx)
    {
        if (isPrime[i])
        {
            primes.push_back(i);
        }
    }
    int n;
    cin >> n;

    VL v(n);
    bool f1 = true;
    VL fact(1000000 + 5, 0);
    rep(i, n)
    {
        cin >> v[i];
    }
    ll sgcd = v[0];
    rep(i, n)
    {
        sgcd = gcd(sgcd, v[i]);
        ll x = v[i];
        ll cur = 0;
        while (x != 1 && isPrime[x] == false)
        {
            //cerr << cur << endl;
            if (x % primes[cur] == 0)
            {
                while (x % primes[cur] == 0)
                {
                    x /= primes[cur];
                }
                fact[primes[cur]]++;
            }
            cur++;
        }
        if (isPrime[x])
        {
            fact[x]++;
        }
    }
    rep(i, 1000000 + 5)
    {
        f1 &= (fact[i] <= 1);
    }

    bool f2 = sgcd == 1;
    if (f1)
    {
        cout << "pairwise coprime" << endl;
    }
    else if (f2)
    {
        cout << "setwise coprime" << endl;
    }
    else
    {
        cout << "not coprime" << endl;
    }

    return 0;
}

Measured memory_bytes: 35676
from collections import defaultdict

if __name__ == '__main__' :
        n = int(input())
        dic = defaultdict(list)
        for i in range(n):
            s,num = input().split(" ")
            dic[s].append(int(num))

        for s in ["S","H","C","D"]:
            for i in range(1,14):
                if i not in dic[s]:
                    print(s + " " + str(i))


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


using namespace std;

template <typename T>
class arr {
  int n;
  T *a;
  void raise(int x) {
    T *b=a;
    a=new T[x];
    copy(b,b+n,a);
    delete b;
  }
  T& operator << (T x) {
    if ((n&-n)==n) {
      raise(n<<1);
    }
    a[n++]=x;
  }
  void resize(int x) {
    if (n<x) {
      raise(1<<(32-__builtin_clz(x)));
    }
    n=x;
  }
  arr() {
    n=0;
    a=NULL;
  }
  arr(int x) {
    n=0;
    a=NULL;
    resize(x);
  }
  T& operator << (int x) {
    return a[x];
  }
};

int main() {
  string s;
  cin>>s;
  int k;
  cin>>k;
  for (int i=0;i<(int)s.length();i+=k) {
    cout<<s[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            
            if(H == 0 && W == 0){
                break;
            }
            
            for(int i = 0; i < H; i++){
                for(int j = 0; j < W; j++){
                    System.out.print("#");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

            


Measured memory_bytes: 35748
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] sa = br.readLine().split(" ");
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int i = 0; i < n; i++) {
			int a = Integer.parseInt(sa[i]);
			addCntMap(map, a);
		}
		br.close();

		int ans = 0;
		Integer[] arr = map.keySet().toArray(new Integer[0]);
		int t = 30;
		for (int r = arr.length - 1; r >= 0; r--) {
			if (!map.containsKey(arr[r])) {
				continue;
			}
			for ( ; t >= 0; t--) {
				if (arr[r] >= (1 << t)) {
					t++;
					break;
				}
			}
			int x = (1 << t) - arr[r];
			delCntMap(map, arr[r]);
			if (map.containsKey(x)) {
				delCntMap(map, x);
				ans++;
				r++;
			}
		}
		System.out.println(ans);
	}

	static void addCntMap(Map<Integer, Integer> map, Integer key) {
		if (map.containsKey(key)) {
			map.put(key, map.get(key) + 1);
		} else {
			map.put(key, 1);
		}
	}

	static void delCntMap(Map<Integer, Integer> map, Integer key) {
		if (key != null && map.containsKey(key)) {
			int val = map.get(key);
			if (val == 1) {
				map.remove(key);
			} else {
				map.put(key, val - 1);
			}
		}
	}
}


Measured memory_bytes: 63832
#include<stdio.h>
#define MAX 1000000
#define NO -1

typedef struct Node{
  int p;
  int l;
  int r;
}S;
S tree[MAX];

int Depth(int);
void Out(int);

int main(){
  int a,b,i,j,l,m,n;

  scanf("%d",&n);
  for(i = 0  ; i < n ; i++){
    tree[i].p=tree[i].r=tree[i].l=NO;
  }
  for(i = 0 ; i < n ; i++){
    scanf("%d%d",&a,&b);
    for(j = 0 ; j < b ; j++){
      scanf("%d",&m);
      if(j == 0){
        tree[a].l = m;
      }
      else {
        tree[l].r = m;
      }
      l = m;
      tree[m].p = a;
    }
  }
  for(i = 0 ; i < n ; i++){
    Out(i);
  }

  return 0;
}

int Depth(int x){
  int d=0;

  while(tree[x].p != NO){
    x = tree[x].p;
    d++;
  }

  return d;
}

void Out(int y){
  int i,j;

  printf("node %d: ",y);
  printf("parent = %d, ",tree[y].p);
  printf("depth = %d, ",Depth(y));

  if(tree[y].p == NO){
    printf("root, ");
  }
  else if(tree[y].l==NO){
    printf("leaf, ");
  }
  else{
    printf("internal node, ");
  }
  printf("[");

  for(i = 0 , j = tree[y].l ; j != NO ; i++ , j = tree[j].r){
    if(i){
      printf(", ");
    }
    printf("%d",j);
  }
  printf("]\n");
}



Measured memory_bytes: 2884
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mxn 100005
#define mp make_pair
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long int ll;
int n;
int dp[mxn];
int rec(int arr[], int i){
	if(i==n-1) return 0;
	if(dp[i] != -1) return dp[i]; 
	if(i+2 < n)
		dp[i] = min(rec(arr,i+1)+abs(arr[i+1] - arr[i]), rec(arr,i+2)+ abs(arr[i+2] - arr[i]));
	else if(i+1 < n)
		dp[i] = rec(arr,i+1) + abs(arr[i+1] - arr[i]);
	return dp[i];
}
int main(){
	 cin>>n;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	for(int i=0; i<=n; i++){
		dp[i] = -1;
	}
	cout<<rec(arr,0);
}

Measured memory_bytes: 8272
// D - Maximum Average Sets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

long double dp[51][51]; // dp[i][j]: i番目の品物の中からj個選んだときの合計の最大値
ll dp_cnt[51][51]; // dp_cnt[i][j]: i番目の品物の中からj個選んだときの合計を最大にする選び方の数
long double v[51];

int main() {
	int N, A, B;
	cin >> N >> A >> B;

	for (int i=1; i<=N; i++) {
		cin >> v[i];
	}

	dp_cnt[0][0] = 1;

	for (int i=0; i<N; i++) {
		for (int j=0; j<=i; j++) {
			// 品物iを選ばない更新
			if (dp[i+1][j] < dp[i][j]) {
				dp[i+1][j] = dp[i][j];
				dp_cnt[i+1][j] = dp_cnt[i][j];
			} else if (dp[i+1][j] == dp[i][j]) {
				dp_cnt[i+1][j] += dp_cnt[i][j];
			}

			// 品物iを選ぶ更新
			if (dp[i+1][j+1] < dp[i][j] + v[i+1]) {
				dp[i+1][j+1] = dp[i][j] + v[i+1];
				dp_cnt[i+1][j+1] = dp_cnt[i][j];
			} else if (dp[i+1][j+1] == dp[i][j] + v[i+1]) {
				dp_cnt[i+1][j+1] += dp_cnt[i][j];
			}
		}
	}

	vector<ll> K; // 選んだ品物の価値の平均が最大になるときの選んだ数（複数の場合あり）
	long double max_mean = 0;
	long double tmp_mean;
	for (int i=A; i<=B; i++) {
		tmp_mean = dp[N][i] / i;
		if (tmp_mean > max_mean) {
			max_mean = tmp_mean;
			K.clear();
			K.push_back(i);
		} else if (tmp_mean == max_mean) {
			K.push_back(i);
		}
	}

	ll num_choice = 0;
	for (ll k : K) {
		num_choice += dp_cnt[N][k];
	}

	cout << fixed << setprecision(10);
	cout << max_mean << endl;
	cout << num_choice << endl;

	// **** debug ****
	/*
	for (int i=0; i<=N; i++) {
		for (int j=0; j<=i; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	for (int i=0; i<=N; i++) {
		for (int j=0; j<=i; j++) {
			cout << dp_cnt[i][j] << " ";
		}
		cout << endl;
	}
	*/

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e18)+ll(7);
const ll MOD=1000000007LL;

vector<ll> three;
ll calc(ll T,ll V){
	if(T==0)return 0;
	ll ans=0;
	if(T-V*4>=0){
		ans = 2 + calc(T-V*4,V*3);
	}else if(T==V){
		ans = 1;
	}else{
		int ind = upper_bound(three.begin(),three.end(),T)-three.begin();
		ind--;
		if(three[ind]>V)ans = 1+calc(T-V,V);
		else ans = 1 + calc(T-three[ind],V);
	}
	return ans;
}


int main(){
	ll t,ans=0;
	cin >> t;
	ans = t;
	ll th = 1;
	FOR(i,0,34){
		three.push_back(th);
		th*=3;
	}
	if(t==4) ans=2;
	if(t>=5)ans = min(ans,calc(t-4,3)+2);
	cout << ans << endl;
}



Measured memory_bytes: 3172
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	vector<int> used(n + 1);
	rep(i, n) {
		used[b[i]] = 1;
	}
	int cnt = 0;
	rep(i, n) {
		cnt += used[i + 1];
	}
	if (cnt == n) {
		cout << "Yes" << endl;
		return;
	}
	cout << "No" << endl;
	rep(i, n-1)cout << 1 <<" ";
	cout <<1<< endl;
	rep(i, n) {
		if (used[a[i]])cout << 1;
		else cout << 2 ;
		if (i != n - 1)cout << " ";
	}
	cout << endl;
	return;
}

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


Measured memory_bytes: 4152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;ll A,B,l,r;
int main()
{
	cin>>n>>A>>B>>l>>r;
	B-=A;
	for (int i=1;i<n;i++){//
		ll R=1ll*i*r-1ll*(n-i-1)*l;
		ll L=1ll*i*l-1ll*(n-i-1)*r;
		if (L<=B&&B<=R) return puts("YES"),0;
	}
	puts("NO");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_N 125
#define INF 1e9
const double EPS = 1e-8;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<double> vec;
typedef vector<vec> mat;
 
vec gauss_jordan(const mat &A,const vec &b){
    int n = A.size();
    mat B(n,vec(n+1));
    for(int i = 0 ; i < n ; i++){
	for(int j = 0 ; j < n ; j++){
	    B[i][j] = A[i][j];
	}
    }
    for(int i = 0 ; i < n ; i++){
	B[i][n] = b[i];
    }
    for(int i = 0 ; i < n ; i++){
	int pivot = i;
	for(int j = i ; j < n ; j++){
	    if(abs(B[j][i]) > abs(B[pivot][i])){
		pivot = j;
	    }
	}
	swap(B[i],B[pivot]);
	if(abs(B[i][i]) < EPS) return vec();
	for(int j = i+1 ; j <= n ; j++){
	    B[i][j] /= B[i][i];
	}
	for(int j = 0 ; j < n ; j++){
	    if(i != j){
		for(int k = i+1 ; k <= n ; k++){
		    B[j][k] -= B[j][i]*B[i][k];
		}
	    }
	}
    }
    vec x(n);
    for(int i = 0 ; i < n ; i++){
	x[i] = B[i][n];
    }
    return x;
}
 
struct Edge{
    int to,dist;
    Edge(int to,int dist) :
	to(to),dist(dist) {}
};
 
void solve(vi &sign,vii &road,vii &d,int S,int T,int N){
    mat A(N,vec(N,0));
    vec b(N,0);
    for(int i = 0 ; i < N ; i++){
	if(i == T){
	    A[i][i] = 1; b[i] = 0;
	    continue;
	}
	double sum = 0;
	int cnt = 0;
	if(sign[i] == 0){
	    for(int j = 0 ; j < N ; j++){
		if(road[i][j] != INF){
		    A[i][j] = -1;
		    sum += road[i][j];
		    cnt++;
		}
	    }
	}else{
	    int mini = INF;
	    for(int j = 0 ; j < N ; j++){
		if(road[i][j] != INF){
		    mini = min(mini,road[i][j]+d[j][T]);
		}
	    }
	    for(int j = 0 ; j < N ; j++){
		if(mini == road[i][j]+d[j][T] && road[i][j] != INF){
		    cnt++;
		    A[i][j] = -1;
		    sum += road[i][j];
		}
	    }
	}
	A[i][i] = cnt;
	b[i] = sum;
    }
    vec res = gauss_jordan(A,b);
    printf("%.10f\n",res[S]);
}
 
int main(){
    int N,S,T;
    while(cin >> N >> S >> T, N){
	S--; T--;
	vi sign(N);
	vii d(N,vi(N)),road(N,vi(N));
	for(int i = 0 ; i < N ; i++){
	    cin >> sign[i];
	}
	for(int i = 0 ; i < N ; i++){
	    for(int j = 0 ; j < N ; j++){
		cin >> d[i][j];
		if(d[i][j] == 0){
		    d[i][j] = INF;
		}
	    }
	    d[i][i] = 0;
	}
	road = d;
	for(int k = 0 ; k < N ; k++){
	    road[k][k] = INF;
	    for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
		    d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
		}
	    }
	}
	if(d[S][T] == INF){
	    cout << "impossible" << endl;
	}else{
	    solve(sign,road,d,S,T,N);
	}
    }
    return 0;
}

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

use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::io::*;
use std::ops::*;
use std::*;

// -----------------------------------------------
// Framework
// -----------------------------------------------

#[allow(unused)]
fn rl() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused)]
fn rw<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|word| T::from_str(word).unwrap())
        .collect()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

#[allow(unused)]
macro_rules! debug {
    ($($arg:expr),*) => {
        #[cfg(debug_assertions)]
        {
            let entries = &[
                $((
                    &stringify!($arg).to_string() as &fmt::Debug,
                    &($arg) as &fmt::Debug,
                )),*
            ];
            eprintln!("{:?}", DebugMap(entries));
        }
    };
}

#[allow(unused)]
struct DebugMap<'a>(&'a [(&'a fmt::Debug, &'a fmt::Debug)]);

impl<'a> std::fmt::Debug for DebugMap<'a> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        let mut m = fmt.debug_map();
        for &(key, value) in self.0.iter() {
            m.entry(key, value);
        }
        m.finish()
    }
}

// -----------------------------------------------
// Polyfill
// -----------------------------------------------

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

#[allow(unused)]
macro_rules! eprintln {
    ($($arg:expr),*) => { _eprintln(format_args!($($arg),*)) }
}

fn _eprintln(args: fmt::Arguments) {
    let err = std::io::stderr();
    let mut err = err.lock();
    err.write_fmt(args).unwrap();
    err.write(b"\n").unwrap();
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

pub fn main() {
    println!(
        "{}",
        if rl().parse::<i32>().unwrap() <= 999 {
            "ABC"
        } else {
            "ABD"
        }
    );
    return;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_ok() {
        assert_eq!(7, 1 + 2 * 3);
    }
}


Measured memory_bytes: 4352
import java.util.Arrays;
import java.util.Scanner;


public class Main {
	Scanner sc;
	int[] value,weight;
	int[][] dp;
	int N,W;
	
	int max(int a,int b){
		return a>=b?a:b;
	}
	
	int dfs(int n,int w){
		if(dp[n][w]>=0){
			return dp[n][w];
		}
		
		int res;
		if(n==N){
			res=0;
		}
		else if(w-weight[n]<0){
			res=dfs(n+1,w);
		}
		else{
			res=max(dfs(n+1,w),dfs(n+1,w-weight[n])+value[n]);
		}
		return dp[n][w]=res;
	}

	int ni(){
		return sc.nextInt();
	}
	
	void io(){
		sc=new Scanner(System.in).useDelimiter(",|\r\n|\n");
		int k=0;
		while((W=ni())!=0){
			++k;
			N=ni();
			dp=new int[N+1][W+1];
			for(int[]r:dp)Arrays.fill(r,-1);
			value=new int[N];weight=new int[N];
			
			for(int i=0;i<N;++i){
				value[i]=ni();
				weight[i]=ni();
			}
			
			int maxvalue=0,maxweight=0;
			for(int w=0;w<=W;++w){
				int res;
				if(maxvalue<(res=dfs(0,w))){
					maxvalue=res;
					maxweight=w;
				}
			}
			System.out.println("Case "+k+":");
			System.out.println(maxvalue);
			System.out.println(maxweight);
		}
		sc.close();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().io();
	}

}

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

#define int long long

template<typename T> 
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(int i){
    T s=bit[0];
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  int lower_bound(int w){
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
	w-=bit[x+k];
	x+=k;
      }
    }
    return x+1;
  }
  
  T sum0(int i){
    return sum(i+1);
  }
  void add0(int i,T a){
    add(i+1,a);
  }

  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  T query0(int l,int r){
    return sum(r)-sum(l);
  }
};

const int INF = 1e9+1;

signed main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for ( int i = 0; i < n; i++ ) cin >> a[i];

  map<int, int> zip;
  vector<int> b = a;
  b.push_back(0);
  b.push_back(INF);
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  for ( int i = 0; i < (int)b.size(); i++ ) {
    zip[b[i]] = i+1;
  }

  BIT<int> bit(b.size(), 0);
  int ans = 0;
  for ( int i = 0; i < n; i++ ) {
    ans += i-bit.sum(zip[a[i]]);
    bit.add(zip[a[i]], 1);    
  }

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



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

int main() {
	
	int A,B,C,G;
	cin >> A ;
	G = A / 100;
	B = A - G * 100;
	C = G * 5;

	if (B > C ) {
		cout << 0 << endl;
	}
	else 
	    cout << 1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
  int N;
  cin >> N;
  vector<set<int>> G(N);
  rep(i,N-1){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    G[a].insert(b);
    G[b].insert(a);
  }
  vector<int> c(N);
  rep(i,N){
    cin >> c[i];
  }
  sort(c.begin(),c.end(),greater<int>());
  queue<int> que;
  rep(i,N){
    if(G[i].size() == 1){
      que.push(i);
    }
  }
  ll sum = 0;
  for(int i=1; i<N; i++){
    sum += c[i];
  }
  vector<int> ans(N);
  while(que.size()){
    if(!c.size()) break;
    int v = que.front();
    que.pop();
    ans[v] = c.back();
    c.pop_back();
    int nv = *G[v].begin();
    G[nv].erase(v);
    if(G[nv].size() == 1){
      que.push(nv);
    }
  }
  cout << sum << endl;
  rep(i,N){
    cout << ans[i] << (i!=N-1 ? " " : "\n");
  }
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ul unsigned long int



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

	ul n;
	cin>>n;
	string s;
	cin>>s;
	ul count = n;
	for(int i = 0; i < n-1; i++) {
		if(s[i] == s[i+1]) count--;
	}

	cout<<count<<"\n";
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int main() {
  double n;
  cin >> n;
  cout << setprecision(20) << pow(n / 3, 3) << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main(void){
	int m, d;
	int i;
	int term;
	int dow;

	while(cin >> m >> d){
		if(m == 0 && d == 0) break;

		term = 0;
		for(i=1;i<m;i++){
			if(i==2){
				term += 29;
			}else if(i==4||i==6||i==9||i==11){
				term += 30;			
			}else{
				term += 31;
			}
		}
		term += d - 1;

		dow = term % 7;

		switch(dow){
		case(0):
			cout << "Thursday" << endl;
			break;
		case(1):
			cout << "Friday" << endl;
			break;
		case(2):
			cout << "Saturday" << endl;
			break;
		case(3):
			cout << "Sunday" << endl;
			break;
		case(4):
			cout << "Monday" << endl;
			break;
		case(5):
			cout << "Tuesday" << endl;
			break;
		case(6):
			cout << "Wednesday" << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 0