akhauriyash/Code-Regression huggingface dataset:
n = int(input())
ls = [0 for i in range(10 ** 5)]
lsa = list(map(int,input().split()))

for i in range(len(lsa)):
    ls[lsa[i] - 1] += 1

ans1 = sum(lsa)
ansls = []

q = int(input())

for i in range(q):
    b, c = map(int,input().split())
    if i == 0:
        ans = ans1 + ((c - b) * ls[b - 1])
    else:
        ans = ansls[-1] + ((c - b) * ls[b - 1])
    ansls.append(ans)
    ls[c - 1] += ls[b - 1]
    ls[b - 1] = 0

for i in range(q):
    print(ansls[i])


Measured memory_bytes: 21848
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << std::setprecision(10) << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n,k;
	std::cin >> n >> k;
	std::vector<int> p(n);
	rep(i,n) std::cin >> p[i];
	std::vector<double> a(n);
	rep(i,n) {
		a[i] = (double)(p[i]+1)/(double)2;
	}
	std::vector<double> ac(n+1,0);
	rep(i,n) {
		ac[i+1] = ac[i]+a[i];
	}
	debug(ac);
	double max = 0;
	rep(i,n-k+1) {
		max = std::max(ac[i+k]-ac[i],max);
		debug(max);
	}
	print(max);

	return 0;
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
int main(){
       int n; cin>>n;
       long int sum=0;
       for(int i=1; i<=n; i++){
           for(int j=1; j<=n; j++){
               for(int k=1; k<=n; k++){
                long int x = __gcd(i, __gcd(j,k));
                sum+=x;
               }
           }
       }
       cout<<sum;
       return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(X) (X).begin(),(X).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
int g[11][11];
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> p;
    rep(i,n) p.push_back(i);
    rep(i,m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a][b] = g[b][a] = 1;
    }
    int ans = 0;
    do{
        bool ok = true;
        if(p[0]!=0) break;
        for(int i = 1; i < n; ++i){
            if(g[p[i-1]][p[i]]!=1) ok = false;
        }
        if(ok) ++ans;
    }while(next_permutation(all(p)));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i>n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65
//おまじない



int main() {

	int ans = 100;
	int n;
	int a[200];

	cin >> n;
	rep(i, 0, n) {
		cin >> a[i];
	}

	rep(i, 0, n) {
			int c = 0, t = a[i];
			while (t%2==0) {
				c++;
				t = t / 2;
		}
			ans = min(c, ans);
	}

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX 40

void solve(int*,int*,int);

int n, post[MAX], idx;

int main(){
  int pre[MAX], in[MAX], i;

  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d",pre+i);
  }
  for(i = 0 ; i < n ; i++){
    scanf("%d",in+i); 
  }

  solve(pre, in, n);

  for(i = 0 ; i < n ; i++){
    printf("%d%c",post[i],(i != n-1 ? ' ':'\n'));
  }

  return 0;
}

void solve(int pre[], int in[], int N){
  int i, p;

  for(i = 0 ; i < N ; i++){
    if(in[i] == pre[0]){
      p = i;
      break;
    }
  }

  if(p != 0){
    solve(pre+1, in, p);
  }
  if(p != N-1){
    solve(pre+p+1, in+p+1, N-p-1);
  }
  post[idx++] = pre[0]; 
}

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

int main()
{
  int a, b, c;

  cin >> a >> b >> c;

  string inrange;
  if( a < b and b < c ) {
    inrange = "Yes";
  }
  else {
    inrange = "No";
  }

  cout << inrange << endl;
  return 0;
}

Measured memory_bytes: 3192
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define clr clear()
#define ins insert
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define mem(x,val) memset((x),(val),sizeof(x));
#define cusmem(x,val) for(auto &i:x) i=val;
#define all(x) x.begin(),x.end()
#define fastio ios_base::sync_with_stdio(false);\
            cin.tie(NULL);\
            cout.tie(NULL);
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int>pli;
typedef vector<ll> vl;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vpii;
string impossible;

mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
// const int N=6;
const int N=1e5+5;
const int L=31;
ll mod=1e9+7;
ll n,i,j,k,x,m,b,a,da,db,u,v;
bool f0,f1,f2;
const int MAXN=1e6+5;
string s;
vector<ll>dp;
ll cal(ll s){
    if(s==3||s==0)    return 1;
    if(s<3) return 0;
    if(dp[s]!=-1)   return dp[s];
    ll ans=0;
    for(ll i=s;i>=3;i--){
            ans+=cal(s-i);
        ans%=mod;
    }
    dp[s]=ans;
    return ans;
}
int main(){
    #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin); 
            freopen("output.txt","w",stdout);
    #endif
    fastio
    cout<<fixed<<setprecision(11);
    int tests=1;    
    // cin>>tests;
    for(int te=1;te<=tests;te++){
        cin>>n;
        if(n<3) cout<<0;
        else{
            dp=vector<ll>(n+1,-1);
            cout<<cal(n);
        }
    }
    return 0;
}





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

int main()
{
    int N;
    cin >> N;
    vector<ll> Ai(N), Bi(N), Ci(N);
    rep(i, N) cin >> Ai[i];
    rep(i, N) cin >> Bi[i];
    rep(i, N) cin >> Ci[i];
    sort(Ai.begin(), Ai.end());
    sort(Ci.begin(), Ci.end());

    ll ans = 0;
    rep(i, N) {
        int b = Bi[i];
        auto itrA = lower_bound(Ai.begin(), Ai.end(), b);
        ll aCount = (itrA - Ai.begin());
        if (aCount == 0) {
            continue;
        }
        auto itrC = upper_bound(Ci.begin(), Ci.end(), b);
        ll cCount = N - (itrC - Ci.begin());
        ans += aCount * cCount;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
import itertools
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
    m=int(input())
    for j in range(m):
        l[i].append(list(map(int,input().split())))
ans=0
it=list(itertools.product([0,1],repeat=n))
for i in it:
    tmp=[]
    for num,j in enumerate(i):
        if j==1:
            for k in l[num]:
                tmp.append(k)
    if all (i[j[0]-1]==j[1] for j in tmp):ans=max(ans,sum(i))
print(ans)

Measured memory_bytes: 51548
#!/usr/bin/env python3
import sys, math, fractions, collections


def solve(N: int, K: int, A: "List[int]"):
    c = collections.Counter(A)
    c = [cc[1] for cc in c.most_common()]
    print(int(sum(c[K:])))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


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

int main() {
    string S;
    cin >> S;
    for(int i=0; i<S.size(); ++i) {
        for(int j=0; i+j<S.size(); ++j) {
            string tmp = S;
            tmp.erase(i, j);
            if(tmp == "keyence") {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iterator>
#include <utility>
#include <iomanip>
#include <cmath>
#include <climits>
#include <cassert>
#include <stdio.h>
#include <string.h>

using namespace std;

void solve() {
  int t, x;
  cin >> t >> x;
  
  std::cout << (double)t/x << std::endl;
}

int main(int argc, char *argv[])
{
  solve();
  return 0;
}


Measured memory_bytes: 256
main :: IO ()
main = do
  n <- readLn :: IO Int
  as1 <- (map read . words) <$> getLine :: IO [Int]
  as2 <- (map read . words) <$> getLine :: IO [Int]
  print $ maximum $ map (\i -> sum $ take (i + 1) as1 ++ drop i as2) [0..n]


Measured memory_bytes: 1020
def validate_x(w: int, x: int, r: int) -> bool:
    if r <= x <= w - r:
        return True
    return False


def validate_y(h: int, y: int, r: int) -> bool:
    if r <= y <= h - r:
        return True
    return False


def resolve():
    w, h, x, y, r = map(int, input().split())

    if validate_x(w, x, r) and validate_y(h, y, r):
        print("Yes")
    else:
        print("No")


resolve()


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

int main() {
  int n,x;
  cin >>n>>x;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  long long sum=0;
  for(int i=1;i<n;i++){
    int wa=a[i]+a[i-1];
    if(wa>x){
      int hikukazu=wa-x;
      if(hikukazu<=a[i]){
        sum+=hikukazu;
        a[i]-=hikukazu;
      }else{
        sum+=hikukazu;
        a[i]=0;
        a[i-1]=a[i-1]+a[i]-hikukazu;
      }
    }
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
def collatz(number):
    if number % 2 == 0:
        return number // 2  # 整数の商
    else:  # elseで良い
        return 3 * number + 1  # // intは不要では？


number = int(input())
if number == 1:
    print(4)
    quit()
a = [number]
while True:
    number = collatz(number)
    a += [number]

    if number == 1:
        break
if 4 in a:
    print(a.index(4)+4)
elif 2 in a:
    print(a.index(2)+4)
else:
    print(a.index(1)+4)


Measured memory_bytes: 3060
#include <cstdio>

typedef long long ll;

const int MAX_N = 2000, MAX_M = 2000; 
ll N, M, Q;
int s[MAX_N + 2][MAX_M + 2];

ll node[MAX_N + 2][MAX_M + 2];
ll left[MAX_N + 2][MAX_M + 2];
ll upper[MAX_N + 2][MAX_M + 2];

int main()
{
    scanf("%lld %lld %lld", &N, &M, &Q);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            char c;
            scanf(" %c", &c);
            if(c == '1'){
                s[i][j] = 1;
            }else{
                s[i][j] = 0;
            }
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            node[i][j] = node[i][j - 1] + node[i - 1][j] - node[i - 1][j - 1] + s[i][j];
            upper[i][j] = upper[i][j - 1] + upper[i - 1][j] - upper[i - 1][j - 1];
            left[i][j] = left[i][j - 1] + left[i - 1][j] - left[i - 1][j - 1];
            if(s[i][j] == 1){
                if(s[i - 1][j] == 1){
                    upper[i][j]++;
                }
                if(s[i][j - 1] == 1){
                    left[i][j]++;
                }
            }
        }
    }
    for(int k = 1; k <= Q; k++){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        int n = node[x2][y2] - node[x1 - 1][y2] - node[x2][y1 - 1] + node[x1 - 1][y1 - 1];
        int e = upper[x2][y2] - upper[x1][y2] - upper[x2][y1 - 1] + upper[x1][y1 - 1];
        e += left[x2][y2] - left[x1 - 1][y2] - left[x2][y1] + left[x1 - 1][y1];
        printf("%d\n", n - e);
    }
}


Measured memory_bytes: 111360
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt(); // tate
		int b = scan.nextInt(); // yoko
		System.out.println((a*b) + " " + (2*a + 2*b));
	}

}

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

int main(){
  string s;
  cin >> s;
  if(s == "A") s = "T";
  else if(s == "T") s = "A";
  else if(s == "G") s = "C";
  else s = "G";
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
def isPrime(n):
    for i in range(2, n):
        if i * i > n:
            return 1
        if n % i == 0:
            return 0
    return 1

ans = 0
n = int(input())
for i in range(n):
    x = int(input())
    ans = ans + isPrime(x)

print(ans)



Measured memory_bytes: 5608
#include <iostream>

class ModInt {
    using ll = long long;

public:
    int value;
    static int MOD;

    ModInt(ll value = 0) {
        this->value = (-MOD < value && value < MOD ? value : value % MOD);
        if (this->value < 0) this->value += MOD;
    }

    operator int() const noexcept { return this->value; }
    operator ll() const noexcept { return this->value; }

    ModInt& operator=(const ModInt& x) {
        if (this != &x) { this->value = x.value; }
        return *this;
    }

    bool operator==(const ModInt& x) const { return this->value == x.value; }
    bool operator!=(const ModInt& x) const { return !(*this == x); }

    ModInt operator+() const { return value; }
    ModInt operator-() const { return MOD - value; }
    ModInt operator~() const { return (*this) ^ ModInt(MOD - 2); }

    ModInt operator++() { return *this += 1; }
    ModInt operator--() { return *this -= 1; }

    ModInt operator++(int) {
        ModInt before = *this;
        ++(*this);
        return before;
    }
    ModInt operator--(int) {
        ModInt before = *this;
        --(*this);
        return before;
    }

    ModInt& operator+=(const ModInt& x) {
        int sum = this->value + x.value;
        return *this = (sum < MOD ? sum : sum - MOD);
    }
    ModInt& operator-=(const ModInt& x) {
        int diff = this->value - x.value;
        return *this = (diff >= 0 ? diff : diff + MOD);
    }
    ModInt& operator+=(int x) { return *this += ModInt(x); }
    ModInt& operator-=(int x) { return *this -= ModInt(x); }

    template <class T>
    ModInt& operator*=(const T& x) { return *this = ll(this->value) * ll(x) % MOD; }
    template <class T>
    ModInt& operator/=(const T& x) { return *this = (this->value % int(x) == 0 ? ModInt(this->value / int(x)) : *this * ~ModInt(x)); }
    template <class T>
    ModInt& operator^=(const T& x) {
        int n = int(x);
        ModInt b = *this;
        *this = 1;
        while (n > 0) {
            if (n & 1) *this *= b;
            n >>= 1;
            b *= b;
        }
        return *this;
    }

    template <class T>
    ModInt operator+(const T& b) const { return ModInt(*this) += b; }
    template <class T>
    ModInt operator-(const T& b) const { return ModInt(*this) -= b; }
    template <class T>
    ModInt operator*(const T& b) const { return ModInt(*this) *= b; }
    template <class T>
    ModInt operator/(const T& b) const { return ModInt(*this) /= b; }
    template <class T>
    ModInt operator^(const T& b) const { return ModInt(*this) ^= b; }
};

std::ostream& operator<<(std::ostream& os, const ModInt& x) { return os << x.value; }
std::istream& operator>>(std::istream& is, ModInt& x) { return is >> x.value; }

int ModInt::MOD = 1000000007;

int main() {
    int N, K;
    std::cin >> N >> K;
    ModInt ans = 1;
    for (int i = 0; i < N; ++i) ans *= K - i;
    std::cout << ans << std::endl;
}


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


int main()
{
	int i;
	int n, x, d;
	cin >> n >> x;
		
	d = 0;

	for (i = 0; i < n; i++) {
		int dValue;
		cin >> dValue;
		if (d + dValue  > x ) {
			break;
		}
		d += dValue;
	}
	
	cout << i+1 << endl;
	

	return 0;
}

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

int main() {
	string S;
	cin >> S;
	int n = S.size();
	string ans = "AC";

	if (S[0] != 'A')
	{
		ans = "WA";
	}

	int cnt = 0;
	for (int i = 1; i < n; i++)
	{
		if (S[i] == 'C' and (i >= 2 and i <= n - 2))
		{
			cnt++;
		}
		else if (S[i] >= 'a' and S[i] <= 'z')
		{
			continue;
		}
		else
		{
			ans = "WA";
		}
	}
	if (cnt != 1)
	{
		ans = "WA";
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	int n, a, b; cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;

int n;
int a[maxn];
int s[2][maxn];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		s[i&1][a[i]]++;
	}
	int mx1=0,p1,mx2=0,p2;
	for(int i=1;i<=1e5;i++)
	{
		if(s[0][i]>mx1)
		{
			mx2=mx1;
			p2=p1;
			mx1=s[0][i];
			p1=i;
		}
		else if(s[0][i]>mx2)
		{
			mx2=s[0][i];
			p2=i;
		}
	}
	int _mx1=0,_p1,_mx2=0,_p2;
	for(int i=1;i<=1e5;i++)
	{
		if(s[1][i]>_mx1)
		{
			_mx2=_mx1;
			_p2=_p1;
			_mx1=s[1][i];
			_p1=i;
		}
		else if(s[1][i]>_mx2)
		{
			_mx2=s[1][i];
			_p2=i;
		}
	}
	if(p1!=_p1)
	{
		printf("%d\n",n-mx1-_mx1);
	}
	else
	{
		printf("%d\n",min(n-mx1-_mx2,n-mx2-_mx1));
	}
	return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
using Data = pair<ll, vector<int>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 50;
struct edge { ll from; ll to; ll cost; };



int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if ((a < c  && c < b) ||(b < c && c < a))cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
retails = []
for i in range(N):
    A,B = map(int,input().split())
    retails.append([A,B])
retails = sorted(retails)
purchase_price = 0
for retail in retails:
    if M > 0:
        if retail[1] >= M:
            purchase_price += retail[0] * M
            M = 0
        else:
            purchase_price += retail[0] * retail[1]
            M -= retail[1]
print(purchase_price)


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

int main() {
  int N;cin>>N;
  vector<int> A(N);
  vector<int> ans(N);
  for(int i=0;i<N;i++) cin>>A.at(i);
  int k=0;
  int l=A.at(0)-k;
  for(int i=1;i<N;i++) l=A.at(i)-l;
  k=k/2+l/2;
  ans.at(0)=2*k;
  for(int j=1;j<N;j++){
    k=A.at(j-1)-k;
    ans.at(j)=2*k;
  }
  for(int k=0;k<N;k++) cout<<ans.at(k)<<" ";
}


Measured memory_bytes: 3984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[300005];
char s[100005];
int cnt[30];
ll mod=1e9+7;
int main()
{
#ifndef ONLINE_JUDGE
   // freopen("in.txt","r",stdin);
#endif 
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    int len=strlen(s);
    ll ans=1;
    for(int i=0;i<len;i++)cnt[s[i]-'a']++;
    for(int i=0;i<=25;i++)
    {
        ans=(ans*(cnt[i]+1))%mod;
    } 
    ans=(ans-1+mod)%mod;
    cout<<ans<<endl;


    return 0;
}


Measured memory_bytes: 384
<?php
fscanf(STDIN,"%d %d",$n,$m);
$s=1;
$e=100000;
for($i=1;$i<=$m;$i++){
	fscanf(STDIN,"%d %d",$x,$y);
	if($s<$x){
		$s=$x;
	}
	if($e>$y){
		$e=$y;
	}
}

$cnt=0;
for($i=1;$i<=$n;$i++){
	if($i>=$s && $i<=$e){
		$cnt++;
	}
}

echo $cnt;
?>

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

from sys import stdin, stderr

def sum1toN(N):
   return N*(N+1)/2

def main():
   N = int(stdin.readline())
   res = sum1toN(N)
   res -= sum1toN(N/3)*3
   res -= sum1toN(N/5)*5
   res += sum1toN(N/15)*15
   print(res)

   return 0

if __name__ == '__main__': main()


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

int main(){
	int n, a, b, p1,p2;
	while(true){
		cin>>n;
		p1=p2=0;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>a>>b;
			if(a>b)p1+=a+b;
			else if(a<b)p2+=a+b;
			else{
				p1+=a;
				p2+=b;
			}
		}
		cout << p1 << " " << p2 << endl;
	}
	return 0;
}

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

int main(){
  int s,f,l;
  cin>>s;
  f=s/100;
  l=s%100;
  if(1<=f&&f<=12){
    if(l>=1&&l<=12)cout<<"AMBIGUOUS";
    else cout<<"MMYY";
  }else{
    if(l>=1&&l<=12)cout<<"YYMM";
    else cout<<"NA";
  }
  return 0;
}


Measured memory_bytes: 888
#[allow(dead_code)]
const MOD: usize = 1_000000000 + 7;

fn main() {
    let mut cin = Scanner::new();
    let n = cin.next_usize();
    let m = cin.next_usize();
    let r = cin.next_usize();
    let ri = (0..r).map(|_| cin.next_usize() - 1).collect::<Vec<_>>();
    let inf = 1<<29;
    let mut dist = vec![vec![inf; n]; n];
    for _ in 0..m {
        let a = cin.next_usize() - 1;
        let b = cin.next_usize() - 1;
        let c = cin.next_usize();
        dist[a][b] = c;
        dist[b][a] = c;
    }
    for i in 0..n { dist[i][i] = 0; }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                dist[i][j] = std::cmp::min(dist[i][j], dist[i][k] + dist[k][j])
            }
        }
    }
    let mut dp = vec![vec![inf; 1<<r]; r];
    for i in 0..r { dp[i][1<<i] = 0 }
    for i in 1..1<<r {
        for j in 0..r {
            for k in 0..r {
                dp[k][i|1<<k] = std::cmp::min(dp[k][i|1<<k], dp[j][i] + dist[ri[j]][ri[k]])
            }
        }
    }
    println!("{}", (0..r).map(|i| dp[i][(1<<r)-1]).min().unwrap());
}


struct Scanner {
    reader: std::io::Stdin,
    tokens: std::collections::VecDeque<String>,
}

impl Scanner {
    fn new() -> Self {
        Scanner {
            reader: std::io::stdin(),
            tokens: std::collections::VecDeque::new(),
        }
    }

    fn next(&mut self) -> String {
        if self.tokens.is_empty() {
            let mut s = String::new();
            loop {
                self.reader.read_line(&mut s).ok();
                let s = s.trim();
                if s.len() != 0 {
                    for it in s.split_whitespace() {
                        self.tokens.push_back(it.into())
                    }
                    break;
                }
            }
        }
        self.tokens.pop_front().unwrap()
    }

    fn next_generics<T>(&mut self) -> T where
        T: std::str::FromStr + std::marker::Copy,
        <T as std::str::FromStr>::Err: std::fmt::Debug
    {
        self.next().parse().unwrap()
    }
    
    #[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next_generics::<i32>() }
    #[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next_generics::<i64>() }
    #[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next_generics::<u64>() }
    #[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next_generics::<usize>() }
    #[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next_generics::<isize>() }
}



Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    bool ans = true;
    for(int i = 0; i < s.size(); i+=2)
    {
        if(s[i] != 'h' || s[i + 1] != 'i')
        ans = false;
    }
    ans ? cout << "Yes" : cout << "No";
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    int len = s.length();
    int i, j;
    for(i=0; i<len; i++){
        if(s[i]=='A'){
            break;
        }
    }
    for(j=len-1; j>=0; j--){
        if(s[j]=='Z'){
            break;
        }
    }
    cout << j-i+1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define imp() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define endl "\n"
#define lli long long int 
#define ll long long 
#define f(i,a,b) for(i=(int)a;i<(int)b;i++)
lli gccd(lli a,lli b)
{
    if(b==0)
    return a;
    //else
    return (b,a%b);
}
lli  sum(string str)
{
    lli s=0;
    for(lli i=0;i<str.size();i++)
    {
        s+=str[i]-'0';
    }
    return s;
}
int main() {
	// your code goes here
	imp();
string str;cin>>str;
if(sum(str)%9==0)
cout<<"Yes"<<"\n";
else
cout<<"No"<<"\n";
	return 0;
}


Measured memory_bytes: 3708
package main

import (
	"fmt"
)

func main() {
	var a, b, c, x, y int
	fmt.Scan(&a, &b, &c, &x, &y)
	var cost int
	if (c < a || c < b) && c*2 < a+b {
		n := Min(x, y)
		cost += c * 2 * n
		x -= n
		y -= n
	}
	if c*2 < a {
		cost += c * 2 * x
		x = 0
	}
	if c*2 < b {
		cost += c * 2 * y
		y = 0
	}
	cost += a * x
	cost += b * y

	fmt.Println(cost)
}

func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const int mod = 1e9 + 7;
// const int mod = 998244353;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

LL f[100010];
int n, w, x, y;

inline void work() {
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        for (int i = w; i >= x; --i) {
            f[i] = max(f[i], f[i - x] + y);
        }
    }
    cout << *max_element(f, f + w + 1) << "\n";
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    work();
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long cc;
static const cc MAX = 2000;

cc i, j;
double N, M, k, sub = 0, n = 0, A[MAX], B[MAX];
double judge = 0, Ans = 0;
string S;
char vec[10];
char T;
/*
vector<cc> vec1(MAX), vec2(MAX);
vector<pair<cc, cc>> pairs(MAX);
*/



int main() {	
	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = 1 / A[i];
		sub += B[i];
	}

	Ans = 1 / sub;

	cout << Ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <thread>
#include <chrono>
#include <random>
#include <fstream>
#include <time.h>


int main()
{
    int N;
    int ans=0;

    std::cin >> N;

    std::vector<int> a(N);

    for(int i=0; i<N; i++){
        std::cin >> a[i];
    }

    for(int i=0; i<N; i++){
        int k=a[i];
        bool flag=true;
        while(flag){
            if (k%2 == 0){
                ans++;
                k = k/2;
            }
            else flag=false;
        }
    }


    std::cout << ans;


    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int main() {
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  if(a[0] == a[1]) {
    if(a[2] == a[1]) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  } else {
    if(a[0] == a[2] || a[1] == a[2]) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main(){
  long N,A,B;
  cin >> N >> A >> B;
  long pair;
  pair = N/(A+B);
  long rest;
  rest = N - (A+B)*pair;
  long ans;
  if(rest > A){
    ans = A*(pair+1);
  }
  else{
    ans = A*pair + rest;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, a[3005];
lnt f[3005][3005];
int main() {
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]), f[i][i] = a[i];
	for (int d = 2; d <= n; d++)
		for (int l = 1, r = d; r <= n; l++, r++)
			f[l][r] = max(a[l]-f[l+1][r], a[r]-f[l][r-1]);
	return printf("%lld\n", f[1][n]), 0;
}


Measured memory_bytes: 70016
def five a,b,num
  a*a*a*a*a-b*b*b*b*b==num
end


num=gets.strip.to_i
a=-120
b=-120
flag=true
while(a<=120 && flag)
  b=-120
  while(b<=120 && flag)
    flag=false if five(a,b,num)
    b+=1 if flag
  end
  a+=1 if flag
end
puts "#{a} #{b}"

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

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

typedef long long ll;

class Edge;
class Node {
 public:
  vector<Edge *> con_edges;
  vector<Node *> con_nodes;
};

class Edge {
 public:
  Node *a;
  Node *b;
  int color;
};

Edge *EDGE_NIL;

void Paint(Node *node, Edge *parent_edge = EDGE_NIL) {
  int color = 1;
  FOR(i, 0, node->con_edges.size()) {
    if (node->con_edges[i] == parent_edge) {
      continue;
    }
    Node *child = node->con_edges[i]->a;
    if (child == node) child = node->con_edges[i]->b;

    // color
    if (parent_edge != EDGE_NIL) {
      if (parent_edge->color == color) color += 1;
    }
    node->con_edges[i]->color = color;
    color++;
    Paint(child, node->con_edges[i]);
  }
}

int main() {
  int n;
  cin >> n;
  vector<Node> nodes(n);
  vector<Edge> edges(n - 1);
  FOR(i, 0, n - 1) {
    int a, b;
    cin >> a >> b;
    edges[i].a = &nodes[a - 1];
    edges[i].b = &nodes[b - 1];
    nodes[a - 1].con_edges.push_back(&edges[i]);
    nodes[b - 1].con_edges.push_back(&edges[i]);
    nodes[b - 1].con_nodes.push_back(&nodes[a - 1]);
    nodes[a - 1].con_nodes.push_back(&nodes[b - 1]);
  }
  int k = 0;
  FOR(i, 0, n) { k = max(k, (int)nodes[i].con_edges.size()); }
  // Node *seek = &nodes[0];
  // while (true) {
  //   if (seek->con_nodes.size() == 1) break;
  //   Node *other = seek->con_nodes[0];
  //   if (other == seek) other = seek->con_nodes[1];
  //   seek = other;
  // }
  // Node *root = seek;
  // seek->con_edges[0]->color = 1;
  // Paint(seek->con_nodes[0]);
  Node *root = &nodes[0];
  Paint(root);
  cout << k << endl;
  FOR(i, 0, n - 1) { cout << edges[i].color << endl; }
  return 0;
}


Measured memory_bytes: 14976
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

N = int(input())
A = list(map(int, (input().split())))

ans = 0
for i in range(60):
    zero, one = 0, 0
    for j in range(N):
        if A[j]>>i&1:
            one += 1
        else:
            zero += 1
    ans += (one * zero)<<i
    ans %= MOD
print(ans)


Measured memory_bytes: 124688
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int judge(int n)
{
  if (n == 2) return 1;
  else if (n == 4 || n == 6 || n == 9 || n == 11) return 2;
  else return 3;
}

int main()
{
  int x, y;
  cin >> x >> y;
  if (judge(x) == judge(y)) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

#define num_max(p,q)((p)>(q)?(p):(q))
#define num_min(p,q)((p)<(q)?(p):(q))
int cmp(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;//昇順
	 //降順ならreturn *(int*)b - *(int*)a;
}
int main()
{
	 int N,i;
	scanf("%d", &N);
	int(*A) = (int(*))malloc(100010 * sizeof(int));
	int(*B) = (int(*))malloc(100010 * sizeof(int));
	
	for (i = 1;i <= N;i++)
	{
		scanf("%d", &A[i]);
		B[A[i]] = i;
	}
	for (i = 1;i <= N;i++)printf("%d ", B[i]);
	free(A);
	free(B);
	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	ll n, k;
	cin >> n >> k;

	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 0; i < n; i++) {
		a[i + 1] += a[i];
	}

	vector<ll> bits;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			bits.emplace_back(a[j + 1] - a[i]);
		}
	}

	sort(rbegin(bits), rend(bits));

	vector<ll> now = bits;
	for (ll i = 63; i >= 0; i--) {
		vector<ll> next;
		for (auto v : now) {
			if (v & (1LL << i)) {
				next.emplace_back(v);
			}
		}

		if (next.size() >= k) {
			now = next;
		}
	}

	ll ans = now[0];
	for (int i = 0; i < k; i++) {
		ans &= now[i];
	}

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


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

int main(){
	int x,y,s;
	cin >> x >> y >> s;
	int loop,loop2,max;
	int a1,a2,b;
	while(x){		//データセット条件 x!=0
		max=0;
		for(loop=1;loop<s;loop++){
			a1 = loop*(100+x)/100;
			if(a1>=s) break;	//重要
			a2 = loop*(100+y)/100;
			loop2=s-a1;
			while(a1+loop2*(100+x)/100>s)		//(a1+loop2*(100+x)/100)==sなるloop2の非存在可能性を考慮 
				loop2--;
			if(a1+loop2*(100+x)/100==s&&max<(a2+loop2*(100+y)/100)){
				max = a2+loop2*(100+y)/100;
			}
		}
		cout << max << endl;
		cin >> x >> y >> s;
	}
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
using str=string;
typedef pair<int,int> P;
typedef vector<int> vi;

ll gcd(ll a,ll b){
    ll v0=a,v1=b,v2=a%b;
    while(v2!=0){
        v0=v1;
        v1=v2;
        v2=v0%v1;
    }
    return v1;
}

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

int main(){
    int a,b;
    cin >>a >> b;
    cout << lcm(a,b) << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int n, k;
    cin >> n >> k;
    int w[100000];
    for(int i=0;i<n;i++) cin >> w[i];

    ll ok=20000000000LL, ng=0;
    while(ok-ng>1){
        ll m=(ok+ng)/2;
        ll w_tot = 0;
        int cars = 0;
        int i=0;
        while(true){
            if(w_tot+w[i]>m){
                w_tot=0;
                cars++;
                if(cars>=k) goto l_ng;
            }else{
                w_tot+=w[i];
                i++;
                if(i>=n) goto l_ok;
            }
        }
        l_ok: ok=m; continue;
        l_ng: ng=m; continue;
    }

    cout << ok << endl;

    return 0;
}


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

int main() {
 int N;
 int a[100008];
 int b[100008];
 int ans;
 cin >> N;
 for(int i=0;i<N;i++){
 	cin >> a[i];
 	cin >> b[i];
 }
 for(int i=0;i<N;i++) ans = ans - a[i] + b[i]+1;
 cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

struct UnionFind{
    vector<int> Parent;
    vector<int> sizes;
    UnionFind(int n):Parent(n),sizes(n,1){ rep(i,n)Parent[i]=i; }
    //find the root of x
    int root(int x){
        if(x!=Parent[x]){
        Parent[x] = root(Parent[x]);
        }
        return Parent[x];
    }
    //merge x and y
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(sizes[x] < sizes[y]) swap(x, y);
        Parent[y] = x;
        sizes[x] += sizes[y];
    }
    bool same(int x,int y){ return root(x) == root(y); }
    int size(int x){ return sizes[root(x)]; }
};

int main() {
	int N,M;
	cin>>N>>M;
	vector<int> a(M),b(M);
	rep(i,M){
		cin>>a[i]>>b[i];
		a[i]--;b[i]--;
	}
	int ans = 0;
	rep(i,M){
		UnionFind tree(N);
		rep(j,M){
			if(i!=j){
				if(!(tree.same(a[j],b[j]))){
					tree.unite(a[j],b[j]);
				}
			}
		}
		if(!(tree.same(a[i],b[i])))ans++;
	}
	cout<<ans<<endl;
}

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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

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



int main(void){

	int N; cin >> N;
	vector<int> h(N);
	REP(i,N) cin >> h[i];

	int ans = 0;
	int active = 0;

	REP(i,N){
		if(active >= h[i]){
			active = h[i];
		}else{
			ans += h[i] - active;
			active = h[i];
		}
	}
	cout << ans << endl;


	return 0;

}


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

using namespace std;

int main()
{
    int a[4];

    cin>>a[0]>>a[1]>>a[2];

    sort(a,a+3);

    a[2] = a[2]*10 ;

    a[3] = a[0]+a[1]+a[2];

    cout<<a[3]<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        v.push_back(t);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < k; i++) {
        res += v[i];
    }
    cout << res << endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

/*
 *
作物を育てるには種を買わなければならない．ここで作物 i の種の名前は Li ，値段は Pi でそれぞれ与えられる．畑に種を植えると時間 Ai 後に芽が出る．芽が出てから時間 Bi 後に若葉が出る．若葉が出てから時間 Ci 後に葉が茂る．葉が茂ってから時間 Di 後に花が咲く．花が咲いてから時間 Ei 後に実が成る．一つの種から Fi 個の実が成り，それらの実は一つあたりSi の価格で売れる．一部の作物は多期作であり，計 Mi 回実をつける．単期作の場合は Mi = 1で表される．多期作の作物は，Mi 回目の実が成るまでは，実が成ったあと葉に戻る．ある種に対する収入は，その種から成った全ての実を売った金額から，種の値段を引いた値である．また，その種の収入効率は，その収入を，種を植えてから全ての実が成り終わるまでの時間で割った値である．
 */

int main(){
	int n;
	while(cin >> n, n){
		vector<pair<double, string>> pir(n);
		rep(i,n){
			string l;
			double p, a, b, c, d, e, f, s, m;
			cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;

			double totalTime = a + b + c + d + e;
			double price = f * s;
			m--;

			totalTime += (d + e) * m;
			price += f * s * m;

			price -= p;

			//cout << -price / totalTime << endl;
			pir[i] = make_pair(-price / totalTime, l);
		}

		sort(all(pir));
		rep(i,pir.size()){
			cout << pir[i].second << endl;
		}
		cout << '#' << endl;
	}
}



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

long long n,x,m;
set <long long> s;
vector <long long> v,vc;

long long cycle_sum(long long x)
{
	long long sum=0;
	set <long long> s;
	vector <long long> v;
	while(s.find(x)==s.end())
	{
		s.insert(x);
		vc.push_back(x);
		sum+=x;
		x=(x*x)%m;
	}
	return sum;
}

int main()
{
	cin>>n>>x>>m;

	if(n<1e6)
	{
		long long s=0;
		for(int i=1;i<=n;i++)
		{
			s+=x;
			x=(x*x)%m;
		}
		cout<<s;
		return 0;
	}

	
	while(s.find(x)==s.end())
	{
		s.insert(x);
		v.push_back(x);
		x=(x*x)%m;
	}
	long long cycle=x;

	if(n<=v.size())
	{
		cout<<accumulate(v.begin(),v.begin()+n,0ll);
		return 0;
	}

	long long csum=cycle_sum(cycle);
	long long ans=accumulate(v.begin(),v.end(),0ll)-csum;
	
	n-=v.size()-vc.size();
	ans+=csum*(n/vc.size());
	n%=vc.size();
	for(int i=0;i<n;i++) ans+=vc[i];
	cout<<ans;
}

Measured memory_bytes: 8540
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int w,d;
    while(cin>>w>>d&&(w||d)){
        vector<int> a(w),b(d);
        rep(i,w)cin>>a[i];
        rep(i,d)cin>>b[i];
        
        map<int,int> hist;
        
        rep(i,a.size()){
            hist[a[i]]++;
        }
        
        int ans = 0;
        rep(i,b.size()){
            if(hist.count(b[i])&&hist[b[i]]>0){
                hist[b[i]]--;
                ans+=b[i];
            }else{
                ans+=b[i];
            }
        }
        for(auto elm : hist){
            if(elm.second!=0)ans+=elm.first*elm.second;
        }
        cout<<ans<<endl;
    }
}

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

void printArray(int A[], int N){
    
    for(int i=0; i<N; i++){
        cout << A[i];
        if(i<N-1) cout << " ";
    }
    
    cout << endl;
    
}

void flip(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void bubbleSort(int A[], int N){
    
    int flip_count = 0;
    
    bool flag = true;
    while(flag){
        flag = false;
        for(int j=N-1; j>0; j--){
            if(A[j] < A[j-1]){
                flip(&A[j], &A[j-1]);
                flip_count++;
                flag = true;
            }
        }
    }
    
    printArray(A, N);
    cout << flip_count << endl;
    
}

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N;
    
    int A[N];
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    bubbleSort(A, N);
    
    return 0;
}



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

ll power(ll n,ll m)
{
    ll ans=1;
    for (ll r=0;m>>r>0;r++)
    {
        if ((m>>r)&1) ans=ans*n;
        n=n*n;
    }
    return ans;
}

int main()
{
    ll h,w,k;cin >> h >> w >>k;
    string S;
    ll now=0;
    vector<vector<ll> >board(h,vector<ll> (w,0));
    for (ll i=0;i<h;i++)
    {
        cin >> S;
        for (ll j=0;j<w;j++)
        {
            board[i][j]=S[j]-'0';
        }
    }
    for (int row=0;row<h;row++)
    {
        for (int column=0;column<w;column++)
        {
            vector<vector<ll> >board2=board;
            board2[row][column]=0;
            for (int k=row;k>0;k--)
            {
                swap(board2[k][column],board2[k-1][column]);
            }

    bool can=true;
    ll times=0;
    ll ans=0;
    while (can)
    {
        can=false;
        for (ll i=0;i<h;i++)
        {
            ll key=board2[i][0];
            ll cnt=1;
            for (ll j=1;j<w;j++)
            {
                if (key==board2[i][j] && key!=0)
                {
                    cnt++;
                }
                else
                {
                    if (cnt>=k)
                    {
                        can=true;
                        ans+=cnt*power(2,times)*board2[i][j-1];
                        for (int m=1;m<cnt+1;m++)
                        {
                            board2[i][j-m]=0;
                        }
                    }
                    key=board2[i][j];
                    cnt=1;
                }
            }
            if (cnt>=k)
            {
                can=true;
                ans+=cnt*power(2,times)*board2[i][w-1];
                for (int m=1;m<cnt+1;m++)
                {
                    board2[i][w-m]=0;
                }
            }
        }
        times++;
        if (can)
        {
            for (int j=0;j<w;j++)
            {
                for (int i=h-1;i>=0;i--)
                {
                    if (board2[i][j]==0)
                    {
                        int zero=i;
                        while (zero>=0 && board2[zero][j]==0)
                        {
                            zero--;
                            if (zero==-1) break;
                        }
                        if (zero!=-1)
                        {
                            board2[i][j]=board2[zero][j];
                            board2[zero][j]=0;
                        }
                    }
                }
            }
        }
    }
    now=max(now,ans);
        }
    }
    cout << now << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

void Main() {
	int n; cin >> n;
	FOR(i, 1, n + 1) {
		bool output_flg = false;
		if (i % 3 == 0) {
			output_flg = true;
		} else {
			int tmp = i;
			while (tmp) {
				if (tmp % 10 == 3) {
					output_flg = true;
					break;
				}
				tmp /= 10;
			}
		}
		if (output_flg) cout << " " << i;
	}
	cout << endl;
}

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



Measured memory_bytes: 3184
# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
ans = 0
for k in range(1, N):
  if A[k-1] > A[k]:
    ans += A[k-1] -  A[k]
    A[k] = A[k-1]
print(ans)

Measured memory_bytes: 32248