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

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

Timus 2002 by Tolia

25/12/2015 by Осецимский Анатолий

Для решения использовалось AVL-дерево выложенное тут.

Алгоритм решения задачи с соответствием с условием задачи.

import java.util.Scanner;

/**
 * Created by green on 25.12.15.
 */

class State{
    String password;
    Boolean login;
    State(String password){
        this.password = password;
        login = false;
    }
}


public class Task2002 {
    public static void main (String[] args) {
        AVL<String, State> DB = new AVL();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s;
        for(int i = 0; i < n; i++){
            s = in.next();
            if(s.equals("register")){
                String name = in.next(), pass = in.next();
                if(DB.containKey(name)){
                    System.out.println("fail: user already exists");
                }else{
                    DB.add(name,new State(pass));
                    System.out.println("success: new user added");
                }
            }else if(s.equals("login")){
                String name = in.next(), pass = in.next();
                State temp = DB.get(name);
                if (temp == null) {
                    System.out.println("fail: no such user");
                }
                else if (!pass.equals(temp.password)) {
                    System.out.println("fail: incorrect password");
                }
                else {
                    if (temp.login == false) {
                        temp.login = true;
                        DB.add(name, temp);
                        System.out.println("success: user logged in");
                    }
                    else {
                        System.out.println("fail: already logged in");
                    }
                }
            }else{
                String name = in.next();
                State temp = DB.get(name);
                if (temp == null) {
                    System.out.println("fail: no such user");
                }
                else {
                    if (temp.login == true) {
                        temp.login = false;
                        DB.add(name, temp);
                        System.out.println("success: user logged out");
                    }
                    else {
                        System.out.println("fail: already logged out");
                    }
                }
            }
        }
    }
}

import java.util.Scanner;

/**

* Created by green on 25.12.15.

class State{

String password;

Boolean login;

State(String password){

this.password = password;

}

public class Task2002 {

public static void main (String[] args) {

AVL<String, State> DB = new AVL();

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s;

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

s = in.next();

if(s.equals("register")){

String name = in.next(), pass = in.next();

if(DB.containKey(name)){

System.out.println("fail: user already exists");

}else{

DB.add(name,new State(pass));

System.out.println("success: new user added");

}

}else if(s.equals("login")){

String name = in.next(), pass = in.next();

State temp = DB.get(name);

if (temp == null) {

System.out.println("fail: no such user");

}

else if (!pass.equals(temp.password)) {

System.out.println("fail: incorrect password");

}

else {

if (temp.login == false) {

temp.login = true;

DB.add(name, temp);

System.out.println("success: user logged in");

}

else {

System.out.println("fail: already logged in");

}

}else{

String name = in.next();

State temp = DB.get(name);

if (temp == null) {

System.out.println("fail: no such user");

}

else {

if (temp.login == true) {

temp.login = false;

DB.add(name, temp);

System.out.println("success: user logged out");

}

else {

System.out.println("fail: already logged out");

}

Ссылка на решение.

Обратная польская запись

20/12/2015 by v.zelinsky96

// Символы во входном потоке следует вводить через пробел.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone{
 
	public static void main (String[] args) throws java.lang.Exception{
		try{
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			String line;
			String a1="";
			int st_len=0;
			Stack<String> st = new Stack();
			while( (line = reader.readLine()) != null){
				String[] a = line.split(" ");
				for(int i = 0 ; i < a.length ; i++){
					if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){
						a1+=a[i];
					}
					else{
						if((a[i].equals("+") || a[i].equals("-")) && st_len>0){
							for(int j=0; j<2;j++){
								if(st_len>0){
									if(!st.peek().equals("(")){
										a1+=st.pop();
										st_len--;
									}
								}
							} 
						}
						if((a[i].equals("*") || a[i].equals("/")) && st_len>0){
							for(int j=0; j<1;j++){
								if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){
									a1+=st.pop();
									st_len--;
								}
							} 
						}
						if(a[i].equals(")") && st_len>0){
							for(int j=0; j<=st_len+2;j++){
								if(!st.peek().equals("(")){
									a1+=st.pop();
									st_len--;
								}
							}
							if(st_len!=0){
					    		a1+=st.pop();
					   			st_len--;
							}
						}
						st.push(a[i]);
						st_len++;
					}
			}
			for(int i = 0 ; i < st_len ; i++){
				a1+=st.pop();
			}
			for(int i = 0 ; i < a1.length() ; i++){
				if(a1.charAt(i)!='(' && a1.charAt(i)!=')')
					System.out.print(a1.charAt(i)+" ");
				}
			}
		}catch(IOException ex){
			System.err.println("Eror");
		}
	}
}

// Символы во входном потоке следует вводить через пробел.

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

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

try{

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

String line;

String a1="";

int st_len=0;

Stack<String> st = new Stack();

while( (line = reader.readLine()) != null){

String[] a = line.split(" ");

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

if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){

a1+=a[i];

}

else{

if((a[i].equals("+") || a[i].equals("-")) && st_len>0){

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

if(st_len>0){

if(!st.peek().equals("(")){

a1+=st.pop();

st_len--;

}

if((a[i].equals("*") || a[i].equals("/")) && st_len>0){

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

if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){

a1+=st.pop();

st_len--;

}

if(a[i].equals(")") && st_len>0){

for(int j=0; j<=st_len+2;j++){

if(!st.peek().equals("(")){

a1+=st.pop();

st_len--;

}

if(st_len!=0){

a1+=st.pop();

st_len--;

}

st.push(a[i]);

st_len++;

}

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

a1+=st.pop();

}

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

if(a1.charAt(i)!='(' && a1.charAt(i)!=')')

System.out.print(a1.charAt(i)+" ");

}

}catch(IOException ex){

System.err.println("Eror");

}

Алгоритм:

Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты:
1) Если символ не является символом функции или скобкой, добавляем его к выходной строке.
2)

Если встретили символ функции, помещаем его в стек.
Если встретили символ функции и при этом стек не пустой, выталкиваем в выходную строку все символы функции, пока не встретим символ, имеющий больший приоритет или открывающую скобку.
Если символ является закрывающей скобкой:
Выталкиваем элементы из стека в выходную строку, пока верхним элементом стека не станет открывающая скобка. Если после этого на вершине стека находится символ функции, выталкиваем его в выходную строку.
Если символ является открывающей скобкой, помещаем его в стек.

Код на Ideone.

Wallpainter

28/07/2015 by Valeriya Rud

Task

One construction company wants to minimize paint expenses. For this reason has to be made a program which can calculate an amount of a paint for the each order. Usually the owner know the longness L , wideness W , and highness H of the each room. Also one can of pain is good enough to paint 16 m², and the size of windows and doors are not important in this calculation

Input:

In the first line should be orders` amount. In the each next line — L, W, H and the wideness, longness, and highness are not more than 1000 .

Output:

For the each order will be shown one one number, what is required amount of the paint cans

Tests

Input	Output
2
8 8 2	4
1 1 3	1
10 6 2	4
11 6 2	5

Solution

Task «Repair» can be solved by using Data Strim processing.

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

class Main{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner s = new Scanner(System.in);
		double order = s.nextDouble();
		for(int i = 0; i < order; i++){
			double l = s.nextDouble();
			double w = s.nextDouble();
			double h = s.nextDouble();
			int quantity =(int)Math.ceil(h * (l + w) / 8);
			System.out.println(quantity);
		}
	}
}

import java.util.*;

import java.io.*;

class Main{

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

Scanner s = new Scanner(System.in);

double order = s.nextDouble();

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

double l = s.nextDouble();

double w = s.nextDouble();

double h = s.nextDouble();

int quantity =(int)Math.ceil(h * (l + w) / 8);

System.out.println(quantity);

}

Three flowers

17/07/2015 by Valeriya Rud

Задача взята с сайта e-olymp.com.

В рождественский вечер на окошке стояло три цветочка, слева на право: герань, крокус и фиалка. Каждое утро Маша вытирала окошко и меняла местами стоящий справа цветок с центральным цветком. А Таня каждый вечер поливала цветочки и меняла местами левый и центральный цветок. Требуется определить порядок цветов ночью по прошествии k дней.

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

Первая строка содержит количество тестов m (1 ≤ m ≤ 12). В каждой из следующих m строк находится количество дней k (1 ≤ k ≤ 1000).

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

Вывести m строк, содержащих по три латинских буквы: «G», «C» и «V» (заглавные буквы без пробелов), описывающие порядок цветов на окошке по истечении k дней (слева направо). Обозначения: G – герань, C – крокус, V – фиалка.

Тесты

Input	Output
2
1	VGC
5	CVG

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

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

Timus 2002 by Tolia

Обратная польская запись

Wallpainter

Task

Input:

Output:

Tests

Solution

Three flowers

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

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

Тесты

Решение