Требования и описание экзамена по информатике

1. Как устроен экзамен

Экзамен по информатике состоит из двух частей: программирование задач на одном из разрешённых языков и короткое интервью (10-15 минут) для обсуждения ваших достижений и знаний в области программирования. Для участия вам потребуется компьютер с установленными необходимыми компиляторами или интерпретаторами, а также настроенными средами разработки. Рекомендуемые языки: Python и C++. Рекомендуемые среды разработки: PyCharm и VSCode.

Экзамен включает несколько задач, каждая из которых оценивается в 100 баллов за полное решение. Частичные решения оцениваются пропорционально количеству пройденных тестов. Результаты будут доступны во время экзамена с небольшой задержкой, однако подробности тестов не предоставляются.

2. Пререквизиты для успешного участия в экзамене по информатике

Для успешного участия необходимо владеть одним из следующих языков программирования: C++, Python, Java, JavaScript, Rust, Kotlin, C#, PHP, Go, Ruby, PascalABC.NET. Оптимальные по асимптотике решения будут проходить по времени на всех поддерживаемых языках.

Необходимые знания для поступления на 4-летнюю программу:

Умение работать с автоматическими тестирующими системами (например, Codeforces, Informatics, Codewars, Timus, HackerRank).
Стандартный ввод и вывод чисел, строк и массивов.
Операции с целыми числами: деление, остаток, возведение в степень.
Условные конструкции, включая вложенные.
Циклы.
Двумерные массивы.
Работа со строками и символами.

Дополнительно для поступающих на 3-летнюю программу:

Функции.
Рекурсия.

3. Примеры задач

Задача А. Дорога в школу.

Однажды утром Серёжа проспал будильник. А первый урок информатики в школе, где он работает, уже очень скоро! К счастью, у Серёжи есть мощный автомобиль. Для простоты будем считать, что автомобиль работает следующим образом:

В начале каждой секунды у автомобиля есть текущая скорость $v$ метров в секунду.
В начале каждой секунды Серёжа может оставить скорость без изменений, увеличить её на 1 м/с или уменьшить на 1 м/с.
После этого в течение секунды автомобиль проезжает расстояние, равное текущей скорости.
Затем процесс повторяется.

До школы нужно проехать ровно $S$ метров. При этом на старте и в конце скорость равна 0. Отрицательная скорость невозможна (за движение задним ходом можно и прав лишиться!). Определите минимальное время, за которое Серёжа сможет добраться до школы.

Входные данные:

В первой строке задано единственное число — $S$ ($1 \leq S \leq 10^{18}$) — расстояние от дома Серёжи до The Island School. (Обратите внимание, необходимы 64-битные или неограниченные целые числа: int в Python, long long в C++, long в Java и C#, int64 в Pascal и т.п.)

Выходные данные:

Выведите единственное число — минимальное время в секундах, за которое Серёжа сможет доехать до школы.

Примеры:

В первую секунду Серёжа едет со скоростью 1 м/с, во вторую — 2 м/с, в третью — снова 1 м/с. В начале 4-й секунды он останавливается, поэтому на весь путь уйдёт ровно 3 секунды.

Скорости по секундам: 1 м/с, 2 м/с, 2 м/с, 3 м/с, 2 м/с, 1 м/с.

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

В данной задаче 25 тестов, помимо тестов из условия; каждый из них оценивается в 4 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время экзамена.

Задача B. Unbirthday.

Unbirthday — это такой день в году «напротив» для рожденья. Но это «напротив» можно считать по-разному. Можно взять дату ровно через 6 месяцев: например, для 1 марта (3 месяц) это будет 1 сентября (9 месяц). А можно прибавить $365/2$ или $366/2$ дней. Первое число нечётное, поэтому будем брать 182 или 183 дня. Например, для 1 марта это будет 30 или 31 августа.

Будем говорить, что данный день unbirthday-красивый, если та же дата ровно через 6 месяцев отстоит либо на 182, либо на 183 дня. (Если такого дня в месяце через 6 после текущего нет, то день не может быть красивым). Так 1 марта 2025-го года некрасивый день, а вот 5 апреля 2025-го года — unbirthday-красивый, ведь через 183 дня будет 5 октября 2025-го года, очень красиво!

Определите, сколько unbirthday-красивых дней в данном году (не забывайте про високосный год).

Входные данные:

В первой строке задано единственное число — $y$ номер года ($2001 \leq y \leq 2099$).

Выходные данные:

Выведите единственное число — число unbirthday-красивых дней в этом году.

Примеры:

Ответ на самом деле не 17, его нужно посчитать. Но если бы в 2025-м году было бы 17 unbirthday-красивых дней, то ответ нужно было бы вывести именно так.

Задача C. Шахматные ладьи

Дана шахматная доска размером $N \times N$, на которой расположены $K$ ладей. Требуется посчитать, сколько пар ладей бьют друг друга.

В первой строке программа получает на вход натуральное число $N$ ($1 \leq N \leq 10^9$) — размер доски. Во второй строке записано число $K$ ($0 \leq K \leq \min(10^5, N^2)$) — количество ладей. Затем в $K$ строках записаны пары чисел от $1$ до $N$ — координаты ладей. Гарантируется, что никакие две ладьи не находятся в одной и той же клетке.

Напомним, что шахматная ладья бьёт фигуру, если находится с ней в одной строке или одном столбце и между ладьёй и фигурой нет других фигур.

Программа должна вывести одно целое число — ответ на вопрос задачи.

Входные данные:

В первой строке задано единственное число $N$ — размер доски. Во второй строке — число $K$ — количество ладей. В следующих $K$ строках находятся пары чисел — координаты ладей.

Выходные данные:

Выведите одно целое число — количество пар ладей, которые бьют друг друга.

Примеры:

В приведённом примере расположение ладей следующее:

- R - R -
R - R - R
- R - R -
- - - - -
- - - - -

Обратите внимание, что крайние ладьи во второй строке не бьют друг друга.

Примеры считывания и вывода данных

Задача 0. Сложить два числа.

Серёжа разучился считать. Помогите ему найти сумму двух чисел.

Входные данные:

В первых двух строчках задано по натуральному числу (от $0$ до $10^{18}$ каждое).
(Обратите внимание, необходимы 64-битные целые числа: int в Python, long long в C++, long в Java и C#, int64 в Pascal и т.п.)

Выходные данные:

Выведите единственное число — сумму этих чисел.

Примеры:

4
3

110263085964514794
302951845836574401

413214931801089195

Ниже примеры решения задачи на разных языках программирования:

Python

a = int(input())
b = int(input())
print(a + b)

C++

#include <iostream>
using namespace std;
int main()
{
    long long a, b;
    cin >> a;
    cin >> b;
    cout << a + b;
    return 0;
}

Java

import java.io.*;

public final class Main
{
  public static void main(String args[])
  {
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    long a, b;

    st.resetSyntax();
    st.eolIsSignificant(false);
    st.wordChars(33, 255);
    st.whitespaceChars(0, 32);

    try {
      st.nextToken(); a = Long.parseLong(st.sval);
      st.nextToken(); b = Long.parseLong(st.sval);
      System.out.println(a + b);
    } catch (Exception x) {
      System.exit(1);
    }
  }
}

Javascript (Node.js)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];


rl.on('line', (line) => {
    input.push(BigInt(line));
    if (input.length === 2) {
        console.log((input[0] + input[1]).toString());
        rl.close();
    }
});

Kotlin

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`);
    var a: Long = sc.next().toLong();
    var b: Long = sc.next().toLong();
    println(a + b);
}

PHP

<?php
list ($a) = fscanf(STDIN, "%ld");
list ($b) = fscanf(STDIN, "%ld");
print $a + $b . "\n";
?>

Go

package main
import "fmt"

func main(){
    var a, b int64
    fmt.Scan(&a)
    fmt.Scan(&b)
    fmt.Printf("%d\n", a + b)
}

Ruby

a = gets.chomp
b = gets.chomp
puts a.to_i + b.to_i

Rust

use std::io;
use std::io::Read;
fn main()
{
    let mut instr = String::new();
    io::stdin().read_to_string(&mut instr).expect("err");
    let mut viter = instr.split_whitespace();
    let a = viter.next().unwrap().parse::<i64>().expect("err");
    let b = viter.next().unwrap().parse::<i64>().expect("err");
    let c = a + b;
    println!("{}", c);
}

C#

using System;

class MainClass
{
	static void Main(string[] args)
	{
		long a = Int64.Parse(Console.ReadLine());
		long b = Int64.Parse(Console.ReadLine());
		Console.WriteLine("{0}", a + b);
	}
}

PascalABC.NET

program sum;
var a, b, c : int64;
begin
   readln(a);
   readln(b);
   c := a + b;
   writeln(c);
end.