e-olimp 4000. Обход в глубину

30/04/2015

Задача e-olimp 4000 Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину). Входные данные В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел … Continue reading →

e-olimp 695. Range Variation Query

30/04/2015

Задача e-olimp 695. Последовательность [latex]a_{n}[/latex] задается следующей формулой: [latex]a_{n}=n^{2} mod 12345+n^{3} mod 23456[/latex]. Требуется много раз отвечать на запросы следующего вида: найти разность между максимальным и минимальным значением среди элементов [latex]a_{i},a_{i+1}, …,a_{j}[/latex]; присвоить элементу [latex]a_{i}[/latex] значение [latex]j[/latex]. Технические условия. Входные данные Первая строка содержит натуральное число [latex]k (k\leq 100000)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, … Continue reading →

e-olimp 5080. Количество висячих вершин 1

29/04/2015

Условие задачи Ссылка на засчитанное решение Ссылка на Ideone Код:

#include <iostream>
#include <vector>
using namespace std;

int gr[1001][1001]; // матрица смежности
int n; //кол-во вершин
	
//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во
//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.
//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице 
//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int ans = 0; //предположим, что граф не имеет висячих вершин 
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> gr[i][j];	//ввод матрицы смежности
	for (int i=0; i<n; i++){
		int cnt = 0; //счётчик
		for (int j=0; j<n; j++){
			if (gr[i][j] == 1) cnt++;  //подсчёт степени
		}
		if (cnt==1) ans++;  //проверка на висячую вершину
	}
	cout << ans << endl;	//вывод ответа
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int gr[1001][1001]; // матрица смежности

int n; //кол-во вершин

//Просматривая матрицу смежности, подсчитываем кол-во единиц, т.е кол-во

//инцидентных вершин данной вершине. Инцидентные вершины - вершины, которые соединены ребром. Степенью вершины называется кол-во рёбер, инцидентных этой вершине.

//Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице

//только одна единица, то вершина имеет степень 1 и является висячей.

int main() {

ios::sync_with_stdio(false);

cin >> n;

int ans = 0; //предположим, что граф не имеет висячих вершин

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

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

cin >> gr[i][j]; //ввод матрицы смежности

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

int cnt = 0; //счётчик

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

if (gr[i][j] == 1) cnt++; //подсчёт степени

}

if (cnt==1) ans++; //проверка на висячую вершину

}

cout << ans << endl; //вывод ответа

return 0;

}

Related Images:

I. Новорічні іграшки

29/04/2015

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала. Формулировка «У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його … Continue reading →

e-olimp 4513. Сортировка вагонов — B

28/04/2015

Сортировка вагонов — B К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще … Continue reading →

e-olimp 5077. Полуполный граф

27/04/2015

Задача: Полуполный граф Решение ссылка на ideone, засчитанное решение на e-olymp

#include<iostream>
using namespace std;

bool used[101][101];

int main(){
  int n, m; cin >> n >> m;
  for(int i = 0; i < m; i++){
     int a,b; cin >> a >> b;
     used[a][b] = used[b][a] = 1;
  }
  for(int i = 1; i <= n; i++){
     for(int j = i+1; j <= n; j++){
        if(used[i][j] == false){
           cout << "NO\n";
           return 0;
        }
     }
  }
  cout << "YES\n";
  return 0;
}

#include<iostream>

using namespace std;

bool used[101][101];

int main(){

int n, m; cin >> n >> m;

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

int a,b; cin >> a >> b;

used[a][b] = used[b][a] = 1;

}

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

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

if(used[i][j] == false){

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Решение на Java ссылка на ideone, засчитанное решение на e-olymp

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	static boolean[][] used = new boolean[101][101];
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		for(int i = 0; i < m; i++){
	     	int a, b;
	     	a = sc.nextInt();
	     	b = sc.nextInt();
	    	used[a][b] = used[b][a] = true;
	  	}
		for(int i = 1; i <= n; i++){
	    	for(int j = i+1; j <= n; j++){
	    		if(used[i][j] == false){
	    			System.out.println("NO");
	           		return;
	        	}
	    	}
	  	}
	  	System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static boolean[][] used = new boolean[101][101];

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

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

int a, b;

a = sc.nextInt();

b = sc.nextInt();

used[a][b] = used[b][a] = true;

}

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

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

if(used[i][j] == false){

System.out.println("NO");

return;

}

System.out.println("YES");

}

Идея решения Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO». Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015

Задача e-olimp.com №4856. Ссылка на засчитанное решение. Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами. Входные данные Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между … Continue reading →

e-olimp 5078. Турнир

22/04/2015

Задача e-olimp.com №5078. Ссылка на засчитанное решение (C++). Ссылка на засчитанное решение (Java). Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром. Входные данные Входной файл содержит числа [latex]n \left(1\leq n\leq 100 \right)[/latex] — число вершин в графе и [latex]m \left(1\leq m\leq n\left(n-1 … Continue reading →

e-olimp 4847. Очередь с приоритетами

07/04/2015

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции: Добавление элемента в очередь. Удаление из очереди элемента с наибольшим приоритетом. Изменение приоритета для произвольного элемента, находящегося в очереди. Тесты: input data output data add eight 8 <вывод не предусмотрен> add three 3 <вывод не предусмотрен> add eleven 11 <вывод не предусмотрен> add one 1 <вывод … Continue reading →

e-olimp 3837. Выражения

05/04/2015

Задача Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими … Continue reading →

e-olimp 4475. Часы

03/04/2015

4475. Часы Постановка задачи Ученые разработали часы, которые могут налаживаться для отсчета времени на любой планете. Они состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если … Continue reading →

e-olimp 3809. ГАС Очередь

02/04/2015

Задача e-olimp.com №3809. Ссылка на засчитанное решение. За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос «Кто последний?«, посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь. Однако, пока такие системы … Continue reading →

e-olimp 2510. Сортировка очередями

02/04/2015

e-olimp 2510. Сортировка очередями Постановка задачи Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex]. По заданной последовательности различных чисел, которую требуется отсортировать, составить программу для этого устройства, которая будет выводить в выходной поток те же числа, что поступили во входной поток, но упорядоченные по возрастанию. Программа … Continue reading →

e-olimp 122. Горные маршруты

02/04/2015

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и … Continue reading →

АА18

02/04/2015

Задача В строке найти первое слово, которое встречается два раза подряд. Слова разделяются одним или несколькими пробелами. Напечатать его. Пояснение к решению Идея простая: последовательно разбиваем строку на отдельные слова с помощью функций стандартной библиотеки смотрим, не встретилось ли некоторое слово два раза подряд Решение Основной вариант:

#include <iostream>
#include <sstream>
using namespace std;

int main() {
   	string str, a, b, tmp;
    getline(cin, str);
	stringstream ss(str);
	ss >> a;
    while (ss >> tmp) {
    	if (a == tmp) {
    		cout << a << endl;
    		return 0;
    	}
    	a = tmp;
    }
	cout << "Нет повторов" << endl;
	return 0;
}

#include <iostream>

#include <sstream>

using namespace std;

int main() {

string str, a, b, tmp;

getline(cin, str);

stringstream ss(str);

ss >> a;

while (ss >> tmp) {

if (a == tmp) {

cout << a << endl;

return 0;

}

a = tmp;

}

cout << "Нет повторов" << endl;

return 0;

}

Перевод на Java:

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String s, t;
		boolean check = true;
		s = in.next();
		while (in.hasNext()) {
            t = in.next();
            if (s.equals(t)) {
            	System.out.println(s);
            	check = false;
            }
            s = t;
        }
        if (check)
	        System.out.println("Нет повторов");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

String s, t;

boolean check = true;

s = in.next();

while (in.hasNext()) {

t = in.next();

if (s.equals(t)) {

System.out.println(s);

check = false;

}

s = t;

}

if (check)

System.out.println("Нет повторов");

}

Старый неаккуратный и … Continue reading →

AA1

01/04/2015

Задача: В заданной строке заменить подряд идущие пробелы на один пробел. Примечание: Будем называть строку правильной, если она не содержит подряд идущих пробелов. Тестирование: Исходная строка Оптимистичное ожидание Комментарий Gagarin became an international celebrity, and was … Continue reading →

e-olimp 6130. Дек неограниченного размера.

01/04/2015

Задача: Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы: push_front Добавить (положить) в начало дека новый элемент. Программа должна … Continue reading →

AA17

31/03/2015

Задача: В заданной строке найти первый символ, который встречается два раза подряд и удалить одно из этих вхождений. Решение: Заводим цикл от первого символа, в цикле сравниваем каждый символ с предыдущим. Если они совпадают — удаляем один из них. Код C++:

#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 1; i < s.length(); i++){
        if (s[i] == s[i-1]){
            s.erase(s.begin()+i);
        }
    }
    cout << s << endl;
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

for (int i = 1; i < s.length(); i++){

if (s[i] == s[i-1]){

s.erase(s.begin()+i);

}

cout << s << endl;

return 0;

}

Код Java:

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

class Ideone {
	public static void main (String[] args) {
		String st;
		Scanner sc = new Scanner (System.in);
		st = sc.next();
		StringBuilder s = new StringBuilder(st);
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i-1)){
				s.deleteCharAt(i);
			}
		}
		System.out.println(s.toString());
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

String st;

Scanner sc = new Scanner (System.in);

st = sc.next();

StringBuilder s = new StringBuilder(st);

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == s.charAt(i-1)){

s.deleteCharAt(i);

}

System.out.println(s.toString());

}

Тесты: Строка Результат aassddff asdf 1122345566 123456 Related Images:

AA4

31/03/2015

Задача: В заданной строке удалить все латинские буквы. Ввод Вывод zdfgzdfg987w435kjwbsdf987w345 987435987345 Решение: Код программы С++:

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string s;
    cin>>s;
    for (int i=0; i<s.length(); i++){
        if ((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){
            s.erase(i,1); i--;
        }
    }
    cout<<s;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin>>s;

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

if ((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){

s.erase(i,1); i--;

}

cout<<s;

}

Ссылка на ideone Java: http://ideone.com/a2x238

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String sin = in.nextLine();
		StringBuffer str = new StringBuffer(sin);
		char si;
		for (int i=0; i<str.length(); i++){
			si=str.charAt(i);
		    if ((si>='a'&&si<='z')||(si>='A'&&si<='Z')){
		        str.deleteCharAt(i); i--;
		    }
		}
		System.out.printf("%s",str);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

String sin = in.nextLine();

StringBuffer str = new StringBuffer(sin);

char si;

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

si=str.charAt(i);

if ((si>='a'&&si<='z')||(si>='A'&&si<='Z')){

str.deleteCharAt(i); i--;

}

System.out.printf("%s",str);

}

Вводим строку. Перебираем все символы строки в цикле и удаляем символ, если он является латинской буквой Related Images:

А71

31/03/2015

Задача. Дано действительное число [latex]a[/latex]. Вычислить [latex]f(a)[/latex], где [latex]f[/latex] — периодическая функция с периодом 1.5, совпадающая на отрезке [latex][0;1.5][/latex] с функцией [latex]x^{3}-2.25x[/latex]. Тесты: [latex]a[/latex] [latex]f(a)[/latex] Комментарий 2.12 -1.15667 Тест пройден -8 -1.25 Тест пройден 11.6 -1.114 Тест пройден 3.7 -1.232 Тест пройден Код:

#include <iostream>
using namespace std;
int main() 
{
	float f, a, b;
	double p=1.5;
	int c;
	cin>>a;

	if(a>=0)
	{
		c=a/p;
		b=a/p;
		a=(b-c)*p;
	}
	else if(a<0)
	{
		c=(-a)/p;
		a=(c+1)*p+a;
	}
	f=a*a*a-2.25*a;
	cout<<f<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

float f, a, b;

double p=1.5;

int c;

cin>>a;

if(a>=0)

{

c=a/p;

b=a/p;

a=(b-c)*p;

}

else if(a<0)

{

c=(-a)/p;

a=(c+1)*p+a;

}

f=a*a*a-2.25*a;

cout<<f<<endl;

return 0;

}

Решение: Для положительных мы просто приравниваем [latex]a[/latex] к остатку от деления числа [latex]a[/latex] на период [latex]p=1.5[/latex], таким образом … Continue reading →