akhauriyash/Code-Regression huggingface dataset:
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template < typename T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    int len = comma - names;
    for (int i = 0; i < len; ++i) {
        cout << names[i];
    }
    cout <<  " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;

#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const ll LINF = LLONG_MAX, base = 1e9, MOD = 1e9 + 7, N = 1e5 + 10, M = 1e3 + 10;
const int INF = INT_MAX;
const db PI = acos(-1);

ll d[N];
bool vis[N];
vector < pii > g[N];

void test();
void bfs(int s);

int main() {
    fast_io();
    test();
    return 0;
}

void test() {
    int n;
    cin >> n;
    for (int i = 1, x, y, w; i < n; ++i) {
        cin >> x >> y >> w;
        g[x].pb({y, w});
        g[y].pb({x, w});
    }
    bfs(1);
    for (int i = 1; i <= n; ++i) {
        cout << (d[i] & 1) << "\n";
    }
}

void bfs(int s) {
    queue < int > q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto &x: g[v]) {
            if (!vis[x.F]) {
                vis[x.F] = true;
                q.push(x.F);
                d[x.F] = d[v] + x.S;
            }
        }
    }
}


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

int n;
vector<int> a;
vector<vector<int>> G;
vector<int> ans;

void go( int v, int p, vector<int>& w ) {
    int idx=-1,temp=-1;
    if ( w.size()==0||a[v]>w.back() ) {
        w.push_back(a[v]);
    } else {
        idx=lower_bound(w.begin(),w.end(),a[v])-w.begin();
        temp=w[idx];
        w[idx]=a[v];
    }
    ans[v]=w.size();
    for ( int u:G[v] ) {
        if ( u==p ) continue;
        go(u,v,w);
    }
    if ( idx==-1 ) {
        w.pop_back();
    } else {
        w[idx]=temp;
    }
}

int main() {
    cin >> n;
    a.resize(n);
    for ( int i=0; i<n; i++ ) {
        cin >> a[i];
    }
    G.resize(n);
    for ( int i=0; i<n-1; i++ ) {
        int u,v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ans.resize(n);
    vector<int> v;
    go(0,-1,v);
    for ( int i=0; i<n; i++ ) {
        cout << ans[i] << '\n';
    }
    return 0;
}


Measured memory_bytes: 29940
#include "bits/stdc++.h"
using namespace std;
const int N = 505;
const int NN = N * N;
int n;
pair < int , int > x[N];
int arr[NN];
int cur;
int idx;
int main(){
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++i){
        scanf("%d" , &x[i].first);
        x[i].second = i;
    }
    sort(x + 1 , x + 1 + n);
    cur = 1;
    for(int i = 1 ; i <= n ; ++i){
        int val = x[i].first;
        int who = x[i].second;
        for(int j = 1 ; j < who ; ++j){
            while(arr[cur]){
                ++cur;
            }
            arr[cur] = who;
        }
        if(arr[val]){
            printf("No\n");
            return 0;
        }
        arr[val] = who;
    }
    cur = n * n;
    for(int i = n ; i >= 1 ; --i){
        int val = x[i].first;
        int who = x[i].second;
        for(int j = 0 ; j < n - who ; ++j){
            while(arr[cur]){
                --cur;
            }
            arr[cur] = who;
        }
        if(cur < val){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    for(int i = 1 ; i <= n * n ; ++i){
        printf("%d%c" , arr[i] , " \n"[i == n * n]);
    }
}

Measured memory_bytes: 2176
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()]+[0] for i in range(H)] + [[0] * (W+1)]
for i in range(H):
    for j in range(W):
        if X[i][j] == 1 and X[i][j-1] == X[i-1][j] == X[i][j+1] == X[i+1][j] == 0:
            print("No")
            exit()
print("Yes")


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

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

#define pb push_back
#define in ,
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int n;
  while(cin >> n) {
    if(!n) return 0;
    int a[10] = {}, b;
    rep(i, 0, n) cin >> b, a[b]++;
    rep(i, 0, 10) {
      rep(j, 0, a[i]) {
        cout << '*';
      }
      if(!a[i]) cout << '-';
      cout << endl;
    }
  }
}

Measured memory_bytes: 3104
from collections import Counter
from collections import defaultdict

d = defaultdict(int)

N = int(input())
SS = [0]*N
for _ in range(N):
    SS[_] = input()

for S in SS:
    o = [0]*26
    for s in S:
        o[ord(s)-97] += 1
    d[''.join(map(str,o))] += 1

ans = 0
for v in d.values():
    ans += v * (v-1) // 2

print(ans)


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

int main(){
    vector<int> a(3), b(3);
    vector<vector<int> > c(3, vector<int>(3, 0));
    bool is_correct;

    for(int i = 0; i < 3; i++){

        for(int j = 0; j < 3; j++){
            cin >> c.at(i).at(j);
        }

    }

    for(a.at(0) = 0; a.at(0) <= c.at(0).at(0); a.at(0)++){
        is_correct = true;
        b.at(0) = c.at(0).at(0) - a.at(0);
        b.at(1) = c.at(0).at(1) - a.at(0);
        b.at(2) = c.at(0).at(2) - a.at(0);
        a.at(1) = c.at(1).at(0) - b.at(0);
        a.at(2) = c.at(2).at(0) - b.at(0);

        for(int i = 1; i < 3; i++){

            for(int j = 1; j < 3; j++){
                if(c.at(i).at(j) != a.at(i) + b.at(j)){
                    is_correct = false;
                    break;
                }

            }

            if(!is_correct) break;
        }
        if(is_correct) break;
    }
    if(is_correct) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3596
# 2019/05/25
# AtCoder Beginner Contest 127 - D

# Import
from operator import itemgetter

# Input
n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()

bcl = list()
for i in range(m):
    b, c = map(int,input().split())
    wl = [b, c]
    bcl.append(wl)

bcl.sort(key=itemgetter(1), reverse=True)

aidx = 0
midx = 0
while(midx < m and aidx < n):
    if a[aidx] < bcl[midx][1]:
        a[aidx] = bcl[midx][1]
        bcl[midx][0] -= 1
        if bcl[midx][0] <= 0:
            midx += 1
            
    aidx += 1

# Sum
ans = 0
for i in range(n):
    ans += a[i]

# Output
print(ans)


Measured memory_bytes: 25672
N = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)

c = a.zip(b).map { |f, s| f - s }

asum = 0
bsum = 0
a.size.times do |i|
  c = b[i] - a[i]
  if c > 0
    asum += c / 2
    if c % 2 == 1
      bsum += 1
      asum += 1
    end
  else
    bsum += -c
  end
end


# puts "#{asum} #{bsum}"
if asum >= bsum
  puts "Yes"
else
  puts "No"
end


Measured memory_bytes: 5616
s = input()
a = ['AKIHABARA','AKIHABAR','AKIHABRA','AKIHBARA','KIBAHARA',
     'AKIHABR','AKIHBAR','KIHABAR','KIHABRA','AKIHBRA','KIHBARA',
     'AKIHBR','KIHABR','KIHBAR','KIHBRA','KIHBR']
if s in a:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 2940
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
 
int main(){
  ll n,x;
  cin >> n >> x;
  ll a[n];
  ll sum;ll result=0;
  for ( int i = 0 ; i < n ;i++){
  cin >> a[i];
  }
  if ( a[0] > x ) {
		result += a[0] - x;
		a[0] = x;
	}
	sum = a[0];
	for ( int i = 1 ; i < n ; i++){
		sum += a[i];
		if (sum > x){
			result += sum-x;
			a[i] -= sum-x;
			sum = x;
		}
		sum -= a[i-1];
	}
	cout << result;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
// const ll MOD=998244353;

int main(){
  int N,K; cin>>N>>K; K--;
  string S; cin>>S;
  S[K]=tolower(S[K]);
  cout<<S<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
inline char gc(){
	static char buf[1<<16],*S,*T;
	if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
	return *S++;
}
inline int read(){
	int x=0,f=1;char ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
	return x*f;
}
inline int abs(int x){return x<0?-x:x;}
int main(){
//	freopen("calculator.in","r",stdin);
	//freopen("calculator.out","w",stdout);
	int x=read(),y=read();
	if(abs(x)<abs(y)) printf("%d\n",abs(y)-abs(x)+(x<0)+(y<0));
	else printf("%d\n",abs(x)-abs(y)+(x>0)+(y>0));
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
   int w,h,x,y,r;
   scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);
   if(0<=x-r && 0<=y-r && x+r<=w && y+r<=h)
      printf("Yes\n");
   else
      printf("No\n");
   return 0;
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long int
#define INF 1000000007
#define llINF 1000000000000000007
#define v(i) vector<i>
#define vv(i) vector<vector<i>>
// cin.eof() 入力個数の問題
// int num = atoi(string.c_str()); 文字列の整数変換
int keta(ll n){int ans=0;while(n>0){n /= 10; ans++;}return ans;}
ll _pow(ll a,ll b){ll ans = 1;rep(i,b){ ans *= a;}return ans;}

int main() {
ll n; cin>>n;
ll ans;
ans = n*(n-1)/2;
cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>


using std::cout;
using std::cin;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


ll gcd(ll a, ll b) {
    while (b != 0) {
        auto tmp = a;
        a = b;
        b = tmp % a;
    }
    return a;
}

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

int isPrime(int a) {
    for (int i = 2; i * i <= a; ++i) {
        if (a % i == 0) {
            return 0;
        }
    }
    return 1;
}





void oneCase () {
    int n, m;
    cin >> n >> m;
    vector<int> a = {0, 1, 3, 1,2, 1,2,1,1,2, 1,1,2,1};
    if (a[n] == a[m]) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    cout << "\n";
}




int main() {
    int t = 1;
//    cin >> t;
    while (t > 0) {
        oneCase();
        --t;
    }

    return 0;
}

Measured memory_bytes: 256
use std::io;
use std::str::FromStr;

fn input_tuple() -> (u64, u64, u64, u64, u64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1], vec[2], vec[3], vec[4])
}

fn input_vec() -> Vec<u64> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn main() {
    let (x, y, a, b, c) = input_tuple();
    let mut p_vec = input_vec();
    let mut q_vec = input_vec();
    let mut r_vec = input_vec();

    p_vec.sort_by(|a, b| b.cmp(&a));
    q_vec.sort_by(|a, b| b.cmp(&a));
    r_vec.sort_by(|a, b| b.cmp(&a));

    // println!("{:?}", p_vec);

    let mut ans: Vec<u64> = Vec::new();

    for i in 0..x as usize {
        ans.push(p_vec[i]);
    }

    for i in 0..y as usize {        
        ans.push(q_vec[i]);
    }
    ans.sort();
    // println!("{:?}", ans);

    for i in 0..c as usize {
        if r_vec[i] > ans[i] {
            ans[i] = r_vec[i];
        } else {
            break;
        }
    }

    let mut sum = 0;
    for a in ans {
        sum += a;
    }
    println!("{}", sum);
}


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

int n, t, a[3005], b[3005], dp[3005][3005][5];

int solve(int pos, int k, int flag){
    if(k >= t) return -1e9;
    if(pos >= n) return 0;
    if(dp[pos][k][flag] != -1) return dp[pos][k][flag];
    int r1 = solve(pos+1, k, flag);
    int r2 = solve(pos+1, k+a[pos], flag) + b[pos];
    int r3 = -1e9;
    if(flag == 0) r3 = solve(pos+1, k, 1) + b[pos];
    return dp[pos][k][flag] = max(r1, max(r2,r3));
}

int main(){
    memset(dp, -1, sizeof dp);
    cin >> n >> t;
    for(int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    cout << solve(0,0,0) << endl;
	return 0;
}

Measured memory_bytes: 176896
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]

ans="IMPOSSIBLE"
li=[0]*N

for ab in AB:
    if 1 in ab:
        for i in ab:
            if i!=1:
                if li[i-1]==-1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=1
    elif N in ab:
        for i in ab:
            if i!=N:
                if li[i-1]==1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=-1
print(ans)

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

typedef long long ll;
ll n, i, mn;
ll f(ll p) {
	ll s = 0;
	while (p > 0) {
		s++;
		p /= 10;
	}
	return s;
}
int main()
{
	cin >> n;
	for (i = 1; i * i <= n; i++) {
		if (n % i == 0) mn = f(n / i);
	}
	cout << mn;
    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f=true){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f=true){cout<<(f?"YES":"NO")<<endl;}
#define ANS(a) cout<<a<<endl

struct restaurant {
    int n;
    string name;
    int point;
};

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int N; cin >> N;
    vector<string> S(N);
    vector<int> P(N);
    rep(i,N) { cin >> S[i] >> P[i]; }

    vector<int> res(N);
    iota(ALL(res), 1);
    sort(ALL(res), [&](int x, int y) {
        if (S[x-1]!=S[y-1])
            return S[x-1]<S[y-1];
        return P[x-1]>P[y-1];
    });

    for (auto r: res)
        cout << r << endl;
}


Measured memory_bytes: 256
/*
        @uthor: Kashish Gilhotra
        user: CodeChef, CodeForces, HackerEarth, HackerRank, SPOJ: kashish001
*/

#include <bits/stdc++.h>
using namespace std;
  
#define int long long int 
typedef vector<int> vi;
typedef vector<pair<int, int>> vpi;
typedef vector<vi> vvi;
const int mod = 1e9 + 7; 

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define debug(...) cerr << "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " 
#define EB emplace_back
#define ALL(v) v.begin(), v.end() 
#define size(v) (int)v.size() 
#define endl "\n"
#define UMO unordered_map
#define USO unordered_set
#define TC int t; cin >> t; while (t--) 

void Panda() {
    int n;
    cin >> n;
    cout << (!n) << endl; 
}
  
int32_t main() {
 
    FAST;

    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout); 
    
    Panda();

    return 0; 
} 

Measured memory_bytes: 3572
#include<iostream>
using namespace std;
int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b != c) {
    cout << "Yes" << endl;
  }else if (a == c && b !=c){
   	cout << "Yes" << endl; 
  }else if (a != b && b == c){
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;; 
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
        int n = sc.nextInt();
        int ans = 0;
        for (int a = 0; a < 10; a++){
            for (int b = 0; b < 10; b++){
                for (int c = 0; c < 10; c++){
                    for (int d = 0; d < 10; d++){
                        if (a + b + c + d == n){
                            ans++;
                        }
                    }
                }
            }
        }
    System.out.println(ans);   
    }
    }
    
}

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

#define double long double
#define int long long
#define vec vector
#define pb push_back
#define unset unordered_set
#define ii pair<int, int>
#define X first
#define Y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define bitcount(n) __builtin_popcountll(n)
template <typename T,typename U>
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
  return {l.first+r.first,l.second+r.second};
} 
typedef void (*callback_function)(void); // type for conciseness
const long long ZERO = 0LL;
const long long INF64 = 1e18;
const int INF32 = 1e9;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0L);
const double EPS = static_cast<double>(1e-9);
typedef long long ll;

inline int Pow(int a, int k) {
  int s = 1; 
  for(; k; k >>= 1) {
    k & 1 ? s = 1LL * s * a % MOD : 0;
    a = 1LL * a * a % MOD;
  }
  return s;
}

const int N = 1e6 + 7;

void input() {
  //freopen("??.in", "r", stdin);
  //freopen("??.out", "w", stdout);
}

void preprocess() {
}

void debug() {
  //  44gg
  if (true) {

  }
}

int cnt[256];

void solve() {
  preprocess();
  // 50gg
  int n;
  cin >> n;
  string s;
  cin >> s;
  for (char &ch : s) {cnt[ch]++;}
  int res = 1;
  FOR(i, 0, n) {res = (res * 2) % MOD;}
  res = (res + MOD - 1) % MOD;
  //cerr << "res = " << res << endl;
  int d = 1;
  int a[n + 1];
  a[0] = 1;
  FORE(i, 1, n) {a[i] = (a[i - 1] * 2) % MOD;}
  FORE(i, 'a', 'z') {
    if (cnt[i] > 1) {
      int cur = a[cnt[i]];
      cur = (cur + MOD * 2 - cnt[i] - 1) % MOD;
      int rem = a[n- cnt[i]];
      int sub = ((((cur % MOD) * (rem % MOD)) % MOD) * d) % MOD;
      res = (res + MOD - sub) % MOD;
      n -= cnt[i];
      d = (d * (cnt[i] + 1)) % MOD;
      //cerr << (char)(i) << " " << cnt[i] << " " <<  cur << " " << rem 
      //  << " " << d << " " << sub << endl;
    }
  }
  cout << res << endl;
  //debug();
  // read the question correctly (is y a vowel?)
  // look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)
}

void output() {

}

#undef int
int main() {
#define int long long
  ios_base::sync_with_stdio(false);
  cin.tie();
  //auto beginProgram = chrono::steady_clock::now();

  //int t; cin >> t;
  //while (t--) 
  {
    input();
    solve();
    output();
  }

  //auto endProgram = chrono::steady_clock::now();

  return 0;
}



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

using namespace std;

int main()
{
    char str[100];
    cin>>str;
    for(int i=0;i<4;i++)
    {
        cout<<str[i];
    }
    cout<<" ";
    for(int i=4;i<12;i++)
    {
        cout<<str[i];
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld double
long double PI =3.14159265;
using ll = long long;

const ll modo=7;
const ll ms=1e6+5;
const ll inf=-1e17;


vector<int> vv[ms];
int ar[ms]={0};

void go(int v)
{
    ar[v]=1;
    for(int ii:vv[v])
    {
        if(!ar[ii])
        {
            go(ii);
        }
    }
}

int main()
{
    idfc;
    int n,m;
    cin>>n>>m;
    int u,v;
    int i;

    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        vv[u].pb(v);
        vv[v].pb(u);
    }

    int ans=0;

    for(i=1;i<=n;i++)
    {
        if(ar[i]==0)
        {
            go(i);
            ans++;
        }
    }
    ans--;
    cout<<ans;



    return 0;
}


Measured memory_bytes: 31116
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int cnt;
int m,d;
int main(){
    cin>>m>>d;
    for(int i=2;i<=d/10;i++)
        for(int j=2;j<=9;j++){
            if(i*10+j>d) continue;
            if(i*j>=1 && i*j<=m) cnt++;
        }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n,q;
long long s,t;
long long d[200010];
int main(){
	cin>>n>>q>>s>>t;
	int bef,a,b,c;cin>>bef;
	long long ANS=0;
	for(int i=0;i<n;i++){
		cin>>a;d[i]=a-bef;
		bef=a;
		if(d[i]<0)ANS-=t*d[i];
		else ANS-=s*d[i];
	}
	d[n]=0;
	//cout<<"#"<<ANS<<endl;
	for(int u=0;u<q;u++){
		cin>>a>>b>>c;a--;
		long long cnt=0;
		
		if(d[a]<0)cnt+=t*d[a];
		else cnt+=s*d[a];
		if(d[b]<0)cnt+=t*d[b];
		else cnt+=s*d[b];
		//cout<<"$"<<cnt<<endl;
		d[a]+=c,d[b]-=c;d[n]=0;
		
		if(d[a]<0)cnt-=t*d[a];
		else cnt-=s*d[a];
		if(d[b]<0)cnt-=t*d[b];
		else cnt-=s*d[b];
		
		ANS+=cnt;
		cout<<ANS<<endl;
	}
	return 0;
}

Measured memory_bytes: 4660
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a=0,b=0,k=0;
    cin>>k;
    cin>>a>>b;
    bool flag=false;
    for(int i=a;i<=b;++i)
    {
        if(i%k==0)
        {
            flag=true;
            break;
        }
    }
    if(flag)
        cout<<"OK";
    else
        cout<<"NG";
    cout<<endl;
}

Measured memory_bytes: 3640
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const vector<ll> materials = {3, 5, 7};
vector<ll> nums753;

ll map_num(vector<int> indexes) {
  ll result = 0;
  for (int i = 0; i < indexes.size(); i++) {
    result += materials[indexes[i]] * powl(10, i);
  }
  return result;
}

// 753条件を満たすか
bool check_indexes(vector<int> indexes) {
  bool has3 = false;
  bool has5 = false;
  bool has7 = false;
  for (int index : indexes) {
    switch (index) {
      case 0:
        has3 = true;
        break;
      case 1:
        has5 = true;
        break;
      case 2:
        has7 = true;
        break;
    }
  }
  return has3 && has5 && has7;
}

void _make(vector<int> indexes, int cur) {
  while (true) {
    if (check_indexes(indexes)) {
      ll num = map_num(indexes);
      nums753.push_back(num);
    }
    indexes[cur]++;

    // 繰り上げ
    for (int i = 0; i < indexes.size(); i++) {
      if (indexes[i] > materials.size() - 1) {
        // 繰り上げ発生時の処理
        indexes[i] = 0;
        if (i + 1 > indexes.size() - 1) {
          return;
        }
        indexes[i + 1] += 1;
      } else {
        break;
      }
    }
  }
}

// N桁のときの753数を作る
void make(int N) {
  vector<int> indexes(N, 0);
  _make(indexes, 0);
}

int main() {
  ll N;
  cin >> N;

  for (int i = 3; i < 10; i++) {
    make(i);
  }

  ll count = 0;
  for (ll num : nums753) {
    if (num <= N) {
      count++;
    } else {
      break;
    }
  }
  cout << count << endl;

  // for (ll num : nums753) cout << num << endl;
  // cout << nums753.size() << endl;
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include <algorithm>
#include<cstdlib>
#include<cmath>
#include<deque>
#include <numeric>
#include<valarray>
typedef unsigned long long ull;
typedef  long long ll;

int main() {
	int N;

	std::cin >> N ;

	std::vector < ll > ax;
	ax.reserve(1000);
	int cntsize = 1;
	ll tmpinx;
	std::cin >> tmpinx;
	ax.push_back(tmpinx);


	for (int i = 1; i < N; i++) 
	{
		ll tmpin;
		std::cin >> tmpin;

		if (ax[cntsize - 1] >= tmpin)
		{
			ax.push_back(tmpin);
			cntsize++;
			continue;
		}
		for (int cnti = 0; cnti < cntsize; cnti++)
		{
			if (ax[cnti] < tmpin)
			{
				ax[cnti] = tmpin;
				break;
			}
		}
	}

	std::cout << ax.size() << std::endl;

	return 0;
}


Measured memory_bytes: 1424
#include<bits/stdc++.h>
#define REP(i,x) for(int i=0,i##_len=(x);i<i##_len;++i)
#define rep(i,a,b) for(int i=(a),i##_len(b);i<i##_len;++i)
#define All(x) begin(x),end(x)
#define rAll(x) rbegin(x),rend(x)
using namespace std;
using ll = long long;

int main(){
    int L;cin>>L;
    //a+b+c=L,a*b*c=a*b*(L-a-b)=L*a*b
    double a=L/3.0;
    printf("%.16f",a*a*a);
}

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

char x[200010],y[200010];
int main()
{
	scanf("%s",x+1);
	scanf("%s",y+1);
	int a = strlen(x+1);
	int count = 0;
	for(int i=1;i<=a;i++) if(x[i]!=y[i]) count++;
	printf("%d",count);
}

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

int main() {
  int a,s;
  while(true){
      cin >> a >> s;
      if(a == 0 && s == 0)break;
      for(int i = 0;i < a;i++){
          for(int j = 0;j < s;j++){
              cout << "#";
          }
          cout << endl;
          
      }
      cout << endl;
  }
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}n[200001];
bool cmp(node a,node b){
	return a.y<b.y;
}
int main(){
	int a,i,w=0;
	cin>>a;
	for(i=1;i<=a;i++)scanf("%d%d",&n[i].x,&n[i].y);
	sort(n+1,n+a+1,cmp);
	for(i=1;i<=a;i++){
		w+=n[i].x;
		if(w>n[i].y){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

Measured memory_bytes: 1792
import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line1 = br.readLine();
		int n = Integer.parseInt(line1);
		int[] a = new int[n];
		String line2 = br.readLine();
		String[] str = line2.split(" ");
		for (int i = 0; i < n ; i++){
			a[i] = Integer.parseInt(str[i]);
		}
		int max = a[0];
		int min = a[0];
		long sum = (long) a[0];
		for (int i = 1; i < n ; i++){
			max = Math.max(max,a[i]);
			min = Math.min(min,a[i]);
			sum += (long) a[i];
		}
		System.out.println(min + " " + max +" "+ sum);
	}
}

Measured memory_bytes: 28632
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class BIT:
  # [1,n]に値が入ってる1-indexであることに注意
  def __init__(self,size):
    self.data = [0]*(size+1)
    self.size = size
  
  # [1,n]までの総和
  def sum(self,n):
    res = 0
    while n > 0:
      res += self.data[n]
      n -= n & -n
    return res
  
  def add(self,k,x):
    while k < self.size + 1:
      self.data[k] += x
      k += k & -k

n,q = map(int,input().split())
bit = BIT(n)
for _ in range(q):
  typo,x,y = map(int,input().split())
  if  typo == 0:
    bit.add(x,y)
  else:
    print(bit.sum(y)-bit.sum(x-1))




Measured memory_bytes: 8560
a,b,k=map(int, input().split())
for i in range(k):
    if i%2==0:
        if a%2==1:
            a-=1
        b+=a//2
        a//=2
    else:
        if b%2==1:
            b-=1
        a+=b//2
        b//=2
print(a,b)

Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<time.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<list>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double pi = acos(-1);
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define pb(x) push_back(x)
int read(){
	int rt=0,fl=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0';ch=getchar();}
	return rt*fl;
}
ll readl(){
	ll rt=0,fl=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0';ch=getchar();}
	return rt*fl;
}
void write(ll num){
	if(!num)putchar('0');
	static char str[50];
	static int cnt=0;
	while(num){str[++cnt]=num%10+'0';num/=10;}
	while(cnt){putchar(str[cnt--]);}
}
int n,k;
struct ele{
	int x,y,tag;
	bool obey; 
};
ele data[200000];
int f[2000][3],g[2000][3];
char str[1000];
vector<int> ggg[2000];
int main(){
//	int mx,my;
//	mx = my = 0x7fffffff;
	int ans=0,fal=0;
	n=read();k=read();
	for(int i=1;i<=n;i++){
		int a=read(),b=read();
		//c=read();
		a++;b++;
		scanf("%s",str);
		data[i].x=a;
		data[i].y=b;
		data[i].tag=str[0]=='B';
	//	f[a%k][data[i].tag] ++;
	//	g[b%k][data[i].tag] ++;
		int color = a/k + b/k;
		color %= 2;
		ans += (data[i].tag == color);
		color = (data[i].tag == color);
		f[a%k][color]++;
		g[b%k][color]++;
		ggg[b%k].pb(i);
		data[i].obey = color;
//		mx = min(mx,a);
//		my = min(my,b);
	//	cout<<i<<" "<<color<<endl;
	}
	fal = n-ans;
	int pre = ans;
//	cout<<ans<<" "<<fal<<endl;
	for(int i=0;i<k;i++){
		int now_ans = pre;
		for(int j=0;j<k;j++){
			now_ans -= f[j][1];
			now_ans += f[j][0];
			ans = max(ans,now_ans);
			fal = max(fal,n-now_ans);
		}
		for(int j=0;j<(int)ggg[i].size();j++){
			int a = data[ggg[i][j]].x;
		//	int b = data[ggg[i][j]].y-i;
		//	int color = a/k + b/k;
		//	color %= 2;
		int color = data[ggg[i][j]].obey;//(data[i].tag == color);
			f[a%k][color]--;
			f[a%k][color^1]++;
			if(color==1){
				pre --;
			}else{
				pre ++;
			}
			data[ggg[i][j]].obey ^= 1;
			//g[b%k][color]++;
		}
	//	pre -= g[i][0];
	//	pre += g[i][1];
		ans = max(ans,pre);
		fal = max(fal,n-pre);
	//	cout<<ans<<" "<<fal<<" "<<pre<<endl;
	}
	cout<<max(ans,fal);
	return 0;
}

Measured memory_bytes: 2556
sa = list(input()+'x')
sb = list(input()+'x')
sc = list(input()+'x')

card = sa.pop(0)
turn = 'A'
while card != 'x':
    if card == 'a':
        card = sa.pop(0)
        turn = 'A'
    elif card == 'b':
        card = sb.pop(0)
        turn = 'B'
    else:
        card = sc.pop(0)
        turn = 'C'
print(turn)


Measured memory_bytes: 9068
#include<iostream>
#include<cmath>
#include <utility>
 #include <iomanip>

using namespace std;
#define Pi 3.14159265359

void koch(pair<double,double> p1,pair<double,double> p2,int depth){
  if(depth==0){
    cout<<fixed;
    pair<double,double> begin=make_pair(0.0,0.0);
    pair<double,double> end=make_pair(100.0,0.0);
    if(p1.first==0.0&&p1.second==0.0) cout<<setprecision(8)<<begin.first<<" "<<setprecision(8)<<begin.second<<endl;
    if(p2.first==100.0&&p2.second==0.0) cout<<setprecision(8)<<end.first<<" "<<setprecision(8)<<end.second<<endl;
    return;
  }

  pair<double,double> s,t,u;
  double temp1,temp2;
  temp1=(p2.first-p1.first)/3.0;
  temp2=(p2.second-p1.second)/3.0;
  s=make_pair(p1.first+temp1,p1.second+temp2);
  u=make_pair(p1.first+temp1*2,p1.second+temp2*2);
  t=make_pair((u.first-s.first)*cos(Pi/3.0)-(u.second-s.second)*sin(Pi/3.0)+s.first,(u.first-s.first)*sin(Pi/3.0)+(u.second-s.second)*cos(Pi/3.0)+s.second);
  koch(p1,s,depth-1);
  cout<<setprecision(8)<<s.first<<" "<<setprecision(8)<<s.second<<endl;
  koch(s,t,depth-1);
  cout<<setprecision(8)<<t.first<<" "<<setprecision(8)<<t.second<<endl;
  koch(t,u,depth-1);
  cout<<setprecision(8)<<u.first<<" "<<setprecision(8)<<u.second<<endl;
  koch(u,p2,depth-1);

}

int main(void){
  pair<double,double> p1=make_pair(0.0,0.0);
  pair<double,double> p2=make_pair(100.0,0.0);
  int depth;
  cin>>depth;
  koch(p1,p2,depth);
  return 0;

}



Measured memory_bytes: 3228
import sys
readline = sys.stdin.readline

def main():
    K, S = map(int, readline().rstrip().split())
    ans = 0
    for x in range(K+1):
        for y in range(K+1):
            if 0 <= S - x - y <= K:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
#include <iostream>

using namespace std;

int main()
{
    int K, X;

    cin >> K >> X;

    int s = X - (K-1) ;
    int e = X + (K  - 1);

    if ( s < -1000000 ) s = -100000;
    if ( e > 1000000 ) e = 1000000;
    
    for ( int i = s; i <= e; i ++ ) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = []
B = []
for _ in range(N):
    a,b = [int(i) for i in input().split()]
    A.append(a)
    B.append(b)

ans = 0
for i in range(1,N+1):
    A[-i] += ans
    if A[-i]%B[-i] != 0:
        ans += B[-i]-A[-i]%B[-i]

print(ans)


Measured memory_bytes: 15020
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define PB push_back
#define REP(i,a,b) for (int i = a ; i <= b ; i++)
#define REPI(i,a,b) for (int i = a ; i >= b ; i--)
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> pi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const ll OO = 1e18+7;
const int MOD = 1e9+7;
const int N = 2e5+7;

// vec[i] = ls of intervals with r = i
vector<pi> vec[N];
int n,m;
ll dp[N],st[N*4],lzy[N*4];

void push(int p,int l,int r)
{
    if (l==r)
    {
        st[p] += lzy[p];
        lzy[p] = 0;
        return;
    }
    lzy[p*2] += lzy[p];
    lzy[p*2+1] += lzy[p];
    //if (lzy[p] == -30) cout << l << ' ' << r<< st[p] << endl;
    st[p] += lzy[p];
    lzy[p] = 0;
    //cout << st[p] << endl;
}

void update(int i,int j,ll x,int p = 1,int l = 0,int r = n)
{
    push(p,l,r);
    if (i > r || j < l) return;
    if (l >= i && r <= j) {lzy[p] += x;push(p,l,r);return;}

    int mid = (l+r)/2;
    update(i,j,x,p*2,l,mid);
    update(i,j,x,p*2+1,mid+1,r);
    //cout << l << ' ' << r << endl;
    //cout << st[p*2] << ' ' << st[p*2+1] << endl;
    st[p] = min(st[p*2],st[p*2+1]);
}

ll query(int i,int j,int p = 1,int l = 0,int r = n)
{
    push(p,l,r);
    if (i > r || j < l) return 0;
    if (l >= i && r <= j) return st[p];

    int mid = (l+r)/2;
    ll ch1 = query(i,j,p*2,l,mid);
    ll ch2 = query(i,j,p*2+1,mid+1,r);
    return min(ch1,ch2);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("teleport.in","r",stdin);
    //freopen("teleport.out","w",stdout);

    //REP(i,0,N*4 -1 ) st[i] = OO;

    cin >> n >> m;
    ll sum = 0;
    REP(i,0,m-1)
    {
        int l,r,a;
        cin >> l >> r >> a;
        sum += a;
        vec[r].PB({l,a});
    }

    // dp[i][j] = min of values we dont trigger if last 1 is j
    ll ans = 0;
    ll best = 0;
    REP(i,1,n)
    {
        dp[i] = query(0,i-1);
        update(i,i,dp[i]);
        for(auto p:vec[i])
        {
            int l = p.F;
            int a = p.S;
            //cout << l-1 << ' ' << a << endl;
            update(0,l-1,a);
            //cout << st[1] << endl;
        }
        //cout << dp[i] << endl;
    }

    ans = min(dp[n],st[1]);
    ans = min(ans,0LL);
    //cout << st[1] << endl;
    cout << sum-ans << endl;

    return 0;
}


Measured memory_bytes: 25216
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

A.sort()
B.sort()

a = np.searchsorted(A, B, side='left')

B = sorted(B * (-1))
C = sorted(C * (-1))

c = np.searchsorted(C, B, side='left')
c = np.fliplr([c])[0]


print((a * c).sum())

Measured memory_bytes: 33544
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
  int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty;
  string s = "";
  int x = tx - sx;
  int y = ty - sy;
  //行き１
  rep(i,x){
    s += 'R';
  }
  rep(i,y){
    s += 'U';
  }
  //帰り１
  rep(i,x){
    s += 'L';
  }
  rep(i,y){
    s += 'D';
  }
  //行き２
  s += 'D';
  rep(i,x+1){
    s += 'R';
  }
  rep(i,y+1){
    s += 'U';
  }
  s += 'L';
  //帰り２
  s += 'U';
  rep(i,x+1){
    s += 'L';
  }
  rep(i,y+1){
    s += 'D';
  }
  s += 'R';
  cout << s << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

LL a[55];

LL solve(LL n) {
    sort(a, a+n);
    if (a[n-1] < n) return 0;
    int i = 0;
    while (i < n) {
        if (a[i] >= a[n-1] - n - 1 && a[i]>n) break;
        i++;
    }
    i--;
    LL dis = a[n-1];
    if (i >= 0) dis = min(dis, (a[i+1]-a[i])/(n+1));
    for (int j = i+1; j < n; j++) {
        dis = min(dis, (a[j]-n) / (j+2));
        if (dis == 0) break;
    }
    if (dis == 0) {
        a[n-1] -= n;
        for (int j = 0; j < n-1; j++) a[j]++;
        return 1LL + solve(n);
    }
    for (int j = 0; j <= i; j++) a[j] += dis*(n-i-1);
    for (int j = i+1; j < n; j++) a[j] -= n*dis - dis*(n-i-2);
    return solve(n) + (n-i-1)*dis;


}

int main() {
//    freopen("test.txt", "r", stdin);
    int n;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    cout << solve(n) << endl;


    return 0;
}

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

int main() {
  int N, M, A;
  cin >> N;
  int count = 0;
  for(int i = 2; i < 10; i++){
      M = N/i;
      A = N%i;
      if(M > 0 && M < 10 && A == 0){
          count++;
      }
  }
  if(N == 1 || N == 2) cout << "Yes" << endl;

  else if(count > 0){
      cout << "Yes" << endl;
  }
  else cout << "No" << endl;

}

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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

    double a, b, x;
    cin >> a >> b >> x;
    double h = x / (a * a);

    double ans;
    if (h * 2.0 < b) {
        double z = 2.0 * a * h / b;
        double l = sqrt(z * z + b * b);
        ans = asin(b / l);
    }
    else {
        double z = 2.0 * (b - h);
        double l = sqrt(z * z + a * a);
        ans = acos(a / l);
    }

    ans *= 180.0 / M_PI;

    cout << setprecision(20) << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

int b()
{
    long long a;
    std::cin >> a;
    
    long long thousand = a / 500;
    long long remind = a - thousand * 500;
    long long one = remind / 5;
    
    std::cout << thousand * 1000 + one * 5;
    
    return 0;
}



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

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#define INF 1e9
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using namespace std;
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; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
  s << vv[i] << endl;
  }
  return s;
}

int N,M;
vector<pair<int,int>>p;
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> N >> M;
  p.resize(M);
  rep(i,M){
    cin >> p[i].second >> p[i].first;
  }
  sort(p.begin(),p.end());
  int ret = 0;
  int last = 0;
  rep(i,M){
    if(p[i].second >= last){
      last = p[i].first;
      ret++;
    }
  }


  cout << ret << endl;
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        long x,a,b; cin>>x>>a>>b;
        string ans;
        if(a-b>=0)ans="delicious";
        else if(b-a<=x)ans="safe";
        else ans="dangerous";
        cout<<ans<<endl;
}

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

int main(){
    int n,d;
    cin >> n >> d;
    double X[n][d];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < d; j++){
            cin >> X[i][j];
        }
    }
    int count = 0;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            int distance = 0;
            //i,jが固定されて計算をする
            for(int k = 0; k < d; k++){
                distance += (X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
                //cout << distance << endl;
            }
            //計算終了
            //二乗の形かどうか判別
            //cout << distance << endl;
            for(int k = 1; k < 1000; k++){
                if(k*k == distance){
                    count += 1;
                }
            }
            
        }
    }
    cout << count << endl;
    return 0;
}



Measured memory_bytes: 256
from __future__ import division
import sys
raw_input = sys.stdin.readline
N = int(raw_input())
ans = [0 for x in range(N+1)]
ans[0] = 1
arr = map(float,raw_input().split())
for i in range(N):
    a = arr[i]
    for j in range(i+1,0,-1):
        ans[j] += ans[j-1]*a
        ans[j-1] *= (1-a)
res = 0
for i in range(int(N/2)+1,N+1):
    res += ans[i]
print res

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

int n;
string d;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<n; ++i){
		char c;
		cin >> c;
		d.push_back(c);
	}
	for(int i=0; i<=1111; ++i){
		string s = to_string(i);
		bool f = true;
		for(int j=0; j+s.size()<=n; ++j)
			if(s == d.substr(j, s.size()))
				f = false;
		if(f){
			cout << i << "\n";
			return 0;
		}
	}
}


Measured memory_bytes: 3292
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

// #define DEBUG 1
#define DFILE "t1.1"

int main()
{
#ifdef DEBUG
#define cin fin
  fstream fin(DFILE);
#endif
  int a, p;
  cin >> a >> p;
  int n;
  p += a * 3;
  n = p / 2;
  cout << n << endl;
  return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, m;
  cin>>n>>m;
  vector<int> l(m), r(m);
  int maxl=1, minr=n+1;
  rep (i, m) cin>>l.at(i)>>r.at(i);
  rep (i, m) {
    maxl = max(maxl, l.at(i));
    minr = min(minr, r.at(i));
  }
  if(minr<maxl) cout<<0<<endl;
  else cout<<minr-maxl+1<<endl;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353a
#define pi acos(-1)
#define all(v) v.begin(),v.end()
 
int main(){
    int x,k;
    cin>>k>>x;
    if(500*k>=x){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3596
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if((a+b)%3==0||a%3==0||b%3==0)
    	cout<<"Possible";
    else
    	cout<<"Impossible";
	return  0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // ver1.8
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
#define PAI 3.14159265358979
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  cout << fixed << setprecision(14);
  Vi a(4),ans(4);
  rep(i,0,4) cin >> a[i];
  sort(ALL(a));
  ans = {1,4,7,9};
  if(a==ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


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

int main()
{
	int l, a, sum_angle = 90;
	double x, y;

	x = y = 0.0;

	while (scanf("%d,%d", &l, &a), l || a){
		x += l * cos(M_PI * sum_angle / 180);
		y += l * sin(M_PI * sum_angle / 180);

		sum_angle = (sum_angle - a) % 360;
	}

	cout << (int)x << endl << (int)y << endl;

	return (0);
}

Measured memory_bytes: 1212
// Words are flowing out like endless rain into a paper cup
// They slither while they pass they slip away across the universe
// Pools of sorrow, waves of joy are drifting through my open mind
// Possessing and caressing me

#include <bits/stdc++.h>
using namespace std;

using LL = long long;

namespace _buff {

const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
    if (ib == ie) {
        ib = ibuf;
        ie = ibuf + fread(ibuf, 1, BUFF, stdin);
    }
    return ib == ie ? -1 : *ib++;
}

}

LL read() {
    using namespace _buff;
    LL ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

const size_t N = 55;

int n, a[N];

bool ok() {
    for (int i = 1; i < n; ++i) {
        if (a[i - 1] > a[i]) return false;
    }
    return true;
}

int main() {
    n = read();
    generate_n(a, n, read);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            swap(a[i], a[j]);
            if (ok()) {
                return puts("YES"), 0;
            }
            swap(a[i], a[j]);
        }
    }
    puts("NO");
    return 0;
}

Measured memory_bytes: 256