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

09/05/2018 by Иван Василевский

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

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

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

Входные данные
В первой строке входного файла записано количество [latex]N[/latex] претендентов на звание вождя в этом году [latex](1 ≤ N ≤ 1000000)[/latex], а во второй – [latex]N[/latex] целых чисел в пределах от [latex]1[/latex] до [latex]10000[/latex], каждое из которых определяет силу соответствующего кандидата.

Выходные данные
Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.

Continue reading →

Related Images:

MS2. Сумма чисел во входном потоке

23/04/2017 by Роман Саркисян

Условие

Сосчитайте сумму чисел во входном потоке.

Тесты

Ввод	Вывод
1 2 3 4 5 6	21
12 13 14	39
1-100	5050

#include <iostream>
using namespace std;

int main() {
    double x, S=0;
    while( cin>>x){
        S+=x;
    }
    cout<<S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, S=0;

while( cin>>x){

S+=x;

}

cout<<S;

return 0;

}

import java.util.*;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner scan = new Scanner(System.in);
        double sum = 0;
        double number = 0;
        while(scan.hasNext()){
            number=scan.nextInt();
            sum+=number;
        }
        System.out.println(sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

Scanner scan = new Scanner(System.in);

double sum = 0;

double number = 0;

while(scan.hasNext()){

number=scan.nextInt();

sum+=number;

}

System.out.println(sum);

}

Решение

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

Код на ideone C++
Код на ideone Java

Related Images:

MS 7. Средняя зарплата

28/03/2017 by Андреев Даниил

Задача

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

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

Фамилия работника ([latex]name[/latex]) и величина его зарплаты ([latex]sal[/latex]).

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

Средняя зарплата по компании.

Тесты

Входные данные		Выходные данные
[latex]name[/latex]	[latex]sal[/latex]
Ivanov	200	200
Ivanov Smirnov Popov Sokolov	100 150 200 150	150

Код программы на C++

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

int main() {
    string name;
    double sal, total=0, sum=0;
    
    while (cin >> name){
        cin >> sal;
        total+=sal;
        sum++;
    }
    
    cout << total/sum;
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string name;

double sal, total=0, sum=0;

while (cin >> name){

cin >> sal;

total+=sal;

sum++;

}

cout << total/sum;

return 0;

}

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

import java.util.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        double total=0, sum=0;
        
        while (scan.hasNext()){
            if (!scan.hasNextDouble()){
                scan.next();
                total += scan.nextDouble();
                sum++;
            }
            else    scan.next();
        }
        System.out.print(total/sum);
    }
}

import java.util.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

double total=0, sum=0;

while (scan.hasNext()){

if (!scan.hasNextDouble()){

scan.next();

total += scan.nextDouble();

sum++;

}

else scan.next();

}

System.out.print(total/sum);

}

Решение

В переменную [latex]total[/latex] которая изначально равна [latex]0[/latex] прибавляем зарплату каждого сотрудника, а [latex]sum[/latex] показывает количество сотрудников. Выводим зарплату всех сотрудников деленную на их количество.

Ссылки

Ideone C++
Ideone Java

Related Images:

MS15. Зашифровка и расшифровка текста

12/12/2016 by Эммануил Прокопов

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

Условие задачи MS14.
Зашифруйте текст из входного потока заменяя каждый символ по формуле [latex]c=at+b \mod 256[/latex], где [latex]t[/latex] — символ открытого текста, [latex]c[/latex] — символ зашифрованного текста, [latex]a[/latex], [latex]b[/latex] — произвольные ключи (параметры) шифрования.

Входные данные:
Два ключа через пробел и, через ещё один пробел, текст.

Выходные данные:
Зашифрованный текст.

Тесты.

№	Входные данные			Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	Исходный текст	Зашифрованный текст
1	f	n	Kittens	P▲D*ж.ж.м(B,@.
2	4	j	Hello, world!	◙☼ю¶z▬z▬ў▬z○ъ♠ц↑ў▬т↨z▬║¶▲•
3	?	.	0123456789	■♂=♀\|♀╗♀·♀9♪x♪╖♪ў♪5♫

Код на С++

#include <iostream>
using namespace std;

int main() {
    unsigned char c, a, b;
    scanf("%c", &a); //Первый ключ
    scanf("%c", &c); //Пробел
    scanf("%c", &b); //Второй ключ
    scanf("%c", &c); //Пробел
    while (EOF != scanf("%c", &c)) //Пока не кончатся входные данные
    {
        printf("%c", (c*a+b)%256);
        printf("%c", (c*a+b)/256);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned char c, a, b;

scanf("%c", &a); //Первый ключ

scanf("%c", &c); //Пробел

scanf("%c", &b); //Второй ключ

scanf("%c", &c); //Пробел

while (EOF != scanf("%c", &c)) //Пока не кончатся входные данные

{

printf("%c", (c*a+b)%256);

printf("%c", (c*a+b)/256);

}

return 0;

}

Код на Java

import java.util.*;
import java.math.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        in.useDelimiter(""); //Чтение по одному символу.
        
        int a = (int)in.next().charAt(0); //Первый ключ
        int c = (int)in.next().charAt(0); //Пробел
        int b = (int)in.next().charAt(0); //Второй ключ
        c = (int)in.next().charAt(0);     //Пробел
        
        while(in.hasNext()){
            c = (int)in.next().charAt(0);
            System.out.print((char)((c*a+b)%256));
            System.out.print((char)((c*a+b)/256));
        }
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

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

int a = (int)in.next().charAt(0); //Первый ключ

int c = (int)in.next().charAt(0); //Пробел

int b = (int)in.next().charAt(0); //Второй ключ

c = (int)in.next().charAt(0); //Пробел

while(in.hasNext()){

c = (int)in.next().charAt(0);

System.out.print((char)((c*a+b)%256));

System.out.print((char)((c*a+b)/256));

}

Условие задачи MS15.
Найдите способ и напишите программу расшифровки текста зашифрованного в предыдущем задании по известным [latex]a[/latex] и [latex]b[/latex].

Входные данные:
Два ключа через пробел и, через ещё один пробел, зашифрованный текст.

Выходные данные:
Расшифрованный текст.

Тесты.

№	Входные данные			Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	Зашифрованный текст	Расшифрованный текст
1	f	n	P▲D*ж.ж.м(B,@.	Kittens
2	4	j	◙☼ю¶z▬z▬ў▬z○ъ♠ц↑ў▬т↨z▬║¶▲•	Hello, world!
3	?	.	■♂=♀\|♀╗♀·♀9♪x♪╖♪ў♪5♫	0123456789

Код на C++

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

int main() {
    unsigned char a, b, tmp, c1, c2;
    scanf("%c", &a); //Первый ключ
    scanf("%c", &c1); //Пробел
    scanf("%c", &b); //Второй ключ
    scanf("%c", &c1); //Пробел
    while (EOF != scanf("%c", &c1)) //Пока не кончатся входные данные
    {
        scanf("%c", &c2);
        tmp=round((c1-b+256*c2)*1.0/a);
        printf("%c", tmp);
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned char a, b, tmp, c1, c2;

scanf("%c", &a); //Первый ключ

scanf("%c", &c1); //Пробел

scanf("%c", &b); //Второй ключ

scanf("%c", &c1); //Пробел

while (EOF != scanf("%c", &c1)) //Пока не кончатся входные данные

{

scanf("%c", &c2);

tmp=round((c1-b+256*c2)*1.0/a);

printf("%c", tmp);

}

return 0;

}

Код на Java

import java.util.*;
import java.math.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        in.useDelimiter(""); //Чтение по одному символу.
        
        //String a = new String();
        int a = (int)in.next().charAt(0);  //Первый ключ
        int c1 = (int)in.next().charAt(0); //Пробел
        int b = (int)in.next().charAt(0);  //Второй ключ
        int c2 = (int)in.next().charAt(0); //Пробел
        
        while(in.hasNext()){
            c1 = (int)in.next().charAt(0);
            c2 = (int)in.next().charAt(0);
            System.out.print((char) Math.round((c1-b+256*c2)*1.0/a));
        }
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

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

//String a = new String();

int a = (int)in.next().charAt(0); //Первый ключ

int c1 = (int)in.next().charAt(0); //Пробел

int b = (int)in.next().charAt(0); //Второй ключ

int c2 = (int)in.next().charAt(0); //Пробел

while(in.hasNext()){

c1 = (int)in.next().charAt(0);

c2 = (int)in.next().charAt(0);

System.out.print((char) Math.round((c1-b+256*c2)*1.0/a));

}

Решение.
Основной трудностью при решении задачи является тот момент, что при шифровке символов строго по формуле, указанной в условии MS14, а именно [latex]c=at+b \mod 256[/latex], символы зашифрованного текста могут расшифровываться неоднозначно. К примеру, при [latex]a=8[/latex] и [latex]b=1[/latex] после зашифровки символов [latex]@[/latex] и [latex]`[/latex] в обоих случаях получим символ с кодом [latex]1[/latex]. Это часто лишает расшифрованный текст какого-либо смысла. Так происходит, поскольку в переменных типа [latex]unsigned[/latex] [latex]char[/latex] могут храниться элементы с кодом от [latex]0[/latex] до [latex]255[/latex], и при попытке присвоить переменной большее значение совершается своеобразный «круг». Так, если ей присвоить значение [latex]257[/latex], при выводе получим символ с кодом [latex]1[/latex]. Сначала в ходе работы обеих программ вводятся два ключа, а лишние пробелы читаются в одну из переменных для хранения символов. Программа для зашифровки принимает символ, зашифровывает его по указанной формуле, и выводит, а сразу за ним — элемент с кодом, который высчитывается по другой формуле: [latex]c=(at+b) / 256[/latex]. Этот код совпадает с числом совершённых «кругов». Программа для расшифровки же на каждом цикле принимает эти два символа, и выводит символ исходного текста, код которого вычисляется округлением до целых значения выражения [latex]\frac { c1-b+256\cdot c2 }{ a } [/latex], где [latex]c1[/latex] — первый символ, а [latex]c2[/latex] — второй.

Условия задач.
Код MS14 на ideone.com(C++)
Код MS15 на ideone.com(C++)
Код MS14 на ideone.com(Java)
Код MS15 на ideone.com(Java)