akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,n,cc=0;
  cin>>a>>b>>c>>n;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      int s=n-(i*500+j*100);
      if(s>=0&&s<=c*50&&s%50==0)
        cc++;
    }
  }
  cout<<cc;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long 
using namespace std;

const int maxn = (1 << 18) + 100;
ll a[maxn];

struct node
{
	int pos1; int pos2;
};
node p[maxn];

void update(int x, node& p)
{
	if (x == p.pos1 || x == p.pos2) return;
	if (a[x] >= a[p.pos1]) { p.pos2 = p.pos1; p.pos1 = x; }
	else if (a[x] >= a[p.pos2]) { p.pos2 = x; }
}

int main()
{
	memset(a, 0, sizeof(a));
	int n; cin >> n;
	int N; N = (1 << n);
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		p[i].pos1 = i; p[i].pos2 = N;
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if ((i >> j & 1) == 0) continue;
			int k = (1 << j);
			update(p[(i^k)].pos1, p[i]);
			update(p[(i^k)].pos2, p[i]);
		}
	}

	ll ans = 0;
	for (int i = 1; i < N; i++)
	{
		ans = max(ans, a[p[i].pos1] + a[p[i].pos2]);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 7168
#include <stdio.h>
int main(void)
{
	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if((x + r <= W && x - r >= 0) && (y + r <= H && y - r >= 0))
	{
        printf("Yes\n");
    }
	else
	{
		printf("No\n");
	}
	
	return 0;
}


Measured memory_bytes: 2692
#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
char c[2]={'C','F'};
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++)
		if(s[i]==c[ans])
			ans++;
	if(ans==2) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX = 13, INF = 1e9;
int N, M, X, A[MAX][MAX], C[MAX];
int main() {
    cin >> N >> M >> X;
    for(int i=0; i<N; i++) {
        cin >> C[i];
        for(int j=0; j<M; j++)
            cin >> A[i][j];
    }
    int S = INF;
    for(int mask=0; mask<(1<<N); mask++) {
        int cost = 0;
        vector<int> tmp(M, 0);
        for(int i=0; i<N; i++) {
            if(mask & (1<<i)) {
                cost += C[i];
                for(int j=0; j<M; j++) {
                    tmp[j] += A[i][j];
                }
            }
        }
        bool passed = 1;
        for(int j=0; j<M; j++) {
            if(tmp[j] < X) {
                passed = 0;
                break;
            }
        }
        if(passed)  S = min(S, cost); 
    }
    if(S == INF)    cout << -1;
    else            cout << S;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  if(A == 1 && B == 2) cout << "3" << endl; 
  if(A == 1 && B == 3) cout << "2" << endl;
  if(A == 2 && B == 1) cout << "3" << endl; 
  if(A == 2 && B == 3) cout << "1" << endl;
  if(A == 3 && B == 1) cout << "2" << endl; 
  if(A == 3 && B == 2) cout << "1" << endl;
}

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

#define rep(i, n) for (int i=0; i< (n); ++i)
typedef long long ll;
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; }

using namespace std;

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

    int a[n];

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

    rep(i, n) {
        if (a[i] % 2 == 0) {
            if (!(a[i] % 3 == 0 || a[i] % 5 == 0)) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
}

Measured memory_bytes: 256
#include<iostream>

#define MAX 40

using namespace std;

typedef struct{
	int a,b,c;
}LIQUID;
void process(LIQUID liquid[], LIQUID mix, int n, int pos, int Ma, int Mb, int *min);
int main(){
	LIQUID liquid[MAX],mix = {0,0,0};
	int n,Ma,Mb;
	int i;
	int min = -1;
	cin >> n >> Ma >> Mb;
	
	for(i=0; i<n;i++){
	 cin >> liquid[i].a >> liquid[i].b >> liquid[i].c;
	}
	process(liquid,mix,n,0,Ma,Mb,&min);
	cout << min << endl;
}
void process(LIQUID liquid[], LIQUID mix, int n, int pos, int Ma, int Mb, int *min){
	if( pos == n )
		return;
	process(liquid,mix,n,pos+1,Ma,Mb,min);
	mix.a += liquid[pos].a;
	mix.b += liquid[pos].b;
	mix.c += liquid[pos].c;
	if( mix.a * Mb == mix.b * Ma ){
		if( *min == - 1 || *min > mix.c )
			*min = mix.c;
	}
	if( *min != -1 && *min < mix.c )
		return;
	process(liquid,mix,n,pos+1,Ma,Mb,min);
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
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; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int dp[1010][20010];

int main(){
    int h, n;
    cin >> h >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    for (int i = 0; i < 1010; ++i) {
        for (int j = 0; j < 20010; ++j) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 20010; ++j) {
            dp[i+1][j] = dp[i][j];
            if (j - a[i] >= 0){
                chmin(dp[i+1][j], dp[i+1][j-a[i]] + b[i]);
            }
        }
    }

    int res = INF;
    for (int i = h; i < 20010; ++i) {
        chmin(res, dp[n][i]);
    }
    cout << res << endl;
}

Measured memory_bytes: 82572
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    class ClassMain {




        public static void Main(String[] args) {
            string line;
            char[,] pat = new char[8, 8];
           // while ((line = Console.ReadLine()) != null) {

                for (int i = 0; i < 8; i++)
                {
                    line = Console.ReadLine();
                    char[] chs = line.ToCharArray();
                    for(int j=0; j<8; j++){
                          pat[i,j] =chs[j];
                    }


                }
                Console.WriteLine("90");
                priArr(migi90(pat));
                Console.WriteLine("180");
                priArr(migi180(pat));
                Console.WriteLine("270");
                priArr(migi270(pat));

               // Console.ReadLine();
            //}
        }


        public static void priArr(char[,] arr) {
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    Console.Write(arr[i, j]);
                }
                Console.WriteLine();
            }
        
        }

        public static char[,] migi90(char[,] pat) {
            char[,] rot = new char[8, 8];
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    rot[j, 7 - i] = pat[i, j]; 
                }
            }
            return rot;        
        }
        public static char[,] migi180(char[,] pat) {
            char[,] rot = new char[8, 8];
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                     rot[j, 7 - i] = pat[i, j];
                }
            }
            return migi90(rot);
        }
        public static char[,] migi270(char[,] pat) {
            char[,] rot = new char[8, 8];
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                     rot[j, 7 - i] = pat[i, j] ;
                }
            }
            return migi180(rot);
        }

    }
}

Measured memory_bytes: 5284
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=100005;
//i_am_noob
int a,b,c,k,ans=0;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> a >> b >> c >> k;
	ans+=min(a,k);
	k-=min(a,k);
	if(k==0){
		print1(ans);
		return 0;
	}
	k-=min(b,k);
	if(k==0){
		print1(ans);
		return 0;
	}
	ans-=min(c,k);
	k-=min(c,k);
	if(k==0){
		print1(ans);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#include<chrono>
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define mt make_tuple
#define tc  ll t; cin>>t; while(t--)
#define io ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define F first
#define S second
#define vi vector<ll>
#define pii pair<ll,ll>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define vii vector<pair<ll,ll>>
ll gcd(ll n,ll m)
{
    if(n==0)
            return m;
    return gcd(m%n,n);
}
bool ifprime(ll n)
{
if(n==1)
return false;
    ll i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
return false;
 
}
return true;
}
void disp(vi v)
{
    for(auto u:v)
    cout<<u<<" ";
    cout<<"\n";
}
void remleadzero(vector<int> &v)
{
    vector<int> u;
    int i=0;
    while(v[i]==0)
        i++;
    while(i<v.size())
    {
        u.push_back(v[i]);
        i++;
    }
    v=u;
}
#define mod 1000000007LL
/*
void myscanf(long long *n)
{
    register long long c=getchar_unlocked();
    *n=0;
    for(;(c<48 ||c>57);c=getchar_unlocked())
        ;
    for(;(c>47 && c<58);c=getchar_unlocked())
    {
        *n=(*n<<1)+(*n<<3)+(c&15);
    }
 
}
void fastscan(long long &number)
{
    bool negative = false;
    register long long c;
 
    number = 0;
 
    c = getchar_unlocked();
    if (c=='-')
    {
 
        negative = true;
 
        c = getchar_unlocked();
    }
 
 
    for (; (c>47 && c<58); c=getchar_unlocked())
        number = number *10 + c - 48;
 
 
    if (negative)
        number *= -1;
}
*/
ll fast_expo(ll n,ll m, ll md)
{
    ll a=1;
    while(m>0)
    {
        if(m&1) a=(a*n)%md;
        n=(n*n)%md;
        m/=2;
    }
    return a%md;
}
// checks if a number is a perfect square in almost O(1) time
long long sqroot(long long n){
    long double N = n;
    N = sqrtl(N);
    long long sq = N-2;
    sq = max(sq,0LL);
    while(sq*sq<n){
        sq++;
    } 
    if((sq*sq)==n)
        return sq;
    return -1;
}
int dig_sum(ll n){
    int ret=0;
    while(n>0){
        ret+=(n%10);
        n/=10;
    }
    return ret;
}


int main()
{
    io;
    ll ans = 0;

    ll x;
    cin>>x;
    while(x>=500){
        x-=500;
        ans+=1000;
    }
    while(x>=5){
        x-=5;
        ans+=5;
    }
    cout<<ans;
    return 0;
}


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

int main(){
  int n;
  double x[100], y[100], sub[100];
  double d, d2, d3, dmax;
  d = d2 = d3 = dmax = 0.0;

  scanf("%d", &n);

  for(int i = 0; i < n; i++){
	scanf("%lf", &x[i]);
  }
  for(int i = 0; i < n; i++){
	scanf("%lf", &y[i]);
  }

  for(int i = 0; i < n; i++){
	sub[i] = fabs(x[i] - y[i]);
	d += sub[i];
  }

  double temp = 0.0;
  for(int i = 0; i < n; i++){
	temp += pow(sub[i], 2.0);
  }
  d2 = sqrt(temp);

  temp = 0.0;
  for(int i = 0; i < n; i++){
	temp += pow(sub[i], 3.0);
  }
  d3 = pow(temp, 1.0/3.0);

  for(int i = 0; i < n; i++){
	if(sub[i] > dmax){
	  dmax = sub[i];
	}
  }

  printf("%lf\n%lf\n%lf\n%lf\n", d, d2, d3, dmax);

  return 0;
}


Measured memory_bytes: 2100
import java.util.Scanner;

public class Main {
    
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        String number = scanner.nextLine();
        
        double r = Double.parseDouble(number);
        
        System.out.println(String.format("%.6f %.6f", r*r*Math.PI, 2*r*Math.PI));
    }
}


Measured memory_bytes: 26376
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
const ll MOD=1000000007;
const long double PI=3.14159265358979;
const ll MAX=0;

int main() {
  ll N,D,ans=0;
  cin>>N>>D;
  rep(i,N){
    ll x,y;
    cin>>x>>y;
    if(x*x+y*y<=D*D){
      ans++;
    }
  }
  cout<<ans;
}

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



#ifndef DEBUG 
#define fprintf (void)
#endif 

int main(void){
	
	int rec,i,j,t;
	int count=0;
	int n[3]={0,0,0};
	
	scanf("%d",&t);
	
	for(i=0;i<t;i++){
		for(j=0;j<3;j++){
			scanf("%d",&rec);
			if(rec==0){
				count=1;
			}
			if(rec>n[0]){
				n[2]=n[1];
				n[1]=n[0];	
				n[0]=rec;
			}else if(rec>n[1]){
				n[2]=n[1];
				n[1]=rec;
			}else if(rec>n[2]){
				n[2]=rec;
			}
		}
		fprintf(stdout,"%d %d %d\n",n[0],n[1],n[2]);
		if(count==1){
			fprintf(stdout,"invalid");
			printf("NO\n");
		}else if(n[0]*n[0]==n[1]*n[1]+n[2]*n[2]){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
		n[0]=n[1]=n[2]=0;
	}
	
	return 0;
}

Measured memory_bytes: 2584
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int n,m,a[1000];

map<int,int> c;

int main() {
    while(true) {
        cin >> n >> m;
        if(n == 0)break;
        rep(i,n){
            cin >> a[i];
            c[a[i]] = 0;
        }
        rep(i,n) {
            c[a[i]]++;
        }
        sort(a,a+n);//aをソート

        int ans = -1;
        rep(i,n) {
            int* itr = upper_bound(a,a+n,m - a[i]);//m-a[i]<a[j] となる最小のjのa[j]へのポインタを取得
            if(itr - a == 0) {//m - a[i]>=a[j]を満たすjが存在しない時
                continue;
            }
            itr--;//ポインタを一つ減算してm-a[i]>=a[j]となる最大のjのa[j]へのポインタを取得
            if(*itr == a[i] && c[a[i]] < 2) {//境界のものがa[i]だった時
                if(itr - a == 0) {//a[i]未満のものがない時
                    continue;
                }
                itr--;//さらに一つ前に
            }
            ans = max(ans,*itr + a[i]);
        }
        if(ans == -1)cout << "NONE" << endl;
        else cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3700
def li():
    return list(map(int, input().split()))


def combination2(a, b, n):
    # print('call 2: ', a, b, n)
    com2 = 0
    a_quot = n // a + 1
    for j in range(a_quot):
        com2 = com2 + combination1(b, n - j * a)
    return com2


def combination1(a, n):
    # print('call 1: ', a, n)
    if n % a == 0:
        return 1
    else:
        return 0


[r, g, b, n] = li()
r_quot = n // r + 1
com_num = 0
for i in range(r_quot):
    com_num = com_num + combination2(g, b, n - i * r)
print(com_num)


Measured memory_bytes: 3060
import sys

def main():
    N = int(input())
    text = input()
    K = int(input())
    textK = text[K-1]
    ans = ''
    for t in text:
        if t!=textK:
            ans += '*'
        else:
            ans += t
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REPS(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
using ll = long long;
using ld = long double;

const int MOD = 1000000007;

int main(void) {
    int N, K;
    cin >> N >> K;

/*
    long long sumOfCombinations =
        (N+N-1) - (0+1) + 1 + // 5
        (N+N-1+N-2) - (0+1+2) + 1 + // 4
        (N+N-1+N-2+N-3) - (0+1+2+3) + 1; // 1
*/
    long long sum[220000];
    for (long long i = 1; i <= N+1; i++) {
        if (i == 1) {
            sum[i] = N + 1;
            continue;
        }
        long long d = N * i - ((i - 1) * i) + 1;
        sum[i] = sum[i-1] + d;
    }

    long long ans = sum[N+1] - sum[K-1];
    ans %= MOD;

    cout << ans << endl;
}

Measured memory_bytes: 5128
#include<stdio.h>

#define MAX 100
 #define INF 1000000
#define W 1
 #define B 2
 int A[MAX][MAX], u, d[MAX];

void DIJ(int n){
   int minc, i, color[MAX], v, pi[MAX];

   for(i=0 ; i<n ; i++){
     color[i] = W;
     d[i] = INF;
   }
   d[0] = 0;

   
   while(1){
     minc = INF;
     for(i=0 ; i<n ; i++){
       if(color[i] != B && d[i] < minc){
	 minc = d[i];
	 v = i;
       }
     }
     if(minc == INF)break;
     color[v] = B;
     for(i=0 ; i<n ; i++){
       if(color[i] !=B && d[v]+A[v][i]<d[i]){
	 pi[i] = v;
	 d[i] = d[v] + A[v][i];
       }
     }
   }
  
 }

 
int main(){
  int n, k, v, i, j,a;
   scanf("%d",&n);

   for(i=0 ;i<n; i++){
     for(j=0 ; j<n ; j++)A[i][j] = INF;
   }
   
   for(i=0 ; i<n ; i++){
     scanf("%d%d",&u,&k);
     for(j=0 ; j<k ; j++){
       scanf("%d%d",&v,&a);
     A[u][v] = a;
     }
   }
  
   DIJ(n);
   
   for(i=0 ;i<n ;i++){
     printf("%d %d\n",i, d[i]);
   } 
   return 0;
}



Measured memory_bytes: 2028
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
int n, k, x, total=0;
	
int main(){
	IOS
	cin >> n >> k;
	for(int i=0;i<n;i++){
		cin >> x;
		int temp=2*abs(x-0);
		temp=min(temp, 2*abs(x-k));
		total+=temp;
	}
	cout << total << '\n';
}


Measured memory_bytes: 3580
N = int(input())
a = [int(x) for x in input().split()]

for i in range(0, len(a)) :
    repl = i
    cur_num = a[i]
    
    # fetch idx to replace
    for j in range(i, -1, -1) :
        if a[j] >= a[i] :
            repl = j
    
    # shift
    for k in range(i, repl - 1, -1) :
        a[k] = a[k - 1]
    
    a[repl] = cur_num
    
    print(" ".join(map(str, a)))



Measured memory_bytes: 5604
#include <iostream>
#include <string>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(){
  string S;
  cin >> S;
  int len = S.size();
  long long int ret = 0;
  int B = 0;
  REP(i,len) {
    if(S[i] == 'B') {
      B++;
    } else {
      ret += B;
    }
  }
  cout << ret << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  vector<mint> sums(n+1, 0);
  rep(i, n) sums.at(i+1) = sums.at(i) + a.at(i);
  mint ans = 0;
  rep(i, n){
    mint add = (sums.back() - sums.at(i+1)) * a.at(i);
    ans += add;
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 5576
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

int main()
{
	long long int i, j, k, l, m,N, n,A,B, sum, flag, cc, cnt;
	sum = 0;
	flag = 1;
	cin >> N;
	char W[101][11];
	int len[101] = {};
	for (i = 0; i < N; i++) {
		cin >> W[i];
		len[i] = strlen(W[i]);
	}
	for (i = 0; i < N-1; i++) {
		for (j = i + 1; j < N; j++) {
			flag = 1;
			if (len[i] == len[j]) {
				for (k = 0; k < len[i]; k++) {
					if (W[i][k] != W[j][k]) {
						flag = 0;
						break;
					}
				}

			}
			else
				flag = 0;
			if (flag == 1) {
				break;
			
			}
			
		}
		if (flag == 1) {
			break;
		}
	}
	int fla;
	fla = 1;
	if (flag == 1) {
		cout << "No" << endl;
	}
	else {
		for (i = 0; i < N - 1; i++) {
			if (W[i][len[i] - 1] != W[i + 1][0]) {
				fla = 0;
				break;
			}
		}
		if (fla == 0) {
			cout << "No" << endl;
		}
		else
			cout << "Yes" << endl;

	}





    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 60
int main(){
    char *s;
    const char *t = "ABC";
    int N, c = 0;
    s = calloc(sizeof(char), M);
    // t = calloc(sizeof(char), 5);

    scanf("%d%s", &N, s);
    for (int i = 0; i < M; i++){
        if (strncmp(&s[i], t, strlen(t)) == 0)
            c++;
    }
    printf("%d\n", c);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>

 

using namespace std;

 

int main()
{
   int i,h,m,s;
   cin >> i;
   h = i / 3600;
   m = i / 60 - (h * 60);
   s = i - (h * 3600)- m*60 ; 
   cout << h << ":" << m << ":" << s << endl; 
   
   return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template

//main
signed main(){
  int Q;cin>>Q;
  typedef pair<int,int> P;
  std::vector<P> ans;
  int c=0;
  multiset<int> s;
  Q--;
  int z,zz,zzz;cin>>z>>zz>>zzz;
  c+=zzz;
  s.insert(zz);
  int mi=0,ma=0;
  auto it=s.lower_bound(zz);
  while(Q--){
    int a;cin>>a;
    if(a==1){
      int w,e;cin>>w>>e;c+=e;
      s.insert(w);
      if(s.size()%2){
        if(*it>w)mi+=w;
        else{
          ma+=w;
          mi+=*it;
          it++;
          ma-=*it;
        }
      }
      else{
        if(*it>w){
          mi+=w;
          ma+=*it;
          it--;
          mi-=*it;
        }
        else{
          ma+=w;
        }
      }
    }
    else{
      //cout<<mi<<" "<<ma<<endl;
      int rs=c;
      int x=*it;
      rs+=(s.size()-1)/2*x-mi;
      rs+=ma-(s.size()-(s.size()-1)/2-1)*x;
      ans.push_back(P(x,rs));
    }
  }
  for(auto p:ans)cout<<p.first<<" "<<p.second<<endl;
}


Measured memory_bytes: 9600
#include<stdio.h>

#define Length 1000000
 
typedef struct{
  char name[20];
  int time;
}Quence;
 
Quence que[Length];

int head = 0, tail = 0;
 
void push(Quence);

Quence pop(void);

int size();


int main()
{
  int n, q;
  Quence Que;
  int i, j, x,clock = 0;
 
  scanf("%d %d",&n,&q);
  
  for(i = 0;i < n;i ++)
    {
      scanf("%s %d",Que.name,&Que.time);
      push(Que);
    }
 
  while(1)
    {
      Que = pop();
      if(Que.time <= q)
    {
      clock += Que.time;
      printf("%s %d\n",Que.name,clock);
    }
      else
    {
      Que.time -= q;
      clock += q;
      push(Que);
    }
 
      if(size()==0)break;
    }
 
  return 0;
}

void push(Quence q)
{
  que[head++] = q;
  
}
 
Quence pop(void)
{

  return que[++tail-1];
}
 
int size(void)
{
  return head-tail;
}

Measured memory_bytes: 6736
// Aizu Vol-5 0554: Total Time
// 2017.8.30 bal4u@uu

#include <stdio.h>

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

	scanf("%d%d%d%d", &a, &b, &c, &d), s = a + b + c + d;
	printf("%d\n%d\n", s / 60, s % 60);
	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
	ll h, n;
	cin >> h >> n;

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

	sort(a, a+n, greater<int>());

	// for(int i=0;i<n;i++) cout << a[i] << " ";

	ll ans = 0, ok = 0;
	for(int i=0;i<n;i++)
	{
		if(ans >= h)
		{
			cout << "Yes\n";
			ok = 1;
			break;
		}
		else
		{
			ans += a[i];
		}
	}
	if(ans >= h && !ok) cout << "Yes\n";
	else if(!ok) cout << "No\n";
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define inf 100000


int N,M;
int ab[100][100];

set<pair<int,int>> use;

int dijkstra(int k){
	vector<int> dist(N,inf);
	vector<vector<int>> prev(N);
	priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
	dist[k] = 0;
	que.push({0,k});
	while(!que.empty()){
		auto cur = que.top().second; que.pop();
		for(int i=0;i<N;i++){
			if(ab[cur][i] == 0) continue;
			if(dist[cur] + ab[cur][i] < dist[i]){
				dist[i] = dist[cur] + ab[cur][i];
				que.push({dist[i],i});
				prev[i].clear();
				prev[i].push_back(cur);
			}else if(dist[cur] + ab[cur][i] == dist[i]){
				prev[i].push_back(cur);
			}
		}
	}
	for(int v=0;v<N;v++){
		for(auto u:prev[v]){
			use.insert(make_pair(min(u,v), max(u,v)));
		}
	}
	return 0;
}

int solve(){
	for(int i=0;i<N;i++){
		dijkstra(i);
	}
	// for(auto u:use){
	// 	cout << u.first << "," << u.second << endl;
	// }
	cout << M - (int)use.size() << endl;
	return 0;
}


int main(){
	int a,b,c;
	cin >> N >> M;
	for(int i=0;i<M;i++){
		cin >> a >> b >> c;
		a--;b--;
		ab[a][b] = c;
		ab[b][a] = c;
	}
	solve();
	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	HashSet<String> gHs;

	void eM(String s, HashSet<String> l) {
		int n = s.length();

		String pre[] = new String[n];
		String post[] = new String[n+1];

		for (int i = 0; i < n; i++) {
			pre[i] = s.substring(0, i);
		}

		for (int i = 0; i < n; i++) {
			post[i] = s.substring(i);
		}
		post[n] =""; 
		for (int i = 0; i < n ; i++) {
			l.add(pre[i] + post[i + 1]); // del
//			System.out.println(pre[i]+post[i+1]);
			// gHs.add(pre[i] + post[i + 1]);
			for (char c = 'a'; c <= 'z'; c++) {
				l.add(pre[i] + c + post[i + 1]); // rep
				// gHs.add(pre[i] +c+ post[i + 1]);
			}
		}
		

		for (int i = 0; i < n; i++) {
			for (char c = 'a'; c <= 'z'; c++) {
				l.add(pre[i] + c + post[i]); // ins
				// gHs.add(pre[i]+c + post[i ]);
			}
		}
		for (char c = 'a'; c <= 'z'; c++) {
			l.add(s + c);
			l.add(c+s);
			// gHs.add(s+c);
		}

		char[] chmap = s.toCharArray();

		for (int i = 0; i < n - 1; i++) {
			int j = i + 1;
			{
				char sw = chmap[i];
				chmap[i] = chmap[j];
				chmap[j] = sw;
				l.add(new String(chmap)); // exc
				// gHs.add(new String(chmap));
				sw = chmap[i];
				chmap[i] = chmap[j];
				chmap[j] = sw;
			}
		}
		
	}

	@SuppressWarnings("unchecked")
	void run() {
		for (;;) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}

			int d = sc.nextInt();
			gHs = new HashSet<String>();
			String[] name = new String[n];

			for (int i = 0; i < n; i++) {
				name[i] = sc.next();
			}

			Arrays.sort(name);

			// System.out.println(Arrays.toString(name));
			int cnt = 0;

			HashSet<String>[] llst = new HashSet[n];
			for (int i = 0; i < n; i++) {
				llst[i] = new HashSet<String>();
				eM(name[i], llst[i]);
			}

			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					if (name[i].equals(name[j])) {
						System.out.println(name[i] + "," + name[j]);
						cnt++;
					} else if (d > 0) {
						boolean check = llst[i].contains(name[j]);
						if (check) {
							System.out.println(name[i] + "," + name[j]);
							cnt++;
						} else if (d > 1) {
							boolean check2 = false;
							for (String str : llst[i]) {
								check2 = llst[j].contains(str);
								if (check2) {
									break;
								}
							}
							if (check2) {
								System.out.println(name[i] + "," + name[j]);
								cnt++;
							}
						}
					}
				}
			}
			System.out.println(cnt);

		}

	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
}

Measured memory_bytes: 31000
#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)+1;i++)
#define vec vector
typedef int64_t intl;
#define fi first
#define se second
#define pushb push_back
#define popb pop_back
#define SortA(v) sort(v.begin(), v.end())
#define SortD(v) sort(v.rbegin(), v.rend())
vec<int> dx = {0, 1, 0, -1, 1, 1, -1, -1};
vec<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};



int main(){
 int N,M;
  cin >> N>>M;
  vec<int> A(N);
  double sum=0;
  Rep(i,N){
    cin >> A.at(i);
    sum+=A.at(i);
  }
  SortD(A);
  Rep(i,M){
    if (A.at(i) < sum /(4*M) ) {cout <<"No";return 0;}
  }
  cout <<"Yes";
}


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

int main(void){
    
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if(a == b && b == c) cout << '1' << endl;
    else if(a == b && b != c) cout << '2' << endl;
    else if(a != b && b == c) cout << '2' << endl;
    else if(a == c && a != b) cout << '2' << endl;
    else cout << '3';
    
    return 0;

}

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

using namespace std;

#define repeat(n) for(int _______ = (n); _______ > 0; --_______)
#define loop(i, l, r) for(auto i = (l), __r = decltype(i)(r); i <= __r; ++i)
#define iloop(i, l, r) for(auto i = (l), __r = decltype(i)(r); i < __r; ++i)
#define rloop(i, r, l) for(auto i = (r), __l = decltype(i)(l); i >= __l; --i)

using LL = long long;

template<typename Container>
inline
int size(const Container& x)
{ return x.size(); }

#ifdef CAI_WEI_HAN

#include "my_print.h"
#include "LOG.h"

#else

#define LOG(...)

#endif

struct P
{ LL x, y, i; };

P operator - (P a, P b)
{ return P{ a.x - b.x, a.y - b.y, 0 }; }

LL operator ^ (P a, P b)
{ return a.x * b.y - a.y * b.x; }

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	constexpr char endl = '\n';
#ifdef CAI_WEI_HAN
	freopen("test.in", "r", stdin);
	register auto program_start_time = clock();
	#define cout cerr
#endif
	
	string s, t;
	cin >> s >> t;
	
	int ans = 0;
	loop(i, 0, size(s) - 1)
		ans += (s[i] == t[i]);
	
	cout << ans;
	
#ifdef CAI_WEI_HAN
	cout << "\n\n--------------------------------\n"
		 << "time:   " << double(clock() - program_start_time) / CLOCKS_PER_SEC;
#endif
}

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

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

using LL = long long int;
using LD = long double;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

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

	int n;
	LL t, a;
	cin >> n >> t >> a;

	REP(i, n - 1) {
		int nowT, nowA;
		cin >> nowT >> nowA;

		LL ma = max((t - 1) / nowT + 1, (a - 1) / nowA + 1);

		t = nowT * ma;
		a = nowA * ma;
	}

	cout << t + a << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n,k = i2()
s = l()
s[k-1] = s[k-1].lower()
for k in s:
    print(k,end="")

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

int main(void){
  int i,N; cin >> N;
  long long score=1000;
  vector<int> A(N);
  for(i=0; i<N; ++i){
    cin >> A[i];
    if(i>0 && A[i-1]<A[i]) score += (score/A[i-1])*(A[i]-A[i-1]);
  }
  cout << score << endl;
  return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M,ans=0;
  cin >> N >> M;
  int a[M],b[M-1];
  for(int i=0;i<M;i++)
    cin >> a[i];
  sort(a,a+M);
  for(int i=0;i<M-1;i++)
    b[i]=a[i+1]-a[i];  
  sort(b,b+M-1);
  for(int i=0;i<M-N;i++)
    ans += b[i];
  cout << ans << endl;
}


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

const ll mod = 1000000007;
const double eps = 1e-8;

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

int main() {
    int a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define LL long long

int n;
int h[200005],a[200005];
LL dp[200005];
set<pair<int,LL> > s;

int main() {
	scanf("%d",&n);
	for (int i=0; i<n; i++) {
		scanf("%d",&h[i]);
	}
	for (int i=0; i<n; i++) {
		scanf("%d",&a[i]);
	}
	dp[0] = a[0];
	s.insert({h[0],dp[0]});
	LL ret = dp[0];
    for (int i=1; i<n; i++) {
		auto it = s.lower_bound({h[i],0});
		if (it == s.begin()) {
			dp[i] = a[i];
		}
		else {
			it--;
			dp[i] = (*it).second+a[i];
			it++;
		}
		while (it != s.end() && (*it).second <= dp[i]) {
			it = s.erase(it);
		}
		s.insert({h[i],dp[i]});
		/*
		for (auto it=s.begin(); it!=s.end(); it++)
			printf("(%d,%lld) ",it->first,it->second);
		printf("\n%d: %lld\n",i,dp[i]);
		*/
		ret = max(ret,dp[i]);
    }
	printf("%lld\n",ret);
	return 0;
}


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

const int BASE = 80 * 160 + 5;
int A[85][85];
bool dp[85][85][BASE*2];

int main() {
    int h, w;
    cin >> h >> w;
    rep(i, h) rep(j, w) cin >> A[i][j];
    rep(i, h) rep(j, w) {
      int a;
      cin >> a;
      A[i][j] -= a;
    }
    dp[0][0][BASE+A[0][0]] = dp[0][0][BASE-A[0][0]] = true;
    rep(i, h) rep(j, w) rep(k, BASE*2) {
      int x = k - A[i][j], y = k + A[i][j];
      if (0<=x && x<BASE*2) {
        if (i) dp[i][j][k] |= dp[i-1][j][x];
        if (j) dp[i][j][k] |= dp[i][j-1][x];
      }
      if (0<=y && y<BASE*2) {
        if (i) dp[i][j][k] |= dp[i-1][j][y];
        if (j) dp[i][j][k] |= dp[i][j-1][y];
      }
    }
    int ans = BASE*2;
    rep(i, BASE*2) {
      if (dp[h-1][w-1][i]) ans = min(ans, abs(i-BASE));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 170240
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

const ll INF=1e18;
const int MOD=1000000007;

struct node{
	int s,e,m;
	ll val=0;
	bool zero=false;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void set_zero(int i,int j){	
		if (zero) return;
	
		if (s==i && e==j) zero=true,val=0;
		else{ 
			if(j<=m) l->set_zero(i,j);
			else if (m<i) r->set_zero(i,j);
			else l->set_zero(i,m),r->set_zero(m+1,j);
			
			val=(l->val+r->val)%MOD;
		}
	}
	
	void update(int i,ll j){
		if (zero) return;
	
		if (s==e) (val+=j)%=MOD;
		else{
			if (i<=m) l->update(i,j);
			else r->update(i,j);
			
			val=(l->val+r->val)%MOD;
		}
	}
	
	ll query(int i,int j){
		if (zero) return 0;
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return (l->query(i,m)+r->query(m+1,j))%MOD;
	}
}*arr=new node(0,100005),*brr=new node(0,100005);

ll n,a,b;
ll val[100005];

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>a>>b;
	
	val[0]=-INF;
	for (int x=1;x<=n;x++) cin>>val[x];
	
	arr->update(0,1);
	brr->update(0,1);
	
	
	int ai,bi;
	for (int x=2;x<=n;x++){
		ai=upper_bound(&val[0],&val[x-1],val[x]-a)-val;
		bi=upper_bound(&val[0],&val[x-1],val[x]-b)-val;
		
		arr->update(x-1,brr->query(0,ai-1));
		brr->update(x-1,arr->query(0,bi-1));
		
		if (val[x]-val[x-1]<a) arr->set_zero(0,x-2);
		if (val[x]-val[x-1]<b) brr->set_zero(0,x-2);
		
		/*
		for (int y=0;y<x;y++) cout<<arr->query(y,y)<<" ";
		cout<<endl;
		for (int y=0;y<x;y++) cout<<brr->query(y,y)<<" ";
		cout<<endl<<endl;
		*/
	}
	
	cout<<(arr->query(0,n)+brr->query(0,n))%MOD;
}


Measured memory_bytes: 26112
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

typedef pair<int, int> P;
int main()
{
	int n, m;
	while (scanf("%d %d", &m, &n), n)
	{
		int thick[100];
		for (int i = 0; i < n; ++i)
			scanf("%d", thick+i);

		int maxThick = 0;
		for (int i = 0; i < n; ++i)
			maxThick = max(maxThick, thick[i]);

		int ans = -1;
		for (int t = maxThick; ans == -1; ++t)
		{
			int step = 0;
			int sum = 0;
			int i;
			for (i = 0; i < n && step < m; ++i)
			{
				if (sum + thick[i] > t)
				{
					sum = 0;
					++step;
				}
				sum += thick[i];
			}
			if (i == n && step < m)
				ans = t;
		}
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 876
def shoelace(A):
    ret = 0

    for idx in range(1, len(A)):
        left = A[idx - 1]
        right = A[idx]
        ret += left[0] * right[1] - left[1] * right[0]

    ret += A[-1][0] * A[0][1] - A[-1][1] * A[0][0]

    return abs(ret) / 2


index = 1

while True:
    N = int(input())
    if N == 0:
        break

    A = []

    for i in range(N):
        A.append([int(elem) for elem in input().split()])

    print(index, shoelace(A))
    index += 1

    input()



Measured memory_bytes: 5620
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N;
  cin >> N;
  vector<double> p(N);
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }
  double dp[N][N];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N + 1; j++) {
      dp[i][j] = 0.0;
    }
  }
  dp[0][1] = p[0];
  dp[0][0] = 1.0 - p[0];
  for (int i = 1; i < N; i++) {
    for (int j = 0; j <= i; j++) {
      if (N - i + j < N / 2) {
        continue;
      } else {
        dp[i][j + 1] += dp[i - 1][j] * p[i];
        dp[i][j] += dp[i - 1][j] * (1.0 - p[i]);
      }
      // cout << i << "," << j << "," << dp[i][j] << endl;
      // cout << i << "," << j + 1 << "," << dp[i][j + 1] << endl;
    }
  }
  double ans = 0.0;
  for (int i = 0; i <= N; i++) {
    if (i < (double)N / 2) continue;
    // cout << dp[N - 1][i] << "," << i << endl;
    ans += dp[N - 1][i];
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

Measured memory_bytes: 70528
import copy
n,q=map(int,input().split())
l=[]
for i in range(n-1):
  l.append(list(map(int,input().split())))
l2=[]
for i in range(q):
  l2.append(list(map(int,input().split())))
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)

L4=[]
for i in range(n):
  L4.append(0)
for i in range(q):
  L4[l2[i][0]-1]+=l2[i][1]
distance=[0 for i in range(n)]
distance[0]=L4[0]
ans=[0 for i in range(n)]
ans[0]=L4[0]
L=[0]
L2=[]
L3=[]
while len(L2)!=n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      distance[connection[L[j]][k]]=distance[L[j]]+L4[connection[L[j]][k]]
      L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
for i in range(len(distance)):
  distance[i]=str(distance[i])
print(' '.join(distance))

Measured memory_bytes: 157688
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include<cstdlib>
#define FOR(i,a,b) for(i=a;i<=b;i++)

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long


ll N,A[100050], ans;


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

	for (int i = 0; i <= N; i++)
		ans+= abs(A[i]-A[i + 1]);
	for (int i = 1; i <= N; i++)
		cout << ans + abs(A[i - 1] - A[i + 1]) - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) << endl;


    return 0;
}



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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pii pair < int , int >
#define task "flight"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 2e5 + 123;
const int mod = 1e9 + 7;
const int INF = 1e9 + 1;
const ll INFL = 3e18 + 1;
const double pi = acos(-1.0);

void files (string s) {
  if (fopen ((s + ".in").c_str(),"r")) {
  	freopen ((s + ".in").c_str(),"r", stdin);
    freopen ((s + ".out").c_str(),"w", stdout);
  }
}
    
int main () {
	files ("");

	int x, y, z;
	cin >> x >> y >> z;
                  
	cout << (x - z) / (y + z);

	return 0;
}

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

using namespace std;

class RSQ
{
public:
    vector<int> data;
    int n;

    RSQ(int _n)
    {
        data.resize(4*_n);
        for(n=1;n<_n;n<<=1);
        fill(data.begin(),data.end(),0);
    }

    void add(int p,int l,int r,int x,int a,int b)
    {
        if(a>=r||b<=l) return;
        if(a<=l&&r<=b)
        {
            data[p]+=x;
            return;
        }

        int mid=(l+r)/2;
        add(p*2+1,l,mid,x,a,b);
        add(p*2+2,mid,r,x,a,b);
        data[p]=data[2*p+1]+data[2*p+2];
    }

    int getSum(int p,int l,int r,int a,int b)
    {
        int sum=0;
        if(a>=r||b<=l){
            sum=0;
        }else if(a<=l&&r<=b)
        {
            sum=data[p];
        }else
        {
            int mid=(l+r)/2;
            sum=getSum(p*2+1,l,mid,a,b)+getSum(p*2+2,mid,r,a,b);
        }
        return sum;
    }
};

int main()
{
    int n,q;

    while(cin>>n>>q)
    {
        RSQ rsq(n);

        while(q--)
        {
            int op,a,b;
            cin>>op>>a>>b;
            if(op)
            {
                cout<<rsq.getSum(0,0,rsq.n,a-1,b)<<endl;
            }else
            {
                rsq.add(0,0,rsq.n,b,a-1,a);
            }
        }
    }


    return 0;
}



Measured memory_bytes: 4356
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using edge = struct {int to; ll cost;};

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define INF (1 << 29)


void solve() {
    string a, b;
    cin >> a >> b;
    auto c = a + b;
    auto ans = atoi(c.c_str());
    if((double)ans == pow((int)sqrt(ans), 2)){
        cout << "Yes" << "\n";
    }
    else{
        cout << "No" << "\n";
    }
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t n;cin>>n;
  map<char,int64_t>a;
  a['M']=a['A']=a['R']=a['C']=a['H']=0;
  string tmp;
  for(int i=0;i<n;i++){
    cin>>tmp;
    if(a.count(tmp.at(0))){
      a.at(tmp.at(0))++;
    }
  }
  int64_t ans=0;
  vector<int64_t>aa(5);
  aa.at(0)=a['M'];
  aa.at(1)=a['A'];
  aa.at(2)=a['R'];
  aa.at(3)=a['C'];
  aa.at(4)=a['H'];
  for(int i=0;i<3;i++){
    for(int j=i+1;j<4;j++){
      for(int k=j+1;k<5;k++){
        ans+=aa.at(i)*aa.at(j)*aa.at(k);
      }
    }
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 3568
N,K = map(int,input().split())
D = list()
Snuke = {x for x in range(1,N+1)}

for i in range(K):
    d = int(input())
    j = list(map(int,input().split()))
    D.append(j)    
    
for i in D:
    Snuke = Snuke.difference(set(i))


print(len(Snuke))

Measured memory_bytes: 9192
#include<bits/stdc++.h>
#define int long long
#define P(x) cout << x << endl
#define D(x) P(#x << ": " << x)
#define F(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEC(i,n) for(int i = (int)(n); --i >= 0;)
#define S(s) (int)((s).size())
#define ALL(v) v.begin(), v.end()
#define V vector
#define pb push_back
#define mt make_tuple
using namespace std;

signed main() {
	string s; cin >> s;
	int n = S(s);

	int cnt[26]; fill(cnt,cnt+26,0);
	F(i,n)
		++cnt[s[i]-'a'];
	int ans = 1;
	F(i,26) {
		for(int j = i+1; j < 26; ++j)
			ans += cnt[i] * cnt[j];
	}
	P(ans);
}

Measured memory_bytes: 640
n = int(input())
robots = []
for i in range(n):
    x, l = map(int, input().split())
    robots.append([max(x-l, 0), x+l])

robots.sort(key=lambda robot: robot[1])

ans = 0
t = 0
for i in range(n):
    if t <= robots[i][0]:
        ans += 1
        t = robots[i][1]

print(ans)


Measured memory_bytes: 64984
#include <stdio.h>
int main(void){
  int k,a,b;
  scanf("%d %d %d",&k,&a,&b);
  long int sum=1;
  if(a>=b-2){
    sum=sum+k;
    printf("%ld\n",sum);
  }else{
    while(k>0){
    if(sum>=a && k>=2){
      sum=sum+b-a;
      k=k-2;
    }else{
          sum=sum+1;
          k=k-1;
    }
    }
    printf("%ld\n",sum);
  }
}


Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100005];
int main(){
    std::ios::sync_with_stdio(false);
    int a,b,k,cot=0;
    cin>>a>>b>>k;
    for(int i=min(a,b);i>=1;i--){
        if(a%i==0&&b%i==0){
            //cout<<i<<endl;
            cot++;
        }
        if(k==cot){
            cout<<i<<endl;
            return 0;
        }
    }
}



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

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

  count = a[0];

  for(i=1; i<n; i++){
    count ^= a[i];
  }

  cout << ((count==0) ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 640
from collections import deque
n, q = map(int,input().split())

A = deque()
for i in range(n):
    name, time = input().split()
    A.append([name, int(time)])

t = 0
seq = []
while len(A)>0:
    name, time = A.popleft()
    if time > q:
        time -= q
        t += q
        A.append([name, time])
    else:
        t += time
        seq.append([name, t])

for name, time in seq:
    print(name, time)


Measured memory_bytes: 15100
def make_dict_trump():
    t = {}
    for i in range(13):
        t[i+1] = 0
    return t

S = make_dict_trump()
H = make_dict_trump()
C = make_dict_trump()
D = make_dict_trump()

def countup_trump(trump, number):
    trump[number] += 1
    return trump

n = int(input())

for i in range(n):
    kind, number = input().split()
    number = int(number)
    if kind=="S":
        S = countup_trump(S, number)
    elif kind=="H":
        H = countup_trump(H, number)
    elif kind=="C":
        C = countup_trump(C, number)
    elif kind=="D":
        D = countup_trump(D, number)

def output(kind, trump):
    keys = [k for k, v in trump.items() if v == 0]
    for key in keys:
        print(kind, key)

output("S", S)
output("H", H)
output("C", C)
output("D", D)


Measured memory_bytes: 5616