Chuck Norris

11/05/2017 by Антон Куперман

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

The input message consists of ASCII characters (7-bit)
The encoded output message consists of blocks of 0
A block is separated from another block by a space
Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
— First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
— Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

Input	Output
C	0 0 00 0000 0 00
CC	0 0 00 0000 0 000 00 0000 0 00
%	00 0 0 0 00 00 0 0 00 0 0 0
Hello	0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

Code

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


string binary(unsigned char x){
    unsigned char mask=64;
    string s;
    for(int i=0; i<7; i++) {
        s.push_back((x&mask)>0 ? '1':'0');
        mask=mask>>1;
    }
    return s;
}

int main() {
    string l;
    string a;
    unsigned char x;
    while(cin >> x){
        l+=binary(x);
    }
    for(int i=0;i<l.size();i++)
    {
        if(l.at(i)=='0')
        {
            if(i==0||l.at(i-1)=='1')
            {
                if(i!=0)
                {
            a+=" ";
            a.push_back('0');
            a.push_back('0');
            a+=" ";
                } else {
                    a.push_back('0');
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        } else if(l.at(i)=='1')
        {
            if(i==0||l.at(i-1)=='0')
            {
                if(i!=0)
                {
                a+=" ";
                a.push_back('0');
                a+=" ";
                } else{ 
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        }   
    }
    for(int i=0;i<a.size();i++)
    {
        if(a.at(i)=='1')
        {
            a.at(i)='0';
        }
    }
    cout<<a;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string binary(unsigned char x){

unsigned char mask=64;

string s;

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

s.push_back((x&mask)>0 ? '1':'0');

mask=mask>>1;

}

return s;

}

int main() {

string l;

string a;

unsigned char x;

while(cin >> x){

l+=binary(x);

}

for(int i=0;i<l.size();i++)

{

if(l.at(i)=='0')

{

if(i==0||l.at(i-1)=='1')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else {

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

} else if(l.at(i)=='1')

{

if(i==0||l.at(i-1)=='0')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else{

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

}

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

{

if(a.at(i)=='1')

{

a.at(i)='0';

}

cout<<a;

return 0;

}

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin. Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

Related Images:

ASCII ART

16/04/2017 by Вадим Гордийчук

Task

In stations and airports you often see this type of screen:

Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!

Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.

Input

Line 1: the width L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text T, composed of N ASCII characters.
Following H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.

[latex]0 < [/latex] L[latex] < 30[/latex] [latex]0 < [/latex] H[latex] < 30[/latex] [latex]0 < [/latex] N[latex] < 200[/latex]

Output

The text T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.

Tests

Input	Output
1 1 Encoding using ASCII? Hah! ?ZYXWVUTSRQPONMLKJIHGFEDCBA	WNYMXSNUAGISNUA?IYSSAAT?TA

Codes of the program

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    short Lwidth, Lheight;
    cin >> Lwidth >> Lheight; cin.ignore();
    string Text;
    char **alphabet = new char*[256];
    
    //initializing alphabet
    for (char ltr = 'a'; ltr < 'z'+1; ++ltr)
    {
        alphabet[ltr] = new char[Lwidth];
    }
    for (char ltr = 'A'; ltr < 'Z'+1; ++ltr)
    {
        alphabet[ltr] = new char[Lwidth];
    }
    alphabet['?'] = new char[Lwidth];
    
    getline(cin, Text);
    for (short h = 0; h < Lheight; ++h)
    {
        char ltr;
        for (ltr = 'a'; ltr < 'z'+1; ++ltr) //reading letters
        {
            for (short w = 0; w < Lwidth; ++w)
            {
                scanf("%c", &alphabet[ltr][w]);
                alphabet[ltr-('a'-'A')][w] = alphabet[ltr][w];
            }
        }
        
        for (short w = 0; w < Lwidth; ++w) //reading ?
        {
            scanf("%c", &alphabet['?'][w]);
        }
        
        scanf("%c", &ltr); //reading endl
        if (ltr != '\n') cerr << "ERROR: INVALID TESTS PROVIDED\n";
        
        //Putting result out.
        for (short i = 0; i < Text.size(); ++i)
        {
            if //it is a letter
            (
                (('a'-1 < Text[i]) && (Text[i] < 'z'+1)) ||
                (('A'-1 < Text[i]) && (Text[i] < 'Z'+1))
            ) //then print it
                cout << alphabet[Text[i]];
            else //it is definitely something weird
                cout << alphabet['?'];
        }
        cout << '\n';
    }
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

short Lwidth, Lheight;

cin >> Lwidth >> Lheight; cin.ignore();

string Text;

char **alphabet = new char*[256];

//initializing alphabet

for (char ltr = 'a'; ltr < 'z'+1; ++ltr)

{

alphabet[ltr] = new char[Lwidth];

}

for (char ltr = 'A'; ltr < 'Z'+1; ++ltr)

{

alphabet[ltr] = new char[Lwidth];

}

alphabet['?'] = new char[Lwidth];

getline(cin, Text);

for (short h = 0; h < Lheight; ++h)

{

char ltr;

for (ltr = 'a'; ltr < 'z'+1; ++ltr) //reading letters

{

for (short w = 0; w < Lwidth; ++w)

{

scanf("%c", &alphabet[ltr][w]);

alphabet[ltr-('a'-'A')][w] = alphabet[ltr][w];

}

for (short w = 0; w < Lwidth; ++w) //reading ?

{

scanf("%c", &alphabet['?'][w]);

}

scanf("%c", &ltr); //reading endl

if (ltr != '\n') cerr << "ERROR: INVALID TESTS PROVIDED\n";

//Putting result out.

for (short i = 0; i < Text.size(); ++i)

{

if //it is a letter

(

(('a'-1 < Text[i]) && (Text[i] < 'z'+1)) ||

(('A'-1 < Text[i]) && (Text[i] < 'Z'+1))

) //then print it

cout << alphabet[Text[i]];

else //it is definitely something weird

cout << alphabet['?'];

}

cout << '\n';

}

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

class Solution
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        short Lwidth = in.nextShort(), Lheight = in.nextShort();
        Map alphabet = new HashMap();
        
        if (in.hasNextLine())
        {
            in.nextLine();
        }
        
        String Text = in.nextLine();

        for (short h = 0; h < Lheight; ++h)
        {
            String alphabet_line = in.nextLine();
            short i = 0;
            
            for(char sym = 'a', Sym = 'A'; sym <= 'z'; ++sym, ++Sym, ++i)
            {
                String letter = alphabet_line.substring(i*Lwidth, (i+1)*Lwidth);
                alphabet.put(sym, letter);
                alphabet.put(Sym, letter);
            }
            alphabet.put('?', alphabet_line.substring(i*Lwidth, (i+1)*Lwidth));
            
            for(i = 0; i < Text.length(); ++i)
            {
                if //it is a letter
                (
                    (('a' <= Text.charAt(i)) && (Text.charAt(i) <= 'z')) ||
                    (('A' <= Text.charAt(i)) && (Text.charAt(i) <= 'Z'))
                )
                    out.print(alphabet.get(Text.charAt(i)));
                else //it is definitely something weird
                    out.print(alphabet.get('?'));
            }
            out.print('\n');
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

class Solution

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short Lwidth = in.nextShort(), Lheight = in.nextShort();

Map alphabet = new HashMap();

if (in.hasNextLine())

{

in.nextLine();

}

String Text = in.nextLine();

for (short h = 0; h < Lheight; ++h)

{

String alphabet_line = in.nextLine();

short i = 0;

for(char sym = 'a', Sym = 'A'; sym <= 'z'; ++sym, ++Sym, ++i)

{

String letter = alphabet_line.substring(i*Lwidth, (i+1)*Lwidth);

alphabet.put(sym, letter);

alphabet.put(Sym, letter);

}

alphabet.put('?', alphabet_line.substring(i*Lwidth, (i+1)*Lwidth));

for(i = 0; i < Text.length(); ++i)

{

if //it is a letter

(

(('a' <= Text.charAt(i)) && (Text.charAt(i) <= 'z')) ||

(('A' <= Text.charAt(i)) && (Text.charAt(i) <= 'Z'))

)

out.print(alphabet.get(Text.charAt(i)));

else //it is definitely something weird

out.print(alphabet.get('?'));

}

out.print('\n');

}

out.flush();

}

<?php
fscanf(STDIN, "%d", $Lwidth);
fscanf(STDIN, "%d", $Lheight);

$alphabet = array();

$Text = stream_get_line(STDIN, 1024, "\n");

for ($h = 0; $h < $Lheight; ++$h)
{   
    $ltr = 'a';
    $ltr2 = 'A';
    while(true) //reading letters
    {
        $alphabet[$ltr] = stream_get_line(STDIN, $Lwidth);
        $alphabet[$ltr2] = $alphabet[$ltr];
        if ($ltr == 'z') break;
        ++$ltr;
        ++$ltr2;
    }
    
    //reading '?'
    $alphabet['?'] = stream_get_line(STDIN, $Lwidth);

    //reading endl   
    fscanf(STDIN, "%c", $useless);
    
    for ($i = 0; $i < strlen($Text); ++$i)
    {
        if //it is a letter
        (
            (('a' <= $Text[$i]) and ($Text[$i] <= 'z')) or
            (('A' <= $Text[$i]) and ($Text[$i] <= 'Z'))
        ) //then print it
            echo $alphabet[$Text[$i]];
        else //it is definitely something weird
            echo $alphabet['?'];
    }
    echo "\n";
}
?>

<?php

fscanf(STDIN, "%d", $Lwidth);

fscanf(STDIN, "%d", $Lheight);

$alphabet = array();

$Text = stream_get_line(STDIN, 1024, "\n");

for ($h = 0; $h < $Lheight; ++$h)

{

$ltr = 'a';

$ltr2 = 'A';

while(true) //reading letters

{

$alphabet[$ltr] = stream_get_line(STDIN, $Lwidth);

$alphabet[$ltr2] = $alphabet[$ltr];

if ($ltr == 'z') break;

++$ltr;

++$ltr2;

}

//reading '?'

$alphabet['?'] = stream_get_line(STDIN, $Lwidth);

//reading endl

fscanf(STDIN, "%c", $useless);

for ($i = 0; $i < strlen($Text); ++$i)

{

if //it is a letter

(

(('a' <= $Text[$i]) and ($Text[$i] <= 'z')) or

(('A' <= $Text[$i]) and ($Text[$i] <= 'Z'))

) //then print it

echo $alphabet[$Text[$i]];

else //it is definitely something weird

echo $alphabet['?'];

}

echo "\n";

}

Solution of the task

After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.

Links

Related Images:

There is no Spoon — Episode 1

15/04/2017 by Вадим Гордийчук

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

You give an incorrect neighbor for a node.
You give the neighbors for an empty cell.
You compute the same node twice.
You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

( x1, y1) the coordinates of a node.
( x2, y2) the coordinates the closest neighbor on the right of the node.
( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input	Output
2 2 00 0.	0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1
4 4 .0.. .000 000. ..0.	1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1

The code of the program

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

int main()
{
    short width; // the number of cells on the X axis
    cin >> width; cin.ignore();
    short height; // the number of cells on the Y axis
    cin >> height; cin.ignore();
    string *node = new string[height];
    short x, y;
    for (y = 0; y < height; ++y)
    {
        getline(cin, node[y]);
    }
    for (y = 0; y < height; ++y)
    {
        for (x = 0; x < width; ++x)
        {
            if (node[y][x] == '0')
            {
                cout << x << ' ' << y << ' ';
                short x2, y2, ansX = -1, ansY = -1;
                for (x2 = x+1; x2 < width; ++x2)
                {
                    if (node[y][x2] == '0')
                    {
                        ansX = x2;
                        ansY = y;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << ' ';
                ansX = -1; ansY = -1;
                for (y2 = y+1; y2 < height; ++y2)
                {
                    if (node[y2][x] == '0')
                    {
                        ansX = x;
                        ansY = y2;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << '\n';
                x = x2-1;
            }
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

short width; // the number of cells on the X axis

cin >> width; cin.ignore();

short height; // the number of cells on the Y axis

cin >> height; cin.ignore();

string *node = new string[height];

short x, y;

for (y = 0; y < height; ++y)

{

getline(cin, node[y]);

}

for (y = 0; y < height; ++y)

{

for (x = 0; x < width; ++x)

{

if (node[y][x] == '0')

{

cout << x << ' ' << y << ' ';

short x2, y2, ansX = -1, ansY = -1;

for (x2 = x+1; x2 < width; ++x2)

{

if (node[y][x2] == '0')

{

ansX = x2;

ansY = y;

break;

}

cout << ansX << ' ' << ansY << ' ';

ansX = -1; ansY = -1;

for (y2 = y+1; y2 < height; ++y2)

{

if (node[y2][x] == '0')

{

ansX = x;

ansY = y2;

break;

}

cout << ansX << ' ' << ansY << '\n';

x = x2-1;

}

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

class Player
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        short width = in.nextShort(); // the number of cells on the X axis
        short height = in.nextShort(); // the number of cells on the Y axis
        
        if (in.hasNextLine()) {
            in.nextLine();
        }

        String node[] = new String[height];
        
        for(short y = 0; y < height; ++y)
        {
            node[y] = in.nextLine();
        }
        
        for(short y = 0; y < height; ++y)
        {
            for(short x = 0; x < width; ++x)
            {
                if (node[y].charAt(x) == '0')
                {
                    out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");
                    short x2, y2, ansX = -1, ansY = -1;
                    for (x2 = (short)(x+1); x2 < width; ++x2)
                    {
                        if (node[y].charAt(x2) == '0')
                        {
                            ansX = x2;
                            ansY = y;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");
                    ansX = -1;
                    ansY = -1;
                    
                    for(y2 = (short)(y+1); y2 < height; ++y2)
                    {
                        if (node[y2].charAt(x) == '0')
                        {
                            ansX = x;
                            ansY = y2;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");
                    x = (short)(x2-1);
                }
            }
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short width = in.nextShort(); // the number of cells on the X axis

short height = in.nextShort(); // the number of cells on the Y axis

if (in.hasNextLine()) {

in.nextLine();

}

String node[] = new String[height];

for(short y = 0; y < height; ++y)

{

node[y] = in.nextLine();

}

for(short y = 0; y < height; ++y)

{

for(short x = 0; x < width; ++x)

{

if (node[y].charAt(x) == '0')

{

out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");

short x2, y2, ansX = -1, ansY = -1;

for (x2 = (short)(x+1); x2 < width; ++x2)

{

if (node[y].charAt(x2) == '0')

{

ansX = x2;

ansY = y;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");

ansX = -1;

ansY = -1;

for(y2 = (short)(y+1); y2 < height; ++y2)

{

if (node[y2].charAt(x) == '0')

{

ansX = x;

ansY = y2;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");

x = (short)(x2-1);

}

out.flush();

}

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Related Images:

Разбор Proggy-Buggy Contest

16/12/2015 by Вустянюк Ігор Дмитрович

5 декабря компанией DataArt проводилась международная юмористическая олимпиада по программированию Proggy-Buggy Contest.

Задачи на ней не были сложными, но решать их нужно было очень быстро: на 13 задач отводилось 42 минуты времени.

В Одесском офисе DataArt было рекордное количество команд-участинков среди всех городов, принимавших мероприятие. Среди участников была команда ONU_Rabid_Pandas (Марченко, Илларионова, Вустянюк), которая подготовила разбор задач соревнования:

Условия

Разбор

Пожалуйста, сообщайте в комментариях обо всех найденных очепятках и непонятках. Мы исправим и ответим на вопросы.

Related Images:

Horse-racing Duals

16/10/2014 by Вустянюк Ігор Дмитрович

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

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

Первая строка: число n — количество лошадей.

Следующие n строк — в каждой указано одно целое число — характеристика соответствующей лошади.

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

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу в лоб, нам понадобятся два цикла: один пробегает все значения по i, а другой — все значения по [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма: [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях n лучше, чем [latex] n^2 [/latex]. Пусть b — конечная последовательность, в которой элементы последовательности a расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности b, при любом [latex] i [/latex] имеем [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых [latex] i,j [/latex] если [latex]i < j[/latex], то [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за n действий. Таким образом, новая сложность составит примерно [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно [latex] n \cdot log(n) [/latex] и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int n;	// Количество лошадей
	cin >> n;
	int horses[n];	
	for (int i = 0; i < n; i++) {	// Помещаем характеристики лошадей
		cin >> horses[i];			// в массив
	}	
	std::sort(horses, horses + n);	// Сортируем массив horses по возрастанию
	int min_dif = horses[1] - horses[0];
	for (int i = 1; i < n - 1; i++) {	// Поиск минимальной разницы характеристик
	    int cur_dif = horses[i+1] - horses[i];
	    if (cur_dif < min_dif)
	        min_dif = cur_dif;
	}
	cout << min_dif;
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

int n; // Количество лошадей

cin >> n;

int horses[n];

for (int i = 0; i < n; i++) { // Помещаем характеристики лошадей

cin >> horses[i]; // в массив

}

std::sort(horses, horses + n); // Сортируем массив horses по возрастанию

int min_dif = horses[1] - horses[0];

for (int i = 1; i < n - 1; i++) { // Поиск минимальной разницы характеристик

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

cout << min_dif;

return 0;

}

Код на Java

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[] horses = new int[n];
		for (int i = 0; i < n; i++)
			horses[i] = in.nextInt();
		Arrays.sort(horses);
		int min_dif = horses[1] - horses[0];
		for (int i = 1; i < n-1; i++) {
			int cur_dif = horses[i+1] - horses[i];
			if (cur_dif < min_dif)
				min_dif = cur_dif;
		}
		System.out.println(min_dif);
	}
}

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[] horses = new int[n];

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

horses[i] = in.nextInt();

Arrays.sort(horses);

int min_dif = horses[1] - horses[0];

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

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

System.out.println(min_dif);

}

Подтверждение

Related Images:

Heat Detector

16/10/2014 by Вустянюк Ігор Дмитрович

Задача

Речь пойдёт о первой задаче уровня Medium на сайте codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа W и H — соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x и y — координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка DIR, задающая направление, в котором следует искать бобму:

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через BX и BY и введём четыре вспомогательных параметра: l, r, u, b — «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства [latex] l \leq BX \leq r [/latex] и [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex], [latex] r = W — 1 [/latex], [latex] u = 0 [/latex] и [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения Bx и By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

[latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство [latex] l \leq BX \leq x — 1 [/latex]. Положим [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.
[latex] BX = x [/latex] (если DIR — одна из строк «U» и «B»). В этом случае всё хорошо.
[latex] BX > x [/latex] (если DIR — одна из строк «R», «DR», «UR»). В этом случае справедливо неравенство [latex] x + 1 \leq BX \leq r [/latex]. Положим [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.

Если [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число, ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int W, H;   // Количество окон по горизонтали и вертикали соответственно
    cin >> W >> H; cin.ignore();
    int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ
    int N;
    cin >> N; cin.ignore();
    int x, y;
    cin >> x >> y; cin.ignore();

    // Игровой цикл
    while (1) {
        string DIR; // Направление, в котором находится бомба
        cin >> DIR;
        if ((DIR[0] == 'L')  ||  (DIR[1] == 'L'))
            r = x - 1;
        if ((DIR[0] == 'R')  ||  (DIR[1] == 'R'))
            l = x + 1;
        if (DIR[0] == 'U')
            d = y - 1;
        if (DIR[0] == 'D')
            u = y + 1;
        
        x = (l + r)/2;  // Абсцисса нового окна
        y = (u + d)/2;  // Ордината нового окна
        
        cout << x << " " << y << endl;
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int W, H; // Количество окон по горизонтали и вертикали соответственно

cin >> W >> H; cin.ignore();

int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ

int N;

cin >> N; cin.ignore();

int x, y;

cin >> x >> y; cin.ignore();

// Игровой цикл

while (1) {

string DIR; // Направление, в котором находится бомба

cin >> DIR;

if ((DIR[0] == 'L') || (DIR[1] == 'L'))

r = x - 1;

if ((DIR[0] == 'R') || (DIR[1] == 'R'))

l = x + 1;

if (DIR[0] == 'U')

d = y - 1;

if (DIR[0] == 'D')

u = y + 1;

x = (l + r)/2; // Абсцисса нового окна

y = (u + d)/2; // Ордината нового окна

cout << x << " " << y << endl;

}

Код на Java

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 w = in.nextInt(), h = in.nextInt();
        int l = 0, r = w-1, u = 0, d = h-1;
        int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        
        while (true) {
            char dir = in.next().charAt(0);
            if ((dir == 'L') || (dir == 'L'))
                r = x-1;
            if ((dir == 'R') || (dir == 'R'))
                l = x+1;
            if (dir == 'U')
                d = y-1;
            if (dir == 'D')
                u = y+1;
            x = (l + r) / 2;
            y = (u + d) / 2;
            System.out.println(x + " " + y);
        }
    }
}

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 w = in.nextInt(), h = in.nextInt();

int l = 0, r = w-1, u = 0, d = h-1;

int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();

while (true) {

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

if ((dir == 'L') || (dir == 'L'))

r = x-1;

if ((dir == 'R') || (dir == 'R'))

l = x+1;

if (dir == 'U')

d = y-1;

if (dir == 'D')

u = y+1;

x = (l + r) / 2;

y = (u + d) / 2;

System.out.println(x + " " + y);

}

Подтверждение

Heat Detector

Related Images:

Conway Sequence

15/10/2014 by Іванов Вячеслав Володимирович

Conway Sequence

Conway Sequence — седьмая по счету игра уровня сложности medium, основанная на свойствах последовательности Конвея (правильнее было бы назвать её look-and-say sequence). Последовательность рекурсивна, но в более широком понимании: предыдущая строка полностью характеризует текущую. Изучение последовательности Конвея приводит к занятным открытиям, включая так называемую космологическую теорему, но лучше меня об этом расскажет лично Джон Хортон Конвей. Но начиная с определенного номера получить новую строку становится непросто даже на бумаге. Авторы просят нас помочь математикам и составить программу, которая по заданным значениям выводит определенную строку последовательности.

Алгоритм вывода следующей строки уместно проиллюстрировать на примере:
Sequence seed: 3
Строка №1 имеет вид: «3»
В ней записана одна тройка.
Следовательно, строка №2 запишется как: «1 3».
В ней записаны одна единица и одна тройка
Следовательно, строка №3 выглядит так: «1 1 1 3».
В ней содержатся три единицы и одна тройка,
потому строка №4 имеет вид: «3 1 1 3» et cetera.

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

[latex]R[/latex] — основание последовательности («sequence seed»)
[latex]L[/latex] — номер последней строки

Выходные данные:
Строка №[latex]L[/latex], все элементы которой разделены пробелами.

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

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    int R; //первое число
    cin >> R; cin.ignore();
    int L; //номер целевой строки
    cin >> L; cin.ignore();

    vector<int>current_line (1, R); //вектор для хранения текущей строки
    vector<int> next_line; //вектор для хранения следующей строки
    int previous = R; //предыдущий элемент строки (необходим для сравнения)
    int counter = 0; //инициализация счетчика
    for(int step = 0; step < L - 1; step++)
    {
        int length = current_line.size(); //длина строки
        for(int i = 0; i < length; i++)
        {
            int current = current_line[i]; //текущее число
            if(current == previous) //если подряд идут одинаковые элементы
            {
                counter++; //посчитать их количество
                if(i + 1 == length) //для последнего элемента
                {
                    next_line.push_back(counter); //количество подряд идущих чисел
                    next_line.push_back(current); //число
                }
            }
            else
            {
                next_line.push_back(counter); //количество одинаковых подряд идущих чисел
                counter = 1; //сбросить счетчик
                next_line.push_back(previous); //число
                previous = current; //назначить текущее число в качестве предыдущего

                if(i + 1 == length) //для последнего элемента
                {
                    next_line.push_back(counter);
                    next_line.push_back(current);
                }
            }
        }
        current_line.clear(); //очистить текущую строку
        current_line.swap(next_line); //обменять значение векторов
        previous = current_line[0]; //назначить новый элемент для сравнения на старте
        counter = 0; //обнулить счетчик
    }

    int length =  current_line.size() - 1;
    for(int i = 0; length > i; i++) //вывести на экран элементы строки, разделенные пробелами
    {
            cout << current_line[i] << " ";
    }
    cout << current_line[length] << endl; //за последним символом не должно следовать пробела
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int R; //первое число

cin >> R; cin.ignore();

int L; //номер целевой строки

cin >> L; cin.ignore();

vector<int>current_line (1, R); //вектор для хранения текущей строки

vector<int> next_line; //вектор для хранения следующей строки

int previous = R; //предыдущий элемент строки (необходим для сравнения)

int counter = 0; //инициализация счетчика

for(int step = 0; step < L - 1; step++)

{

int length = current_line.size(); //длина строки

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

{

int current = current_line[i]; //текущее число

if(current == previous) //если подряд идут одинаковые элементы

{

counter++; //посчитать их количество

if(i + 1 == length) //для последнего элемента

{

next_line.push_back(counter); //количество подряд идущих чисел

next_line.push_back(current); //число

}

else

{

next_line.push_back(counter); //количество одинаковых подряд идущих чисел

counter = 1; //сбросить счетчик

next_line.push_back(previous); //число

previous = current; //назначить текущее число в качестве предыдущего

if(i + 1 == length) //для последнего элемента

{

next_line.push_back(counter);

next_line.push_back(current);

}

current_line.clear(); //очистить текущую строку

current_line.swap(next_line); //обменять значение векторов

previous = current_line[0]; //назначить новый элемент для сравнения на старте

counter = 0; //обнулить счетчик

}

int length = current_line.size() - 1;

for(int i = 0; length > i; i++) //вывести на экран элементы строки, разделенные пробелами

{

cout << current_line[i] << " ";

}

cout << current_line[length] << endl; //за последним символом не должно следовать пробела

}

Алгоритм решения:

Начать просмотр содержимого строки слева направо. Если подряд идут несколько одинаковых чисел, запомнить их количество.
Если следующее число в строке отлично от предыдущего записать в новую строку количество повторов предыдущего числа и само это число.
Если строка подошла к концу, дописать к новой строке количество повторений последнего элемента и сам этот элемент.
Если номер полученной строки меньше [latex]L[/latex], повторить процедуру для новой строки.

Эффективность алгоритма:
Программа успешно проходит все данные тесты.

Технические детали реализации:

Для удобства работы с строками произвольной длины использована библиотека vector, в частности функции .clear(), .push_back(), .size(), .swap()
Так как принципиальное значение имеют только три факта: значение текущего элемента последовательности, значение предыдущего и количество подряд идущих одинаковых элементов, стоящих за ним — достаточно завести три переменные типа int для их хранения.
На каждой итерации вектор [latex]next\_line[/latex] копируется в вектор [latex]current\_line[/latex] и очищается. Переменной [latex]previous[/latex] присваивается значение первого элемента вектора [latex]current\_line[/latex].

Related Images:

Puzzle — Temperatures

15/10/2014 by Ілларіонова Марія Валеріївна

Задача взята с этого сайта.

В этой задаче необходимо проанализировать значения температуры, дабы найти ближайшее к нулю.

Ввод:

Строка 1: [latex]N[/latex], количество значений температуры.

Строка 2: собственно говоря, сами значения температуры, выраженные целыми числами в диапазоне от -273 до 5526.

Вывод:

Вывести 0 в том случае, если не введено ни одного значения.

Если введено хотя бы одно, то вывести на экран значение ближайшее к 0. Отметить, что если есть 2 значения, одинаково близкие к нулю, но с разными знаками, то на экране должно отобразиться положительное число.

	[latex]N[/latex]	Ввод	Вывод	Комментарий.
Простой тест	5	1 -2 -8 4 5	1	Пройден.
Сложный тест	10	-5 -4 -2 12 -40 4 2 18 11 5	2	Пройден.
Без температур	0	—	0	Пройден.
Дополнительный тест	14	7 -10 13 8 4 -7 -12 -3 3 -9 6 -1 -6 7	-1	Пройден.

Код программы (C++):

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

using namespace std;

int main() {
	int N;
	cin >> N;
	if (N!=0) {
	    int closest=5527, TEMPS;
        for (int i=0; i<N; i++) {
            cin >> TEMPS;
            if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {
                closest=TEMPS;
	        }
        }
        cout << closest << endl;
	}
	else {
        cout << 0 << endl;
    }
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

if (N!=0) {

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

else {

cout << 0 << endl;

}

Для первого теста нужно было найти ближайшее к нулю значение, когда все числа по модулю были попарно различными. Для этого достаточно было завести переменную типа int и положить в неё значение, которое заведомо больше всех возможных (это 5527, так как по условию задачи значения температур не выходят за пределы [-273;5527]). И в цикле сделать проверку того, что же больше — модуль нашего текущего значения или модуль только что введённого.

Задача 1.

#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
 
int main() {
	int N;
	cin >> N;
	int closest=5527, TEMPS;
    for (int i=0; i<N; i++) {
        cin >> TEMPS;
        if (abs(closest)>abs(TEMPS)) {
            closest=TEMPS;
	    }
    }
    cout << closest << endl;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

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

Задача 2.

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

using namespace std;

int main() {
	int N;
	cin >> N;
	int closest=5527, TEMPS;
    for (int i=0; i<N; i++) {
        cin >> TEMPS;
        if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {
            closest=TEMPS;
	    }
    }
    cout << closest << endl;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N;
		Scanner in = new Scanner (System.in);
		N=in.nextInt();
		int closest=5527, TEMPS;
	    for (int i=0; i<N; i++) {
	        TEMPS=in.nextInt();
	        if (Math.abs(closest)>Math.abs(TEMPS)||(Math.abs(closest)==TEMPS)) {
	            closest=TEMPS;
		    }
	    }
	    System.out.format("%d%n", closest);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int N;

Scanner in = new Scanner (System.in);

N=in.nextInt();

int closest=5527, TEMPS;

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

TEMPS=in.nextInt();

if (Math.abs(closest)>Math.abs(TEMPS)||(Math.abs(closest)==TEMPS)) {

closest=TEMPS;

}

System.out.format("%d%n", closest);

}

И для последней задачи, конечно, достаточно было ввести условие, что [latex]N[/latex] не равно нулю. В противном случае программа выведет на экран 0. Конечный код указан первым.

Related Images:

Skynet: the Virus

14/10/2014 by Бронфен-Бова Роман

SKYNET FINALE — LEVEL 1

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз, нам нужна ваша помощь. СТОП

Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

N — Количество узлов, включая шлюзы
L — Количество связей
E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N; //Количество узлов, включая шлюзы
    int L; //Количество связей
    int E; //Количество шлюзов
    cin >> N >> L >> E; cin.ignore();
    
    int N1[L][2]; // Массив для связей
    for (int i = 0; i < L; i++) {
        cin >> N1[i][0] >> N1[i][1]; cin.ignore();
    }
    
    int EI[E]; // Индексы шлюзов
    for (int i = 0; i < E; i++) {
        cin >> EI[i]; cin.ignore();
    }
    
    // Алгоритм сортировки (его достаточно)
    for(int i = 0; i < L; i++){
        for(int k =0; k < E; k++){
            if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);
        }
    }

    // игровой цикл
    while (1) {
        int SI; //Индекс связи, на которой находится Агент
        cin >> SI; cin.ignore();

        bool AgentIsNear = false; //Агент возле шлюза!
        
        for(int i = 0; i < L; i++){
            bool T = false; //Для прерывания цикла
            for(int k = 0; k < E; k++){
                if(EI[k] == N1[i][0] && SI == N1[i][1]){
                    cout << EI[k] << ' ' << SI << endl;
                    N1[i][0] = -1;
                    AgentIsNear = true;
                    T = true;
                    break;
                }
            }
            if(T) break;
        }
        
        if(!AgentIsNear){
            for(int i = 0; i < L; i++){
                bool T = false; //Для прерывания цикла
                for(int k = 0; k < E; k++){
                    if(N1[i][0] == EI[k]){
                        cout << EI[k] << ' ' << N1[i][1] << endl;
                        N1[i][0] = -1;
                        T = true;
                        break;
                    }
                }
                if(T) break;
            }
        }
        
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int N; //Количество узлов, включая шлюзы

int L; //Количество связей

int E; //Количество шлюзов

cin >> N >> L >> E; cin.ignore();

int N1[L][2]; // Массив для связей

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

cin >> N1[i][0] >> N1[i][1]; cin.ignore();

}

int EI[E]; // Индексы шлюзов

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

cin >> EI[i]; cin.ignore();

}

// Алгоритм сортировки (его достаточно)

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

for(int k =0; k < E; k++){

if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);

}

// игровой цикл

while (1) {

int SI; //Индекс связи, на которой находится Агент

cin >> SI; cin.ignore();

bool AgentIsNear = false; //Агент возле шлюза!

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

bool T = false; //Для прерывания цикла

for(int k = 0; k < E; k++){

if(EI[k] == N1[i][0] && SI == N1[i][1]){

cout << EI[k] << ' ' << SI << endl;

N1[i][0] = -1;

AgentIsNear = true;

T = true;

break;

}

if(T) break;

}

if(!AgentIsNear){

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

bool T = false; //Для прерывания цикла

for(int k = 0; k < E; k++){

if(N1[i][0] == EI[k]){

cout << EI[k] << ' ' << N1[i][1] << endl;

N1[i][0] = -1;

T = true;

break;

}

if(T) break;

}

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

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

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

Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

Related Images:

Temperatures

14/10/2014 by Вустянюк Ігор Дмитрович

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

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

Вывести нуль, если [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число [latex] a [/latex] ближе к нулю, чем число [latex] b [/latex]» означает, что [latex] a [/latex] по модулю меньше, чем [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	int N;
	cin >> N;
	if (N == 0)
        cout << 0 << endl;
    else {
        int min, temp;
        cin >> min;
        for (int i = 1; i < N; i++) {
            cin >> temp;
            if ((abs(temp) < abs(min)) || (temp == abs(min)))
                min = temp;
	    }
	    cout << min;
    }
	return 0;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main()

{

int N;

cin >> N;

if (N == 0)

cout << 0 << endl;

else {

int min, temp;

cin >> min;

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

cin >> temp;

if ((abs(temp) < abs(min)) || (temp == abs(min)))

min = temp;

}

cout << min;

}

return 0;

}

Код на Java

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();
		if (N == 0)
			System.out.println(0);
		else {
			int min = in.nextInt(), temp;
			for (int i = 1; i < N; i++) {
				temp = in.nextInt();
				if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))
					min = temp;
			}
			System.out.println(min);
		}
	}
}

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();

if (N == 0)

System.out.println(0);

else {

int min = in.nextInt(), temp;

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

temp = in.nextInt();

if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))

min = temp;

}

System.out.println(min);

}

P.S.. Возможно, усложнив оператор ветвления можно сделать алгоритм более эффективным за счёт уменьшения числа сравнений или присваиваний.

Related Images:

Ragnarök — Power of Thor

14/10/2014 by Вустянюк Ігор Дмитрович

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Инициализация

Одна строка, в которой даны четыре целых числа: LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

Поскольку Тор движется по прямоугольному полю, на котором нет преград, кратчайший путь получится, если на каждом шаге сравнивать положение Тора с положением источника по каждой из осей и направлять Тора в соответствующую сторону (так, чтобы скомпенсировать различие в координатах). Подробно этот процесс ниже описан в комменатариях к коду. Здесь сделаем только две ремарки.

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

Во-вторых, если бы поле не было прямоугольным (или на нём были бы преграды, не позволяющие двигаться в том или ином направлении), то наш метод пришлось бы серьёзно модифицировать.

Код на С++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int LX; // абсцисса источника энергии
    int LY; // ордината источника энергии
    int TX; // абсцисса Тора
    int TY; // ордината Тора
    cin >> LX >> LY >> TX >> TY;

    while (1) {
        int E;
        cin >> E;
        string hor;     // Куда нужно двигаться Тору по оси абсцисс
        string ver;     // Куда нужно двигаться Тору по оси ординат
        // Определяем, куда нужно двигаться Тору по оси Х
        if (TX == LX)           // Если абсцисса Тора совпадает с абсциссой источника,
            hor = "";		// её менять не нужно
        else {				
            if (TX < LX) {	// Если абсцисса Тора МЕНЬШЕ абсциссы источника,
                hor = "E";	// УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК
                TX++;		// Фиксируем изменение положения Тора
            }
            else {		// Если абсцисса Тора БОЛЬШЕ абсциссы источника, 
                hor = "W";	// УМЕНЬШИМ её, т.е. двинемся на ЗАПАД
                TX--;		// Фиксируем изменение положения Тора
            }
        }
        // Определяем, куда нужно двигаться Тору по оси Y
        if (TY == LY)		// Если ордината Тора совпадает с ординатой источника,
            ver = "";           // её менять не нужно
        else {
            if (TY < LY) {	// Если ордината Тора меньше ординаты источника,
                ver = "S";	// УВЕЛИЧИМ её, т.е. двинемся на ЮГ
                TY++;		// Фиксируем изменение положения Тора 
            }
            else {		// Если ордината Тора больше ординаты источника,
                ver = "N";	// УМЕНЬШИМ её, т.е. двинемся на СЕВЕР
                TY--;		// Фиксируем изменение положения Тора
            }
        }     
        cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int LX; // абсцисса источника энергии

int LY; // ордината источника энергии

int TX; // абсцисса Тора

int TY; // ордината Тора

cin >> LX >> LY >> TX >> TY;

while (1) {

int E;

cin >> E;

string hor; // Куда нужно двигаться Тору по оси абсцисс

string ver; // Куда нужно двигаться Тору по оси ординат

// Определяем, куда нужно двигаться Тору по оси Х

if (TX == LX) // Если абсцисса Тора совпадает с абсциссой источника,

hor = ""; // её менять не нужно

else {

if (TX < LX) { // Если абсцисса Тора МЕНЬШЕ абсциссы источника,

hor = "E"; // УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК

TX++; // Фиксируем изменение положения Тора

}

else { // Если абсцисса Тора БОЛЬШЕ абсциссы источника,

hor = "W"; // УМЕНЬШИМ её, т.е. двинемся на ЗАПАД

TX--; // Фиксируем изменение положения Тора

}

// Определяем, куда нужно двигаться Тору по оси Y

if (TY == LY) // Если ордината Тора совпадает с ординатой источника,

ver = ""; // её менять не нужно

else {

if (TY < LY) { // Если ордината Тора меньше ординаты источника,

ver = "S"; // УВЕЛИЧИМ её, т.е. двинемся на ЮГ

TY++; // Фиксируем изменение положения Тора

}

else { // Если ордината Тора больше ординаты источника,

ver = "N"; // УМЕНЬШИМ её, т.е. двинемся на СЕВЕР

TY--; // Фиксируем изменение положения Тора

}

cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг

}

Код на 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);
		int LX = in.nextInt(), LY = in.nextInt();
		int TX = in.nextInt(), TY = in.nextInt();
		while (true) {
			int E = in.nextInt();
			String hor, ver;
			if (TX == LX)
				hor = "";
			else {
				if (TX < LX) {
					hor = "E";
					TX++;
				}
				else {
					hor = "W";
					TX--;
				}
			}
			if (TY == LY)
				ver = "";
			else {
				if (TY < LY) {
					ver = "S";
					TY++;
				}
				else {
					ver = "N";
					TY--;
				}
			}
			System.out.println(ver + hor);
		}
	}
}

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);

int LX = in.nextInt(), LY = in.nextInt();

int TX = in.nextInt(), TY = in.nextInt();

while (true) {

int E = in.nextInt();

String hor, ver;

if (TX == LX)

hor = "";

else {

if (TX < LX) {

hor = "E";

TX++;

}

else {

hor = "W";

TX--;

}

if (TY == LY)

ver = "";

else {

if (TY < LY) {

ver = "S";

TY++;

}

else {

ver = "N";

TY--;

}

System.out.println(ver + hor);

}

Related Images:

The Descent

14/10/2014 by Вустянюк Ігор Дмитрович

Задача

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

Гор имеется 8 штук. Корабль летает кругами над горами: сначала слева направо, потом справа налево, и так далее. Один полный «пролёт» состоит из восьми игровых ходов. За один пролёт мы можем выстрелить только один раз и только по горе, над которой находимся. При этом высота горы уменьшится на случайное число.

Чтобы благополучно приземлиться нам нужно уничтожить все горы. Создатели игры дали ценную подсказку: если стрелять на каждом пролёте по самой высокой горе, посадка будет безопасной.

Входные данные для одного игрового хода

В первой строке введены два числа (SX и SY) — соответственно горизонтальная и вертикальная координаты нашего корабля. Горизонтальная меняется слева направо от нуля до семи. Вертикальная, как показал опыт, нам не понадобится.

Следующие восемь строк содержат каждая по одному целому числу от нуля до девяти — высоту соответствующей горы. Высоты перечислены слева направо.

Выходные данные для одного игрового хода

Одна строка: «FIRE», чтобы выстрелить, и «HOLD», если на текущем ходе стрелять не нужно.

Решение

Считаем SX и SY. После этого в цикле for считаем высоты гор. Нам нужно стрелять на каждом пролёте по самой высокой горе. Для этого мы применим приём, уже опробованный нами на практических занятиях: введём новую переменную max_height, в которую поместим высоту первой горы (точнее, нулевой). А в цикле будем обновлять эту переменную, если наткнёмся на более высокую гору. Всё? Нет, не всё. Стрелять мы можем только по горе, которая находится под нами. Чтобы знать, когда стрелять, введём переменную max_position, которая будет хранить координату самой высокой горы. Вначале присвоим ей нулевое значение. А в цикле будем обновлять эту переменную, вместе с переменной max_height.

Когда цикл for завершится, останется только проверить находимся ли мы на текущем ходу над самой высокой горой: для этого будем каждый раз сравнивать текущую координату корабля (SX) с координатой самой высокой горы, которая после цикла for хранится в переменной max_position. В случае совпадения — стреляем, в противном случае — ждём.

Код на С++

#include <iostream>

using namespace std;

int main()
{
    while (true) {
        int SX, SY, current_height, max_height, max_position = 0;
        cin >> SX >> SY >> max_height;
        for (int i = 1; i < 8; i++) {
            cin >> current_height;
            if (max_height < current_height) {
                max_height = current_height;
                max_position = i;
            }
        }
        if (SX == max_position)
            cout << "FIRE" << endl;
        else
            cout << "HOLD" << endl;
    }
}

#include <iostream>

using namespace std;

int main()

{

while (true) {

int SX, SY, current_height, max_height, max_position = 0;

cin >> SX >> SY >> max_height;

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

cin >> current_height;

if (max_height < current_height) {

max_height = current_height;

max_position = i;

}

if (SX == max_position)

cout << "FIRE" << endl;

else

cout << "HOLD" << endl;

}

Код на Java

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		while (true) {
			Scanner in = new Scanner(System.in);
			int SX, SY, max_height, current_height, max_position = 0;
			SX = in. nextInt();
			SY = in. nextInt();
			max_height = in. nextInt();
			for (int i = 1; i < 8; i++) {
				current_height = in. nextInt();
				if (max_height < current_height) {
					max_height = current_height;
					max_position = i;
				}
			}
			if (SX == max_position)
				System.out.println("FIRE");
			else
				System.out.println("HOLD");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

while (true) {

Scanner in = new Scanner(System.in);

int SX, SY, max_height, current_height, max_position = 0;

SX = in. nextInt();

SY = in. nextInt();

max_height = in. nextInt();

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

current_height = in. nextInt();

if (max_height < current_height) {

max_height = current_height;

max_position = i;

}

if (SX == max_position)

System.out.println("FIRE");

else

System.out.println("HOLD");

}

Related Images:

Skynet: The Chasm

13/10/2014 by Іванов Вячеслав Володимирович

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

Движение по стартовой площадке.
Прыжок через пропасть.
Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

Координату мотоцикла [latex]X[/latex].
Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

JUMP — совершить прыжок.
SPEED — увеличить скорость на единицу.
SLOW — уменьшить скорость на единицу.
WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.
Continue reading →

Related Images:

Ragnarök — Power of Thor

12/10/2014 by Байков Дмитро

Четвертая по счету игра на сайте называется Ragnarök — Power of Thor, где нам посчастливилось быть Великим Воином Тором. Тору необходимо самым кратчайшим путем добраться до источника энергии, которая придаст ему еще больше сил и уверенности в дальнейших сражениях.

Пока еще не всемогущий Тор ждет указаний

Инициализация

В начале нам сообщают положение на карте источника и самого персонажа (их координаты по X и Y) (int LX, LY) (int TX, TY) соответственно.

Игровой цикл

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

Вход

В самом игровом цикле нам сообщают величину энергии Тора (int E), которая уменьшается на 1 с каждым последующим ходом.

Выход

В выходной поток необходимо вывести одну строку. Нам представлено всего 8 возможных вариантов дальнейшего передвижения Тора. Screenshot_2222

Движение возможно только как показано на картинке (т.е. по компасу). Например, если мы хотим, чтобы персонаж двигался вправо (на восток) мы выведем буквочку E и т.д.

Перевод строки на новую обязателен.

Тест 1

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

        cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1) {

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

// Write an action using cout. DON'T FORGET THE "<< endl"

// To debug: cerr << "Debug messages..." << endl;

cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW

}

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

Адекватное решение

Немного подумав вспоминаем, что нам даны начальные координаты как источника так и энергии. Сразу же приходит в голову мысль, что их надо сравнивать.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

Если равны координаты Тора и источника энергии по X, то тут мы находим разность координат источника и Тора по Y, если LY — TY > 0 (Источник находится выше Тора по оси Y), то идем на юг (вверх), в противном случае на север (вниз). Аналогично и с движением по Y, что дает нам силы пройти первые два теста.

Дважды заряженный энергией боец рвется подзарядиться и в третий раз, но вдруг остается стоять на месте. Обескураженный обстоятельствами Тор замечает, что источник уже находится не ровно по оси движения, а под каким-то определенным углом. Оставаясь на месте, Тор принимает обет молчания (не выводит ничего на экран) и погружается в свои мысли.

Цикл for идет на помощь

Конечно, мы могли бы высчитывать конечное число выводов команд на экран или подбивать все это проваливая тесты раз за разом. Но Тор нам подсказывает, что этого делать не надо, ведь он вспомнил могучее заклинание под названием цикл, которое спасает в очень многих ситуациях и эта не исключение.

Код на C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
        if (( LX - TX ) > 0) //Movement to the left half of the map
        {
            
            if (( LY - TY ) < 0)
            {
               for(int i = 0;i < abs ( LY - TY );i++)
               {
                    cout << "NE" << endl;
               }
                for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                {
                    cout << "E" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                 {
                    for(int i = 0;i < abs ( LY - TY );i++)
                    {
                        cout << "SE" << endl;
                    }
                   for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                    {
                        cout << "E" << endl;
                    }
                }
            }
        }
        if (( LX - TX ) < 0) //Movement to the right half of the map
        {
            
            if (( LY - TY ) < 0)
            {
                for(int i = 0;i < abs ( LY - TY );i++)
                {
                    cout << "NW" << endl;
                }
                for (int i=0;i < abs ( TX - ( LY - TY ));i++)
                {
                    cout << "W" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                {
                   for (int i = 0;i < abs ( LY - TY );i++)
                   {
                        cout << "SW" << endl;
                   }
                    for (int i = 0;i< abs ( TX - ( LY - TY ));i++)
                    {
                        cout << "W" << endl;
                    }
                }
            }
        }
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

if (( LX - TX ) > 0) //Movement to the left half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "SE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

if (( LX - TX ) < 0) //Movement to the right half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NW" << endl;

}

for (int i=0;i < abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for (int i = 0;i < abs ( LY - TY );i++)

{

cout << "SW" << endl;

}

for (int i = 0;i< abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

Код на Java:

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

class Player 
{
    public static void main(String args[]) 
    {
    	Scanner in = new Scanner(System.in);
	    int lightX = in.nextInt(); // the X position of the light of power
	    int lightY = in.nextInt(); // the Y position of the light of power
	    int initialTX = in.nextInt(); // Thor's starting X position
	    int initialTY = in.nextInt(); // Thor's starting Y position
	
	    // game loop
	    while (true) 
	    {
	        int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.
	        if (lightX == initialTX) //Movement along the X axis.
	        {
	            if ((lightY - initialTY) < 0)
	            	System.out.println("N");
	            else 
	            	System.out.println("S");
	        }    
	        if (initialTY == lightY) //Movement along the Y axis.
	        {
	            if ((lightX - initialTX) < 0)
	            	System.out.println("W");
	            else 
	                System.out.println("E");
	        }
	        if ((lightX - initialTX) > 0) //Movement to the left half of the map
	        {
	            if ((lightY - initialTY) < 0)
	            {
	               for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    System.out.println("NE");
	               for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                   System.out.println("E");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                 {
	                    for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    	System.out.println("SE");
	               		for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                		System.out.println("E");
	                }
	            }
	        }
	        if ((lightX - initialTX) < 0) //Movement to the right half of the map
	        {
	            
	            if ((lightY - initialTY) < 0)
	            {
	                for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("NW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                {
	                   for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("SW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	                }
	            }
	        }
	    }
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

int lightX = in.nextInt(); // the X position of the light of power

int lightY = in.nextInt(); // the Y position of the light of power

int initialTX = in.nextInt(); // Thor's starting X position

int initialTY = in.nextInt(); // Thor's starting Y position

// game loop

while (true)

{

int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.

if (lightX == initialTX) //Movement along the X axis.

{

if ((lightY - initialTY) < 0)

System.out.println("N");

else

System.out.println("S");

}

if (initialTY == lightY) //Movement along the Y axis.

{

if ((lightX - initialTX) < 0)

System.out.println("W");

else

System.out.println("E");

}

if ((lightX - initialTX) > 0) //Movement to the left half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

if ((lightX - initialTX) < 0) //Movement to the right half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

Получается вот такой вот симпатичный код, описывающий все возможные ситуации по передвижению Тора (переносит Тора к источнику из любой точки карты). Разбивая на два возможных случая, движение в правой половине карты и в левой половине карты, получается, что программа охватывает любую ее точку. В самом цикле возьмем модуль между разностью (т.к. источник может находиться и ниже Тора). Сравниваем LX и TX, для того, чтобы узнать в какой половине карты находится источник. Если LX — TX > 0, то в цикле будем отнимать от LX, в противном случае — от TX, дабы не получить отрицательные значения. В конечном счете переменная E (энергия) там так и не понадобилось, так как воин и так находил кратчайшее расстояние.

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

Related Images:

Skynet — The Chasm

12/10/2014 by Байков Дмитро

Вторая по счету игра на сайте называется Skynet — The Chasm. В игре мы будем управлять мотоциклистом, который изо всех сил пытается попасть на другую сторону пропасти и остановиться на конечной платформе.

Ни о чем не подозревающий мотоциклист

Инициализация

В начале нам сообщают всевозможные данные о будущем пути: расстояние от мотоциклиста до пропасти (int R), длину пропасти (int G), длину платформы для приземления (int L).

Игровой цикл

Вход

Каждый новый ход (т.е. после каждого следующего выполненного действия в самом цикле while) нам сообщают скорость мотоциклиста (int S) и его позицию на дороге (int X).

Выход

В выходной поток необходимо вывести одну строку. Тут разработчики представляют нам 4 варианта:

ускоряться (SPEED);
тормозить (SLOW);
ехать вперед без ускорения (WAIT);
прыгать (JUMP).

Перевод строки на новую обязателен.

Тест 1

В начале нам представлен базовый код программы.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int R; // the length of the road before the gap.
    cin >> R; cin.ignore();
    int G; // the length of the gap.
    cin >> G; cin.ignore();
    int L; // the length of the landing platform.
    cin >> L; cin.ignore();

    // game loop
    while (1) {
        int S; // the motorbike's speed.
        cin >> S; cin.ignore();
        int X; // the position on the road of the motorbike.
        cin >> X; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

        cout << "SPEED" << endl; // A single line containing one of 4 keywords: SPEED, SLOW, JUMP, WAIT.
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int R; // the length of the road before the gap.

cin >> R; cin.ignore();

int G; // the length of the gap.

cin >> G; cin.ignore();

int L; // the length of the landing platform.

cin >> L; cin.ignore();

// game loop

while (1) {

int S; // the motorbike's speed.

cin >> S; cin.ignore();

int X; // the position on the road of the motorbike.

cin >> X; cin.ignore();

// Write an action using cout. DON'T FORGET THE "<< endl"

// To debug: cerr << "Debug messages..." << endl;

cout << "SPEED" << endl; // A single line containing one of 4 keywords: SPEED, SLOW, JUMP, WAIT.

}

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

Спасательный код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    int R; // the length of the road before the gap.
    cin >> R; cin.ignore();
    int G; // the length of the gap.
    cin >> G; cin.ignore();
    int L; // the length of the landing platform.
    cin >> L; cin.ignore();

    // game loop
    while (1) 
    {
        int S; // the motorbike's speed.
        cin >> S; cin.ignore();
        int X; // the position on the road of the motorbike.
        cin >> X; cin.ignore();
        if (X < R - G ) //Checking thе position of the bike.
        {
            cout << "SPEED" << endl; 
        }
        if (X == R - 1) //The bike must jump if the distance before the gap is 1 step
        {
            cout << "JUMP" << endl;
        }
        if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate
        {
            cout << "SLOW" << endl;
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int R; // the length of the road before the gap.

cin >> R; cin.ignore();

int G; // the length of the gap.

cin >> G; cin.ignore();

int L; // the length of the landing platform.

cin >> L; cin.ignore();

// game loop

while (1)

{

int S; // the motorbike's speed.

cin >> S; cin.ignore();

int X; // the position on the road of the motorbike.

cin >> X; cin.ignore();

if (X < R - G ) //Checking thе position of the bike.

{

cout << "SPEED" << endl;

}

if (X == R - 1) //The bike must jump if the distance before the gap is 1 step

{

cout << "JUMP" << endl;

}

if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate

{

cout << "SLOW" << endl;

}

Мы, с чувством выполненного долга, наблюдаем как мотоциклист, с улыбкой на лице, наконец перепрыгивает первую пропасть, а затем и вторую и третью. Понимая, что мотоциклист должен прыгнуть в момент, когда пропасть будет перед ним (т.е. за 1 шаг до нее), приказываем ему ускоряться до того момента (пока расстояние до пропасти не станет равным 1 (X == R — 1)). То есть пока положение мотоциклиста Х меньше, чем расстояние до пропасти R минус длинна пропасти G (X < R — G) мотоциклист будет ускоряться. После прыжка нам нужно затормозить, то есть если положение мотоциклиста X будет уже за пропастью (X > R — G), но меньше чем конец самой дороги (X < R + G + L), он будет тормозить.

Подходя к 4 тесту сталкиваемся с новой проблемой. Длинна платформы для приземления очень мала и наш бессмертный каскадер вылетает за окончание дороги. Что же делать?

Еще более спасательный код

И тут вступает в игру переменная, которую до этого момента нам не приходилось использовать в программе, а именно, скорость мотоциклиста S.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    int R; // the length of the road before the gap.
    cin >> R; cin.ignore();
    int G; // the length of the gap.
    cin >> G; cin.ignore();
    int L; // the length of the landing platform.
    cin >> L; cin.ignore();

    // game loop
    while (1) 
    {
        int S; // the motorbike's speed.
        cin >> S; cin.ignore();
        int X; // the position on the road of the motorbike.
        cin >> X; cin.ignore();
        if (X < R - G ) //Checking thе position of the bike.
        {
            if (S==G+1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.
            {
                cout << "WAIT" << endl; 
            }
            else 
            {
               cout << "SPEED" << endl; 
            }
        }
        if (X == R - 1) //The bike must jump if the distance before the gap is 1 step
        {
            cout << "JUMP" << endl;
        }
        if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate
        {
            cout << "SLOW" << endl;
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int R; // the length of the road before the gap.

cin >> R; cin.ignore();

int G; // the length of the gap.

cin >> G; cin.ignore();

int L; // the length of the landing platform.

cin >> L; cin.ignore();

// game loop

while (1)

{

int S; // the motorbike's speed.

cin >> S; cin.ignore();

int X; // the position on the road of the motorbike.

cin >> X; cin.ignore();

if (X < R - G ) //Checking thе position of the bike.

{

if (S==G+1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.

{

cout << "WAIT" << endl;

}

else

{

cout << "SPEED" << endl;

}

if (X == R - 1) //The bike must jump if the distance before the gap is 1 step

{

cout << "JUMP" << endl;

}

if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate

{

cout << "SLOW" << endl;

}

После тысячи непройденых тестов начинаешь понимать, что ты что то упустил. Вот тут то и вступает в игру всеми любимый «любимый» magic number равный, в данном случае, единице. И вправду, для того, чтобы перелететь пропасть нам потребуется скорость всего лишь на 1 больше, чем длинна этой пропасти. То есть если скорость будет равна длине пропасти + 1, то мы будем ехать с этой постоянной скоростью, в противном случае будем ускоряться. С этим замечанием программа позволяет с легкостью останавливаться на конечной платформе любой длинны.

Кажется, что мы предусмотрели все варианты развития событий, но не тут то было. Разработчики устанавливают новую, увлекательную задачу. Что будет, если начальная скорость будет не равна 0, спрашивают они? И мы пускаемся в глубокие размышления.

Код дающий, в прямом смысле, крылья

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

На С++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    int R; // the length of the road before the gap.
    cin >> R; cin.ignore();
    int G; // the length of the gap.
    cin >> G; cin.ignore();
    int L; // the length of the landing platform.
    cin >> L; cin.ignore();

    // game loop
    while (1) 
    {
        int S; // the motorbike's speed.
        cin >> S; cin.ignore();
        int X; // the position on the road of the motorbike.
        cin >> X; cin.ignore();
        if (X < R - G ) //Checking thе position of the bike.
        {
            if (S > G + 1)  // Slowing, until suitable speed.
            {
                cout << "SLOW" << endl; 
            }
            else
            {
                if (S==G+1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.
                {
                    cout << "WAIT" << endl; 
                }
                else 
                {
                   cout << "SPEED" << endl; 
                }
            }
        }
        if (X == R - 1) //The bike must jump if the distance before the gap is 1 step
        {
            cout << "JUMP" << endl;
        }
        if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate
        {
            cout << "SLOW" << endl;
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int R; // the length of the road before the gap.

cin >> R; cin.ignore();

int G; // the length of the gap.

cin >> G; cin.ignore();

int L; // the length of the landing platform.

cin >> L; cin.ignore();

// game loop

while (1)

{

int S; // the motorbike's speed.

cin >> S; cin.ignore();

int X; // the position on the road of the motorbike.

cin >> X; cin.ignore();

if (X < R - G ) //Checking thе position of the bike.

{

if (S > G + 1) // Slowing, until suitable speed.

{

cout << "SLOW" << endl;

}

else

{

if (S==G+1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.

{

cout << "WAIT" << endl;

}

else

{

cout << "SPEED" << endl;

}

if (X == R - 1) //The bike must jump if the distance before the gap is 1 step

{

cout << "JUMP" << endl;

}

if ((X > R - G ) && ( X < R + G + L )) // Lastly, we have to accelerate

{

cout << "SLOW" << endl;

}

На Java:

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

class Player
{
	public static void main(String args[])
	{
		Scanner in = new Scanner(System.in);
	  	int road = in.nextInt(); // the length of the road before the gap.
        int gap = in.nextInt(); // the length of the gap.
        int platform = in.nextInt(); // the length of the landing platform.
	    // game loop
	    while (true) 
	    {
	    	int speed = in.nextInt(); // the motorbike's speed.
            int coordX = in.nextInt(); // the position on the road of the motorbike.
	        if (coordX < road - gap ) //Checking thе position of the bike.
	        {
	            if (speed > gap + 1)  // Slowing, until suitable speed.
	            {
	                System.out.println("SLOW"); 
	            }
	            else
	            {
	                if (speed == gap + 1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.
	                {
	                    System.out.println("WAIT"); 
	                }
	                else 
	                {
	                   System.out.println( "SPEED"); 
	                }
	            }
	        }
	        if (coordX == road - 1) //The bike must jump if the distance before the gap is 1 step
	        {
	            System.out.println("JUMP");
	        }
	        if ((coordX > road - gap ) && ( coordX < road + gap + platform )) // Lastly, we have to accelerate
	        {
	            System.out.println("SLOW");
	        }
	    }
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

int road = in.nextInt(); // the length of the road before the gap.

int gap = in.nextInt(); // the length of the gap.

int platform = in.nextInt(); // the length of the landing platform.

// game loop

while (true)

{

int speed = in.nextInt(); // the motorbike's speed.

int coordX = in.nextInt(); // the position on the road of the motorbike.

if (coordX < road - gap ) //Checking thе position of the bike.

{

if (speed > gap + 1) // Slowing, until suitable speed.

{

System.out.println("SLOW");

}

else

{

if (speed == gap + 1) //Speed should be bigger, than gap length on 1 point to slow down at small landing platform.

{

System.out.println("WAIT");

}

else

{

System.out.println( "SPEED");

}

if (coordX == road - 1) //The bike must jump if the distance before the gap is 1 step

{

System.out.println("JUMP");

}

if ((coordX > road - gap ) && ( coordX < road + gap + platform )) // Lastly, we have to accelerate

{

System.out.println("SLOW");

}

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