e-olymp 236. Триомино

14/09/2020 by Евгений Фищук

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

Первая строка содержит количество тестов $t$ ($1 \leqslant t \leqslant 100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

№	Входные данные	Выходные данные
1	3 3 4 6	3 0 11
2	4 12 15 21 9	153 571 7953 41

Код

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


class Main
{
    static long MOD=1000000;
    static long[][] multiply(long[][] v1) {
        long[][] ans=new long[2][2];
        long x00 = v1[0][0];
        long x01 = v1[0][1];
        long x10 = v1[1][0];
        long x11 = v1[1][1];
        long res00, res01, res10, res11;
        res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
        res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
        res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
        res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
        ans[0][0]=(res00+MOD)%MOD;
        ans[0][1]=(res01-MOD)%MOD;
        ans[1][0]=(res10+MOD)%MOD;
        ans[1][1]=(res11-MOD)%MOD;
        return ans;
    }

    static long[][] pow_mod(long[][] v, int p) {
        if (p == 1) return v;
        //if ((p % 2) == 0)
        return multiply((pow_mod(v, p / 2)));
    }
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);

        int t=in.nextInt();
        for (int i = 0; i < t; i++)
        {
            int n=in.nextInt();
            if (n % 3!=0)
            {
                System.out.println(0);
            }
            else
            {
                n /= 3;
                int p = 2;
                long a1 = 1, a2 = 1;
                while (n > 0)
                {
                    if ((n & 1)==1)
                    {
                        long[][] a = { {4,-1},{1,0} };
                        a = pow_mod(a, p / 2);
                        long tmp1 = a1;
                        long tmp2 = a2;
                        a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
                        a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
                    }
                    p *= 2;
                    n >>= 1;
                }
                a1=a1%MOD;
                System.out.println(a1);
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static long MOD=1000000;

static long[][] multiply(long[][] v1) {

long[][] ans=new long[2][2];

long x00 = v1[0][0];

long x01 = v1[0][1];

long x10 = v1[1][0];

long x11 = v1[1][1];

long res00, res01, res10, res11;

res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;

res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;

res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;

res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;

ans[0][0]=(res00+MOD)%MOD;

ans[0][1]=(res01-MOD)%MOD;

ans[1][0]=(res10+MOD)%MOD;

ans[1][1]=(res11-MOD)%MOD;

return ans;

}

static long[][] pow_mod(long[][] v, int p) {

if (p == 1) return v;

//if ((p % 2) == 0)

return multiply((pow_mod(v, p / 2)));

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int t=in.nextInt();

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

{

int n=in.nextInt();

if (n % 3!=0)

{

System.out.println(0);

}

else

{

n /= 3;

int p = 2;

long a1 = 1, a2 = 1;

while (n > 0)

{

if ((n & 1)==1)

{

long[][] a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

long tmp1 = a1;

long tmp2 = a2;

a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;

a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;

}

p *= 2;

n >>= 1;

}

a1=a1%MOD;

System.out.println(a1);

}

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\\
1&0 \\\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\\
1\\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

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

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

e-olymp 6261. Устройство для анализа бюллетеня

14/09/2020 by Евгений Фищук

Задача

Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил $p$ голосов, результат в процентах составляет $\frac{100 \cdot p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более $100$ английских букв. Нет ни одного кандидата с именем «Invalid».

Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘$\%$’. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите $«12.35»$ для $12.345$).

Тесты

№	Входные данные	Выходные данные
1	4 7 Loudy Apples Dogman Miller .X.. X… …. ..X. ..XX ..X. ..X.	Dogman 42.86% Loudy 14.29% Apples 14.29% Miller 0.00% Invalid 28.57%
2	4 10 Loudy Apples Dogman Miller X……………….. X………………….. X……………… X…………………. X………….. x……………………….. X………………. X…………… X..x xxxx	Loudy 70.00% Apples 0.00% Dogman 0.00% Miller 0.00% Invalid 30.00%

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

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

class Main
{
	
	private static class Candidates implements Comparable<Candidates>{
	    public String name;
	    public float numb;
	
	    public Candidates(String name, float numb) {
	        this.name = name;
	        this.numb = numb;
	    }
	    
	    @Override
		public int compareTo(Candidates o) 
		{
			int res = (int)(o.numb - this.numb);
		    return res;
		}
	}

	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		int candidateNum = in.nextInt(), ballotNum=in.nextInt();
	    Candidates[] candidate=new Candidates[candidateNum+1];
	    String s2 = in.nextLine();
	    for (int i = 0; i < candidateNum; i++)
	    {
	    	String s = in.nextLine();
	    	Candidates tmp=new Candidates(s,0);
	    	candidate[i]=tmp;
	    }
	    Candidates tmp=new Candidates("Invalid",0);
	    candidate[candidateNum]=tmp;
	    int count = 0, num=0;
	    for (int i = 0; i < ballotNum; i++)
	    {
	        String s = in.nextLine();
	        count = 0;
	        for (int j = 0; j < candidateNum; j++)
	        {
	            if (s.charAt(j) == 'X')
	            {
	                count++;
	                num = j;
	            }
	            if (Character.isLetter(s.charAt(j)) && s.charAt(j) != 'X')
	                count=2;
	        }
	        if (count == 1)
	        {
	            candidate[num].numb++;
	        }
	        else
	            candidate[candidateNum].numb++;
	 
	    }
	    Arrays.sort(candidate,0,candidateNum);
	    for (int i = 0; i <= candidateNum; i++)
	    {
	    	if(i!=candidateNum)
	    		System.out.printf("%s %.2f%% \n", candidate[i].name, candidate[i].numb*100/ballotNum);
	    	else
	    		System.out.printf("%s %.2f%%", candidate[i].name, candidate[i].numb*100/ballotNum);
	    }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

private static class Candidates implements Comparable<Candidates>{

public String name;

public float numb;

public Candidates(String name, float numb) {

this.name = name;

this.numb = numb;

}

@Override

public int compareTo(Candidates o)

{

int res = (int)(o.numb - this.numb);

return res;

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int candidateNum = in.nextInt(), ballotNum=in.nextInt();

Candidates[] candidate=new Candidates[candidateNum+1];

String s2 = in.nextLine();

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

{

String s = in.nextLine();

Candidates tmp=new Candidates(s,0);

candidate[i]=tmp;

}

Candidates tmp=new Candidates("Invalid",0);

candidate[candidateNum]=tmp;

int count = 0, num=0;

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

{

String s = in.nextLine();

count = 0;

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

{

if (s.charAt(j) == 'X')

{

count++;

num = j;

}

if (Character.isLetter(s.charAt(j)) && s.charAt(j) != 'X')

count=2;

}

if (count == 1)

{

candidate[num].numb++;

}

else

candidate[candidateNum].numb++;

}

Arrays.sort(candidate,0,candidateNum);

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

{

if(i!=candidateNum)

System.out.printf("%s %.2f%% \n", candidate[i].name, candidate[i].numb*100/ballotNum);

else

System.out.printf("%s %.2f%%", candidate[i].name, candidate[i].numb*100/ballotNum);

}

Решение

Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

Ссылки

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

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

java@Cat

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

Author Archives: Евгений Фищук

e-olymp 236. Триомино

Триомино

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

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

Тесты

№

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

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

Код

Решение

Ссылки

e-olymp 6261. Устройство для анализа бюллетеня

Задача

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

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

Тесты

№

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

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

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

Решение

Ссылки