Общий форум @ Timus Online Judge

gio_gio why the tag for this problem is "data structures"? [6] // Задача 1654. Шифровка 2 фев 2011 23:21

Nguyen Khac Tung Hints [1] // Задача 1654. Шифровка 10 авг 2011 11:07

K-A-R-E-N(YSU) Who can explain me?Please.....This problem wrong!!!!!!!!!!! [5] // Задача 1654. Шифровка 11 фев 2009 20:05

kare61 6 test // Задача 1787. Поворот на МЕГУ 4 окт 2012 04:13

Alexey Shmelev [NNSU] To admins: "strange" radiobeacons [1] // Задача 1151. Радиомаяки 21 авг 2010 01:14

HaiyangZheng the means of luck // Задача 1493. В одном шаге от счастья 3 окт 2012 20:27

kostan3 возмущения [1] // Задача 1076. Trash 27 апр 2012 23:26

HaiyangZheng help me find a test data for the error. // Задача 1005. Куча камней 3 окт 2012 18:42

Yagudin Ruslan why wa 6 // Задача 1127. Кубики 3 окт 2012 09:28

why WA 6, i search two pair, if pair=2, then count++
    #include <queue>
    #include <iostream>
    #include <set>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <string>
    #include <stack>
    #include <sstream>

    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    char a[10000][6];
    void swap(char &a,char &b)
    {
        if(a>b)
        {
            char c;
            c=a;
            a=b;
            b=c;
        }
    }
    int amx(int a,int b)
    {
        if(a>b)
        {
            return(a);
        }
        else return (b);
    }
    int main()
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>a[i][0];
            cin>>a[i][2];
            cin>>a[i][3];
            cin>>a[i][1];
            cin>>a[i][4];
            cin>>a[i][5];
        }
        /*
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<6;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        */

        int max1=0;
        for(int i=0;i<n;i++)
        {
            int coutn1=0,count2=0,count3=0;
            for(int j=0;j<n;j++)
            {
                //if(i!=j)
                {
                    if(
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5])
                        ))
                        ||
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5])
                        ))
                        )
                    {
                        coutn1++;
                    }
                    if(
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][0]==a[j][0] && a[i][1]==a[j][1])|| (a[i][0]==a[j][2] && a[i][1]==a[j][3]) || (a[i][0]==a[j][4] && a[i][1]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        ||
                        (((a[i][1]==a[j][0] && a[i][0]==a[j][1])|| (a[i][1]==a[j][2] && a[i][0]==a[j][3]) || (a[i][1]==a[j][4] && a[i][0]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        )
                    {
                        count2++;
                    }
                    if(
                        ((
                        (a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5]))
                        && ((a[i][4]==a[j][0] && a[i][5]==a[j][1])|| (a[i][4]==a[j][2] && a[i][5]==a[j][3]) || (a[i][4]==a[j][4] && a[i][5]==a[j][5])
                        ))
                        ||
                        (((a[i][2]==a[j][0] && a[i][3]==a[j][1])|| (a[i][2]==a[j][2] && a[i][3]==a[j][3]) || (a[i][2]==a[j][4] && a[i][3]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        ||
                        (((a[i][3]==a[j][0] && a[i][2]==a[j][1])|| (a[i][3]==a[j][2] && a[i][2]==a[j][3]) || (a[i][3]==a[j][4] && a[i][2]==a[j][5]))
                        && ((a[i][5]==a[j][0] && a[i][4]==a[j][1])|| (a[i][5]==a[j][2] && a[i][4]==a[j][3]) || (a[i][5]==a[j][4] && a[i][4]==a[j][5])
                        ))
                        )
                    {
                        count3++;
                    }

                }
            }
            max1=amx(amx(coutn1,count2),(max1,count3));
        }
        cout<<max1;

    return 0;
    }

Edited by author 03.10.2012 09:29

ZiDo Wrong answer [3] // Задача 1001. Обратный корень 15 сен 2012 20:44

Neo Nomaly test 3 [4] // Задача 1348. Пусти козла в огород 2 6 апр 2005 18:15

navi1893 C++ Answer [5] // Задача 1068. Сумма 21 июн 2012 05:38

tt123753 No subject [2] // Задача 1759. Долгожители 2 окт 2012 18:25

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

struct Date
{
    int day;

    int month;

    int year;
};

struct person
{
    int num;

    int live;

    Date die;
};

bool comp(person a, person b)
{
    if (a.live != b.live) return a.live > b.live;
    if (a.die.year != b.die.year) return a.die.year < b.die.year;
    if (a.die.month != b.die.month) return a.die.month < b.die.month;
    if (a.die.day != b.die.day) return a.die.day < b.die.day;
}

bool leap(int year)
{
    if (year%400==0) return 1;
    if (year%100==0) return 0;
    if (year%4==0) return 1;
    else return 0;
}

int monthDay(int year, int month)
{
    if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) return 31;

    else if (month == 4 || month == 6|| month == 9 || month == 11) return 30;

    else if (leap(year))return 29;

    else return 28;
}

int Distance(Date a, Date b)//a??¨®¨²b o??e¨º?¨®????1¨¨??¨²
{
    int dis = 0;

    for (int i = a.year+1; i < b.year; ++i)
    {
        if (leap(i)) dis += 366;

        else dis += 365;
    }

    if (a.year != b.year)
    {
        for (int i = a.month+1; i <= 12; ++i)
        {
            dis += monthDay(a.year, i);
        }

        dis += (monthDay(a.year, a.month) - a.day + 1);

        for (int i = 1; i < b.month; ++i)
        {
            dis += monthDay(b.year, i);
        }

        dis += b.day;
    }
    else
    {
        if (a.month != b.month)
        {
            dis += (monthDay(a.year, a.month) - a.day + 1);cout << monthDay(a.year, a.month) << endl;

            for (int i = a.month+1; i < b.month; ++i)
            {
                dis += monthDay(b.year, i);
            }

            dis += b.day;
        }
        else
        {
            dis += (b.day - a.day + 1);
        }
    }

    return dis;
}

int convert(char a, char b)
{
    return (a - '0')*10 + b - '0';
}

int convert(char a, char b, char c, char d)
{
    return (a - '0')*1000 + (b - '0')*100 + (c - '0')*10 + d - '0';
}

void print(Date a)
{
    cout << a.year << " " << a.month << " " << a.day << endl;
}

int main()
{
    int m;

    cin >> m;

    char useless[11];

    Date a, b;

    person p[101];

    for (int i = 0; i < m; ++i)
    {
        scanf("%d.%d.%d", &a.day, &a.month, &a.year);

        cin >> useless;

        scanf("%d.%d.%d", &b.day, &b.month, &b.year);

        p[i].num = i+1;

        p[i].live = Distance(a, b);

        p[i].die = b;
    }

    sort(p, p+m, comp);

    cout << p[0].num << endl;

    system("pause");
}

tt123753 Re: No subject [1] // Задача 1759. Долгожители 2 окт 2012 18:26

I don't know why it always gets wrong answer;

tt123753 Re: No subject // Задача 1759. Долгожители 2 окт 2012 18:30

i know………… it's my fault... because i cout more sth.

Sandro (USU) Problem 1325 "Dirt". Time limit now is 0.5 sec. // Задача 1325. Грязь 2 окт 2012 17:27

Aharon_Smbatyan(YSU) this is a good algorithm. [17] // Задача 1009. K-ичные числа 20 июн 2010 04:03

n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).
3. else answer(n) = ( k-1 ) * ( answer(n-1,k) + answer(n-2,k) ).

Edited by author 20.06.2010 04:04

f309587969 Re: this is a good algorithm. // Задача 1009. K-ичные числа 27 июл 2010 11:13

是好啊！！！！

archimede_syracuse Re: this is a good algorithm. [8] // Задача 1009. K-ичные числа 15 авг 2010 12:34

n>=2 !!!

Andrew Hoffmann aka SKYDOS [Vladimir SU] Re: this is a good algorithm. [7] // Задача 1009. K-ичные числа 15 авг 2010 12:49

There is good O(1) memory and O(n) algo (n - number length)
info: http://skydos.blogspot.com/2010/07/k.html

Artem Khizha [DNU] Re: this is a good algorithm. [6] // Задача 1009. K-ичные числа 16 авг 2010 03:25

Okay, I'll join to Captains Obvious. You can find an answer with O(1) memory and O(logN) time.

Andrew Hoffmann aka SKYDOS [Vladimir SU] Re: this is a good algorithm. [5] // Задача 1009. K-ичные числа 16 авг 2010 03:32

Can you explain this algo?
Really interesting to know better one.
Thx.

Artem Khizha [DNU] писал(a) 16 августа 2010 03:25
Okay, I'll join to Captains Obvious. You can find an answer with O(1) memory and O(logN) time.

Artem Khizha [DNU] Re: this is a good algorithm. [4] // Задача 1009. K-ичные числа 16 авг 2010 13:32

Sure, you're welcome.
Okay, we're already know, that the answer can be found reccurently: F(N) = (K-1)*(F(K-1)+F(N-2)), where F(0) = 1, F(1) = K-1. We see, that the {F(N)} sequence is very similar to Fibonacci's one and can assume some facts. I see two different approaches to solve the problem.

1) First way is to build characteristic equation, solve it and get an exact formula for F(N). I didn't try this way, because I foresaw some problems with precision and float calculations. If you're interested, you can turn to this article as a manual:
http://www.intuit.ru/department/algorithms/algocombi/8/2.html

2) I assumed, that method with fast matrix exponentiation will work as well as for Fibonacci's numbers.
Just consider a matrix: L(N) = {{F(N+1), F(N)}, {F(N), F(N-1)}}.
Let's try to find such R, that L(N)*R = L(N+1).
If you write down this information, you'll easily see, that R = {{K-1, 1}, {K-1, 0}}. So all you need is to find L(1)*R.pow(N-2).

Hope this information was helpful, I'm not sure it is the best way to describe an approach though. :-)

Edited by author 16.08.2010 13:34

Artem Khizha [DNU] Re: this is a good algorithm. // Задача 1009. K-ичные числа 16 авг 2010 13:39

Actually, I implemented only O(N)-solution before. Today I wrote a code for a fast exponentiation, but (it seems I don't know java well) my time increased in #1013, where BigInteger is needed. Strange. :-)

Andrew Hoffmann aka SKYDOS [Vladimir SU] Re: this is a good algorithm. [2] // Задача 1009. K-ичные числа 16 авг 2010 16:29

Artem Khizha [DNU]
Thx for explanations and idea! I got it!
Really nice approach with matrixes!

dima11221122 Re: this is a good algorithm. [1] // Задача 1009. K-ичные числа 15 сен 2010 14:10

#include <iostream>

using namespace std;
unsigned long stepen(unsigned long K,unsigned long N)
{
    unsigned long i, result=1;
    if (N<0)
        return 0;
    else
    {
        i=1;
        for(; i<=N; i++)
            result*=K;
        return result;
    }
}

int main()
{
    unsigned long N, K, i, result;
    cin>>N;
    cin>>K;

        result=stepen(K, N)-(stepen(K,N-2)+stepen(K, N-1)-1);
        cout<<result<<endl;
        //system("Pause");
        return 0;

}

WA #2. Why?

Frankie Re: this is a good algorithm. // Задача 1009. K-ичные числа 26 ноя 2011 06:41

>>dima11221122

Firstly, I came up with something like that and got WA2 too.

N = (k-1)^n + n(k-1)^(n-1) - that formula looks pretty alright; but it isn't.
It assumes there can't be more than one zero in the number, while there obviously can. The actual answer is something like that -
N = (k-1)^n + n * (П(i=1 to min(k,n)) of (k-i)^(n-1))
and i think it's anyways easier to solve that like original poster did.

Btw, your code is sooooo bad; u might wanna do something about that.

Edited by author 26.11.2011 06:42

TLaum Re: this is a good algorithm. // Задача 1009. K-ичные числа 23 сен 2011 17:49

good job!

daminus Re: this is a good algorithm. // Задача 1009. K-ичные числа 1 мар 2012 12:15

Thanks! Good algo

thefourtheye Re: this is a good algorithm. [4] // Задача 1009. K-ичные числа 29 мар 2012 02:25

Aharon_Smbatyan(YSU) писал(a) 20 июня 2010 04:03

n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).
3. else answer(n) = ( k-1 ) * ( answer(n-1,k) + answer(n-2,k) ).

Edited by author 20.06.2010 04:04

I am not sure, how the number of zero digit numbers (of course, without two zeros in it) become 1.

Edited by author 29.03.2012 02:38

David Hi [3] // Задача 1009. K-ичные числа 23 май 2012 11:28

Can anybody tell me where can i get some info about this topic(k-based numbers), I really don't get from where cames this recurrent formula? Greetings

Amir Aupov [MIPT] Re: Hi [1] // Задача 1009. K-ичные числа 8 авг 2012 19:02

How can we get valid n-digit number? Trivially, we can append each of (k-1) possible digits (k digits except for 0) to the front of each of (n-1)-digit valid numbers.
But we can also form valid number this way: append 0 to the front of (n-2)-digit valid number, and then append (k-1) possible digits, as in the first case.

This gives us F(n) = (k-1)*F(n-1)+(k-1)*F(n-2), where F is the function to yield the amount of valid n-digit numbers.

I'd recommend you to ensure this yields only the valid numbers, think why can't it produce duplicates, and whether other means to construct valid numbers are possible.

Then you follow Artem Khizha's [DNU] recipe and get an AC (=

Edited by author 08.08.2012 19:05

Bogatyr Re: Hi // Задача 1009. K-ичные числа 2 окт 2012 15:31

> Amir Aupov [MIPT]

I like your explanation. I approached the construction of N digit numbers from N-1 digit numbers in the typical way of constructing numbers: multiply N-1 digit number by base, and add in the new digits to the units position. This has the benefit of being clear and natural, so we can be sure that we're not missing any numbers. It has the disadvantage that you must track numbers that end in zero separately from those that don't. But this is still quite simple:
Z(n): # of valid numbers ending in zero
NZ(n): # of valid numbers not ending in zero
Z(2) = k - 1
NZ(2) = (k - 1) * k - (k - 1) (total number of valid 2-digit numbers, minus those that end in 0)
then,
Z(n) = NZ(n - 1)
NZ(n) = (Z(n-1) + NZ(n-1)) * (k - 1)

Compute Z(n) and NZ(n) iteratively (DP), and then output F(n) at the end
F(n) = Z(n) + NZ(n)

Bogatyr Re: Hi // Задача 1009. K-ичные числа 2 окт 2012 14:32

HI David,
The problem statement language is confusing. A "k-based number" is a number represented in base "k", that's all.

HaiyangZheng I am very surprised to hear the fact!! // Задача 1001. Обратный корень 1 окт 2012 21:50

efg переведите задание // Задача 1056. Центры сети 1 окт 2012 15:37

-XraY- Your tests are incorrect. [1] // Задача 1285. Нитка в гиперкосмосе 29 сен 2012 23:21

Zawi [java] Wrong answer test 3 - what is going on ? [1] // Задача 1001. Обратный корень 21 июл 2012 20:09

吕蒙子明 Hint // Задача 1864. Посиделки у Дена 30 сен 2012 19:23