akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] XYZK = str.split(" ");
        int X = Integer.parseInt(XYZK[0]);
        int Y = Integer.parseInt(XYZK[1]);
        int Z = Integer.parseInt(XYZK[2]);
        int K = Integer.parseInt(XYZK[3]);
        int cont = 0;
        str = br.readLine();
        Long[] A = new Long[X];
        for (String s:str.split(" ")){
            A[cont] = Long.parseLong(s);
            cont++;
        }
        str = br.readLine();
        Long[] B = new Long[Y];
        cont = 0;
        for (String s:str.split(" ")){
            B[cont] = Long.parseLong(s);
            cont++;
        }
        str = br.readLine();
        Long[] C = new Long[Z];
        cont = 0;
        for (String s:str.split(" ")){
            C[cont] = Long.parseLong(s);
            cont++;
        }
        Arrays.sort(A,Comparator.reverseOrder());
        Arrays.sort(B,Comparator.reverseOrder());
        Arrays.sort(C,Comparator.reverseOrder());
        ArrayList<Long> ABC = new ArrayList<>();
        for (int i=0;i<X;i++){
            for (int j=0;j<Y;j++){
                if ((i+1)*(j+1)>K){
                    break;
                }
                for (int k=0;k<Z;k++){
                    if ((i+1)*(j+1)*(k+1)>K){
                        break;
                    }
                    ABC.add(A[i]+B[j]+C[k]);
                }
            }
        }
        Collections.sort(ABC,Collections.reverseOrder());
        for (int i=0;i<Integer.parseInt(XYZK[3]);i++){
            System.out.println(ABC.get(i));
        }
    }
}

Measured memory_bytes: 29284
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <utility>
 
int main(){
  int N,M;
  std::cin >> N >> M;
 
  std::unordered_map<int, std::vector<int>> v_dict;
  for(int i = 0; i < M; i++){
    int u,v;
    std::cin >> u >> v;
    v_dict[u].push_back(v+N);
    v_dict[u+N].push_back(v+2*N);
    v_dict[u+2*N].push_back(v);
  }
  int S,T;
  std::cin >> S >> T;
 
  if(S == T){
    std::cout << "0" << std::endl;
    return 0;
  }
 
  int nsteps = 1;
  std::unordered_set<int> found;
  std::vector<int> current_nodes, next_nodes;
  found.insert(S);
  current_nodes.push_back(S);
  while(true){
    if(current_nodes.size() == 0){
      std::cout << "-1" << std::endl;
      return 0;
    }
    for(const auto& n: current_nodes){
      if(v_dict.find(n) == v_dict.end()) continue;
      for(const auto& neigh: v_dict[n]){
        if(neigh == T){
          std::cout << nsteps/3 << std::endl;
          return 0;
        }
        if(found.find(neigh) != found.end()) continue;
        next_nodes.push_back(neigh);
        found.insert(neigh);
      }
    }
    nsteps++;
    std::swap(current_nodes, next_nodes);
    next_nodes.clear();
  }
 
  return 0;
}

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

int main(){
    bool x[2019];
    for(int i = 0; i < 2019; i++){
        x[i] = 0;
    }
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        a--;
        x[a] = 1;
    }
    
    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int b,cnt = 0;;
        cin >> b;
        for(int j = 0; j < 2019; j++){
            if(x[j] == 1){
                cnt++;
                if(cnt == b){
                    if(x[j+1] == 0 && j != 2018) swap(x[j],x[j+1]);
                }
            }
        }
    }
    
    for(int j = 0; j < 2019; j++){
        if(x[j]){
            cout << j+1 << endl;
        }
    }
    return 0;
}


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

int main(){
    int n;
    vector<int> h;
    int tmp;
    int num;
    int max;
    int i, j;
    cin >> n;
    for(i=0; i<n; i++){
        cin >> tmp;
        h.push_back(tmp);
    }
    num = 0;
    max = 0;
    i = 0;
    while(i < n-1){
        if(h[i+1]<=h[i]){
            num++;
            if(i==n-2){
                if(num>max){
                    max = num;
                }                
            }
        }else{
            if(num>max){
                max = num;
            }
            num = 0;
        }
        i++;
    }
    cout << max << endl;
}

Measured memory_bytes: 892
X, Y, A, B, C = map(int, input().split())
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p.sort()
q.sort()
r.sort()
red_remain = X
green_remain = Y
ans = 0
flag = False
for i in range(X+Y):
    if flag:
        flag = False
        continue
    if red_remain == 0 or len(p) == 0:
        if green_remain == 0 or len(q) == 0:
            ans += r.pop(-1)
        elif len(r) == 0:
            ans += q.pop(-1)
            green_remain -= 1
        elif q[-1] < r[-1]:
            ans += r.pop(-1)
        else:
            ans += q.pop(-1)
            green_remain -= 1
    elif green_remain == 0 or len(q) == 0:
        if len(r) == 0:
            ans += p.pop(-1)
            red_remain -= 1
        elif p[-1] < r[-1]:
            ans += r.pop(-1)
        else:
            ans += p.pop(-1)
            red_remain -= 1
    elif len(r) == 0:
        if p[-1] == q[-1]:
            if i == X+Y-1:
                ans += p[-1]
            else:
                flag = True
                ans += p.pop(-1) + q.pop(-1)
                red_remain -= 1
                green_remain -= 1
        elif p[-1] < q[-1]:
            ans += q.pop(-1)
            green_remain -= 1
        else:
            ans += p.pop((-1))
            red_remain -= 1
    else:
        if p[-1] < r[-1] and q[-1] < r[-1]:
            ans += r.pop(-1)
        elif p[-1] == q[-1]:
            if i == X+Y-1:
                ans += p[-1]
            else:
                flag = True
                ans += p.pop(-1) + q.pop(-1)
                red_remain -= 1
                green_remain -= 1
        elif p[-1] < q[-1]:
            ans += q.pop(-1)
            green_remain -= 1
        else:
            ans += p.pop((-1))
            red_remain -= 1
print(ans)

Measured memory_bytes: 104548
def judge_month(s):
    if '00' < s and s <= '12':
        return True
    else:
        return False

S = input()

s1 = S[0] + S[1]
s2 = S[2] + S[3] 

month_1 = judge_month(s1)
month_2 = judge_month(s2)

if month_1 and month_2:
    print('AMBIGUOUS')
elif month_1:
    print('MMYY')
elif month_2:
    print('YYMM')
else:
    print('NA')



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}
const int INF = 1e18;

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

    vi A(N, 0);
    int res = 0;
    rep(i, K) {
        int d;
        cin >> d;
        rep(i, d) {
            int a;
            cin >> a;
            a--;
            A[a]++;
        }
    }

    rep(i, N) {
        if(!A[i]) res++;
    }

    cout << res << endl;
    return 0;
}

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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define sz(a) int((a).size())
#define endl '\n'

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b+c>=22)
		cout<<"bust"<<endl;
	else
		cout<<"win"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int main(){
    int n; cin >> n;
    string s1, s2; cin >> s1 >> s2;
    ll dp = 1;
    int i=0;
    int freeness;
    if(s1[i] == s2[i]){
        dp  = 3;
        i++;
        freeness = 2;
    }else{
        dp = 6;
        i+= 2;
        freeness=1;
    }
    while(i<n){
        if(s1[i] == s2[i]){
            i++;
            if(freeness == 1){
            }else{
                dp*= 2;
            }
            freeness=2;
        }else{
            if(freeness==1){
                dp *= 3;
            }else{
                dp *= 2;
           }
           freeness = 1;
           i+=2;
        }
    }
    cout << dp % MOD << endl;

}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr= input.trim().split("\n");
var [m,n]=arr.shift().split(" ").map(Number);
var yx=[];
for(var i=0;i<m;i++)yx.push(arr.shift().split(""));
var memo=[];
for(var i=0;i<m;i++){
   for(var j=0;j<n;j++){
      if(i==0)memo.push([i,j]);
      if(yx[i][j]=="o"){
         [[0,-1],[0,1]].forEach(v=>{
            var y=i+v[0];
            var x=j+v[1];
            if((y<0 || x<0 || y>=m || x>=n)==false)memo.push([y,x]);
         });
      }else if(yx[i][j]=="x"){
         for(var ii=-1;ii<=1;ii++)for(var jj=-1;jj<=1;jj++){
            if(ii==0 && jj==0)continue;
            var y=i+ii;
            var x=j+jj;
            if(y<0 || x<0 || y>=m || x>=n)continue;
            memo.push([y,x]);
         }
      }
   }
}
memo.forEach(v=>{
   yx[v[0]][v[1]]="b";
});
console.log(yx.join("").replace(/[^-]/g,"").length);


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

const int MOD = 1000000007;
#define p(var) std::cout<<#var" = "<<var<<std::endl
#define PI (acos(-1))
#define rep(i, n)   for (int i = 0; i <  (n); i++)
#define repeq(i, n) for (int i = 1; i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
using ll = long long;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a;}
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b;}

int main(){
    int a[5];
    rep(i,5){
        cin >> a[i];
    }
    int k;
    cin >> k;
    rep(i,5){
    rep(j,5){
        if(a[i]-a[j]>k){
            cout <<":(" << endl;
            return 0;
        }
    }
    }

    cout <<"Yay!" << endl;
    

    return 0;
    
}






Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ll n; cin >> n;
	ll sum[n] = {}; cin >> sum[0];
	for(int i = 1; i < n; ++i){
		ll a; cin >> a;
		sum[i] = sum[i - 1] + a;
	}
	ll ans = 1145148931919810;
	for(int i = 0; i < n - 1; ++i) ans = min(ans, abs(sum[i] - (sum[n - 1] - sum[i])));
	cout << ans << endl;
	return 0;
}

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

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

    string s,t;
    cin >> s >> t;

    int n,m;
    n = s.size();
    m = t.size();

    vector<vector<int>> dp(n+1,vector<int>(m+1));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }


    string ans;
    int i = n;
    int j = m;

    while(i && j){
        if(dp[i][j] == dp[i-1][j]) i--;
        else if(dp[i][j] == dp[i][j-1]) j--;
        else {
            i--;
            j--;
            ans.push_back(s[i]);
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;

}


Measured memory_bytes: 35584
N, M = map(int, input().split())
a = [0] * N
b = [0] * N
c = [0] * M
d = [0] * M
for i in range(N):
    a[i], b[i] = map(int, input().split())

for i in range(M):
    c[i], d[i] = map(int, input().split())

for i in range(N):
    dist = 10 ** 9
    for j in range(M):
        if abs(a[i] - c[j]) + abs(b[i] - d[j]) < dist:
            dist = abs(a[i] - c[j]) + abs(b[i] - d[j])
            index = j + 1
            
    print(index)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

#define PT pair<int, int>

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


	int H, W, K;
	cin >> H >> W >> K;
	K = min(K, H + W);
	string S[800];
	rep(i, H) cin >> S[i];
	bool D[640000] = {};
	int k = 0;
	vector<int> que1;
	rep(i, H) rep(j, W) {
		if (S[i][j] == 'S') {
			D[k] = true;
			que1.pb(k);
		}
		k++;
	}
	rep(d, K) {
		vector<int> que2;
		for (int k : que1) {
			int i = k / W;
			int j = k - i * W;
			if (i == 0 || j == 0 || i == H - 1 || j == W - 1) continue;
			else {
				if (!D[k + 1] && S[i][j + 1] != '#') { que2.pb(k + 1); D[k + 1] = true; }
				if (!D[k - 1] && S[i][j - 1] != '#') { que2.pb(k - 1); D[k - 1] = true; }
				if (!D[k + W] && S[i + 1][j] != '#') { que2.pb(k + W); D[k + W] = true; }
				if (!D[k - W] && S[i - 1][j] != '#') { que2.pb(k - W); D[k - W] = true; }
			}
		}
		que1 = que2;
	}

	int kotae = 1e9;
	k = 0;
	rep(i, H) rep(j, W) {
		if (D[k]) {
			int tmp = min(min(i, H - i - 1), min(j, W - j - 1));
			kotae = min(kotae, 1 + (tmp + K - 1) / K);
		}
		k++;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 1536
N, P = map(int, input().split())
A = list(map(int, input().split()))

c_odd , c_even = 0, 0

for a in A:
  if a%2 == 0:
    c_even += 1
  else:
    c_odd += 1

if c_odd == 0:
  print(2**N if P==0 else 0)
else:
  print(2**(N-1))
    
"""
fact = [1] * 51

for i in range(1,51):
  fact[i] = fact[i-1] * i
  
def comb(n,r):
  return int(fact[n] / fact[r] / fact[n-r])

idx = 1 if P == 1 else 0

work = 0
while idx <= c_odd:
  work += comb(c_odd, idx)
  idx += 2

print(work * ( 2 ** c_even) )
"""

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

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

  char c;
  cin >> c;
  if(isupper(c)) cout << "A" << endl;
  else cout << "a" << endl;

  return 0;
}

Measured memory_bytes: 3604
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

long long f(long long x, long long K) {
    if (x == -1) return 0;
    return x / K + 1;
}

int main() {

    long long X, Y, K;
    cin >> X >> Y >> K;

    cout << f(Y, K) - f(X-1, K) <<endl;

}






















































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

vector<vector<int>> g;
vector<int> c;
int cnt;

void dfs(int cur, int par, vector<int>& d){
    d[cur] = c[cnt++];
    for(int nex : g[cur]){
        if(nex == par) continue;
        dfs(nex, cur, d);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    g.resize(n);
    c.resize(n);

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    long long sum = 0;
    int mx = 0;
    for(int i = 0; i < n; i++){
        cin >> c[i];
        sum += c[i];
        mx = max(mx, c[i]);
    }
    sort(c.rbegin(), c.rend());

    cnt = 0;
    vector<int> d1(n, 0);
    dfs(0, -1, d1);

    long long ans = sum - mx;
    cout << ans << endl;
    for(int i = 0; i < n; i++){
        cout << d1[i] << " \n"[i+1 == n];
    }
    return 0;
}

Measured memory_bytes: 1408
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 2019;
//constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

int main(void){
	string s;
	cin >> s;
	ll n = s.size();

	ll ans = 0;
	Vec prev(MOD), cur(MOD);
	rep(i, n){
		cur.assign(MOD, 0);
		ll k = s[i] - '0';
		cur[k]++;
		ll cnt = 0;
		for(ll i : prev){
			cur[(cnt++ * 10 + k) % MOD] += i;
		}

		ans += cur[0];
		swap(cur, prev);
	}

	co(ans);

	return 0;
}


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

int main() {
  int N,i,j,k,A=0,B=0;
  cin>>N;
  vector<int> a(N);
  for(i=0;i<N;i++){
    cin>>a[i];
  }
  for(i=0;i<N;i++){
    for(j=i+1;j<N;j++){
      if(a[i]<a[j]){
        k=a[i];
        a[i]=a[j];
        a[j]=k;
      }
    }
  }
  for(i=0;i<N;i++){
    if(i%2)B+=a[i];
    else A+=a[i];
  }
  cout<<A-B<<endl;
}


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


int main(){
  int n;
  cin >> n;
  vector<int> fib(n+1);
  
  if(n==0||n==1){
    cout << 1 << endl;
  }
  else{
  	fib[0] = 1;
  	fib[1] = 1;
  	for(int i=2;i<=n;i++){
    	fib[i] = fib[i-1] + fib[i-2];
    	//cout << fib[i+2] << endl;  
  	}
  	cout << fib[n] << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define repd(i,a,b) for (ll i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;
int judge(string a, int l)
{
	rep(i, l/2)
	{
		if(a[i] != a[l-i-1]) return false;
	}
	return true;
}
int main(void)
{
	string S;
	cin >> S;
	int L = S.size();
	if(!judge(S, L))
	{
		cout << "No" << endl;
		return 0;
	}
	string H = S.substr(0, (L-1)/2);
	if(!judge(H, H.size()))
	{
		cout << "No" << endl;
		return 0;
	}
	string T = S.substr((L+3)/2-1,L-(L+3)/2+1);
	if(!judge(T, T.size()))
	{
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)]
parent = [-1] * (N+1) # -1なら未訪問
for m in range(M):
    a,b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
q = queue.Queue() # 自分の部屋番号、親の部屋番号
q.put((1,0)) # 部屋1の親は部屋0と考える
while(not q.empty()):
    x, p = q.get()
    if parent[x] != -1: # 訪問済み
        continue
    parent[x] = p
    for next in adj[x]:
        if parent[next] == -1: # 未訪問なら
            q.put((next,x)) # 探索候補に追加
print ('Yes') # 必ず目標は達成できる
for p in parent[2:]: # 部屋2以降の親（前の部屋）
    print(p)

Measured memory_bytes: 39968
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <math.h>
#include <array>
#include <list>
#include <set>
#include <unordered_map>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> tup;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vp;
ll a,b,c;
ll ans=0;

int main(int argc,char const* argv[])
{
  cin >> a >> b >> c;
  if(b>=c)
    {
      cout << b+c << endl;
      return 0;
    }
  else
    {
      if(c<=(b+a))
	{
	  cout << b+c << endl;
	  return 0;
	}
      else
	{
	  cout << 2*b+min(c-b,a+1) << endl;
	  return 0;
	}
    }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P  = pair<int, int>;
int main() {
    ll n, k;
    ll r;
    cin >> n >> k;
    vector<vector<ll>> v(n);
    vector<ll> p(n), c(n), siz(n, 0);
    for (ll& i : p) cin >> i, --i;
    for (ll& i : c) cin >> i;
    r = c[0];
    for (ll i = 0; i < n; ++i) {
        ll cur = i, sum = 0;
        do {
            ++siz[i];
            v[i].push_back(sum += c[cur]);
            cur = p[cur];
        } while (cur != i);
    }
    for (ll i = 0; i < n; ++i) {
        ll kt = k, s = 0, tail = v[i].back();
        if (k > siz[i] * 2) {
            if (tail > 0) {
                s  = tail * (k / siz[i] - 1);
                kt = k % siz[i] + siz[i];
            }
            else
                kt = siz[i];
        }
        for (ll j = 0; j < kt; ++j)
            r = max(r, s + v[i][j % siz[i]] + tail * (j >= siz[i]));
    }
    cout << r;
}

Measured memory_bytes: 218928
#include<bits/stdc++.h>
using namespace std;
#define BOOST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ll long long
#define test(t) int t ; cin>>t ; while(t--)
ll mulmod(ll a, ll b, ll mod){ll res = 0;a = a % mod;while (b > 0){if (b % 2 == 1)res = (res + a) % mod;a = (a * 2) % mod;b /= 2;}return res % mod;}
int n;
int main(){
	BOOST;
	// cin >> n;
	int arr[3];
	for(int i = 0 ; i < 3 ; ++i){
		cin >> arr[i];
	}
	sort(arr, arr + 3);
	cout << arr[2] - arr[0] ;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
a = [int(x) for x in input().split()]
l = [0]*N
r = [0]*N
for i in range(N):
    l[i] = a[i] + i + 1
    r[i] = i + 1 - a[i]
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[r[i]] += 1
ans = 0
for i in range(N):
    d[r[i]] -= 1
    ans += d[l[i]]
print(ans) 

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

int main(){
    using namespace std;
    unsigned long H, N;
    cin >> H >> N;
    vector<unsigned long> dp(H + 10000, numeric_limits<unsigned long>::max() / 5);
    dp[0] = 0;
    for(unsigned long i{0}, A, B; i < N; ++i){
        cin >> A >> B;
        for(unsigned long j{A}; j < H + 10000; ++j)dp[j] = min(dp[j], dp[j - A] + B);
    }
    cout << *min_element(dp.begin() + H, dp.end()) << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    char s[101];
    scanf("%d\n%s", &n, s);
    if (n % 2)
    {
        printf("No");
        return 0;
    }
    int n_2 = n / 2;

    for (size_t i = 0; i < n_2; i++)
    {
        if (s[i] != s[n_2 + i])
        {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
}


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

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    int count = 0;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        if(x == y) count++;
        else count = 0; 
        if(count == 3) break;
    }
    if(count == 3) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int maxn = 110;
int N,W, w[maxn],v[maxn];
map< pair<int,LL>, LL > dp;

LL dfs(const int i, const LL j)
{
    if (i == N)
        return 0;
    pair<int,LL> k = make_pair(i,j);
    if (!in_(k,dp)) {
        if (j + w[i] <= W)
            dp[k] = max(dp[k], v[i]+dfs(i+1,j+w[i]));
        dp[k] = max(dp[k], dfs(i+1,j));
    }
    return dp[k];
}

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    while (cin >> N >> W) {
        dp.clear();
        FOR(i,0,N)
            cin >> w[i] >> v[i];
        const LL ans = dfs(0,0);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 6272
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

using namespace std;
using ll = long long;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

bool isAllVisit(const vector<bool>& visit) {
    for (auto&& v : visit) {
        if (!v)return false;
    }
    return true;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}


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

    int N, X;
    cin >> N >> X;
    vector<int>A(N);
    cin >> A;

    ll ans = 0;
    REP(i, N - 1) {
        int sum = A[i] + A[i + 1];
        if (sum > X) {
            int a = sum - X;
            ans += a;
            int b = min(A[i + 1], a);
            A[i + 1] -= b;
            a -= b;
            if (a > 0) {
                A[i] -= a;
            }
        }
    }

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

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

int main(void) {
    vector<int> zohe(3);
    for (int i = 0; i < 3; i++) cin >> zohe[i];
    sort(zohe.begin(), zohe.end(), greater<int>());
    cout << (long long)abs(zohe[0] - zohe[0] / 2 * 2) * zohe[1] * zohe[2] << endl;
}


Measured memory_bytes: 256
#include<stdio.h>


int main()
{
	int i;
	char str[1201];
	fgets(str,1201,stdin);
	
	for(i=0;str[i] != 0;i++){
		if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z'))
		putchar(str[i]^0x20);
		else
		putchar(str[i]);
		
	}
		
	
	return 0;
}


Measured memory_bytes: 2108
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static 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;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int n = sc.nextInt();
    System.out.println((int) Math.ceil((double) n / Math.max(h, w)));
  }
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll i, temp,t, n,j, a[2000010], ans, g, C[2000010];
bool cond;
char c;
string s;
void solve(ll x)
{
    if(cond)
        return;
    for(j=1;j*j<=x;j++)
    {
        if(x%j==0)
        {
            ll a = j;
            ll b = x/j;
            if(a==b)
            {
                a = j;
                b = 1;
            }
            if(a!=1)
            {
                if(C[a])
                {
                    cond = true;
                  //  cout << "Here 1  " << a <<endl;
                    return;
                }
                C[a]++;
                //cout << "a = "<< a << endl;
            }
            if(b!=1)
            {
                if(C[b])
                {
                    cond = true;
                    //cout << "Here 2" <<" "<< b <<" "<<x <<" "<<C[b]<<endl;
                    return;
                }
                C[b]++;
                //cout << "b = " << b << endl;
            }
        }
    }
}
int main()
{
    //I am Monim, a tiny creature of Allah
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n;
    for(i=0;i<n;i++)
        cin >> a[i];
    g = a[0];
    solve(a[0]);
    for(i=1;i<n;i++)
    {
        solve(a[i]);
        g = __gcd(g,a[i]);
    }
    if(!cond)
        cout << "pairwise coprime";
    else if(g==1)
        cout << "setwise coprime";
    else
        cout << "not coprime";
    return 0;
}


Measured memory_bytes: 12068
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,a[10000],cnt,ans;
int32_t main(){
CODE_START;
cin>>n;
for(ll i=0;i<n;i++)
{
    cin>>a[i];
    if(a[i]%2==1) cnt++;
}
if(cnt!=0){
    rc(0);
}
while(cnt==0){
        ans++;
    for(ll i=0;i<n;i++)
        a[i]=a[i]/2;
    for(ll i=0;i<n;i++)
    if(a[i]%2==1){
            cnt++;
        break;
        break;
    }
}
cout<<ans;
}



Measured memory_bytes: 256
import java.util.*;

class Main {
        public static void main(String args[]) {
                Scanner sc = new Scanner(System.in);
                while (true) {
                        int N = sc.nextInt();
                        if (N == 0) {
                                System.out.println(0);
                                continue;
                        } else if (N == -1) {
                                return;
                        }
                        int ans[] = new int[100];
                        int i = 0;
                        while (N != 0) {
                                ans[i] = N % 4;
                                N /= 4;
                                i++;
                        }
                        i--;
                        for (; i>=0; i--) {
                                System.out.print(ans[i]);
                        }
                        System.out.println("");
                }
        }
}

Measured memory_bytes: 31120
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,S=0;cin>>N;int A[N+2];
  A[0]=0;A[N+1]=0;
  for(int i=1;i<=N;i++){
    cin>>A[i];S+=abs(A[i]-A[i-1]);
  }
  S+=abs(A[N]);
  for(int i=1;i<=N;i++)cout<<S-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1])<<endl;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
#define chmax(a,b) if(b>a) a = b
#define chmin(a,b) if(b<a) a = b
typedef long long ll;
using namespace std;

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll n,k; cin >> n >> k;

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

    
    vector<ll> c(n+1,0);

    chmin(k,100);

    rep(i,k){
          rep(i,n+1) c[i] = 0;
          rep(i,n){
              if(a[i] == 0){ c[i]++; c[i+1]--;}
              else{
                  if(i - a[i] >= 0) c[i-a[i]]++;
                  else c[0] ++;
                  if(i+a[i]+1 <= n) c[i+a[i]+1]--;
                  else c[n]--;
              }
          }
          rep(i,n+1){  //simulate
              if(0 < i) c[i] += c[i-1];
          }
          rep(i,n) a[i] = c[i];  //update
    }

    

    rep(i,n) cout << a[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 6372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};



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

	int n,m;
	cin >> n >> m;
	vector<i_i> a(m);
	rep(i,m) cin >> a[i].sc >> a[i].fs;
	sort(all(a));
	int res = 0;
	int endtime = 0;

	rep(i,m){
		if(a[i].sc >= endtime){
			endtime = a[i].fs;
			++res;
		}
	}
	cout << res << endl;

    return 0;
}


Measured memory_bytes: 1024
/* https://atcoder.jp/contests/arc070/submissions/2788370 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	4000

int query(int a, int b) {
	static char s[2];

	printf("? %d %d\n", a, b), fflush(stdout);
	scanf("%s", s);
	return s[0] == 'Y';
}

int main() {
	static char cc[N + 1];
	int n, a, b, i, i_, k;

	scanf("%d%d", &a, &b), n = a + b;
	if (a <= b) {
		printf("Impossible\n");
		return 0;
	}
	i_ = -1, k = 0;
	for (i = 0; i < n; i++)
		if (k == 0)
			i_ = i, k++;
		else
			k += query(i, i_) ? 1 : -1;
	for (i = 0; i < n; i++)
		cc[i] = i == i_ ? '1' : query(i_, i) + '0';
	printf("! %s\n", cc);
	return 0;
}


Measured memory_bytes: 3732
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		String s = sc.next();
		int c = 0, d = 0;

		for(int i=0; i<n; i++){
			if(s.charAt(i)=='a'){
				if(c<a+b){
					System.out.println("Yes");
					c++;
				}else{
					System.out.println("No");
				}
			}else if(s.charAt(i)=='b'){
				if(c<a+b&&d<b){
					System.out.println("Yes");
					c++;
				}else{
					System.out.println("No");
				}
				d++;
			}else{
				System.out.println("No");
				continue;
			}
		}
	}
}

Measured memory_bytes: 23988
#include<stdio.h>
#include<math.h>
main()
{
    long long int n,m,a,s=0;
    scanf("%lld%lld",&n,&m);
    while(m--)
    {
        scanf("%lld",&a);
        s=s+a;
    }
    if(s>n)
        printf("-1");
    else
        printf("%lld",n-s);
}


Measured memory_bytes: 1712
#include<bits/stdc++.h>
using namespace std;
int ans,x[4],tmp[4];
map< pair < int , pair < int, int > > , bool > mp;
int main()
{
	for(int i=0;i<3;i++)
	{
		scanf("%d",&x[i]);
	}
	sort(x,x+3);
	while(1)
	{
		if(x[0]%2 || x[1]%2 || x[2]%2) break;
		ans++;
		for(int i=0;i<3;i++)
		{
			tmp[i] = (x[(i+1)%3]+x[(i+2)%3])/2;
		}
		sort(tmp,tmp+3);
		for(int i=0;i<3;i++)
		{
			x[i] = tmp[i];
		}
		if(mp[make_pair(x[0],make_pair(x[1],x[2]))])
		{
			ans = -1;
			break;
		}
		else
		{
			mp[make_pair(x[0],make_pair(x[1],x[2]))] = 1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        String[] tmp = scanner.nextLine().split(" ");
        scanner.close();
        Integer side1 = Integer.valueOf(tmp[0]);
        Integer side2 = Integer.valueOf(tmp[1]);
        Double angle1 = Math.toRadians(Double.valueOf(tmp[2]));
 
        Double s = (side1 * side2 * Math.sin(angle1)) / 2;
        Double l = (side1 + side2)
                + Math.sqrt((side1 * side1) + (side2 * side2)
                        - (2 * side1 * side2 * Math.cos(angle1)));
        Double h = side2 * Math.sin(angle1);
 
        System.out.println(s + "\n" + l + "\n" + h);
    }
 
}

Measured memory_bytes: 26304
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ld long double
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

////////////////////////////////////////////////////////

// デバッグを消し忘れるな！！！

// dijkstra
// 有向グラフ

const ll mx = 10005;

vector<pair<ll, ll>> adj[mx];
ll d[mx];
ll color[mx];
ll n;

// 頂点0から各頂点vまでの最短経路

void dijkstra(){
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    rep(i, 0, mx) d[i] = INF;
    d[0] = 0;
    color[0] = 1;
    pq.push({0, 0});

    while(!pq.empty()){
        pair<ll, ll> f = pq.top(); pq.pop();
        ll u = f.second; // 番号
        color[u] = 1;
        if(d[u] < f.first) continue;
        rep(j, 0, sz(adj[u])){
            ll v = adj[u][j].first;
            if(color[v])  continue;
            if(d[v] > d[u] + adj[u][j].second){
                d[v] = d[u] + adj[u][j].second;
                pq.push({d[v], v});
            }
        }
    }

    rep(i, 0, n){
        cout << i << " " << (d[i] == INF ? -1 : d[i]) << endl;
    }

}

int main() {
    cin >> n;
    rep(i, 0, n){
        ll u, k; cin >> u >> k;
        rep(j, 0, k){
            ll v, c; cin >> v >> c;
            adj[u].push_back({v, c});
        }
    }

    dijkstra();

    return 0;
}



Measured memory_bytes: 12200
#include <iostream>
#include <string>

std::string solve(int a, int b, int c)
{
  if (a < b && a < c && c < b) return "Yes";
  if (b < a && b < c && c < a) return "Yes";
  return "No";
}

int main()
{
  int a, b, c;
  std::cin >> a >> b >> c;

  std::cout << solve(a, b, c) << std::endl;
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[200005];
struct Vertex {
    vector<ll> node;
};

Vertex V[200005];
ll C[200005];

void dfs(vector<ll> &v, ll index = 0, ll par = -1) {
    ll a = A[index];
    ll mi = lower_bound(v.begin(), v.end(), a) - v.begin();
    ll t = v[mi];
    v[mi] = a;
    C[index] = lower_bound(v.begin(), v.end(), INF) - v.begin();
    REP(i, V[index].node.size()) {
        ll n = V[index].node[i];
        if (n == par)
            continue;
        dfs(v, n, index);
    }
    v[mi] = t;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }
    REP(i, N) {
        C[i] = 0;
    }
    REP(i, N - 1) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        V[a].node.push_back(b);
        V[b].node.push_back(a);
    }

    vector<ll> v(N + 5, INF);
    dfs(v);

    REP(i, N) {
        cout << C[i]  << endl;
    }
    return 0;
}

Measured memory_bytes: 33116
#include <iostream>

int main()
{
    while(true)
    {
        int h,w;
        std::cin >> h >> w;
        
        if(h==0 && w==0)    break;
        
        for(int i=0;i<h;i++)
        {
            if(i%2)
                for(int j=0;j<w;j++)
                {
                    if(j%2) std::cout << "#";
                    else    std::cout << ".";
                }
            else
                for(int j=0;j<w;j++)
                {
                    if(j%2) std::cout << ".";
                    else    std::cout << "#";
                }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    }
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    int sm = accumulate(all(a), 0);
    if (sm % 10 != 0) {
        cout << sm << endl;
        return 0;
    }
    int mx = 0;
    rep(i, n) {
        if ((sm - a[i]) % 10 != 0) chmax(mx, sm - a[i]);
    }
    cout << mx << endl;
}

Measured memory_bytes: 256