akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define ll long long

int main(){
  int n,i,src,dest,j;
  cin >> n;
  vector<ll> v(n,1);
  vector<vector<int> > g(n, vector<int>());
  for(i=0;i<n-1;i++){
    cin >> src >> dest;
    g[src-1].push_back(dest-1);
    g[dest-1].push_back(src-1);
  }
  vector<ll> c(n);
  for(i=0;i<n;i++){cin >> c[i];c[i]++;}
  vector<bool> vi(n,false);
  sort(c.begin(), c.end(), greater<ll>());
  ll node,score=0,tmp;
  for(i=0;i<n;i++){
    score=0;
    for(j=0;j<n;j++){
       if(vi[j])continue;
       tmp=0;
       for(auto k:g[j]){
          tmp+=v[k];
       }
       if(tmp>score){
        score=tmp;
        node=j;
       }
    }
    vi[node]=true;
    v[node]=c[i];
  }
  score=0;
  for(i=0;i<n;i++){
    for(auto j:g[i])
     score+=min(v[i],v[j])-1;
  }
  cout << score/2 << "\n";
  for(i=0;i<n;i++)cout << v[i]-1 << " ";
  return 0;  
}


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

int main(){
  int N;
  cin >> N;
  int sum = 0, l, r;
  for (int i = 0;i < N; i++){
    cin >> l >> r;
    sum += (r - l + 1);
  }
  cout << sum << endl;
}

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

int main()
{
	int sx, sy, tx, ty;
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
	for (int i = sx; i < tx; i++) putchar('R');
	for (int i = sy; i < ty; i++) putchar('U');
	for (int i = sx; i < tx; i++) putchar('L');
	for (int i = sy; i < ty; i++) putchar('D');
	
	putchar('D');
	for (int i = sx; i < tx + 1; i++) putchar('R');
	for (int i = sy; i < ty + 1; i++) putchar('U');
	putchar('L');
	putchar('U');
	for (int i = sx; i < tx + 1; i++) putchar('L');
	for (int i = sy; i < ty + 1; i++) putchar('D');
	putchar('R');
	putchar('\n');

	return 0;
}

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

using namespace std;

template <class T>
using lim = numeric_limits<T>;

typedef long long ll;
typedef long double ld;

const int maxN = 100;
const int maxCom = 50;
vector<int> primes;

int multis[maxN+1];
ll combi[maxCom+1][maxCom+1];

void sieve(){
	for (int i = 2; i <= maxN; i++){
		bool isPrime = true;
		for (int p : primes){
			if (p*p > i) break;
			if (i%p == 0){
				isPrime = false;
				break;
			}
		}
		
		if (!isPrime) continue;
		primes.push_back(i);
	}
}

void computeCombi(){
	memset(combi, 0, sizeof combi);
	
	for (int i = 0; i <= maxCom; i++){
		combi[i][0] = 1;
	}
	
	for (int i = 1; i <= maxCom; i++){
		for (int j = 1; j <= maxCom; j++){
			combi[i][j] = combi[i-1][j-1]+combi[i-1][j];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	sieve();
	computeCombi();
	memset(multis, 0, sizeof multis);
	
	int n; cin >> n;
	// prime factorize
	for (int i = 2; i <= n; i++){
		int temp = i;
		for (int p : primes){
			while(temp%p == 0){
				multis[p]++;
				temp /= p;
			}
		}
	}
	
	unordered_map<int, int> counters;
	for (int i = 2; i <= n; i++){
		counters[multis[i]]++;
	}
	
	// include i and more in the count
	for (int i = 100; i >= 2; i--){
		counters[i-1] += counters[i]; 
	}
	
	ll ways = 0;
	// 3 * 5 * 5
	ways += combi[counters[5-1]][2]*combi[counters[3-1]-2][1];
	// 3 * 25
	ways += combi[counters[3-1]-1][1]*combi[counters[25-1]][1];
	// 5 * 15
	ways += combi[counters[5-1]-1][1]*combi[counters[15-1]][1];
	// 75
	ways += combi[counters[75-1]][1];
	
	cout << ways << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

int main() {
  string s;
  stack<int> left_bank;
  stack<P> pond;
  int area = 0;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '\\') {
      left_bank.push(i);
    } else if (s[i] == '/' && !left_bank.empty()) {
      int j = left_bank.top();
      left_bank.pop();
      int sub_area = i - j;
      area += sub_area;
      while (!pond.empty() && j < pond.top().first) {
        sub_area += pond.top().second;
        pond.pop();
      }
      pond.emplace(j, sub_area);
    }
  }
  vector<int> v;
  while (!pond.empty()) {
    v.push_back(pond.top().second);
    pond.pop();
  }
  cout << area << "\n" << v.size();
  for (int i = v.size() - 1; i >= 0; i--) {
    cout << " " << v[i];
  }
  cout << "\n";
}


Measured memory_bytes: 3272
package main

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

func sum(a []int) int {
	ret := 0
	for _, v := range a {
		ret += v
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	h, n := nextInt(), nextInt()
	a := nextInts(n)
	if sum(a) >= h {
		puts("Yes")
	} else {
		puts("No")
	}
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 2048
/*
 Aizu Vol-1 0129 Hide-and-Seek Supporting System.c
 2017.8.14 bal4u@uu
 ????????¨?????¨???????????????
 */

#include <stdio.h>

#define SIZE 100
int x[SIZE+5], y[SIZE+5], r[SIZE+5];
int xt, yt, xs, ys;

int between(int x1, int y1, int x2, int y2, int x, int y)
{
    int sa, sb;
    sa = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);
    sb = (x1 - x2) * (x - x2) + (y1 - y2) * (y - y2);
    return (sa >= 0 && sb >= 0) || (sa < 0 && sb < 0);
}

int disCmp(int x1, int y1, int x2, int y2, int x, int y, int r2)
{
    int a, b, c, t;			/* ax + by + c = 0 */
    int squ;
    a = y1 - y2, b = x2 - x1, c = y2*x1-x2*y1;
    squ = a*a + b*b;
    if (squ == 0) return 0;
    t = (a * x) + (b * y) + c;
    t = t*t - r2*squ;
    if (t > 0) return 1;
    if (t < 0) return -1;
    return 0;
}

int main()
{
    int n, m;
    int i, dt, ds, rr;
    
    while (1) {
        scanf("%d", &n); if (!n) break;
        for (i = 0; i < n; i++) scanf("%d%d%d", x+i, y+i, &rr), r[i] = rr*rr;
        scanf("%d", &m);
        while (m-- > 0) {
            scanf("%d%d%d%d", &xt, &yt, &xs, &ys);
            for (i = 0; i < n; i++) {
                dt = (xt - x[i])*(xt - x[i]) + (yt - y[i])*(yt - y[i]);
                ds = (xs - x[i])*(xs - x[i]) + (ys - y[i])*(ys - y[i]);
                if ((dt < r[i] && ds > r[i]) || (dt > r[i] && ds < r[i])) { puts("Safe"); goto NEXT; }
                if (dt > r[i] && ds > r[i] && between(xt, yt, xs, ys, x[i], y[i]) &&
                    disCmp(xt, yt, xs, ys, x[i], y[i], r[i]) <= 0) { puts("Safe"); goto NEXT; }
            }
            puts("Danger");
        NEXT:;
        }
    }
    return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  unordered_map<string, ll> mp;
  rep(i, N) {
    cin >> S[i];
    sort(S[i].begin(), S[i].end());
    if(mp.find(S[i]) == mp.end())
      mp[S[i]] = 1;
    else
      mp[S[i]]++;
  }
  ll ans = 0;
  for(auto itr=mp.begin(); itr!=mp.end(); itr++)
    ans += itr->second * (itr->second-1) / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 17700
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>

using namespace std;

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A;
  for(int i=0; i<N; i++)
    A.push_back(0);
  for(int i=0; i<N; i++){
    int in;
    cin >> in;
    A[in-1]++;
  }
  sort(A.begin(), A.end(), greater<int>());
  cout << accumulate(A.begin()+K, A.end(), 0) << endl;
  return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
string chtostr(char ch)
{
	if(ch==' ') return "101";
	if(ch=='\'') return "000000";
	if(ch==',')	return "000011";
	if(ch=='-') return "10010001";
	if(ch=='.')	return "010001";
	if(ch=='?')	return "000001";
	if(ch=='A')	return "100101";
	if(ch=='B')	return "10011010";
	if(ch=='C')	return "0101";
	if(ch=='D')	return "0001";
	if(ch=='E')	return "110";
	if(ch=='F')	return "01001";
	if(ch=='G')	return "10011011";
	if(ch=='H') return "010000";
	if(ch=='I') return "0111";
	if(ch=='J')	return "10011000";
	if(ch=='K')	return "0110";
	if(ch=='L')	return "00100";
	if(ch=='M')	return "10011001";
	if(ch=='N')	return "10011110";
	if(ch=='O')	return "00101";
	if(ch=='P')	return "111";
	if(ch=='Q')	return "10011111";
	if(ch=='R')	return "1000";
	if(ch=='S')	return "00110";
	if(ch=='T') return "00111";
	if(ch=='U')	return "10011100";
	if(ch=='V')	return "10011101";
	if(ch=='W')	return "000010";
	if(ch=='X')	return "10010010";
	if(ch=='Y')	return "10010011";
	return "10010000";
}
char strtoch(string str)
{
	reverse(str.begin(),str.end());
	int tmp=0;
	for(int i=0;i<str.size();i++) {char ch; ch=str[i]; tmp+=pow(2,i)*(ch-'0');}
	if(tmp<=25) return ('A'+tmp);
	if(tmp==26) return ' ';
	if(tmp==27) return '.';
	if(tmp==28) return ',';
	if(tmp==29) return '-';
	if(tmp==30) return '\'';
	return '?';
}
int main()
{
	string str;
	while(getline(cin,str))
	{
		string tmp="";
		for(int i=0;i<str.size();i++) {char ch; ch=str[i]; tmp+=chtostr(ch);}
		while(tmp.size()%5) tmp+='0';
		string ans="";
		for(int i=0;i<tmp.size();i+=5) ans+=strtoch(tmp.substr(i,5));
		cout << ans << '\n';
	}
}

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

int main(){
  int n,ans=0;
  cin >> n;
  for(int i=1;i<=n;++i){
    if(i%2==0)continue;
	int b=0;
    for(int j=1;j<=i;++j){
      if(j%2==0)continue;
      if(i%j==0)b++;
    }
    if(b==8)ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
/**
 * ALDS1_5_C Koch Curve
 */

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

class Vector {
    double x;
    double y;

    Vector(double x, double y) {
        this.x = x;
        this.y = y;
    }

    void print() {
        System.out.printf("%.8f %.8f%n", this.x, this.y);
    }

}

class Main {
    static void drawCoch(int depth, Vector start, Vector goal) {
        if (depth == 0) {
            return;
        }

        Vector s = new Vector(2.0 / 3.0 * start.x + 1.0 / 3.0 * goal.x, 2.0 / 3.0 * start.y + 1.0 / 3.0 * goal.y);
        Vector u = new Vector(1.0 / 3.0 * start.x + 2.0 / 3.0 * goal.x, 1.0 / 3.0 * start.y + 2.0 / 3.0 * goal.y);
        Vector t = new Vector(1.0 / 2.0 * (goal.x + start.x) - Math.sqrt(3.0) / 6.0 * (goal.y - start.y),
                            1.0 / 2.0 * (goal.y + start.y) + Math.sqrt(3.0) / 6.0 * (goal.x - start.x));

        drawCoch(depth - 1, start, s);
        s.print();
        drawCoch(depth - 1, s, t);
        t.print();
        drawCoch(depth - 1, t, u);
        u.print();
        drawCoch(depth - 1, u, goal);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        Vector start = new Vector(0.0, 0.0);
        Vector goal = new Vector(100.0, 0.0);

        start.print();
        drawCoch(n, start, goal);
        goal.print();
    }
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int64_t n,a;
    cin >> n >> a;

    auto ok=[&](int64_t k,int64_t x){
        return powl(x,k+1)>=n;
    };
    int64_t ans=n;
    rep(i,0,64){
        int64_t lb=0,ub=n;
        while(ub-lb>1){
            int64_t m=(lb+ub)/2;
            if(ok(i,m)) ub=m;
            else lb=m;
        }
        int64_t tmp=a*i+ub*(i+1),p=powl(ub,i+1);
        while(p/ub*(ub-1)>=n){
            p=p/ub*(ub-1);
            --tmp;
        }
        ans=min(ans,tmp);
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
using namespace std;




void solve(){
   string s,s1,r;
    cin>>s>>s1;
    r = s1.substr(0,s1.size()-1);
    if (s == r){
        cout<<"Yes";
    }
    else cout<<"No";
   
}


int main(){
	fast;
	solve();
}

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

int main(void){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a+b>=c){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define llu unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define moda 998244353
#define pi 3.14159265358979323846
#define io ios::sync_with_stdio(0); cin.tie(0);
#define debug cout<<"f\n";
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(), x.rend()

ll ad(ll a, ll b)
{
    return (a%mod + b%mod)%mod;
}

int main()
{

ll h, w;
cin>>h>>w;

char a[h][w];

for(int i = 0 ; i < h ; i++)
{
    for(int j = 0 ; j < w ; j++)
    {
        cin>>a[i][j];
    }
}

ll dp[h][w];

for(int i = 0 ; i < h ; i++)
{
    for(int j = 0 ; j < w ; j++)
    {
        dp[i][j] = 0;
    }
}

dp[0][0] = 1;

for(int i = 0 ; i < h ; i++)
{
    for(int j = 0 ; j < w ; j++)
    {
        if(a[i][j] == '#')continue;
        if( i - 1 >= 0 && j - 1 < 0)dp[i][j] = dp[i - 1][j];
        if(i - 1 < 0 && j - 1 >= 0)dp[i][j] = dp[i][j - 1];
        if(i - 1 >= 0 && j - 1 >= 0)dp[i][j] = ad(dp[i - 1][j], dp[i][j - 1]);
    }
}

cout<<dp[h - 1][w - 1];

return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n,m,c;
    cin>>n>>m>>c;
    ll b[m];
    rep(0,i,m)cin>>b[i];
    ll ans=0;
    rep(0,i,n){
        ll sum=0;
        rep(0,j,m){
            ll a;
            cin>>a;
            sum+=a*b[j];
        }
        if(sum+c>0)++ans;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin >> n >> m;
  scc_graph graph(n);
  while(m--){
    int from,to;
    cin >> from >> to;
    graph.add_edge(from,to);
  }
  vector<vector<int>> ans = graph.scc();
  cout << ans.size() << '\n';
  for(auto& v : ans){
    cout << v.size();
    for(int i : v) cout << ' ' << i;
    cout << '\n';
  }
  return 0;
}

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

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

inline void normal(ll &a) { if (a >= MOD) a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) {normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) {normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) {normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; } //if MOD is prime, modPow(b, p % (MOD-1))
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

const int mx = 2e3 + 9;

ll s;
ll dp[mx];

ll solve(ll sum) {
    if (sum == 0) return 1;
    ll& ans = dp[sum];
    if (ans != -1) return ans;
    ans = 0;
    for (int i = 3; i <= s; i++) {
        if (sum - i < 0) break;
        ans = modAdd(ans, solve(sum - i));
    }

    return ans;
}

int main() {
    cin >> s;
    if (s < 3) {
        cout << 0 << endl;
        return 0;
    }

    memset(dp, -1, sizeof dp);
    ll ans = solve(s);
    cout << ans << endl;
}

Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>

using namespace std;

int main() {

    int n;
    cin >> n;

    int ans = 0;
    int ma = 0;
    for(int i=0; i<n; i++)
    {
        int p;
        cin >> p;
        ans += p;
        ma = max(ma, p);
    }

    cout << ans - ma / 2 << endl;
}

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

using namespace std;

int main()
{
  string s;
  cin >> s;
  for (int i = 1; i < s.size(); i++)
  {
    if (s[i-1] == s[i])
    {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
}

Measured memory_bytes: 256
// "include" {{{
#include <deque>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
// }}}
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

vector<int> c(550);
vector<int> s(550);
vector<int> f(550);

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	reps(i,n-1){
		cin >> c[i] >> s[i] >> f[i];
	}
	reps(i,n-1){
		int t = 0;
		t = s[i];
		for(int j = i+1;j <= n-1;j++){
			t += c[j-1];
			if(t > s[j]){
				t = s[j] + ((t - s[j]) + f[j] - 1) / f[j] * f[j];
			}
			else{
				t = s[j];
			}
		}
		cout << t + c[n-1] << '\n';
	}

	cout << 0 << '\n';

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC087A
{
    class Program
    {
        static void Main(string[] args)
        {
            var x = int.Parse(Console.ReadLine());
            var a = int.Parse(Console.ReadLine());
            var b = int.Parse(Console.ReadLine());


            x -= a;
            x %= b;

            Console.WriteLine(x);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11220
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collection;


 
public class Main{
	
        static final Scanner sc=new Scanner(System.in);
        static int a=sc.nextInt();
        static int b=sc.nextInt();
        
        
        
        
        
        public static void main(String[]args){
                if(a+b==15){
                        System.out.println("+");
                }else if(a*b==15){
                        System.out.println("*");
                }else{
                        System.out.println("x");
                }
                
                
                

        }
        
        
        

		
	
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define int long long
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }

const int N = 1e5 + 5;
int cnt[N];  
int32_t main() {

  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  cerr << fixed << setprecision(10);
  cin.tie(0);
  //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  
  int n;
  cin>>n;
  int m = n, M = 1;
  
  RE (i, n) {
    int c;
    cin>>c;
    cnt[c]++;
    maxi(M, c);
    mini(m, c);
  }
  if (M - m >= 2) {
    cout<<"No\n";
    return 0;
  }
  if (m == M) {
    if (m <= n / 2 || m == n - 1) {
      cout<<"Yes\n";
    } else {
      cout<<"No\n";
    }
  } else {
    int min_ans = cnt[m] + 1, max_ans = cnt[m] + cnt[M] / 2;
    if (min_ans <= M && M <= max_ans) {
      cout<<"Yes\n";
    } else {
      cout<<"No\n";
    }
  }
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  return 0;
}


Measured memory_bytes: 1024
require 'set'

### constant

MAX = 20

### subroutines

def count_line(line, r, c, s)
  pos = 0
  while line[pos] == '.'
    pos += 1
  end
  idt = pos
  
  while pos < line.length
    case line[pos]
    when '('
      r += 1
    when ')'
      r -= 1
    when '{'
      c += 1
    when '}'
      c -= 1
    when '['
      s += 1
    when ']'
      s -= 1
    end

    pos += 1
  end

  [idt, r, c, s]
end

### main

loop do
  pn, qn = gets.split.map(&:to_i)
  break if (pn | qn) == 0

  r = c = s = 0
  mat = []
  v = []
  
  pn.times do
    line = gets.strip

    mat << [r, c, s]
    idt, r, c, s = count_line(line, r, c, s)
    v << idt
  end
  mat.shift
  v.shift
  pn -= 1
  #p [mat, v]

  r = c = s = 0
  mat0 = []

  qn.times do
    line = gets.strip
    mat0 << [r, c, s]
    idt, r, c, s = count_line(line, r, c, s)
  end
  #p mat0

  idts = Array.new(qn){Set.new}

  for r in (1..MAX)
    for c in (1..MAX)
      for s in (1..MAX)
        ok = true
        for i in (0...pn)
          idt = mat[i][0] * r + mat[i][1] * c + mat[i][2] * s
          if idt != v[i]
            ok = false
            break
          end
        end

        if ok
          for i in (0...qn)
            idts[i] << mat0[i][0] * r + mat0[i][1] * c + mat0[i][2] * s
          end
        end
      end
    end
  end
  #p idts

  puts idts.map{|is| is.size != 1 ? -1 : is.first}.join(' ')
end

Measured memory_bytes: 6204
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976
#define MAX_N 100010

lint b;
lint dig(lint a){//桁数を返す
	lint re=0;
	while(a)++re,b=a,a/=10;
	return re;
}

int main(){
	lint n;cin>>n;++n;
	cout<<9*(dig(n)-1)+b-1<<endl;
}

//int main(){//平方数を1<k<=nで割ったあまりを求める
//	lint n;cin>>n;
//	LIV ans(n);
//	for(int i=1;i<=n;++i){
//		set<int> s;
//		rep(x,i)s.insert(x*x%i);
//		cout<<i<<": ";
//		for(auto x:s)cout<<x<<",";cout<<endl;
//		ans[i-1]=s.size();
//	}rep(i,n)cout<<ans[i]<<endl;
//	getchar();
//	getchar();
//}

//sub-EOF


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, a, b) for(int i = a; i >= b; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const int INF = 1e9;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
int main() {
    int N;
    cin >> N;
    int h[N];
    int dp[N];
    REP(i, N) {
        cin >> h[i];
        dp[i] = INF;
    }
    dp[0] = 0;
    FOR(i, 1, N) {
        chmin(dp[i], dp[i-1]+abs(h[i] - h[i-1]));
        if(i > 1) chmin(dp[i], dp[i-2]+abs(h[i] - h[i-2]));
    }
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define req(i,n,m) for(int i=n;i<m;i++)
#define REQ(i,n,m,l) for(int i=n;i<m;i+=l) 
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
signed gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
signed lcm(int x, int y) {
    return x / gcd(x, y) * y;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main() {
    int N, M, X; cin >> N >> M >> X;
    vector<int>A(M);
    int low=0;
    int high = 0;
    rep(i, M) {
        cin >> A[i];
        if (X > A[i])low++;
        else high++;
    }
    cout << min(low, high) << endl;
}

Measured memory_bytes: 3600
#include<stdio.h>
#define N 100

int min(int a,int b){
  if(a>b) return b;
  if(a<b) return a;
}
int main(){
  int n,p[N+1],m[N+1][N+1];
  int i,j,k,l;

  scanf("%d",&n);
  for(i = 1;i <= n;i++){
    scanf("%d",&p[i - 1]);
    scanf("%d",&p[i]);
  }

  for(i = 1;i <= n;i++) m[i][i] = 0;
  
  for(l = 2;l <= n;l++){

    for(i = 1;i <= n-l+1;i++){
      j = i + l -1;
      m[i][j] = (1<<21);
      for(k = i; k<= j-1;k++){
	m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] + p[i-1]*p[k]*p[j]);
      }
    }
  }
  
  printf("%d\n",m[1][n]);

  return 0;
}



Measured memory_bytes: 2052
//       Author: Mostafa Mounir Shehab
 
#include <bits/stdc++.h>
using namespace std;
 
#define PI  acos(-1)
#define EPS (1e-10)
#define endl "\n"
#define SZ(v) (int)(v.size())
#define IO ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);
typedef long long ll;
typedef long double ld;
 

 
ll MOD=1e9 + 7;
ll OO=1e10;
const int N=3e3 + 5,M=1e5 + 5;
int arr[N];
ll dp[N][N][2];


int n,m,k,cnt,SU,idx,len,MN,MX,T;
int l,r,mid;
int a,b,c;

ll Solve(int l,int r,bool player){
	
	if(l>r)
		return 0;
	
	ll &ret = dp[l][r][player];
	if(~ret)
		return ret;
	
	if(player)	
		ret = max(arr[l] + Solve(l+1,r,!player),arr[r] + Solve(l,r-1,!player));
	else
		ret = min(-arr[l] + Solve(l+1,r,!player),-arr[r] + Solve(l,r-1,!player));
	
	return ret;
}



int main(){
	IO
	
	memset(dp,-1,sizeof dp);
	cin>>n;
	for(int i=0;i<n;++i)
		cin>>arr[i];
	
	cout<<Solve(0,n-1,1)<<endl;
		
	
	

}





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

using namespace std;
 
int main() {
  int N;
  cin >> N;
  if(N<10) cout << N <<endl;
  else if(N<100) cout << 9 <<endl;
  else if(N<1000) cout << 9+N-99 <<endl;
  else if(N<10000) cout << 909 <<endl;
  else if(N<100000) cout << 909+N-9999 <<endl;
  else cout << 90909 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[55];
int main()
{
	long long k;
	scanf("%lld",&k);
	for(int i=1;i<=50;i++)
	{
		a[i]=k/50+i-1;
	}
	k%=50;
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=50;j++)
		a[j]--;
		a[i]+=51;
	}
	printf("50\n");
	for(int i=1;i<=50;i++)
	{
		printf("%lld",a[i]);
		if(i!=50)
		printf(" ");
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int n, i, j, k, s;
	cin >> n;
	vector<int> a(n);
	for (i = 0; i < n; i++) cin >> a[i];
	sort(a.rbegin(), a.rend());
	s = 0;
	for (i = 0; i < n; i++) {
		if (i % 2 == 0) s += a[i];
		else s -= a[i];
	}
	cout << s << "\n";

	return 0;
}


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

const long long INF=1e18+5;
int main()
{
    int n;
    cin>>n;
    long long a[402];
    for(int i=0;i<n;i++)
        cin>>a[i];
    long long dp[402][402];
    for(int i=0;i<402;i++)
    {
        for(int j=0;j<402;j++)
            dp[i][j]=INF;
    }
    auto sum=[&](int l,int r){
        long long sum=0;
        for(int i=l;i<=r;i++)
            sum+=a[i];
        return sum;
    };
    for(int l=n-1;l>=0;l--)
    {
        for(int r=l;r<n;r++)
        {
            if(l==r)   
                dp[l][r]=0;
            else
            {
                long long s=sum(l,r);
                for(int i=l;i<r;i++)
                {
                    dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+s);
                }
            }
        }
    }
    cout<<dp[0][n-1];
}

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

int main(){
    int x, y;
    int c[13] = {0,1,3,1,2,1,2,1,1,2,1,2,1};
    cin >> x >> y;
    if(c[x] == c[y]){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int n,ok,x;
int main()
{
    cin>>n;
    ok=1;
    while(n)
    {
        cin>>x;
        if(x%2==0 && !(x%5==0 || x%3==0))
            ok=0;
        n--;
    }
    if(ok)
        cout<<"APPROVED"<<'\n';
    else cout<<"DENIED"<<'\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
bool used[100005][3][3];
int main(){
  ll h,w,n;
  cin>>h>>w>>n;
  for(int i=0;i<100005;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++) used[i][j][k]=false;
    }
  }
  map<P,ll> mp;
  vector<P> vec;
  for(int i=0;i<n;i++){
    ll x,y;
    cin>>x>>y;
    vec.push_back(P(x,y));
    mp[P(x,y)]=i;
  }
  ll ans[10]={0};
  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(used[i][j][k]) continue;
        ll sx=vec[i].first-j,sy=vec[i].second-k;
        if(sx<=0||sy<=0||sx+2>h||sy+2>w) continue;
        ll kans=0;
        for(int p=0;p<3;p++){
          for(int q=0;q<3;q++){
            if(mp.find(P(sx+p,sy+q))!=mp.end()){
              kans++;
              used[mp[P(sx+p,sy+q)]][p][q]=true;
            }
          }
        }
        ans[kans]++;
      }
    }
  }
  ans[0]=(h-2)*(w-2);
  for(int i=1;i<10;i++) ans[0]-=ans[i];
  for(int i=0;i<10;i++) cout<<ans[i]<<endl;
}


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

class UnionFind{
    vector<int>p,sz;
public:
    UnionFind(int n){
        p.resize(n,-1);
        sz.resize(n,1);
    }
    int find(int x){
        if(p[x] == -1)return x;
        else return p[x] = find(p[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return;
        if(sz[x] > sz[y])swap(x,y);
        p[x] = y;
        sz[y] += sz[x];
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

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

int main(){
    int h,w;
    cin>>h>>w;
    vector<string>s(h);
    rep(i,h)cin>>s[i];
    UnionFind uf(h*w);
    rep(i,h)rep(j,w){
        rep(dir,4){
            int vy=i+dy[dir];
            int vx=j+dx[dir];
            if(vy<0||vy>=h||vx<0||vx>=w)continue;
            if(s[i][j]!=s[vy][vx])uf.unite(i*w+j,vy*w+vx);
        }
    }
    map<int,int>all,black;
    rep(i,h)rep(j,w){
        all[uf.find(i*w+j)]++;
        if(s[i][j]=='#')black[uf.find(i*w+j)]++;
    }
    ll ans=0;
    for(auto& p:all){
        ans+=(ll)(p.second-black[p.first])*black[p.first];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 17564
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

ans = 0
log = ["*"]*N
win = {"r":"p","s":"r","p":"s"}
score = {"r":P,"s":R,"p":S}
for i,t in enumerate(T):
    if log[i-K]==win[t]: continue
    log[i] = win[t]
    ans += score[t]
print(ans)

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

int main() {
	int n,a,count=0,sum=0;
	cin>>n;
	if(n/10==0){
	    cout<<n<<'\n';
	}
	else if(n/10<10){
	    cout<<9<<'\n';
	}
	else if(n/10<100){
	    cout<<n-90<<'\n';
	}
	else if(n/10<1000){
	    cout<<999-90<<'\n';
	}
	else if(n/10<10000){
	    cout<<n-9000-90<<'\n';
	}
	else if(n/10<100000){
	    cout<<99999-9000-90<<'\n';
	}
	return(0);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll sum;
int main()
{
 cin>>n;
 for(int a=1;a<=n;a++)
    for(int b=1;b<=n;b++)
     for(int c=1;c<=n;c++)
 {
 	sum+=__gcd(a,__gcd(b,c));
 }
 cout<<sum;
return 0;
}


Measured memory_bytes: 3656
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0
count += sum(B)
for i in range(n-1):
    if A[i+1] - A[i] == 1:
        count += C[A[i]-1]
print(count)

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    string sum = a + b + c;
    int s = stoi(sum);
    if(s%4 == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;



    return 0;
}


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

int main() {
    int n; cin >> n;
    string s = to_string(n);
    if (s[0] == '7' || s[1] == '7' || s[2] == '7') {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3696
N =int(input())
L = list(map(int, input().split()))

#print(L)
cnt = 0
for i in range(N-2):
  for j in range(i,N-1):
    for k in range(j,N):
      if L[i] ==L[j] or L[j]==L[k] or L[i]==L[k]:
        continue
      elif L[i] + L[j] > L[k] and L[k] >abs(L[i] - L[j]):
        cnt +=1
        #print(i,j,k)

print(cnt)

Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
const long long INF = 1LL<<60;
#define pairint pair<int,int>
signed main(){
  int x=0,y=0,z=0,n=0;
  double w=0;
vector<int> v;
  std::cin >> x>>y;
  rep(i,x){
    std::cin >> z;
    v.pb(z);
    w+=z;
  }
  w/=4*y;
  sort(rall(v));
  rep(i,y){
    if(v[i]<w){
      std::cout << "No" << '\n';
      return 0;
    }
  }
  std::cout << "Yes" << '\n';
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
int main(){
  int h,w;
  while(cin >> h >> w,h){
    REP(i,h){
      REP(j,w) cout << '#';
      puts("");
    }
    puts("");
  }
}


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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll>p;
    for(ll i=1; i*i<=m; i++){
        if(m%i==0){
            p.push_back(i);
            if(m!=i*i)p.push_back(m/i);
        }
    }
    sort(p.begin(),p.end(),greater<ll>());
    rep(i, 0, p.size()){
        if(p[i]*n<=m){
            cout << p[i] << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
ll inf=LLONG_MAX,mod=1000000007,BS,k;

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif
        ll n,k,d;
        cin>>n>>k>>d;
        // if(abs(n)/d<=k){
        //     if(n<0)
        //     n+=k*d;
        //     else
        //     n-=k*d;
        //
        // }
        // else{
            ll num=min(k,abs(n)/d);
            if(n<0)
            n+=num*d;
            else
            n-=num*d;
            k-=num;
            if(k){
            if(k%2){
                if(n<0){
                    n+=d;
                }
                else{
                    n-=d;
                }
            }
            }
        // }
        cout<<abs(n);

}


Measured memory_bytes: 3660
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int a[3];
    int cnt=0;
    rep(i,0,2){
        cin>>a[i];
    }
    rep(i,0,2){
        rep(j,i+1,2){
            if(a[i]!=a[j]) cnt++;
        }
    }
    if(cnt==0) cout<<'1'<<endl;
    else cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
N, M, s, t = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
    E[y].append(x)

closed = [False] * (N+1)
closed[s] = True
dist = [float("inf")] * (N+1)
q = [s]
for dist_ in range(N):
    q_new = []
    for v in q:
        dist[v] = dist_
        for u in E[v]:
            if closed[u]:
                continue
            closed[u] = True
            q_new.append(u)

    q = q_new
    if len(q) == 0:
        break

dist_st = dist[t]

closed = [False] * (N+1)
closed[t] = True
dist_t = [float("inf")] * (N+1)
q = [t]
for dist_ in range(N):
    q_new = []
    for v in q:
        dist_t[v] = dist_
        for u in E[v]:
            if closed[u]:
                continue
            closed[u] = True
            q_new.append(u)

    q = q_new
    if len(q) == 0:
        break
ds = [0] * (dist_st-1)
dt = [0] * (dist_st-1)
for d in dist:
    if d < (dist_st-1):
        ds[d] += 1
for d in dist_t:
    if d < (dist_st-1):
        dt[d] += 1

ans = 0
for a, b in zip(ds, dt[::-1]):
    ans += a*b
print(ans)



Measured memory_bytes: 32908
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define N 200010
#define M 1010

using namespace std;
const int mod = 1e9 + 7;
int sum[N], a[N], n;

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

signed main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read(), sum[i] = (sum[i - 1] + a[i]) % mod;
	int ans = 0;
	for (int i = 1; i <= n - 1; i++) {
		int xx = (sum[n] - sum[i] + mod) % mod;
		ans = (ans + (a[i] * xx) % mod) % mod;
	}
	cout << ans << "\n";
}

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

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

  int max = 0;
  int sum = 0;
  for (int i = 0; i < N; i++) {
    int l;
    cin >> l;

    sum += l;
    if (l > max) max = l;
  }

  sum -= max;
  if (max >= sum) {cout << "No" << endl;}
  else {cout << "Yes" << endl;}
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

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

    ll ans = (ll)n*(n-1)/2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector< pair<long long,long long> >v;
vector<long long>ans;
void go(int idx,long long int num)
{
    //cout<<idx<<" "<<num<<endl;
    if(idx>=v.size())
    {
        ans.push_back(num);
        return ;
    }
    int i;
    long long g=1;
    go(idx+1,num);
    for(i=0;i<v[idx].second;i++)
    {
        g*=v[idx].first;
        go(idx+1,g*num);
    }
}
int main()
{
    long long n,r;
    cin>>n;
    r=n;
    long long i;
    for(i=2;i*i<=n;i++)
    {
        int c=0;
        while(n%i==0)
        {
            n/=i;
            c++;
        }
        if(c>=1)
        {
            v.push_back(make_pair(i,c));
        }
    }
    if(n>1)
    {
        v.push_back(make_pair(n,1));
    }
    go(0,1);
    long long s=0;
    long long flag=0;
    for(i=0;i<ans.size();i++)
    {
        if(ans[i]==1)
            continue;
        long long gg=ans[i]-1;
        long long hh=r/(ans[i]-1);
        if((hh*gg+hh)==r)
            s+=(ans[i]-1);
    }
    cout<<s-flag<<endl;
}


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

int a,b[110];
  
  cin >> a;
  string s;
  cin >> s;
  
 if(a<3200){
   cout << "red" << endl;
   return 0;
 }
  
  else{
    cout << s << endl;
  }
  
}


Measured memory_bytes: 256
import math
N,D = map(int,input().split())
X = [list(map(int,input().split())) for i in range(N)]
buf_1 = 0
buf_2 = 0

for i in range(N) :
    for j in range(i+1,N) :
        for k in range(D) :
            buf_1 += (X[i][k] - X[j][k])**2
        if math.sqrt(buf_1) - int(math.sqrt(buf_1)) == 0 :
            buf_2 += 1
        buf_1 = 0
print(buf_2)

Measured memory_bytes: 3064
#include<stdio.h>
#include<climits>

int k = 0;

void Merge(long* a, int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	long* L = new long[n1+1];
	long* R = new long[n2+1];
	for ( int i = 0; i < n1; i++) L[i] = a[left + i];
	L[n1] = LONG_MAX;
	for (int i = 0; i < n2; i++) R[i] = a[mid + i];
	R[n2] = LONG_MAX;
	int i = 0;
	int j = 0;
	while(i < n1 || j < n2){
		if (L[i] <= R[j]){
			a[left + i + j] = L[i];
			i++;
			k++;
		}
		else{
			a[left + i + j] = R[j];
			j++;
			k++;
		}
	}
}

void MergeSort(long* a, int left, int right){
	if (left + 1 < right){
		int mid = (left + right) / 2;
		MergeSort(a, left, mid);
		MergeSort(a, mid, right);
		Merge(a, left, mid, right);
	}
}

int main(){
	int n = 0;
	scanf("%d", &n);
	long* a = new long[n];
	for (int i = 0; i < n; i++) scanf("%ld", &a[i]);
	MergeSort(a, 0, n);
	for ( int i = 0; i < n; i++){
		printf("%ld", a[i]);
		if (i != n-1) printf(" ");
	}
	printf("\n");
	printf("%d\n", k);
}


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

int main() {
  int K, S, a=0, cnt=0;
  cin >> K >> S;
  for (int x=0; x<=K; x++){
    if (x>S) break;
    else if (x+K+K<S) continue;
    for (int y=0; y<=K; y++){
      if (x+y>S) break;
      else if (x+y+K<S) continue;
      else cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

mod = 1000000007  # type: int


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return (numerator * pow(denominator, mod - 2, mod)) % mod


def solve(X: int, Y: int):
    n = (2 * Y - X) / 3
    m = (2 * X - Y) / 3

    if n < 0 or m < 0 or (X + Y) % 3 != 0:
        print(0)
    else:
        result = comb_mod(int(n + m), int(n), mod)
        print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064