akhauriyash/Code-Regression huggingface dataset:
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}

int main(void){
	int n, i, j;
	scanf("%d", &n);
	int ans=0;
	j=1;
	for(i=1; i<=n; i++){
		int p;
		scanf("%d", &p);
		if(p==j){
			ans++;
		}else{
			j=i+1;
		}
	}
	printf("%d\n", ans);
}


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

int main() {
    string s; cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '+') ans += 1;
        else ans -= 1;
    }

    cout << ans << endl;

    return 0;
}

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

int main(void){

int H,N,i;

int A;

scanf("%d%d", &H, &N);

i=0;

int G=0;

for (i = 1; i <= N; i++){

scanf("%d", &A);

G=G+A;


}

if(G<H){ 

printf("No");

}else{

printf("Yes");

}

return(0);

}

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

#define ll long long
#define F(i,m,n) for(ll i=m;i<n;i++)
#define Fr(j,n,m) for(ll j=n;j>=m;j--)
#define vll vector<ll>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vpll vector< pll >
#define tlll tuple < ll ,ll,ll >
/*-------------------------------------*---------------------------------------*/

#define godspeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout << #x << "=" << x << endl
#define cout_array(a) cout<<#a<<"=";for(auto x: a){ cout<<x<<" ";}cout<<endl

ll gcd(ll a,ll b){
    return (b?gcd(b,a%b):a);
}
const ll MAX_PRIME = 1e9+7;
const ll INF = 1e18;


/*I NEED YOU TO WORK FOR TWO HOURS ON THIS NO MATTER WHAT....THE RESULT DOESN'T MATTER.....ITS ALL ABOUT YOUR EFFORTS.
---------------------------------------------------------------------------------------------------------------------*/

ll fast_pow(ll x,ll y,ll z){
    if(y==0)return 1%z;
    else if(y==1)return x%z;
    if(y%2==0){
        ll res = fast_pow(x,y/2,z);
        return (res*res)%z;
    }
    else{
        ll res = fast_pow(x,y/2,z);
        ll temp = (res*res)%z;
        return ((x%z)*temp)%z;
    }
}

int main() {
    godspeed

        ll d,t,s;
        cin>>d>>t>>s;
        ll time = ceil((float (d))/s);
        if(time<=t)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 3648
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def suma(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, K = inpl()
a = [0]
for _ in range(N):
    a.append(a[-1] + int(input()) -K)
c = dict([])
for i, v in enumerate(sorted(set(a))):
    c[v] = i+1
Tr = BIT(N+1)
ans = 0
for v in a:
    ans += Tr.suma(c[v])
    Tr.add(c[v], 1)
print(ans)

Measured memory_bytes: 95028
#include <iostream>
#include <vector>
int main(void){
  int n,i,k;
  std::cin>> n;
  std::vector<double> a(100);
  for(i=0;i<n;i++){
  std::cin>> a.at(i);
  }
  for(i=0;i<n;i++){
  	for(k=i+1;k<n;k++){
    int m;
      if(a.at(i)>a.at(k)){
      m=a.at(i);
      a.at(i)=a.at(k);
      a.at(k)=m;
      }
    }
  }
  for(i=0;i<n-1;i++){
  double aver=(a.at(i)+a.at(i+1))/2;
    a.at(i+1)=aver;
  }
  std::cout<< a.at(n-1) << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 1000000000000
#define int long long int
#define hell (int)(1e9+7)

using namespace std;

void solve(){
    int n,k,ok;
    cin>>n>>k;
    vector <int> a(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    set <int> vis;
    vis.insert(1);
    int st=1;
    ok=k;
    if(ok<=1e6){
        while(k>0){
            k--;
            st=a[st];
        }
        cout<<st;
        return;
    }
    while(k>0){
        k--;
        st=a[st];
        if(vis.count(st))
            break;
        vis.insert(st);
    }
    //cout<<st<<" ";
    int cs=1,ost=st;
    while(a[st]!=ost){
        cs++;
        st=a[st];
    }
    //cout<<cs<<" ";
    st=a[st];
    k=ok;
    int ns=1;
    while(k>0&&ns!=st){
        k--;
        ns=a[ns];
    }
    k%=cs;
    while(k>0){
        k--;
        ns=a[ns];
    }
    cout<<ns;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 12000
#!/usr/bin/env python3
n = int(input())

def dfs(k):  # k : str
    if int(k) > n: return 0
    c = 1 if all(k.count(t) for t in "753") else 0  # k judge
    for t in "753":
        c += dfs(k + t)
    return c
print(dfs("0"))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define pb push_back
typedef long long int ll;
using namespace std;
int main(void){
	fast;
	int n,k,i;
	ll s=0;
	cin>>n>>k;
	int a[n];
	for(i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	for(i=0;i<k;i++)
	s+=a[i];
	cout<<s;

}


Measured memory_bytes: 3640
// finish date: 2018/07/23
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N, C, K;
    cin >> N >> C >> K;
    vi T(N);
    rep(i, N) cin >> T[i], T[i] += K;
    sort(T.begin(), T.end());

    int t = INT_MIN;
    int ca = 0;
    int cnt=0;
    rep(i, N) {
        if (T[i] - K <= t && ca > 0) {
            ca--;
        } else {
            t = T[i];
            ca = C - 1;
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}



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

typedef long long ll;

ll t1,t2;
ll a1,a2;
ll b1,b2;

int main(){
	scanf("%lld%lld",&t1,&t2);
	scanf("%lld%lld",&a1,&a2);
	scanf("%lld%lld",&b1,&b2);
	if((a1*t1 + a2*t2) > (b1*t1 + b2*t2)){
		swap(a1,b1);
		swap(a2,b2);
	}
	if((a1*t1 + a2*t2) == (b1*t1 + b2*t2)){
		printf("infinity\n");
		return 0;
	}
	if(b1 > a1){
		printf("0\n");
		return 0;
	}
	
	
	ll abalap = (a1-b1)*t1;
	ll gap = b1*t1 + b2*t2 - a1*t1 - a2*t2;
//	cout << "GAP : " << gap << endl;
	ll batas = abalap/gap;
	ll ans = batas*(ll)(2ll) + (ll)(1ll);
	if(batas * gap == abalap) ans--;
	printf("%lld\n",ans);

	return 0;
}


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

int solve(int *line,int count){
    int thisLine[count];
    for(int i=0; i<count; i++){
        thisLine[i]=(line[i]+line[i+1])%10;
    }
    if(count>1){
        return solve(thisLine,count-1);
    }else{
        return thisLine[0];
    }
}

int main()
{
    string str;
    int line[9];
    while(cin>>str){
        for(int i=0; i<9; i++){
            line[i]=((int)str[i]+(int)str[i+1]-96)%10;
        }
        cout<<solve(line,8)<<endl;
    }
    return 0;
}

Measured memory_bytes: 1180
n = int(input())
l = [_ for _ in range(1,10)]

cnt = 9
d = [-1, 0, 1]
for i in range(10**5):
    if cnt >= n: break
    for j in d:
        if 0 <= int(str(l[i])[-1]) + j <= 9:
            l.append(l[i]*10 + int(str(l[i])[-1]) + j)
            cnt += 1

print(l[n-1])

Measured memory_bytes: 7240
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

	//int x = log2((1/log(2.0) * (float)k));
	int ans = 1;
	for(int i=0;i<n;i++) {
		if(pow(2.0, i+1) - pow(2.0, i) - k <= 0) {
			ans *= 2;
		} else {
			ans += k;
		}
	}
	cout << ans << endl;
	
	return 0;
}


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

int main(void){
  char buf[16] = { 0 };
  int N;
  int n_AC = 0;
  int n_WA = 0;
  int n_TLE = 0;
  int n_RE = 0;
  
  fgets(buf, sizeof(buf), stdin);
  sscanf(buf, "%d", &N);
  
  for(int i = 0; i < N; i++){
    memset(buf, 0, sizeof(buf));
    fgets(buf, sizeof(buf), stdin);
    if(memcmp(buf, "AC", 2) == 0) n_AC++;
    else if(memcmp(buf, "WA", 2) == 0) n_WA++;
    else if(memcmp(buf, "TLE", 3) == 0) n_TLE++;
    else if(memcmp(buf, "RE", 2) == 0) n_RE++;
  }
  
  printf("AC x %d\n", n_AC);
  printf("WA x %d\n", n_WA);
  printf("TLE x %d\n", n_TLE);
  printf("RE x %d\n", n_RE);
  
  return 0;
}

Measured memory_bytes: 1772
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
    ll T1, T2, A1, A2, B1, B2;
    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;
    ll alpha = T1*(A1-B1) + T2*(A2-B2);
    ll beta = T2*(A2-B2);

    if(alpha == 0){
        cout << "infinity" << endl;
    }else{
        ll ans = max(0ll, beta/alpha) + max(0ll, ll(1.0*beta/alpha-1));
        if(beta%alpha==0) ans--; 
        cout << max(0ll, ans) << endl;
    }
}

Measured memory_bytes: 256
s = input()
lowercase = [chr(ord('a') + i) for i in range(26)]
#print(lowercase)

ans = 'AC'
c_count = 0
for i in range(len(s)):
  yet = True
  if i == 0:
    yet = False
    if s[i] != 'A':
      ans = 'WA'
      break
  if yet and 2 <= i <= len(s) - 2:
    if s[i] == 'C':
      yet = False
      c_count += 1
        
  if yet:
      if not s[i] in lowercase:
        ans = 'WA'
        break
if c_count != 1:
  ans = 'WA'
  
print(ans)
    

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

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

    reverse(s.begin(), s.end());

    int size=s.size();
    int i=0;
    while(i<size){
        if(i+5 <= size && s.substr(i,5) == "maerd") i=i+5;
        else if(i+7 <= size && s.substr(i,7) == "remaerd") i=i+7;
        else if(i+5 <= size && s.substr(i,5) == "esare") i=i+5;
        else if(i+6 <= size && s.substr(i,6) == "resare") i=i+6;
        else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 512
import java.io.*;

class Main{
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while(true){
            String line[] = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            if(x == 0 && y == 0){
                break;
            }else{
                sb.append(Integer.toString(x < y ? x : y)).append(" ").append(Integer.toString(x < y ? y : x)).append("\n");
            }
        }
        System.out.print(sb);
    }
}

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

int main(){
  string S;
  ll K;
  cin >> S;
  cin >> K;
  int num1 = 0;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '1'){
      num1++;
    } else break;
  }
  if(K <= num1){
    cout << '1' << endl;
  } else {
    cout << S[num1] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a,b; cin >> a >> b;
  string k=a+b;
  int N=stoi(k);
  for(int i=4;i<400;i++){
    if(i*i==N){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}



Measured memory_bytes: 256
(stdin => {
  // Define Function
  const range = (start, end) => 
    Array.from(Array(end - start).keys(), v => v + start)
  
  const isDiviser = base => diviser => base % diviser === 0
  // Declare Variable
  const inputs = stdin.toString().trim().split('\n')
  const [a, b, c] = Array.from(inputs[0].split(' '), Number)
  const nlist = range(a, b + 1)
  // Main
  const diviser = isDiviser(c)
  const result = nlist.filter(diviser).length


  // Display
  console.log(result)

})(require('fs').readFileSync('/dev/stdin', 'utf8'))



Measured memory_bytes: 17224
x, k, d = map(int, input().split())

a = abs(x) // d
b = abs(x) % d

if k <= a:
  print(abs(x) - d * k)
else:
  if a % 2 == 1:
    if k % 2 == 1:
      print(b)
    else:
      print(d - b)
  else:
    if k % 2 == 0:
      print(b)
    else:
      print(d - b)
  

Measured memory_bytes: 9172
mod = 10**9 + 7
N, M, K = gets.split.map(&:to_i)
ans = 0
com = 1
for i in 1..K-2
  com *= (N*M-1-i) * (K-1-i).pow(mod-2, mod)
  com %= mod
end
for i in 1..N
  ans += (i * (N-i) * M * M) % mod
end
for i in 1..M
  ans += (i * (M-i) * N * N) % mod
end
p ans * com % mod

Measured memory_bytes: 14396
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n - 1, -1, -1):
    if i + 1 > n // 2:
        ans[i] = a[i]
    else:
        cnt = 0
        for j in range(i, n, i + 1):
            if ans[j] == 1:
                cnt += 1
        #ans[i] = cnt % 2 + a[i]
        if cnt % 2 == a[i]:
            ans[i] = 0
        else:
            ans[i] = 1 
#print(sum(s))
s = sum(ans)
print(s)
for i, j in enumerate(ans):
    if j == 1:
        print(i + 1)
            


Measured memory_bytes: 7100
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int main() {
  size_t N;
  int A, B;
  scanf("%zu %d %d", &N, &A, &B);

  std::vector<int> h(N);
  for (size_t i=0; i<N; ++i)
      scanf("%d", &h[i]);

  auto invalid=[&](intmax_t x)->bool {
    intmax_t a=A-B, res=x;
    for (size_t i=0; i<N; ++i) {
      intmax_t hh=h[i]-B*x;
      if (hh <= 0) continue;

      res -= (hh+a-1)/a;
    }

    return res < 0;
  };

  int lb=0, ub=1e9;
  while (ub-lb > 1) {
    int mid=(lb+ub)>>1;
    (invalid(mid)? lb:ub) = mid;
  }

  printf("%d\n", ub);
}


Measured memory_bytes: 640
from collections import Counter  # N : 素因数分解

MOD = 10**9 + 7


def comb(n, r):
    r = r if n-r <= r else n-r
    a = 1
    for x in list(range(r + 1, n + 1)):
        a *= x % MOD
    b = 1
    for x in list(range(1, n - r + 1)):
        b *= x % MOD
    return (a // b)


N, M = [int(s) for s in input().split()]
prime_factor = []
for i in range(2,int(M**0.5)+1):
    while M%i == 0:
        prime_factor.append(i)
        M/=i
if M > 1:
    prime_factor.append(M)
    
c = Counter(prime_factor)

result = 1

for b in c.values():
    result *= comb(b+N-1, b) % MOD


print(result % MOD)


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

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

    int a[n][m], b[m];
    int c[n];

    for(int i=0; i<n; i++) {
	for(int j=0; j<m; j++) {
	    cin >> a[i][j];
	}
    }
    for(int i=0; i<m; i++) {
	cin >> b[i];
    }

    for(int i=0; i<n; i++) {
	c[i] = 0;
	for(int j=0; j<m; j++) {
	    c[i] += a[i][j] * b[j];
	}
    }

    for(int i=0; i<n; i++) {
	cout << c[i] << endl;
    }
}

Measured memory_bytes: 1200
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll r[1100000];
map<ll, ll> m;
ll mod = 2019;
ll powmod(ll a, ll b) {
	a %= mod;
	ll res = 1;
	while (b > 0) {
		if (b % 2 == 1)res = res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}
ll ans = 0;
int main() {
	string s;
	cin >> s;
	m[0]++;
	ll n = s.size();
	REPR(i, n - 1) {
		r[i] = (r[i + 1] + powmod(10, n - 1 - i) * (s[i] - '0')) % 2019;
		//cout << r[i] << endl;
		ans += m[r[i]];
		m[r[i]]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 5244
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.numeric;

void main() {
  long a, b;
  readf (" %d %d", &a, &b);
  writeln ( (a / gcd (a, b)) * b);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int MAX_N = 100;
int N, T;
int c[MAX_N], t[MAX_N];

void _main() {
  cin >> N >> T;
  rep(i, 0, N) cin >> c[i] >> t[i];

  int min_c = inf;
  rep(i, 0, N) {
    if (t[i] <= T) chmin(min_c, c[i]);
  }

  if (min_c == inf) cout << "TLE" << "\n";
  else cout << min_c << "\n";
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        if(A+B+C<=21)
        {
            System.out.println("win");
        }
        else
        {
            System.out.println("bust");
        }
    }
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
#define INF 0x7FFFFFFF
const double EPS = 1e-10;


inline bool eq(double a, double b) { return fabs(b - a) < EPS;}

struct p_t{
  double x;
  double y;
  double norm() { return x * x + y * y; }
  double abs() { return sqrt(norm()); }
};
struct l_t{
	p_t a, b;
};

double cross(p_t p,p_t q);
p_t line(p_t p,p_t q);

bool asc(p_t left,p_t right) {
    return left.x == right.x ? left.y < right.y : left.x < right.x;
}
p_t Crosspoint(l_t l,l_t m);

int main(){
  int n;
  p_t z;
  vector<p_t> a;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>z.x>>z.y;
    a.push_back(z);
  }
  int q;
  cin>>q;
  p_t u,v;
  for(int t=0;t<q;t++){
    double ans=0;
    cin>>v.x>>v.y>>u.x>>u.y;
    // if(u.y>v.y){
    //   z=u;
    //   u=v;
    //   v=z;
    // }
    int c,d;
    int f=0;
    for(c=0;c<2*n;c++){
      if(cross(line(u,v),line(a[c%n],v))<0){
        f=1;
      }
      else if(f==1) break;
    }
    f=0;
    for(d=0;d<2*n;d++){
      if(cross(line(u,v),line(a[d%n],v))>=0){
        f=1;
      }
      else if(f==1) break;
    }
    if(d==2*n&&f==0){
      cout<< fixed <<ans<<endl;
      continue;
    }
    if(d==2*n&&f==1){
      for(int i=0;i<(int)a.size();i++){
        ans+=cross(a[i],a[(i+1)%a.size()]);
      }
      ans/=2.0;
      if(ans<0){
        ans=-ans;
      }
      cout<< fixed <<ans<<endl;
      continue;
    }
    l_t uc,ud,uv;
    uc.a=a[(c-1)%n];
    uc.b=a[c%n];
    ud.a=a[(d-1)%n];
    ud.b=a[d%n];
    uv.a=u;
    uv.b=v;
    vector<p_t> b;
    b.push_back(Crosspoint(uc,uv));
    d%=n;
    for(int i=c%n;i<(c%n<d?d:d+n);i++){
      b.push_back(a[i%n]);
    }
    b.push_back(Crosspoint(ud,uv));
    for(int i=0;i<(int)b.size();i++){
      ans+=cross(b[i],b[(i+1)%b.size()]);
    }
    ans/=2.0;
    if(ans<0){
      ans=-ans;
    }
    cout<< fixed <<ans<<endl;
  }
}


p_t line(p_t p,p_t q){
  p_t z;
  z.x=q.x-p.x;
  z.y=q.y-p.y;
  return z;
}


double cross(p_t p,p_t q){
  return p.x*q.y-p.y*q.x;
}

p_t Crosspoint(l_t l,l_t m){
  p_t aa,bb,cc,dd,ee;
  aa.x=l.b.x-l.a.x;
  aa.y=l.b.y-l.a.y;
  bb.x=m.b.x-m.a.x;
  bb.y=m.b.y-m.a.y;
  cc=aa;
  dd.x=l.b.x-m.a.x;
  dd.y=l.b.y-m.a.y;
	double A = cross(aa,bb);
	double B = cross(cc,dd);
	if (abs(A) < EPS && abs(B) < EPS) return m.a;
  ee.x=m.a.x+(m.b.x-m.a.x)*B/A;
  ee.y=m.a.y+(m.b.y-m.a.y)*B/A;
	return ee;
}



Measured memory_bytes: 3292
#include<stdio.h>
int map[102][102];
int canwalk;
int judgeOK;
maze(int nowy,int nowx,int gy,int gx){
    map[nowy][nowx]=0;
    /*
    printf("%d %d %d\n",nowx,nowy,judgeOK);
    */
    if(judgeOK==1)
        canwalk=6;
    if(nowy==gy&&nowx==gx){
        judgeOK=1;
    }
    if(map[nowy][nowx+1]==canwalk)
        maze(nowy,nowx+1,gy,gx);
    if(map[nowy+1][nowx]==canwalk)
        maze(nowy+1,nowx,gy,gx);
    if(map[nowy][nowx-1]==canwalk)
        maze(nowy,nowx-1,gy,gx);
    if(map[nowy-1][nowx]==canwalk)
        maze(nowy-1,nowx,gy,gx);
    return judgeOK;
}
int main(void){
    int w,h,xs,ys,xg,yg,n,c,d,x,y;
    int i,j,k;
    for(;;){
        for(i=0;i<102;i++){
            for(j=0;j<102;j++){
                map[i][j]=0;
            }
        }
        scanf("%d %d",&w,&h);
        if(w==0&&h==0)
            break;
        scanf("%d %d",&xs,&ys);
        scanf("%d %d",&xg,&yg);
        xs--,ys--,xg--,yg--;
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d %d %d %d",&c,&d,&x,&y);
            x--,y--;
            if(d==0){
                for(j=0;j<2;j++){
                    for(k=0;k<4;k++){
                            map[y+j][x+k]=c;
                    }
                }
            }
            else{
                for(j=0;j<4;j++){
                    for(k=0;k<2;k++){
                            map[y+j][x+k]=c;
                    }
                }
            }
        }
        /*
        for(i=0;i<w;i++){
            for(j=0;j<h;j++){
                printf("%d ",map[i][j]);
            }
        puts("");
        }
        */
            judgeOK=0;
        if(map[ys][xs]==map[yg][xg]){
            if(map[ys][xs]!=0){
                canwalk=map[ys][xs];
                judgeOK=maze(ys,xs,yg,xg);
            }
        }
        if(judgeOK==1)
            puts("OK");
        else
            puts("NG");
    }
return 0;
}

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

int main() {
    int c[3][3];
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin >> c[i][j];

    for(int i=0;i<101;i++)for(int j=0;j<101;j++)for(int k=0;k<101;k++){
        bool ok = true;
        int a[3] ={i,j,k};
        int b[3] ={c[0][0] - a[0],c[0][1]-a[0],c[0][2]-a[0]};

        for(int l=1;l<3;l++)for(int m=0;m<3;m++){
            if(a[l]+b[m]!=c[l][m]){
                ok=false;
                break;
            }
        }
        if(ok){
            cout << "Yes" << endl;
            return 0;
        }

    }
    cout << "No" << endl;
}

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

result=10000000000
for i in range(N):
    x=0
    y=0
    z=0
    for j in range(i+1):
    
        x+=a[j]
        z=j

    for k in range(N-(i+1)):

        y+=a[k+j+1]

    if(result>abs(x-y)):
        result=abs(x-y)
print(result)


Measured memory_bytes: 3060
// Package main provides
//
// File:  d.go
// Author: ymiyamoto
//
// Created on Mon Jan  7 00:42:17 2019
//
package main

import (
	"fmt"
	"math"
)

func scanSlice(slice []int) {
	for i := range slice {
		fmt.Scan(&slice[i])
	}
}

func main() {
	var N int
	fmt.Scan(&N)

	ts := make([]int, N)
	scanSlice(ts)
	ts = append([]int{0}, ts...)
	for i := range ts {
		ts[i] *= 2
	}

	vs := make([]int, N)
	scanSlice(vs)

	for i := range ts {
		if i+1 < len(ts) {
			ts[i+1] += ts[i]
		}
	}

	totalTime := ts[len(ts)-1]
	vecs := make([][]float64, len(vs))
	for i := range vecs {
		vecs[i] = make([]float64, totalTime+1)
		for j := range vecs[i] {
			vecs[i][j] = math.MaxFloat64
		}
	}

	for i := range vs {
		lowerTime := ts[i]
		upperTime := ts[i+1]
		for j := lowerTime; j <= upperTime; j++ {
			vecs[i][j] = float64(vs[i])
		}

		if i+1 < len(vs) && vs[i] < vs[i+1] {
			vec := float64(vs[i])
			for j := upperTime; j < len(vecs[i]); j++ {
				vecs[i][j] = vec
				vec += 0.5
			}
		}
		if i > 0 && vs[i] < vs[i-1] {
			vec := float64(vs[i])
			for j := lowerTime; j >= 0; j-- {
				vecs[i][j] = vec
				vec += 0.5
			}
		}
	}

	v := make([]float64, totalTime+1)
	speed := 0.0
	for i := range v {
		v[i] = speed
		speed += 0.5
	}
	vecs = append(vecs, v)

	v = make([]float64, totalTime+1)
	speed = 0.0
	for j := len(v) - 1; j >= 0; j-- {
		v[j] = speed
		speed += 0.5
	}
	vecs = append(vecs, v)

	var vec []float64
	for t := range vecs[0] {
		min := math.MaxFloat64
		for i := range vecs {
			if vecs[i][t] < min {
				min = vecs[i][t]
			}
		}
		vec = append(vec, min)
	}

	ans := 0.0
	for i := range vec {
		if i+1 < len(vec) {
			ans += (vec[i] + vec[i+1]) / 4.0
		}
	}

	fmt.Println(ans)
}


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

using namespace std;
#define ull unsigned long long
#define ll long long
const int MAXN = 2e5 + 1;
vector<vector<pair<int, int>>> vert(1e5+1, vector<pair<int,int>>(0));
vector<bool> was(1e5+1, false);
int ans[(int)1e5+1];
void dfs(int v, int colorbef){
    was[v]=true;
    int color=1;
    for(auto &son:vert[v]){
        if(was[son.first]) continue;
        else{
            if(color==colorbef) color++;
            ans[son.second]=color;
            dfs(son.first, color);
            color++;
        }
    }
}

void solve() {
    int n;
    cin>>n;
    int maxdeg=-1;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        vert[a].push_back({b,i});
        vert[b].push_back({a,i});
        maxdeg=max(maxdeg, (int)vert[a].size());
        maxdeg=max(maxdeg, (int)vert[b].size());
    }
    dfs(1,-1);
    cout<<maxdeg<<endl;
    for(int i=0;i<n-1;i++){
        cout<<ans[i]<<" ";
    }
}

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


Measured memory_bytes: 7552
using System;
//using System.Collections;
//using System.Collections.Generic;
using System.Linq;

namespace problem
{
  class Test
  {
    static void Main()
    {
      int i = int.Parse(Console.ReadLine());
      //int[] j = new int[i];
      var j = Console.ReadLine().Split().Select(int.Parse).ToArray();

      for (int a = i - 1; a >= 0; a--)
      {
        Console.Write(j[a]);
        if (a != 0) Console.Write(" ");
      }
      Console.WriteLine();
    }
  }
}


Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define Sort(v, n) sort(v, v+n);
#define VSort(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define cY cout<<"Yes";
#define cN cout<<"No";
#define cA(a) cout<<a;
const ll MOD = 1000000007;

int main() {
    ll a,b,k,o = 0;
    cin >> a >>b >> k;
    if(a>k) {
        cout << a-k << ' ' << b;
    } else {
        cout << 0 << ' ' << max(o,a+b-k);
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 300005
#define SIZE 2000005
#define int long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(),v.end()
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   int k,a,b;
   cin>>k>>b>>a;
   int sc = a/k;
   if(b) sc -= (b-1)/k;
   if(sc)cout<<"OK";
   else cout<<"NG";
    return 0;
}

Measured memory_bytes: 3640
using namespace std;
#include<string.h>
#include <sstream>
typedef long long int ll;
typedef long double ld;
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <map>
//#define N 4
#include <stack>
#include <unordered_set>
#include <math.h>
#include <cstring>
#include <bitset>
#include <set>
#include <sstream>
#include <queue>
#define PI 3.14159265358979323846264338327950
#define mp make_pair
#define inf 1e9
//#define M 1000000007
#define M 8888888888
//#define N 1000000009

void solve() {

	ll n, m;
	cin >> n >> m;

	vector<ll> adj[n + 1];

	for (ll i = 1; i <= m; i++) {
		ll x, y;
		cin >> x >> y;

		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	queue<ll> queue;
	vector<ll> vis(n + 1);
	vector<ll> ans(n + 1);

	queue.push(1);
	vis[1] = true;

	while (!queue.empty()) {

		ll val = queue.front();
		queue.pop();

		for (ll i = 0; i < adj[val].size(); i++) {

			if (!vis[adj[val][i]]) {
				vis[adj[val][i]] = true;
				queue.push(adj[val][i]);
				ans[adj[val][i]] = val;
			}
		}
	}

	cout << "Yes\n";
	for (int i = 2; i <= n; i++) {
		cout << ans[i] << "\n";
	}
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	solve();
	return 0;
}



Measured memory_bytes: 13664
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
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 long long LLINF=1LL<<60;
//set<int>::iterator it;
//|\_
//g++ -std=c++1z temp.cpp
//./a.out





int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    string s,t;
    int i,j;
    while(1){
        cin>>s;
        if(s==".")break;
        cin>>t;
        if(s==t){
            cout<<"IDENTICAL"<<endl;
            continue;
        }
        if(count(s.cbegin(), s.cend(), '\"')!=count(t.cbegin(), t.cend(), '\"')){
            cout<<"DIFFERENT"<<endl;
            continue;
        }
        vector<string> v,w;
        string x="",y="";
        for(i=0;i<s.length();i++){
            if(s[i]=='\"'){
                j=1;
                v.push_back("");
                while(s[i+j]!='\"'){
                    v[v.size()-1]+=s[i+j];
                    j++;
                }
                i+=j;
                x+="¥";
            }
            else x+=s[i];
        }
        for(i=0;i<t.length();i++){
            if(t[i]=='\"'){
                j=1;
                w.push_back("");
                while(t[i+j]!='\"'){
                    w[w.size()-1]+=t[i+j];
                    j++;
                }
                i+=j;
                y+="¥";
            }
            else y+=t[i];
        }
        int wrong=0;
        rep(i,v.size())if(v[i]!=w[i])wrong++;
        if(x!=y)cout<<"DIFFERENT"<<endl;
        else if(wrong==1)cout<<"CLOSE"<<endl;
        else cout<<"DIFFERENT"<<endl;
    }
//////////////////////////////////////////////////////
return 0;}



Measured memory_bytes: 3084
function Main(input) {
    const W = parseInt(input[0])
    const H = parseInt(input[1])
    const X = parseInt(input[2])
    const Y = parseInt(input[3])

    var isDup = "0";
    if(X == W/2.0 && Y == H/2.0){
        isDup = "1";
    }

    console.log("" + W*H / 2.0 + " " + isDup);
}

// 1行入力の場合
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

// 改行で分割
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n/));

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 21064
package main

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

func binarySearch(list []int, target int, l int, u int) int {
	if u - l <= 1 {
		if list[u] == target {
			return u
		} else {
			return -1
		}
	}

	m := (u + l) / 2
	if target <= list[m] {
		return binarySearch(list, target, l, m)
	} else {
		return binarySearch(list, target, m, u)
	}
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	s := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		s[i], _ = strconv.Atoi(sc.Text())
	}

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())
	
	cnt := 0
	for i := 0; i < q; i++ {
		sc.Scan()
		target, _ := strconv.Atoi(sc.Text())
		
		result := binarySearch(s, target, -1, n)
		if result >= 0 {
			cnt++
		}
	}
	fmt.Println(cnt)
}



Measured memory_bytes: 2668
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  int R,L;
  cin >> A >> B >> C >> D; 

  L = A + B;
  R = C + D;
  
  if ( L > R ){
    cout << "Left" << endl;
  } else if ( L < R ){
	cout << "Right" << endl;
  } else {
    cout << "Balanced" << endl;    
  }
}

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

int money(int n){
	int m = 100000;
	for(int i=0; i<n; i++){
		m *= 1.05;
		if(m % 1000 != 0){
			m += 1000 - m%1000;
		}
	}
	return m;
}

int main(){
	int n;
	while(cin >> n){
		cout << money(n) << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll a,b;cin>>a>>b;
    cout<<a*b-(a+b-1)<<"\n";
}


Measured memory_bytes: 3640
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().solve();
	}

	private void solve() throws IOException {
		try {
			solveA();
			//			 solveB();
			//			 solveC();
			//			 solveD();
			//			 solveE();
			//			 solveF();
		} finally {
			if (in != null) {
				in.close();
			}
			if (out != null) {
				out.flush();
				out.close();
			}
		}

	}

	private void solveA() {
		int n = nextInt();
		int a = nextInt();
		int b = nextInt();

		out.println(n * a > b ? b : n * a);
	}

	private void solveB() {
		int n = nextInt();

		out.println("");
	}

	private void solveC() {
		int n = nextInt();

		out.println("");
	}

	private void solveD() {
		int n = nextInt();

		out.println("");
	}

	private void solveE() {
		int n = nextInt();

		out.println("");
	}

	private void solveF() {
		int n = nextInt();

		out.println("");
	}

	private final PrintWriter out = new PrintWriter(System.out);
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}

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

int main() {
        int S = 0;
        rep(i, 4) {
                int in;
                cin >> in;
                S += in;
        }

        int s = S%60;
        int m = S/60;

        cout << m << endl << s << endl;
        return 0;
}


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<int,int> p;

int n;
string s[100];
map<char, int> canuse, used;
vector <int> v(26,0);

int main(){
  cin >> n;
  cin >>  s[0];
  rep(i,0,s[0].size()) v[s[0][i]-'a']++;
  rep(i,1,n){
    map<char, int> temp;
    cin >> s[i];
    rep(j,0,s[i].size())temp[s[i][j]]++;
    rep(j,0,26){
      v[j] = min(v[j], temp[j+'a']);
    }
  }
  string ans="";
  for(int i=0;i<26;i++){
    int a = v[i];
    if(a!=0){
      rep(j,0,a)ans +=(i+'a');
    }
  }
  cout << ans <<endl;

}


Measured memory_bytes: 256
import numpy as np

def main():
    """
    N, M, C = np.array([int(x) for x in input().split(' ')])
    b_arr = np.array([int(x) for x in input().split(' ')])
    a_mat = np.zeros((N,M))
    """
    N ,M, C = map(int, input().split())
    b_arr = np.array(list(map(int, input().split())))
    a_mat = np.array( [ list(map(int, input().split())) for i in range(N) ] )
    
   # for i in range(N):
    #    a_mat[i] = np.array(list(map(int, input().split())))
        #a_mat[i] = np.array([int(x) for x in input().split(' ')])

        #print ( len(list( np.where( a_mat.dot(b_arr)> -C ) )[0]) )
    print ( np.array(np.where(a_mat.dot(b_arr) > -C)).shape[1] )

if __name__ == '__main__':
    main()


Measured memory_bytes: 12356
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

#define debug(x) cout << #x << ": " << x << endl;
#define ll long long
#define mod 1000000007

int N, K, H[400];
ll dp[400][400];
// dp[i][j] =
// for k = i+1 to N min of
//   dp[k][j-1]+max(0, H[i]-H[k])
// ans = min(dp[i][N-K]) over i

int main() {
  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);

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

  for(int j = 1;j <= N;j++) {
    for(int i = N;i > 0;i--) {
      if(j == 1) {
        dp[i][j] = H[i];
        continue;
      }
      dp[i][j] = 1e12;
      for(int k = i+1;k <= N;k++) {
        dp[i][j] = min(dp[i][j], dp[k][j-1]+max(0, H[i]-H[k]));
      }
    }
  }

  ll ans = 1e12;
  for(int i = 1;i <= N;i++) {
    ans = min(ans, dp[i][N-K]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1152
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };
	static final int INF = Integer.MAX_VALUE / 3;
	static final long LINF = Long.MAX_VALUE / 3;

	static int n, k;
	static List<Integer> to[];
	
	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		n = fs.nextInt(); k = fs.nextInt();
		to = new ArrayList[n];
		for(int i=0;i<n;i++) to[i] = new ArrayList<>();
		for(int i=0;i<n-1;i++) {
			int a = fs.nextInt()-1, b = fs.nextInt()-1;
			to[a].add(b);
			to[b].add(a);
		}
		long ans = dfs(0, -1, k, 0);
		System.out.println(ans);
	}
	static long dfs(int v, int p, int c, int d) {
		long res = c;
		if(d == 1) res++;
		int nxc = k - 2;
		for(int nx:to[v]) {
			if(nx == p)continue;
			res = mul(res, dfs(nx, v, nxc--, d+1));
		}
		return res;
	}
	
	static long plus(long x, long y) {
		return (x + y) % mod;
	}
	
	static long sub(long x, long y) {
		return (x - y + mod) % mod;
	}
	
	static long mul(long x, long y) {
		return (x * y)%mod;
	}
	
	static long div(long x, long y) {
		return x * modpow(y, mod - 2) % mod;
	}
	
	static long modpow(long x, long y) {
		if(y == 0) return 1;
		if(y%2==1) return (x * modpow(x, y-1))%mod;
		return modpow(x, y/2) * modpow(x, y/2) % mod;	
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

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

int main() {
	int i;
	string s;
	cin >> s;
	for (i = 0; i <= 20; i++) {
		if (s[i] == 0)
			break;
	}
	for (i--; i >= 0; i--) {
		cout << s[i];
	}
	cout << endl;
	return 0;
}


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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

vt<pii> adj{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void solve(int tc) {
    int h, w;
    cin >> h >> w;
    int ch, cw, dh, dw;
    cin >> ch >> cw >> dh >> dw;
    ch--, cw--, dh--, dw--;
    vt<string> s(h);
    for (auto &i : s) cin >> i;

    vt<vt<bool>> vis(h, vt<bool>(w));
    queue<pii> q;
    vt<pii> curVis;
    vis[ch][cw] = true;
    q.emplace(ch, cw);
    for (int r = 0;; r++) {
        while (!q.empty()) {
            pii cur = q.front();
            q.pop();

            if (cur.fi == dh && cur.se == dw) {
                cout << r;
                return;
            }

            curVis.push_back(cur);

            for (pii &i : adj) {
                int x = cur.fi + i.fi, y = cur.se + i.se;
                if (x < 0 || y < 0 || x >= h || y >= w) continue;
                if (vis[x][y] || s[x][y] == '#') continue;
                vis[x][y] = true;
                q.emplace(x, y);
            }
        }

        if (curVis.empty()) {
            cout << -1;
            return;
        }

        for (pii cur : curVis) {
            for (int i = -2; i <= 2; i++) for (int j = -2; j <= 2; j++) {
                int x = cur.fi + i, y = cur.se + j;
                if (x < 0 || y < 0 || x >= h || y >= w) continue;
                if (vis[x][y] || s[x][y] == '#') continue;
                vis[x][y] = true;
                q.emplace(x, y);
            }
        }
        curVis.clear();
    }
}

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

    int tcs = 1;
    for (int tc = 1; tc <= tcs; tc++) solve(tc);
}


Measured memory_bytes: 5060
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n)
using namespace std;
int main()
{
	MaRiaMa;
	set<char> c;
	int k = 0;
	string s;
	set<char> p;
	cin >> s;
	for (int i = 0; i < 26; i++)
	{
		c.emplace(char(97+i));
	}
	for (int i = 0; i < s.size(); i++)
	{
		p.emplace(s[i]);
	}
	auto l = c.begin();
	for (auto it = p.begin(); l != c.end(); it++)
	{
		if (it != p.end())
		{
			if (*l != *it)
			{
				cout << *l;
				return 0;
			}
			l++;
		}
		else
		{
			cout << *l;
			return 0;
		}
	}
	cout << "None";
}





Measured memory_bytes: 3776
import java.io.PrintWriter

val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val k = nextInt()
    println(when (k % 2) {
        0 -> (k / 2)*(k / 2)
        else -> (k / 2)*(k / 2 + 1)
    })
}

fun next() = readLine()!!
fun nextInt() = next().toInt()

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 33660
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string s;
deque<char>q;
cin>>s;
for (char c:s)
q.push_back(c);
bool k =false;

int Q;
cin>>Q;
for (int i=0;i<Q;i++)
{
int t;
cin>>t;
if(t==1)k=!k;
else
{
    int f;char c;
    cin>>f;cin>>c;
    if(k)f=3-f;
    if(f==1)q.push_front(c);
    else q.push_back(c); 
}
}
if(k)reverse(q.begin(),q.end());
string ans ;
for (char c:q)ans +=c;
cout <<ans;
}

Measured memory_bytes: 1412
#include<stdio.h>//1-0167
int main(void)
{
	int data[100+1],i,j,n,temp,cnt;
	scanf("%d",&n);
	while(n!=0) {
		cnt=0;
		for(i=0;i<n;i++) {
		scanf("%d",&data[i]);
		}
		for(i=0;i<n-1;i++) {
			for(j=n-1;j>i;j--) {
				if(data[j]<data[j-1]) {
					temp=data[j];
					data[j]=data[j-1];
					data[j-1]=temp;
					cnt++;
				}
			}
		}
		printf("%d\n",cnt);
	scanf("%d",&n);
	}
	return 0;
}

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

#define      pb    push_back
#define      ff    first
#define      ss    second
#define      ll    long long int
#define      endl  "\n"
#define      FASTIO        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const ll big = 10e12 + 11 ;


int  main (  ) {

    FASTIO ;

    cout << fixed << setprecision( 12 ) ;

    double n ;
    cin >> n ;

    double  ans ;

    ans = n / 3.0 ;

    ans = ans * ans * ans ;

    cout <<  ans ;

    return  0 ;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define Mx(a , b) ((a) > (b) ? (a) : (b))
#define Mn(a , b) ((a) < (b) ? (a) : (b))

const double EPS = 1e-10;
const int INF = 2147483647;

bool b[4];
char s[1010];

int main(){
	scanf("%s" , s);
	for(int i = 0 ; s[i] != 0 ; ++i){
		if(s[i] == 'N'){
			b[0] = 1;
		} else if(s[i] == 'S'){
			b[1] = 1;
		} else if(s[i] == 'W'){
			b[2] = 1;
		} else {
			b[3] = 1;
		}
	}
	printf("%s\n" , !((b[0] ^ b[1]) || (b[2] ^ b[3])) ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);   	
	
	string s, t;
	cin >> s >> t;
	int ans = 0;

	for(int i=0; i<s.size(); i++) {
		if(s[i] != t[i]){
			ans++;
		}
	}

	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3788