akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let mut m = 0;
    let mut a = 0;
    let mut r = 0;
    let mut c = 0;
    let mut h = 0;

    for _ in 0..n {
        let s = sc.next_chars();
        match s[0] {
            'M' => m += 1,
            'A' => a += 1,
            'R' => r += 1,
            'C' => c += 1,
            'H' => h += 1,
            _ => (),
        }
    }

    let v = [m, a, r, c, h];
    let mut ans = 0usize;
    for i in 0..5 {
        for j in i + 1..5 {
            for k in j + 1..5 {
                ans += v[i] * v[j] * v[k];
            }
        }
    }

    println!("{}", ans);
}

pub struct Scanner {
    buf: std::collections::VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: std::collections::VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: std::str::FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn next_char(&mut self) -> char {
        self.next()
    }

    pub fn next_float(&mut self) -> f64 {
        self.next()
    }
}


Measured memory_bytes: 2224
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N;
set<int> SET[26];
char buf[500005];


int main(){

	scanf("%d",&N);
	scanf("%s",buf);

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

		SET[buf[i]-'a'].insert(i+1);
	}

	int num_query;
	scanf("%d",&num_query);

	int command,loc,L,R;
	char work[2];

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d",&command);

		if(command == 1){

			scanf("%d %s",&loc,work);

			SET[buf[loc-1]-'a'].erase(loc);
			SET[work[0]-'a'].insert(loc);

			buf[loc-1] = work[0];

		}else{

			scanf("%d %d",&L,&R);

			int count = 0;
			for(int i = 0; i < 26; i++){

				std::set<int>::iterator it = SET[i].lower_bound(L);

				if(*it >= L && *it <= R){

					count++;
				}
			}
			printf("%d\n",count);
		}
	}
	return 0;
}


Measured memory_bytes: 24192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
main()
{
    ll n,k,e,i,j,mn=14e10;
    vector<ll> v;
    cin >> n >> k;
    for(i=1; i<=n; i++)
    {
        cin >> e;
        v.push_back(e);
    }
    sort(v.begin(),v.end());
    for(i=0, j=k-1; j<n; j++,i++)
    {
        mn = min(mn, v[j]-v[i]);
    }
    cout << mn << endl;
}


Measured memory_bytes: 1400
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
 
int main(int argc, char* argv[])
{
    long a, b;
    scanf("%ld %ld", &a, &b);

    if(a<=8 && b<=8) {
        printf("Yay!\n");
    }
    else {
        printf(":(\n");
    }
 
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
#include <math.h>
#include <cctype>
using namespace std;
#define int long long
#define forn(i, n) for (int i = 0; i < n; ++i)
int32_t main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s[0]== toupper(s[0]))
        cout << "A\n";
    else
        cout << "a\n";
    return 0;
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		int n = sc.nextInt();
		int l = sc.nextInt();
		int[] a = new int[n];
		for (int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		int b = last(a,l);
		if (b==-1) {
			System.out.println("Impossible");
		} else {
			System.out.println("Possible");
			for (int i=0;i<b;i++) {
				System.out.println(i+1);
			}
			for (int i=n-2;i>b;i--) {
				System.out.println(i+1);
			}
			System.out.println(b+1);
		}
	}

	static int last(int[] a, int l) {
		for (int i=0;i<a.length-1;i++) {
			if(a[i]+a[i+1] >= l) {
				return i;
			}
		}

		return -1;
	}

}


Measured memory_bytes: 63168
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define mem(a,x) memset((a),x,sizeof (a))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const int maxn=100+10;
char s[maxn];
int main() {
#ifdef _DEBUG
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    LL k;
    while(cin>>s>>k){
        LL p=0;
        int i=0;
        int len=strlen(s);
        char c=s[i];
        p=c=='1'?1:LLINF;
        while(i<len&&p<k){
            c = s[++i];
            if(c!='1') p=LLINF;
            else {
                p ++;
            }
        }
        cout<<c<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
using System;

namespace ContestJP
{
    class Program
    {
        static void Main(string[] args)
        {
            String s = Console.ReadLine();
            String s1 = s.Substring(0, 4);
            String s2 = s.Substring(4, 8);

            Console.WriteLine(s1 + " " + s2);
        }
    }
}

Measured memory_bytes: 2648
#include "bits/stdc++.h"
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


const int NM = 100000;


void solve() {
    ll a,b,c;
    cin >> a >> b >> c;

    ll tmp = c-b-a;


    if (tmp > 0 && (4*a*b < (tmp * tmp)) ) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}



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







Measured memory_bytes: 256
/* ex3_3
   seira3 */

#include<stdio.h>
#include<stdlib.h>

int main(void){
    int N, K; //変数宣言
    scanf("%d %d",&N,&K); //入力
    int count = 0; //割れた回数をカウントする変数を宣言
    while(N>0){ //割れた回数をカウントするwhile文
        N = N/K; //割る
        count++; //countに1を足す
    }
    printf("%d\n",count); //答えであるcountを出力
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(void){
    int N = 0;
    string S;
    cin >> N;
    cin >> S;
  	int A = S.size();
  	int R = min(A , N);
    for(int i = 0; i < R; i++){
        cout << S.at(i);
    }
    if(S.size() > N){
        cout << "...";
    }
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    REP(i, 8) {
        if ("keyence" == s.substr(0, i) + s.substr(n - 7 + i, 7 - i)) {
            cout << "YES" << EOL;
            return;
        }
    }
    cout << "NO" << EOL;
}



Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
  
// Driver program to test methods of graph class 
int main() 
{
    long long n,k,q;
    cin >> n >> k >> q;
    
    vector<int> b(n);
    for(int i = 0; i < q; i++){
        int tmp;
        cin >> tmp;
        b.at(tmp - 1)++;
    }
    
    
    for(int i= 0; i < n; i++){
        if(k +  b.at(i) - q > 0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 1024
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = floyd_warshall(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))


Measured memory_bytes: 28740
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
S = input()


S += 'X'
Zero_begin = []

begin_checked = False
for i, s in enumerate(S):
    if not begin_checked:
        if s == '0':
            Zero_begin.append(i)
            begin_checked = True

    else:
        if s != '0':
            begin_checked = False


Zero_begin.append(N)
ans = 0
for i in range(N):
    if (i == 0) or (S[i] == '1'):
        left_i = bisect_left(Zero_begin, i)
        right_i = min(left_i + K, len(Zero_begin) - 1)
        ans = max(ans, Zero_begin[right_i] - i)

print(ans)


Measured memory_bytes: 5236
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W,M=LI()
  h=[0]*H
  w=[0]*W
  d={}
  for _ in range(M):
    a,b=LI()
    a-=1
    b-=1
    h[a]+=1
    w[b]+=1
    d[(a,b)]=1

  h_koho=[]
  w_koho=[]

  h_max=max(h)
  w_max=max(w)

  for i,x in enumerate(h):
    if x==h_max:
      h_koho.append(i)
  for i,x in enumerate(w):
    if x==w_max:
      w_koho.append(i)

  for x in h_koho:
    for y in w_koho:
      if (x,y) not in d:
        return h_max+w_max

  return h_max+w_max-1

# main()
print(main())


Measured memory_bytes: 87148
from collections import defaultdict
import bisect
N, M = map(int, input().split())
PY = []
PYd = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    PYd[x].append(y)
    PY.append((x,y))

for i in PYd.keys():
    PYd[i].sort()

for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(bisect.bisect(PYd[p],y)).zfill(6)
    print(str_p + index)

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

#define int long long
#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) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

std::vector<long long> get_divisors(long long n) {
    std::vector<long long> ret;
    long long i;
    for (i = 1; i * i < n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            ret.push_back(n / i);
        }
    }
    if (i * i == n) { ret.push_back(i); }
    std::sort(ret.begin(), ret.end());
    return ret;
}

int N;
signed main() {
    cin >> N;
    int ans = get_divisors(N - 1).size() - 1;
    vint v = get_divisors(N);
    for (int i = 1; i < v.size(); i++) {
        int cur = N;
        while (cur % v[i] == 0) { cur /= v[i]; }
        if (cur % v[i] == 1) { ans++; }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

class card{
    public:
        int val;
        bool remain;
};

int main(int argc, const char * argv[]) {
    
    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    vector<card> a;
    
    cin >> N;
    int i;
    card temp_card;
    for(i=0;i<N;i++){
        cin >> temp_card.val;
        temp_card.remain = true;
        a.push_back(temp_card);
    }
    
    int remain = N;
    int max;
    int max_id;
    int Alice=0;
    int Bob=0;
    bool turn_Alice = true;
    
    while(remain>0){
        max=0;
        max_id = -1;
        for(i=0;i<N;i++){
            if(a[i].remain && a[i].val > max){
                max = a[i].val;
                max_id = i;
            }
        }
        a[max_id].remain=false;
        remain = remain - 1;
        if(turn_Alice)
            Alice += a[max_id].val;
        else
            Bob += a[max_id].val;
        turn_Alice = !turn_Alice;
    }
    
    cout << Alice - Bob << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main () {
  int N;
  cin >> N;
  vector<LL>A(N);
  vector<LL>B(N);
  vector<LL>dis(N);
  for (int i = 0; i < N; i ++) cin >> A[i];
  for (int i = 0; i < N; i ++) cin >> B[i];
  for (int i = 0; i < N; i ++) dis[i] = A[i] - B[i];
  sort(dis.begin(), dis.end());
  LL k = 0;
  int i = 0;
  while(dis[i] < 0) {
    k += dis[i];
    i ++;
  }
  int ans = i;
  for (int j = N - 1; j >= i; j --) {
    if (k >= 0) {
      cout << ans << endl;
      return 0;
    }
    k += dis[j];
    ans ++;
  }
  if (k >= 0) cout << ans << endl;
  else cout << -1 << endl;
}
  


Measured memory_bytes: 2560
#include <iostream>

using namespace std;


int main()
{
  int N;
  double a[101];
  double ave = 0;
  int ans=0;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    ave += a[i];
  }
  ave /= N;
  for(int i = 1; i < N; i++)
    {
      if(max(a[i] - ave, ave - a[i]) < max(a[ans] -ave, ave - a[ans]) )
	{
	  ans = i;
	}
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)


Measured memory_bytes: 93708
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int main(){
  string s;
  cin>>s;
  for(int i=0;i<int(s.size());i++){
    if(s[i]==',') s[i]=' ';
  }
  cout<<s<<endl;
  return 0;
}


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

int main(){
    int N,D;
    float x,y;
    int count=0;
    scanf("%d %d",&N,&D);
    while(N--){
        scanf("%f %f",&x,&y);
        if(sqrt(pow(x,2)+pow(y,2))<=D)
            count++;
    }
    printf("%d\n",count);
}

Measured memory_bytes: 2204
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {

    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    input!{
        n: u64,
        ans_arr: [chars; n]
    }
    use std::collections::HashMap;
    let mut ans_dict = HashMap::new();
    ans_dict.insert(String::from("AC"), 0);
    ans_dict.insert(String::from("WA"), 0);
    ans_dict.insert(String::from("TLE"), 0);
    ans_dict.insert(String::from("RE"), 0);

    for v in ans_arr{
        let s: String= v.iter().collect();
        let count = ans_dict.entry(s).or_insert(0);
        *count += 1;
    }

    println!("AC x {}",ans_dict["AC"]);
    println!("WA x {}",ans_dict["WA"]);
    println!("TLE x {}",ans_dict["TLE"]);
    println!("RE x {}",ans_dict["RE"]);
}


Measured memory_bytes: 7792
#include<stdio.h>
long long t[100],temp,m,q,c;
int main()
{
	int n,i;
	while(~scanf("%d",&n))
	{
		for(i=0;i<n;i++)
		{
			scanf("%lld",&t[i]);
		}
		temp=t[0];
		for(i=1;i<n;i++)
		{
			c=1;
			m=temp;q=t[i];
			while(c!=0)
			{
			    c=t[i]%temp;
			    t[i]=temp;
			    temp=c;
			}
			temp=m/t[i]*q;
		}
		printf("%lld\n",temp);
	}
} 


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

int n_query = 0;

int ask(int y1, int x1, int y2, int x2)
{
	++n_query;
	printf("? %d %d %d %d\n", y1, x1, y2 - 1, x2 - 1);
	fflush(stdout);
	int a;
	scanf("%d", &a);
	return a;
}

int score(int q)
{
	if (q > 2500) return 0;
	if (q >= 930) return max((int)(1e-8 + 125 - 3.2 * sqrt(q - 920)), 40);
	if (q >= 880) return (int)(1e-8 + 288 - 22 * sqrt(q - 870));
	return min(2860 - 3 * q, 300);
}

int H, W, N, K;
int C[50][50];

void solve(int y1, int x1, int y2, int x2, int cnt)
{
	if (y2 - y1 == 1 && x2 - x1 == 1) {
		C[y1][x1] = cnt;
		return;
	}
	if (cnt == 0) return;
	if ((y2 - y1) * (x2 - x1) == cnt) {
		for (int i = y1; i < y2; ++i) {
			for (int j = x1; j < x2; ++j) {
				C[i][j] = 1;
			}
		}
		return;
	}

	bool y_first = false;
	if ((y2 - y1) % 2 == (x2 - x1) % 2) {
		if (y2 - y1 > x2 - x1) y_first = true;
	} else if ((y2 - y1) % 2 == 0) y_first = true;

	if (y_first) {
		int ym = (y2 + y1) / 2;
		int a = ask(y1, x1, ym, x2);
		solve(y1, x1, ym, x2, a);
		solve(ym, x1, y2, x2, cnt - a);
	} else {
		int xm = (x2 + x1) / 2;
		int a = ask(y1, x1, y2, xm);
		solve(y1, x1, y2, xm, a);
		solve(y1, xm, y2, x2, cnt - a);
	}
}

int main()
{
	scanf("%d%d%d%d", &H, &W, &N, &K);
	solve(0, 0, H, W, N);

	int ret = 0;
	int pw = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			ret += C[i][j] * pw;
			ret %= K;
			pw = pw * 2 % K;
		}
	}
	int aa = ask(15, 15, 35, 45);
	while (score(n_query) > aa) ask(0, 0, 1, 1);

//	if (aa != 69 && aa != 76 && aa != 78 && aa != 59 && aa != 63) return 0;

	printf("! %d\n", ret);
	return 0;
}


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


void solve(ll N, vector<ll> A, vector<ll> B)
{
    ll ans = 0;
    ll need = 0;
    vector<ll> beyond;
    for(int i=0;i<A.size();++i)
    {
        if(A[i] < B[i])
        {
            ans++;
            need += B[i] - A[i];
        }else
        {
            if(A[i] > B[i])
            {
                beyond.push_back(A[i]-B[i]);
            }
        }
    }
    sort(beyond.begin(),beyond.end(),greater<int>());
    for(int i=0;i<beyond.size() && need > 0;++i)
    {
        need-=beyond[i];
        ans ++;
        if(need < 0)
        {
            break;
        }
    }
    if(need > 0)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
}


int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0 ; i < N ; i++)
    {
        cin >> A[i];
    }
    vector<ll> B(N);
    for(int i = 0 ; i < N ; i++)
    {
        cin >> B[i];
    }
    solve(N, move(A), move(B));
    return 0;
}


Measured memory_bytes: 2428
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
using namespace std;

map<int,string>m;

//'Q'这个无害的字母在四个字母里代表都ok
long long dp[100][5][5][5];//i,j,k,l分别表示在i的位置上字母为j，i-1的位置上字母表示为a,i-2的位置上字母表示b
bool isok(int  a,int b,int c,int d)//a,b,c,d表示从左到右四个字母
{
    if(m[a]+m[b]+m[d]=="AGC")
        return 0;
    if(m[a]+m[c]+m[d]=="AGC")
        return 0;
    if(m[b]+m[c]+m[d]=="AGC")
        return 0;
    if(m[b]+m[c]+m[d]=="GAC")
        return 0;
    if(m[a]+m[b]+m[c]=="ACG")
        return 0;
    if(m[b]+m[c]+m[d]=="ACG")
        return 0;
    return 1;
}
int main()
{
    m[0]='Q',m[1]='A',m[2]='G',m[3]='C',m[4]='T';//用map一一对应的性质用数字表示字母
    int n;
    cin>>n;
    dp[0][0][0][0]=1;
    for(int i=1; i<=n; i++) //从i=1的位置开始
    {
        for(int j=1; j<=4; j++) //i的位置的字母是m[j]也就是j
        {
            for(int a=0; a<=4; a++) //i-1的位置是m[a]
            {
                for(int b=0; b<=4; b++)//i-2的位置是m[b]
                {
                    for(int l=0; l<=4; l++) //i-3的位置是m[l]
                    {
                        if(isok(l,b,a,j))
                        dp[i][j][a][b]=(dp[i][j][a][b]+dp[i-1][a][b][l])%1000000007;
                    }
                }
            }

        }
    }
    long long ans=0;
    for(int a=1;a<=4;a++)
    {
        for(int b=1;b<=4;b++)
        {
            for(int c=1;c<=4;c++)
            {
                ans=(ans+dp[n][a][b][c])%1000000007;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 384
n = int(input())
xu = []
for _ in range(n):
    x, u = map(str, input().split())
    xu.append((float(x), u))

ans = 0
for i in xu:
    if i[1] == "JPY":
        ans += i[0]
    else:
        ans += i[0] * 380000

print(ans)

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

struct Edge{
  int to,id;
};

vector<vector<Edge>>g;
vector<int>ans;

void dfs(int v,int c = -1,int p = -1){
  int k = 1;
  rep(i,0,g[v].size()){
    int u = g[v][i].to,ei = g[v][i].id;
    if(p == u) continue;
    if(k == c) k++;
    ans[ei] = k;
    k++;
    dfs(u,ans[ei],v);
  }
}
    

int main() {
  int n;
  cin >> n;
  g.resize(n);
  ans.resize(n-1);
  rep(i,0,n-1){
    int a,b;
    cin >> a >> b;
    --a;--b;
    g[a].push_back((Edge){b,i});
    g[b].push_back((Edge){a,i});
  }
  dfs(0);
  int mx = 0;
  rep(i,0,n) mx = max(mx,int(g[i].size()));
  cout << mx << endl;
  rep(i,0,n-1) cout << ans[i] << endl;
}

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

int main(void) {
	string s; cin >> s;
	int i;
	char j;
	for (j = 'a'; j <= 'z'; j++) {
		for (i = 0; i < s.size(); i++) {
			if (s[i] == j) {
				break;
			}
		}
		if (i == s.size()) { cout << j << endl; return 0; }
	}

	cout << "None" << endl;

	return 0;
}



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

int main(){
  long N;
  int c=0;
  cin >> N;
  for(long h=N/4;h<=3500;h++){
    for(long n=N/4;n<=3500;n++){
      if(4*h*n-N*n-h*N>0&&N*h*n%(4*h*n-N*n-h*N)==0&&c==0){
        cout << h <<' '<< n <<' '<< N*h*n/(4*h*n-N*n-h*N) << endl;
        c = 1;
      }
    }
  }
}

Measured memory_bytes: 256
//#pragma GCC optimize("trapv")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
#include<bits/stdc++.h>
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pb push_back
#include <x86intrin.h>
#define pb push_back
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
using ld = long double;
const int maxn = 5e5 + 55, mod = 1e9 + 7 , i2 = (mod+1)/2;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int tree[2*maxn], n;
string s;
void init() {
	cin >>n >> s;
	for(int i = 0; i < n; i++) tree[n+i] = 1<<(s[i]-'a');
	for(int i = n; i--;) tree[i] = tree[i+i]|tree[i+i+1];
}
int upd(int i, int v) {
	for(tree[i+=n] = v; i>>=1;) tree[i] = tree[i<<1]|tree[i<<1|1];
}
int get(int l, int r) {
	int msk = 0;
	for(l += n, r += n + 1; l < r; l>>=1, r>>=1) {
		if(l&1) msk |= tree[l++];
		if(r&1) msk |= tree[--r];
	}
	return __builtin_popcount(msk);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();
	int q;
	cin >> q;
	int t, l, r;
	char c;
	while(q--) {
		cin >> t;
		if(t==1) {
			cin >> l >> c;
			upd(l-1, 1<<(c-'a'));
		} else {
			cin >> l >> r;
			cout << get(l-1, r-1) << '\n';
		}
	}
	
}



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

int main(void) {
  int i, j;
  double d, ans = 0;
  scanf("%lf", &d);
  ans = ((int)d + 1 > d * sqrt(2) ? (int)d + 1: d * sqrt(2));
  printf("%.12lf\n", ans);
  return 0;
}


Measured memory_bytes: 2700
N, K = map(int, input().split())

if N % 2 == 1:
  if len([i for i in range(N+1) if i % 2 == 1]) >= K:
    print("YES")
  else:
    print("NO")
else:
  if len([i for i in range(N) if i % 2 == 1]) >= K:
    print("YES")
  else:
    print("NO")


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <math.h>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define rev(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = INT_MAX;






int main() {

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

    ll ans;
    if (h == 1 || w == 1) ans = 1;
    else if (h % 2 == 0) {
        ans = h / 2 * w;
    }
    else {
        if (w % 2 == 0) {
            ans = (h/2 + h/2 + 1) * (w/2);
        }
        else {
            ans = (h/2 + h/2 + 1) * (w/2) + (h/2 + 1);
        }
    }

    cout << ans << endl;

    return 0;
}




//              g++ -std=c++1z






Measured memory_bytes: 256
/* 
  In the name of ALLAH
  Author : Raashid Anwar
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#define int    int64_t
const int MOD = 1000000007;

int dp[101][101];
string s[101];
int n,m;

void dfs(int x,int y,int d,char p) {
  if(x>=n||y>=m)
    return ;
  int a=d;
  if(s[x][y]=='#'&&p=='.')
    a++;
  if(dp[x][y]!=-1&&dp[x][y]<=a)
    return ;
  dp[x][y]=a;
  dfs(x+1,y,a,s[x][y]);
  dfs(x,y+1,a,s[x][y]);
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin>>n>>m;
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<n;i++)
    cin>>s[i];
  dfs(0,0,0,'.');
  cout<<dp[n-1][m-1]<<"\n";
}


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

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    int n, k, a;
    int mmax = -1, num;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a;
        num = i == 0 ? a : gcd(num, a);
        mmax = max(mmax, a); 
    }
    cout << (k % num == 0 && k <= mmax ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

//-----------------------------------------------------------------------------

int n;
ll length,timelimit,first_pos[100000],last_pos[100000];
int dir[100000];

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

	cin>>n>>length>>timelimit;
	REP(i,n) cin>>first_pos[i]>>dir[i];

	REP(i,n) {
		if(dir[i]==1) last_pos[i]=(first_pos[i]+timelimit%length)%length;
		else last_pos[i]=(first_pos[i]-timelimit%length+length)%length;
	}

	int round_times=0,rest_times=0;
	FOR(i,1,n) {
		if(dir[0]!=dir[i]) {
			round_times+=2;
			if(dir[0]==1) {
				if(first_pos[i]-first_pos[0]<=timelimit%length*2) rest_times++;
				if(first_pos[i]-first_pos[0]+length<=timelimit%length*2) rest_times++;
			}
			else {
				if(length-first_pos[i]+first_pos[0]<=timelimit%length*2) rest_times++;
				if(length-first_pos[i]+first_pos[0]+length<=timelimit%length*2) rest_times++;
			}
		}
	}
	rest_times%=n;

	int	times=(round_times*(timelimit/length)+rest_times)%n;

	ll zero_pos=last_pos[0];
	sort(last_pos,last_pos+n);
	int idx=lower_bound(last_pos,last_pos+n,zero_pos)-last_pos;

	//cout<<"idx="<<idx<<",zero_pos="<<zero_pos<<endl;

	if(dir[0]==1&&idx+1<n&&last_pos[idx]==last_pos[idx+1]) idx++;

	if(dir[0]==1) idx=(n-times+idx)%n;
	else idx=(n+times+idx)%n;

	//cout<<"idx="<<idx<<",times="<<times<<",round="<<round_times<<",rest="<<rest_times<<endl;

	REP(i,n) cout<<last_pos[(i+idx)%n]<<endl;

	return 0;
}


Measured memory_bytes: 3200
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
using namespace std;

int N,Q;
int a[200000],b[200000];
int p[200000],x[200000];

long ans[200001];//頂点iのスコア
 
void solve(){
	memset(ans,0,sizeof(long)*200001);//頂点iのスコアを0で初期化
	vector<vector<int>> list(N+1);//list[i]は頂点iから行ける点の集合
	for(int i=0;i<N-1;i++){
		list[a[i]].push_back(b[i]);
		list[b[i]].push_back(a[i]);
	}
	for(int i=0;i<Q;i++){
		ans[p[i]] += x[i];
	}

	bool visited[200001];//頂点iに訪れているならばvisited[i] = true;
	memset(visited,0,sizeof(bool)*200001);
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int vertex = q.front();
		q.pop();
		visited[vertex] = true;
		for(int i=0;i<list[vertex].size();i++){
			int next_node = list[vertex][i];
			if(!visited[next_node]){
				ans[next_node] += ans[vertex];
				q.push(next_node);
			}
		}
	}
}
 
int main(){
	cin>>N>>Q;
	for(int i=0;i<N-1;i++) cin>>a[i]>>b[i];
	for(int i=0;i<Q;i++) cin>>p[i]>>x[i];

	solve();

	for(int i=1;i<=N;i++){
		cout << ans[i] << ' ';
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 17652
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2666;
int n,m;Vi e[N],tree[N];int fa[N][N];
bool graph[N][N];int top[N][N];
void dfs(int st, int u, int Fa){
	fa[st][u]=Fa;
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=Fa)dfs(st,e[u][i],u);
}
void add(int u, int v){
	if(top[u][v]==v||top[v][u]==u)return;
	if(top[u][v])add(top[u][v],v);
	else if(top[v][u])add(top[v][u],u);
	else{
	//	cerr<<"add "<<u<<' '<<v<<endl;
		vector<Pii>edge;
		rep(tt,1,2){
			static int q[N];int f=0,r=1;q[f]=v;graph[u][v]=1;
			while(f!=r){
				int x=q[f++];top[u][x]=v;
				rep(i,0,SZ(e[x])-1)if(e[x][i]!=fa[u][x]){
					if(graph[u][e[x][i]]){
						graph[u][e[x][i]]=graph[e[x][i]][u]=0;
						edge.pb(Pii(v,e[x][i]));
					}
					else{
						q[r++]=e[x][i];
					}
				}
			}
			swap(u,v);
		}
	//	rep(i,0,SZ(edge)-1)cerr<<"qaq "<<edge[i].fi<<' '<<edge[i].se<<endl;
		rep(i,0,SZ(edge)-1)add(edge[i].fi,edge[i].se);
	}
}

int cur,dfn[N],res,num,dl[N],dr[N];
void dfs1(int u, int fa){
	dl[u]=++num;
	rep(i,0,SZ(tree[u])-1)if(tree[u][i]!=fa)dfs1(tree[u][i],u);
	dr[u]=num;
}
void dfs(int u){
	dfn[u]=cur;res++;
	rep(i,0,SZ(e[u])-1)if(dfn[e[u][i]]!=cur&&dl[u]<=dl[e[u][i]]&&dl[e[u][i]]<=dr[u])dfs(e[u][i]);
}
int main() {
	read(n);read(m);
	rep(i,1,n-1){
		int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
	}
	rep(i,1,n)dfs(i,i,0);
	while(m--){
		int u,v;read(u);read(v);add(u,v);
	//	puts("+++");
	//	rep(i,1,n)rep(j,i+1,n)if(graph[i][j])cerr<<i<<' '<<j<<endl;
	}
	rep(i,1,n)tree[i]=e[i],e[i].clear();
	rep(i,1,n)rep(j,1,n)if(graph[i][j])e[i].pb(j);//,cerr<<i<<' '<<j<<endl;
	for(cur=1;cur<=n;cur++){
		num=0;dfs1(cur,0);
		dfs(cur);
	}
	cout<<(res-n)/2;
	return 0;
}


Measured memory_bytes: 54016
#include <stdio.h>
#include <math.h>
struct xy{
	double x;
	double y; 
};
int kock(int n,struct xy,struct xy);
int main(){
	struct xy p1 ={0,0}, p2 ={100,0};
	int n;
	scanf("%d",&n);
	printf("%.8lf %.8lf\n",p1.x,p1.y);
	kock(n,p1,p2);
	printf("%.8lf %.8lf\n",p2.x,p2.y);
	return 0;
}

int kock(int n,struct xy p1,struct xy p2){
	struct xy s,t,u;
	if(n==0) return 0;
	s.x = (2*p1.x+1*p2.x)/3;
	s.y = (2*p1.y+1*p2.y)/3;
	t.x = (1*p1.x+2*p2.x)/3;
	t.y = (1*p1.y+2*p2.y)/3;
	u.x=(t.x-s.x)/2 -(t.y-s.y)*sqrt(3)/2 +s.x;
	u.y=(t.x-s.x)*sqrt(3)/2 +(t.y-s.y)/2 +s.y;
	kock(n-1,p1,s);
	printf("%.8lf %.8lf\n",s.x,s.y);
	kock(n-1,s,u);
	printf("%.8lf %.8lf\n",u.x,u.y);
	kock(n-1,u,t);
	printf("%.8lf %.8lf\n",t.x,t.y);
	kock(n-1,t,p2);
}


Measured memory_bytes: 2052
#include<cstdio>

int main(void){
    
    int a=0,b=0,c=0;
    int change=0,judge=0,exi=0;
    int right=0,acute=0,obtuse=0,count=0;
    while(true){
        scanf("%d %d %d",&a,&b,&c);
        
        if(c<a){
            change=a;
            a=c;
            c=change;
        }
        if(c<b){
            change=b;
            b=c;
            c=change;
        }
        judge=a*a+b*b-c*c;
        exi=a+b-c;
        if(exi<0){
            break;
        }
        if(judge>0){
            acute++;
        }
        else if(judge==0){
            right++;
        }
        else{
            obtuse++;
        }
        count++;
    }
    
    printf("%d %d %d %d\n",count,right,acute,obtuse);
    return 0;
}


Measured memory_bytes: 2720
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  ll X;cin >> X;
  ll x = 1;
  while(x*(x+1)/2 < X){
    ++x;
  }
  cout << x << endl;
  return 0;
}


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

void solve(int test)
{

    int n;
    cin>>n;


    int i,j;
    int ans = 0;
    for(i=1;i<n;i++)
    {
       int val = n/i;

       if(n%i==0)val--;

        ans = ans +val;
    }
    cout<<ans<<endl;
    return;
}

int main() {

 int t = 1;
// cin>>t;

 for(int x=1;x<=t;x++)
 {
    solve(x);
 }
  return 0;
}


Measured memory_bytes: 3632
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int max_n = 101111, inf = 1011111111;

int n, a[max_n], mx, c1, c2;

void write(string s) {
    cout << s << endl;
    exit(0);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        mx = max(mx, a[i]);
    }
    for (int i = 0; i < n; ++i) {
        if (a[i] == mx) {
            ++c1;
        } else if (a[i] + 1 == mx) {
            ++c2;
        } else {
            write("No");
        }
    }
    if (c2 == 0) {
        if (mx + 1 == n) {
            write("Yes");
        }
    }
    if (c2 + 2 * (mx - c2) <= n && mx - c2 > 0) {
        write("Yes");
    } else {
        write("No");
    }
    return 0;
}


Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;
                                                                                                     
ll MOD=1000000007;                                                                                     
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,ans=inf; cin>>n;
    map<char,int> dir;
    dir['U']=0; dir['R']=1;
    dir['D']=2; dir['L']=3;
    vector<int> X(n,0),Y(n,0);
    vector<char> U(n);
    vector<vector<set<int>>> st(8,vector<set<int>>(400001));
    vector<vector<set<int>>> dr(4,vector<set<int>>(400001));
    rep(i,8)rep(j,400001){
        st[i][j].insert(-inf);
        st[i][j].insert(inf);
    }
    rep(i,4)rep(j,400001){
        dr[i][j].insert(-inf);
        dr[i][j].insert(inf);
    }
    rep(i,n){
        int x,y; char u;
        cin>>x>>y>>u;
        X[i]=x; Y[i]=y; U[i]=u;
        st[dir[u]][x+y].insert(x);
        st[dir[u]+4][200000+x-y].insert(x);
        if(dir[u]%2) dr[dir[u]][y].insert(x);
        else dr[dir[u]][x].insert(y);
    }
    rep(i,n){
        int p,p1,p2;
        if(U[i]=='U'){
            p=*dr[2][X[i]].upper_bound(Y[i]);
            p1=*(--st[1][X[i]+Y[i]].upper_bound(X[i]));
            p2=*st[7][200000+X[i]-Y[i]].upper_bound(X[i]);
            if(abs(p)!=inf) ans=min(ans,5*abs(Y[i]-p));
            if(abs(p1)!=inf) ans=min(ans,10*abs(X[i]-p1));
            if(abs(p2)!=inf) ans=min(ans,10*abs(X[i]-p2));
        }
        if(U[i]=='R'){
            p=*dr[3][Y[i]].upper_bound(X[i]);
            p1=*st[6][200000+X[i]-Y[i]].upper_bound(X[i]);
            p2=*st[0][X[i]+Y[i]].upper_bound(X[i]);
            if(abs(p)!=inf) ans=min(ans,5*abs(X[i]-p));
            if(abs(p1)!=inf) ans=min(ans,10*abs(X[i]-p1));
            if(abs(p2)!=inf) ans=min(ans,10*abs(X[i]-p2));
        }
        if(U[i]=='D'){
            p=*(--dr[0][X[i]].upper_bound(Y[i]));
            p1=*st[3][X[i]+Y[i]].upper_bound(X[i]);
            p2=*(--st[5][200000+X[i]-Y[i]].upper_bound(X[i]));
            if(abs(p)!=inf) ans=min(ans,5*abs(Y[i]-p));
            if(abs(p1)!=inf) ans=min(ans,10*abs(X[i]-p1));
            if(abs(p2)!=inf) ans=min(ans,10*abs(X[i]-p2));
        }
        if(U[i]=='L'){
            p=*(--dr[1][Y[i]].upper_bound(X[i]));
            p1=*(--st[2][X[i]+Y[i]].upper_bound(X[i]));
            p2=*(--st[4][200000+X[i]-Y[i]].upper_bound(X[i]));
            if(abs(p)!=inf) ans=min(ans,5*abs(X[i]-p));
            if(abs(p1)!=inf) ans=min(ans,10*abs(X[i]-p1));
            if(abs(p2)!=inf) ans=min(ans,10*abs(X[i]-p2));
        }
        //cout<<p<<" "<<p1<<" "<<p2<<endl;
    }
    if(ans==inf) cout<<"SAFE"<<endl;
    else cout<<ans<<endl;
    /*
    set<int> ww;
    rep(i,10) ww.insert(i*10);
    cout<<*(--ww.upper_bound(76))<<endl;
    */
}


Measured memory_bytes: 708184
import itertools

n = int(input())
a, b = tuple(map(int, input().split())), tuple(map(int, input().split()))
table = [x for x in range(1, n + 1)]
table2 = list(itertools.permutations(tuple(table)))


print(abs(table2.index(a) - table2.index(b)))





Measured memory_bytes: 8052
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll; const ll MM = 1000000000; ll mod = MM + 7;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

//二分累乗法
ll binarypow(ll a, ll n, ll mod) {
  ll res = 1;
  while(n > 0) {
    if(n & 1) {
      res *= a;
      res %= mod;
    }
    a *= a;
    a %= mod;
    n >>= 1;
  }
  return res;
}

ll gyaku[200100];

ll combination(ll n, ll r) {
  if(r==1)return n;
  else return n * combination(n-1, r-1) % mod * gyaku[r] % mod;
}

int main() {
    ll n, a, b; cin >> n >> a >> b;
    ll ans = binarypow(2, n, mod);
    rep(i, 200100) gyaku[i] = binarypow(i, mod - 2, mod);
    ans -= 1;
    ans %= mod;
    ans -= combination(n, a);
    ans %= mod;
    ans -= combination(n, b);
    ans %= mod;
    if(ans < 0) ans += mod;
    cout << ans << endl;
}

Measured memory_bytes: 8064
import Control.Monad                                                                                                       
                                                                                                                           
main :: IO ()                                                                                                              
main = do                                                                                                                  
  [h,w] <- map read . words <$> getLine                                                                                    
  as <- replicateM h getLine                                                                                               
  putStrLn $ replicate (w+2) '#'                                                                                           
  forM_ as $ \x -> do                                                                                                      
    putChar '#'                                                                                                            
    putStr x                                                                                                               
    putStrLn "#"                                                                                                           
  putStrLn $ replicate (w+2) '#'

Measured memory_bytes: 1276
n, k = map(int, input().split())
s = input().rstrip()

#s = "0001111011110"
#n, k = len(s), 1

s="1"+s

k_pt = 0
cur_tail = 0
for cur in range(1, len(s)):

  if  s[cur-1] == '1' and s[cur] == '0':
    k_pt+=1

  if k_pt > k:
    cur_tail+=1
    if s[cur_tail] == '0' and s[cur_tail+1] == '1':
      k_pt-=1

  #print((cur_tail, cur,k_pt))

print(cur-cur_tail)


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

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

 vector<int> dp(n+1);
 for(int i=1; i<=n;i++) {
    dp [i] = 1001001;
}
dp[1] = 0;
for(int i=2;i <= n;i++){
	dp[i]=dp[i-1]+abs(h[i-1]-h[i]);
	for(int j=2;j <=k;j++){
           if(i-j>=1)dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]));
     }
}
cout  << dp[n] << endl;
return 0;
}

Measured memory_bytes: 1024
N, X = map(int,input().split())
L = list(map(int,input().split()))
D = [0] * (N+1)
count = 1
D[0] = 0
for i in range(1,N+1):
    D[i] = D[i-1] + L[i-1]
    if D[i] <= X:
        count += 1
print(count)

Measured memory_bytes: 3064
if __name__ == '__main__':
	n = int(input())
	x = [float(s) for s in input().split()]
	y = [float(s) for s in input().split()]

	# p=1
	tmp = 0
	for i in range(n):
		tmp += abs(x[i]-y[i])
	print("%.10f" % (tmp))
	
	# p=2
	tmp = 0
	for i in range(n):
		tmp += (abs(x[i]-y[i]))**2
	print("%.10f" % (tmp**0.5))

	# p=3
	tmp = 0
	for i in range(n):
		tmp += (abs(x[i]-y[i]))**3
	print("%0.10f" % (tmp**(1/3)))

	# p=∞
	tmp = []
	for i in range(n):
		tmp.append(abs(x[i]-y[i]))
	print(max(tmp))


Measured memory_bytes: 5668
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  string s; cin >> s;
  auto cs = s.find('C'), fs = s.find('F', cs);
  if (cs == string::npos || fs == string::npos) {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
}

Measured memory_bytes: 256
using System;

namespace Tak_and_Hotels_Easy
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var k = int.Parse(Console.ReadLine());
            var x = int.Parse(Console.ReadLine());
            var y = int.Parse(Console.ReadLine());

            var roomCharge = 0;
            for (int i = 1; i <= n; i++)
            {
                if (k < i)
                {
                    roomCharge += y;
                }
                else
                {
                    roomCharge += x;
                }
            }

            Console.WriteLine(roomCharge);
        }
    }
}


Measured memory_bytes: 11092
n = int(input())
v = list(range(n))
for x in range(n):
  v[x] = input()

import collections
c = collections.Counter(v)
values, counts = zip(*c.most_common())
num = list(counts).count(max(counts))
answers = list(values[:num])
answers.sort()
for z in range(num):
  print(answers[z])

Measured memory_bytes: 59492