Районная олимпиада 2019-2020 информатика

Задача A. Равнобедренные треугольники

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Треугольник называется равнобедренным, если хотя бы две из трёх сторон имеют одинаковую длину. Посчитайте количество равнобедренных треугольников, у которых длина каждой стороны - целое число от $1$ до $N$. Не забывайте, что треугольник существует только в том случае, когда длина каждой стороны меньше суммы длин двух других сторон.

Формат входного файла

В единственной строке вводится одно натуральное число $N$.

Формат выходного файла

Выведите количество подходящих треугольников.

Система оценки

Это задача состоит из 10 тестов, каждый оценивается в 10 баллов:

1. 2 теста при $1 <= N <= 100$
2. 3 теста при $1 <= N <= 5000$
3. 5 тестов при $1 <= N <= 10^6$

Пример:

Вход

4

Ответ

12

Замечание

Подходящие треугольники:
1 1 1
2 2 1
2 2 2
2 2 3
3 3 1
3 3 2
3 3 3
3 3 4
4 4 1
4 4 2
4 4 3
4 4 4

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
int main(){
	long int n,q = 0,x; cin >> n;
	for(long int i = 1;i<=n;i++){
		x = 2*i;
		if(x>n)
			x = n+1;
		q+=x - 1;
	}
	cout << q;
	return 0;
}

показать/скрыть код

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	long result = 0;
	for(int a=1;a<=n;a++) {
		if (2*a > n) {
			result += n;
		} 
		else {
			result += 2 * a - 1;
		}
	}

	cout << result;
	return 0;
}

Есть более краткий код

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

long long n, ans = 1;

int main () {
    cin >> n;
    for (int i = 2; i <= n; i ++) {
        int h =  (i - (i / 2));
        ans += (i - 1) + h;
    }
    cout << ans;
}

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
#define wa(x) cout << (#x) << " is " << (x) << endl
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pii pair <int,int>
#define f first
#define s second
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define forever() for(;;)
#define str string
int main()
{
      boost
      ll n;
      cin >> n;
      ll ans = 1;
      n--;
      ll z = 2;
      bool step = true;
      while(n--){
            ans += z;
            if(step){
                  z += 2;
                  step = false;
            }
            else{
                  z += 1;
                  step = true;
            }
      }
      cout << ans;
      return 0;
}

показать/скрыть код

#include <bits/stdc++.h>

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;
 
#define F first
#define S second
#define EB emplace_back
#define PB push_back
#define ld long double
#define lb lower_bound
#define ub upper_bound
#define ar array
#define sz(x) (int)x.size()
#define bit(x) __builtin_popcount(x)
#define all(x) (x).begin(), (x).end()
#define FOR(c,l,r) for(int c=(l);c<=(r);c++)
 
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
 
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
 
using ll = long long;
#define int ll
 
const int N = 2e6 + 7;
const int MOD = 1e9 + 7;
const int inf = 2e9 + 7;
const int dx[]  = {-1,   0,   1,   0,  1, -1, -1,  1};
const int dy[]  = { 0,   1,   0,  -1,  1, -1,  1, -1};

void solve() {	
	int n;
	cin >> n;
	int ans = 1;
	if (n == 2) {
		cout << 3;
		return;
	} if (n == 3) {
		cout << 7;
		return;
	}
	for (int i = 2; i <= n; i ++) {
		int k = (i + i);
		if (n < k) {
			//cout << n << '\n';
			ans += n;
		} else {
			//cout << k - 1 << '\n';
			ans += k - 1;
		}
	}
	cout << ans;
}
 
main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
   	//cin >> tt;
    while (tt --){
        solve();
        cout << '\n';
    }
}

показать/скрыть код

n=int(input())
count=0
for i in range(1,n+1):
    for j in range(i,i+1):
        for k in range(1,n+1):
            if i+j <= k: continue
            count+=1
            print(i,j,k)
print(count)

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n;
ll ans = 1;

int main () {
    start
    cin >> n;
    if(n % 2 == 0) {
        ans *= n * 1LL * n;
        ans >>= 2;
        ans += (n * 1LL * n) >> 1;
        cout << ans;
        return 0;
    }
    else {
        int x = ((n + 1) >> 1);
        ans *= x * 1LL * x;
        ans += ((n - 1) * 1LL * n) >> 1;
        cout << ans;
        return 0;
    }
    return 0;
}

показать/скрыть код

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define russian setlocale(LC_ALL,"Russian_Russia.20866");
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#define ll long long
#define dl double long
#define all(s) s.begin(), s.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N = 2007;
ll binpow(ll a, ll n) {
    ll res = 1;
    while(n) {
        if(n & 1) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}
int main() {
    speed;
    russian;
    ll n;
    cin >> n;
    ll res = 0;
    for(ll a = 1; a <= n; a++) {
        if(2 * a > n) {
            res += n;
        }
        else {
            res += 2 * a - 1;
        }
    }
    cout << res << '\n';
}

#include <iostream>

using namespace std;

int main (){

long N;

cin >> N;

cout << ((N / 2) * (N / 2)) + ((N - (N / 2)) * N);

}