Category Archives: 4. Потоковая обработка

В этот раздел входят задачи, читающие и обрабатывающие некоторый поток входных данных. В основном данные будут поступать или записываться в стандартные потоки ввода вывода. Основная особенность этих задач состоит в том, что поступающие данные не следует запоминать — после обработки очередного значения программа никогда к нему не возвращается. Такие задачи следует отличать от задач в которых входные данные необходимо сначала сохранить в памяти, а потом выполнить их обработку.
Например, если Вам нужно отыскать самое большое число во входном потоке, то это потоковая задача — запоминать нужно только текущее предполагаемое максимальное значение.
Если же в задаче, например, требуется вывести числа из входного потока в измененном порядке (в обратном порядке, по возрастанию или убыванию), то задача к потоковым не относится. Все числа нужно хранить в оперативной памяти во время выполнения программы. Такие задачи относятся к разделу «Массивы» или другим структурам данных.
В некоторых задачах требуется, например, поменять местами чётные и нечётные буквы вводимого текста. Естественно, хранить весь текст необходимости нет, но нужно запоминать предыдущую букву. Это тоже потоковая задача — используется всего одна или несколько переменные простых типов,
Формально задачи этого типа определяются так — последовательная обработка входного потока данных сколь угодно длинного потока входных данных при использовании постоянного объёма оперативной памяти.

e-olymp 441. Наиболее круглое число

27/12/2018 by Кирилл Бондаренко

Наиболее круглое число

Назовем число более круглым, чем другие числа, если оно имеет больше заключительных нулей. Если два числа имеют одинаковое количество заключительных нулей, то более круглым считается меньшее число.

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

В первой строке входных данных задано количество чисел $N$ $(1 ≤ N ≤ 100)$. Каждая из последующих $N$ строк содержит одно число в пределах от $1$ до $10^{9}$.

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

Вывести наиболее круглое число среди заданных $N$ чисел.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
4 71200 10 200 10001	200
5 711 1 2 10001 234567	1
10 7 1 2 1 2 3 4 6 8 9	1
4 100000 200000 500000 800000	100000

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;
		Scanner in = new Scanner(System.in);
		e = in.nextInt();
		while (e -- > 0) {
        	n = in.nextInt();
			if (p <= n){
				m = n;
				k = 0;
				while ((n % 10) == 0) {
					//считает нули
					n = n / 10;
					k ++;
				}
				if (maxk < k) {
					maxn = m;
					maxk = k;
					p = 1;
					for (int i = 1; i < maxk; i ++) {
						p *= 10;
					}
				} else if (maxk == k) {
					if(maxn > m) maxn = m;
				}
			}
		}
		System.out.print(maxn);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int n, e, k=0, m, maxk = 0, maxn = 1000000000, p = 1;

Scanner in = new Scanner(System.in);

e = in.nextInt();

while (e -- > 0) {

n = in.nextInt();

if (p <= n){

m = n;

k = 0;

while ((n % 10) == 0) {

//считает нули

n = n / 10;

k ++;

}

if (maxk < k) {

maxn = m;

maxk = k;

p = 1;

for (int i = 1; i < maxk; i ++) {

p *= 10;

}

} else if (maxk == k) {

if(maxn > m) maxn = m;

}

System.out.print(maxn);

}

Решение задачи

Имеет смысл проверять каждое введенное число: не является ли оно меньше либо равно чем $p$, где $p$ — наименьшее число с количеством нулей равным $maxk$. $maxk$ — текущее наибольшее количество нулей. Для того, чтобы найти $p$, мы в цикле умножаем $1 maxk$-раз на $10$. Очевидно, что $p$ нужно менять только тогда, когда меняется $maxk$, также следует до цикла полагать $p = 1$. Для того чтобы $p$ не умножалось на $10$ лишнее количество раз. Таким образом мы отсеиваем заведомо негодные числа и ускоряем код.
Положим $maxn$ — наиболее круглое число.
Так как по условию числа не могут быть больше чем $10^{9}$, имеет смысл изначально поставить переменную $maxn = 10^{9}$. Это делается для того случая, когда во всех числах $m$ не будет нулей и нужно будет выбрать наименьшее. Если мы положим в переменную $maxn$ любое другое число то $maxn$ может быть меньше чем $m$ и мы не сможем выбрать ответ так как все $m$ будут больше его.

Условие задачи на e-olimp
Код решения ideone

e-olymp 3843. Простые

27/12/2018 by Илья Черноморец

Задача

Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:

Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.

Вычислить мощность множества Prime$\left(m, n\right)$.

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

Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.

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

Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.

Тесты

Входные данные	Выходные данные
2 20 70 110 5 150	8 10 33
7 2056 14 181 27 367	307 36 64
77 777 55 555 33 333	116 85 56

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

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

2 20

70 110

5 150

7 2056

14 181

27 367

307

77 777

55 555

33 333

116

Код решения

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
     
     Scanner in = new Scanner(System.in);
    
     final int MAXN = 10000001;
     int simple[]=new int[MAXN+1];
     for(int i = 2; i <= MAXN; i++){
         simple[i] = 1;
     }
     for(int i = 2; i <= Math.sqrt(MAXN); i++){
         if(simple[i]==1){
             for(int j = i * i; j <= MAXN; j += i){
                 simple[j] = 0;
             }
         }
     }
 
     int count[]=new int[MAXN+1];
     int lastSum = 0;
     for(int i = 1; i < MAXN; i++){
         count[i] = lastSum + simple[i];
         lastSum = count[i];
     }
      while(in.hasNextInt()) {
        int m = in.nextInt();
    int n = in.nextInt();
        int answer = count[n] - count[m] + simple[m];
        System.out.println();
      System.out.println(answer);
      }
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Arrays;

import java.util.Scanner;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

final int MAXN = 10000001;

int simple[]=new int[MAXN+1];

for(int i = 2; i <= MAXN; i++){

simple[i] = 1;

}

for(int i = 2; i <= Math.sqrt(MAXN); i++){

if(simple[i]==1){

for(int j = i * i; j <= MAXN; j += i){

simple[j] = 0;

}

int count[]=new int[MAXN+1];

int lastSum = 0;

for(int i = 1; i < MAXN; i++){

count[i] = lastSum + simple[i];

lastSum = count[i];

}

while(in.hasNextInt()) {

int m = in.nextInt();

int n = in.nextInt();

int answer = count[n] - count[m] + simple[m];

System.out.println();

System.out.println(answer);

}

Решение

Для решения этой задачи требуется завести большой массив типа bool и присвоить ему значение true. Затем проверяется, простое ли число, если это не так, то присваиваем значение false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от n до m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.

Ссылки

Ссылка на E-olymp
Ссылка на решение

MS9. Шифрование символов

27/12/2018 by Антон Джашимов

Задача

Зашифруйте текст из входного потока, заменяя каждый символ результатом сложения по модулю два его кода и кода предыдущего символа текста. Первый символ шифровать не нужно.

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

Последовательность символов.

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

Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

Входные данные	Выходные данные
pack my box with five dozen liquor jugs	p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14

Код программы

import java.util.*;
import java.math.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        in.useDelimiter(""); //Чтение по одному символу.
        char a;
        char b = in.next().charAt(0);
        System.out.print(b);
        System.out.print(' ');
        while(in.hasNext()){
            a = in.next().charAt(0);
            System.out.printf("%x ", a^b);
            b=a;
        }
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

in.useDelimiter(""); //Чтение по одному символу.

char a;

char b = in.next().charAt(0);

System.out.print(b);

System.out.print(' ');

while(in.hasNext()){

a = in.next().charAt(0);

System.out.printf("%x ", a^b);

b=a;

}

Решение

Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не закончатся данные из потока ввода. По мере ввода запоминаем старый символ во 2 переменной и складываем их по модулю 2 и выводим результат в шестнадцатеричной системе.

Ссылки

Условие задачи
Код решения

e-olymp 176. Выбор вождя

27/12/2018 by Иван Василевский

Условие задачи
Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.

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

Старейшины обратились к вам с просьбой написать программу для определения количества претендентов, которые могут стать вождями.
Входные данные
В первой строке входного файла записано количество $N$ претендентов на звание вождя в этом году $(1 ≤ N ≤ 1000000)$, а во второй – $N$ целых чисел в пределах от $1$ до $10000$, каждое из которых определяет силу соответствующего кандидата.
Выходные данные
Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.
Тесты

Входные данные	Выходные данные
5 1 2 3 4 5	1
6 2 2 2 2 2 2	6
6 3 2 1 3 1 1	2

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        int quantity, force, count = 0, max = 0;
        quantity = Integer.parseInt(params1[0]);
     
        String[] params2 = bufferedReader.readLine().split(" ");
        for(int i = 0; i < quantity; ++i)
        {
            force = Integer.parseInt(params2[i]);
            if (force > max)
            {
                max = force;
                count = 1;
            }
            else if (force == max) count++;
        }
        System.out.print(count);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int quantity, force, count = 0, max = 0;

quantity = Integer.parseInt(params1[0]);

String[] params2 = bufferedReader.readLine().split(" ");

for(int i = 0; i < quantity; ++i)

{

force = Integer.parseInt(params2[i]);

if (force > max)

{

max = force;

count = 1;

}

else if (force == max) count++;

}

System.out.print(count);

}

Решение задачи
Так как задача на потоковую обработку создаем цикл, который работает пока у нас вводится число «Сила Орков». В самом цикле происходит следующее:

Если «Сила Орков» больше max, то мы в переменную max присваиваем значение из «Силы Орков» и счетчику присваиваем единицу.
Если «Сила Орков» равна max то мы прибавляем к счетчику $1$.

Выводим счетчик на экран.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 992. Города и дороги

26/12/2018 by Андрей Лисовой

Задача

В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.

Вводные данные

В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.

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

Вывести одно число — количество дорог на планете «Neptune».

Тесты

Входные данные	Выходные данные
$3$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$	$3$
$3$ $0$ $1$ $0$ $1$ $0$ $0$ $0$ $0$ $0$	$1$
$5$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$	$3$

Код программы(использование матрицы смежности)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] x = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				x[i][j] = in.nextInt();
			}
		}
		int roads = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(x[i][j] == 1) roads++;
			}
		}
		System.out.print(roads);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] x = new int[n][n];

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

for(int j = 0; j < n; j++) {

x[i][j] = in.nextInt();

}

int roads = 0;

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

for(int j = i; j < n; j++) {

if(x[i][j] == 1) roads++;

}

System.out.print(roads);

}

Решение задачи(использование матрицы смежности)

Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и если попадается $1$, то увеличиваем число дорог на $1$. Выводим количество дорог. Задача решена.

Код программы(потоковая обработка)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n=0;
		int i;
		while(in.hasNextInt()) {
			i = in.nextInt();
			if(i == 1) n++;
		}
		System.out.print(n/2);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n=0;

int i;

while(in.hasNextInt()) {

i = in.nextInt();

if(i == 1) n++;

}

System.out.print(n/2);

}

Решение задачи(потоковая обработка)

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

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(матрица смежности)
Код решения на ideone.com(потоковая обработка)

e-olymp 4281. Невнимательность

25/12/2018 by Андрей Лисовой

Задача

Степан успешно прошёл собеседование и вот уже как четыре месяца работает в одной из самых престижных ИТ компаний. Пришло время сдавать проект менеджеру и Степан, как настоящий студент, всё делает в последнюю ночь перед сдачей. Набирает текст Степан необычно очень быстро, но невнимательно. Вот и в этот раз последнюю часть текста он набрал не обратив внимания, что случайно нажал клавишу $caps\;lock.$ Таким образом большие буквы были набраны маленькими, а маленькие — большими. Другие символы он набрал верно. Степан настолько устал, что нет сил исправить ошибки, и он решил несколько часов поспать.

Помогите Степану, пока он спит, напишите программу, которая исправляет невнимательно набранный текст.

Вводные данные

В одной строке содержится невнимательно набранный Степаном текст. В строке не более $500$ символов.

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

Вывести исправленный текст.

Тесты

Входные данные	Выходные данные
$sCHOOL$	$School$
$hOME$	$Home$
$hAPPY nEW yEAR$	$Happy New Year$
$uNIVERSITY$	$University$
$mERRY cHRISTMAS$	$Merry Christmas$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		String c = in.nextLine();
		String str = "";
        for (int i = 0; i < c.length(); i++) {
            if (c.charAt(i) >= 'a' && c.charAt(i) <= 'z')
                str += Character.toUpperCase(c.charAt(i));
            else
                str += Character.toLowerCase(c.charAt(i));
        }
        System.out.print(str);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

String c = in.nextLine();

String str = "";

for (int i = 0; i < c.length(); i++) {

if (c.charAt(i) >= 'a' && c.charAt(i) <= 'z')

str += Character.toUpperCase(c.charAt(i));

else

str += Character.toLowerCase(c.charAt(i));

}

System.out.print(str);

}

Решение задачи

Для решения задачи считываем всю строку. Затем в цикле проверяем каждый символ строки на то, является ли символ маленькой буквой английского алфавита, если да, то увеличиваем букву (функция Character.toUpperCase(c.charAt(i)), если нет, то уменьшаем букву (функция Character.toLowerCase(c.charAt(i))). Складываем получаемые буквы в строку str. Выводи строку. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 1317. Дни рождения

24/12/2018 by Даниель Савчак

Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

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

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

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

Для каждого значения [latex]n[/latex] в отдельной строке вывести вероятность того, что хотя бы у двух из [latex]n[/latex] людей дни рождения (число и месяц) совпадают. Искомую вероятность выводить в процентах и округлять до [latex]8[/latex] знаков после запятой как указано в примере.

Тесты

Входные данные	Выходные данные
[latex]12[/latex]	[latex]16.70247888\%[/latex]
[latex]28[/latex]	[latex]65.44614723\%[/latex]
[latex]399[/latex]	[latex]100.00000000\%[/latex]

Код программы

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double k = 1;
		int n;
		Scanner in = new Scanner(System.in);
			while (in.hasNextInt())
			{
				n = in.nextInt();
				for ( int i = 366 - n; i <= 365; i++ ) {
        			k = k * i;
        			k = k / 365;
        		}
        		System.out.printf("%.8f",100 * ( 1 - k ));
        		System.out.println("%");
        		k=1;
			}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

double k = 1;

int n;

Scanner in = new Scanner(System.in);

while (in.hasNextInt())

{

n = in.nextInt();

for ( int i = 366 - n; i <= 365; i++ ) {

k = k * i;

k = k / 365;

}

System.out.printf("%.8f",100 * ( 1 - k ));

System.out.println("%");

k=1;

}

Решение задачи

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

e-olymp 97. Числа Белла

23/12/2018 by Томас Пасенченко

Задача

Число Белла $B_n$ равно количеству разбиений множества из $n$ элементов на произвольное количество непересекающихся непустых подмножеств. Например, $B_3 = 5$, так как существует $5$ возможных разбиений множества $\lbrace a, b, c\rbrace$: $\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace$. Дополнительно считаем, что $B_0 = 1$.
Рассмотрим определитель $D_n$:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа $p$ найти наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

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

Каждая строка ввода содержит два целых числа $n$ и $p$ ($0\leq\; n,\;p \;\leq\; 10000$). Известно, что $p$ – простое.

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

Для каждой пары входных значений $n$ и $p$ в отдельной строке выведите наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

Тесты

Входные данные	Выходные данные
1 5 3 2 4 2 4 3 10000 3	0 2 5 2 24962375
18 2 465 1009 9998 9221 548 11	134 0 778 14412
1093 1093 1103 1723 3931 617 4868 6113 9534 71	1 0 10635 0 639989
617 17 42 11 0 5	11295 63 0

Код программы

import java.util.Scanner;
public class Main {
 	public static void main (String[] args) {
   		Scanner scanner = new Scanner(System.in);
   		int n, p;
   		while(scanner.hasNextInt()) {
   			n = scanner.nextInt();
   			p = scanner.nextInt();
   			int k = 0;
   			for (int i = 1; i  0) {
   					fact /= p;
   					k += fact;
   				}
   			}
   			System.out.println(k);
   		}
   	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n, p;

while(scanner.hasNextInt()) {

n = scanner.nextInt();

p = scanner.nextInt();

int k = 0;

for (int i = 1; i 0) {

fact /= p;

k += fact;

}

System.out.println(k);

}

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i!$$
Воспользуемся этим свойством для решения данной задачи. Найдём степень числа $p$
в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число $k$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Число Белла на wikipedia

e-olymp 1000. Задача a + b

17/12/2018 by Саша Рябова

Задача

Вычислите сумму $a+b$.

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

В каждой строке задано два целых числа $a$ и $b$ $(|a|,|b| \leq 30000)$.

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

Для каждого теста выведите сумму $a+b$ в отдельной строке.

Тесты

Входные данные	Выходные данные
$4$ $8$ $5$ $0$ $-6$ $8$	$12$ $5$ $2$
$-3$ $3$	$0$
$12$ $8$ $10$ $10$	$20$ $20$
$30000$ $30000$ $3000$ $3000$ $300$ $300$ $30$ $30$ $3$ $3$	$60000$ $6000$ $600$ $60$ $6$
$10$ $23$ $613$ $2$ $-200$ $300$	$33$ $615$ $100$

Код программы

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()){
        	int a = in.nextInt();
        	int b = in.nextInt();
        	System.out.println(a+b);
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

while (in.hasNextInt()){

int a = in.nextInt();

int b = in.nextInt();

System.out.println(a+b);

}

Решение задачи

Пока вводятся пары чисел, они считываются и на экран выводится их сумма.

Ссылки

Условие на e-olymp
Решение на языке C++ с описанием решения
Код на java

e-olymp 247. Несчастливый автобус

15/12/2018 by Георгий Мартынюк

Задача

Витя живёт довольно далеко от школы, поэтому, чтобы не опаздывать на уроки, он ездит на автобусе. Витя — очень наблюдательный мальчик, он старается замечать все интересные совпадения, которые происходят в жизни. Однажды он заметил, что как только он садится в автобус, у которого номер в двоичном представлении второй цифрой справа имеет единичку, так его обязательно вызовут к доске отвечать заданный урок. А кто же любит ходить к доске?! Тем более, если накануне просидел за компьютером и не выучил уроки!!! Явно, что в таком случае грозит «двойка» …

Помогите Вите составить список автобусов, которые он считает «несчастливыми» автобусами.

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

В первой строке записано число [latex]N (0 ≤ N ≤ 100000)[/latex] — количество автобусов, далее указаны номера автобусов [latex]m_i (0 ≤ m_i ≤ 2^{31}-1)[/latex] по одному в строке.

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

Выведите количество «несчастливых» автобусов.

Тесты

Входные данные	Выходные данные
2 0 3	1
3 1 2 4	1
4 2 1 3 5	2
5 1 2 3 7 4	3

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n, number, count = 0;
		n = in.nextInt();
		for (int i = 0;i < n; i++){
			number = in.nextInt();
			if ((number / 2) % 2 == 1) count++;
		}
		System.out.print(count);
		in.close();
		return;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n, number, count = 0;

n = in.nextInt();

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

number = in.nextInt();

if ((number / 2) % 2 == 1) count++;

}

System.out.print(count);

in.close();

return;

}

Решение

В двоичном коде число заканчивается на [latex]1[/latex] тогда и только тогда, когда остаток от деления на [latex]2[/latex] равен [latex]1[/latex] . Для определения предпоследнего символа , в каждом числе отбрасываем последний символ двоичного представления путем деления нацело на [latex]2[/latex] и проверяем нечетность. Подсчитываем все нужные варианты

Ссылки

e-olymp
Ideone

Наиболее круглое число

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

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

Тесты

Код программы

Решение задачи

Задача

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

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

Тесты

Код решения

Решение

Ссылки

Задача

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

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

Тесты

Код программы

Решение

Ссылки

5 1 2 3 4 5

1

6 2 2 2 2 2 2

6

6 3 2 1 3 1 1

2

Задача

Вводные данные

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

Тесты

Код программы(использование матрицы смежности)

Решение задачи(использование матрицы смежности)

Код программы(потоковая обработка)

Решение задачи(потоковая обработка)

Ссылки

Задача

Вводные данные

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

Тесты

Код программы

Решение задачи

Ссылки

Задача

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

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

Тесты

Код программы

Решение задачи

Ссылки

Задача

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

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

Тесты

Код программы

Решение

Ссылки

Задача

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

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

Тесты

Код программы

Решение задачи

Ссылки

Задача

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

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

Тесты

Решение

Ссылки

5
1 2 3 4 5

6
2 2 2 2 2 2

6
3 2 1 3 1 1