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

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-летнюю программу:

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

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

Базовые знания о методе двух указателей, бинарном поиске, динамическом программировании.

Для успешного решения задач не требуется знание специальных структур данных, алгоритмов, математики или библиотек, выходящих за рамки стандартной библиотеки выбранного языка программирования.

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.