I got wrong answer beacuse of test 6
Someone please explain what is test 6
Program in C




#include <stdio.h>
#include <math.h>

int main()
{
    long int n,m,y;
    int x,cont=0,aux1;

scanf("%d %d %d",&n,&m,&y);



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

    aux1=pow(i,n);

    if (aux1%m == y)
    {
        printf("%d ",i);
cont++;

    }


}
if (cont == 0)
{
    printf("-1\n");
}



    return 0;
}

Edited by author 13.10.2020 05:27

Use Bigmod Algorithm

В описании обоих примеров мы делаем одно и то же:
1. Расшифровали
2. Перевернули
3. Зашифровали
4. Показали.
Зачем нам данные о типе компьютера GOOD или BAD?

What is wrong with my code? :(

#include <stdio.h>
#include <stdlib.h>

int main (){

 int N;
 scanf ("%d",&N);

    for (int i = 0 ; i < N ; i++){
       char x;
       int y;
       getchar();
       scanf ("%c %d",&x,&y);
       int movimientos = 0;

       if (y + 2 <= 8)
        if (x - 1 >= 97){
         movimientos++;
        }

       if (y+2 <=8)
        if (x + 1<=104){
         movimientos++;
        }

       if (y-2 >= 1)
        if (x-1 >97){
         movimientos++;
        }

       if (y-2 >= 1)
        if (x + 1 <= 104){
         movimientos++;
        }

       if (x+2 <= 104)
        if (y - 1 >= 1){
         movimientos++;
        }

       if (x+2 <= 104)
        if (y+1 <= 8){
         movimientos++;
        }

       if (x-2 >= 97)
        if (y+1 <= 8){
         movimientos++;
        }

       if (x-2 >= 97)
        if (y-1 >= 1){
         movimientos++;
        }
       printf ("\n %d", movimientos);
       printf ("\n");
    }

 return 0;
}

Edited by author 21.10.2020 01:36

Edited by author 21.10.2020 01:37

Can anybody give me ideas about 21 test, please?

Edited by author 18.10.2020 22:11

Edited by author 19.10.2020 03:42

1^n+2^n+3^n+4^n will never give you summ [1..9]*(2*5)^3, and there will not be three zeros as well, thus this programm will work:



    vector <vector <int>> st(3);
        st[0].push_back(2); st[1].push_back(3); st[2].push_back(4);
        for (int i = 0; i <= 2; i++) {
            int osn = i + 2;
            for (;;) {
                int newst = (osn * *--st[i].end()) % 100;
                if (!count(st[i].begin(), st[i].end(), newst))
                    st[i].push_back(newst);
                else
                    break;
            }
        }
        int n;
        cin >> n;
        n--;
        int sum = 1 + st[0][n < 21 ? n : n  % 20 ] + st[1][n % 20] + st[2][n % 10];
        if (sum % 100 == 0)
            cout << 2;
        else if (sum % 10 == 0)
            cout << 1;
        else
            cout << 0;

Edited by author 17.10.2020 04:13

For n= 1 sum is 10
For n= 2 sum is 30
For n= 3 sum is 100
For n= 4 sum is 354
For n= 5 sum is 1300
For n= 6 sum is 4890
For n= 7 sum is 18700
For n= 8 sum is 72354
For n= 9 sum is 282340
For n= 10 sum is 1108650
For n= 11 sum is 4373500
For n= 12 sum is 17312754
For n= 13 sum is 68711380
For n= 14 sum is 273234810
For n= 15 sum is 1088123500
For n= 16 sum is 4338079554
For n= 17 sum is 17309140420
For n= 18 sum is 69107159370
For n= 19 sum is 276040692700
For n= 20 sum is 1102999460754
For n= 21 sum is 4408508961460
For n= 22 sum is 17623571298330
For n= 23 sum is 70462895745100
For n= 24 sum is 281757423024354
For n= 25 sum is 1126747229006500
For n= 26 sum is 4506141560307690
For n= 27 sum is 18022024241184700
For n= 28 sum is 72080471098818354
For n= 29 sum is 288299007065947540
For n= 30 sum is 1153127396812683450
For n= 31 sum is 4612303693971155500
For n= 32 sum is 18448597098193370754
For n= 33 sum is 73792535363994696580
For n= 34 sum is 295164582378232361610
For n= 35 sum is 1180641652296870041500
For n= 36 sum is 4722516577573661689554
For n= 37 sum is 18889916215521910805620
For n= 38 sum is 75559214577906874318170
For n= 39 sum is 302235507459360068466700
For n= 40 sum is 1208937977281187743262754
For n= 41 sum is 4835739751457092892866660
For n= 42 sum is 19342922532827596354169130
For n= 43 sum is 77371580712312457811295100
For n= 44 sum is 309485994592264844522058354
For n= 45 sum is 1237942993598122010104911700
For n= 46 sum is 4951769020079711120841770490
For n= 47 sum is 19807067217380584093377630700
For n= 48 sum is 79228242280707695941030524354
For n= 49 sum is 316912889356387143941658812740
For n= 50 sum is 1267651318126218219249198818250
For n= 51 sum is 5070604554606882933344392817500
For n= 52 sum is 20282416064733564154220177588754
For n= 53 sum is 81129657797852358383008156681780
For n= 54 sum is 324518611808163747837614220448410
For n= 55 sum is 1298074389082917952281600172439500
For n= 56 sum is 5192297381882460727948627580659554
For n= 57 sum is 20769189004182209740318785033270820
For n= 58 sum is 83076754446685939590963152340836970
For n= 59 sum is 332307013076615060541147022138320700
For n= 60 sum is 1329228038176074149272932079181624754
For n= 61 sum is 5316912110313138319569681793218371860
For n= 62 sum is 21267648314079078448018430611562799930
For n= 63 sum is 85070592874795889305904518780746525100
For n= 64 sum is 340282370354622283774333836163326852354
For n= 65 sum is 1361129477984805314767929371848039216900
For n= 66 sum is 5444517901638169798120393057123771393290
For n= 67 sum is 21778071575649524809701385913984767356700
For n= 68 sum is 87112286209888636090612558664997791190354
For n= 69 sum is 348449144561426154918166427592346682877940
For n= 70 sum is 1393796577411319451340404584976811991513050
For n= 71 sum is 5575186307142122300366015555350241157359500
For n= 72 sum is 22300745221059022686479615050971379025966754
For n= 73 sum is 89202980861707691200969841059079628938666980
For n= 74 sum is 356811923379245566169042951534866593549495210
For n= 75 sum is 1427247693314226668771681457501042086163317500
For n= 76 sum is 5708990772648639887373292563020758437710989554
For n= 77 sum is 22835963088769759186352946008996529944340536020
For n= 78 sum is 91343852349604635655991262422454060186498715770
For n= 79 sum is 365375409381995339355703787080674965630698254700
For n= 80 sum is 1461501637478711747618031964958185844491490546754
For n= 81 sum is 5846006549767038161057779518665020938501229477060
For n= 82 sum is 23384026198624726155988075469008555664869069190730
For n= 83 sum is 93536104793168625159223178894782916850585429435100
For n= 84 sum is 374144419168683662242705356306784306892702573406354
For n= 85 sum is 1496577676662762133788259366752908259875959655922100
For n= 86 sum is 5986310706615130989605351330274572364087420301176090
For n= 87 sum is 23945242826352771321778346988258359885436693418362700
For n= 88 sum is 95780971305087827377184213109256155739680344676816354
For n= 89 sum is 383123885219381535778949328215177781373867160442143140
For n= 90 sum is 1532495540874616821926434740814140620383596124422767850
For n= 91 sum is 6129982163489739324137651248354791005484147220552781500
For n= 92 sum is 24519928653932773405846341851189729672356637600594504754
For n= 93 sum is 98079714615652541951272577983022375797828217657124652180
For n= 94 sum is 392318858462374512788751943676783394830800914591931502010
For n= 95 sum is 1569275433848791086105992669961022294870233874656410675500
For n= 96 sum is 6277101735393043449276925365645369407379158316288468679554
For n= 97 sum is 25108406941565811111666565520064546475725566055735896601220
For n= 98 sum is 100433627766244156390342854252865848766557591269876739954570
For n= 99 sum is 401734511064919361392401193529603296307253403570680596268700
For n= 100 sum is 1606938044259505653062694103673466714252196844456991646028754

The output will be 0, 1 or 2...
See the divisibility of n by some numbers (like 4) , their remainders and make a relation with the outputs...
Have a Happy Coding...
^_^

This is not an MST problem, because finally, we can have a graph with several connected components (not a tree). For example, if a city has a power station and the price to build a line to another city is too high we can just isolate this city. Such test:
4 2
1 4
0 1 1 7
1 0 5 2
1 5 0 2
7 2 2 0

The answer is 2.
We build line 1 <-> 2, 1 <-> 3. The total price is 2. It's not necessary to build any line to city 4.

I don't know, maybe there are no tests for such cases.


Edited by author 09.10.2019 16:52

12341321
12344321

12991321
12999921

12341991
12344321

12343991
12344321

12344991
12355321

1234554991
1234664321

1234559991
1234664321

1134559921
1134664311

1134998821
1135005311

8999999999
9000000009

89999
90009

1250025
1250521

1999
2002

100003
101101

11111
11111

1000003
1001001

1999992
2000002

1009002
1010101

18
22

36313404080
36313431363

3373687313428241827948801150507677526
3373687313428241828281428243137863733

669262074855963079771197586206281259112
669262074855963079777970369558470262966

242167700017836474388100
242167700018810007761242

16252383
16255261

469342775745586144105609869
469342775745595547577243964

37461293193018561603953493340
37461293193018581039139216473

9194184285169534216966507128749
9194184285169534359615824814919

21
22

1330454685235862
1330454774540331

78336742687917227491028
78336742687978624763387

47923802054017335212073765802860114
47923802054017335253371045020832974

505752
506605

940
949

428540910018912794058956977
428540910018919810019045824

9770330728908946347636591906356869449214
9770330728908946347667436498098270330779

7068416097840258049887921681085
7068416097840258520487906148607

517805724457730620
517805725527508715

506833497
506838605

5820
5885

484243646784563247619038458645194136
484243646784563247742365487646342484

91413688117232096060
91413688122188631419

771886477139587251334596
771886477139931774688177

8304292305552149553379655920949280409378
8304292305552149553443559412555032924038

9628134090110628
9628134114318269

2445193927845273449357413443
2445193927845335487293915442

519
525

6885428526826048829
6885428527258245886

72924386042452563577194755578
72924386042452625424068342927

123012
123321

123131
123321

36408
36463

123
131

I get AC using priority_queue<unsigned int>
At first I push n/2+1 numbers then I read next number,push it to queue,pop biggest element until I have elements
If n odd I use 1 top elem for answer
else
I use 2 top elements for answer such way:
if (top1+top2) mod 2=0 I output top1/2+top2/2+top1 mod 2 and then print ".0"
else I output top1/2+top2/2 and then print ".5"
I hope it'll help somebody.
P.S thank to authors of this problem.I like this problem very much!


Edited by author 07.02.2008 01:49

Please help. what is test case 8. so that i can verify my answers.

I can't find a problem
Please, help


my code (C++):


#include <iostream>
#include <string>
using namespace std;
int main()
{
    int a, b, c, sum, sr, i, n;
    cin >> n;
    cin >> a >> b >> c;
    sum = 0;
    if (n == 3) {
        sum = a + b + c;
        sr = 2;
    }
    else {
        for (i = 3; i < n; i++) {
            if ((a + b + c) > sum) {
                sum = a + b + c;
                sr = i - 1;

            }
            a = b;
            b = c;
            cin >> c;

        }
    }
    cout << sum<< " "<<sr;

    return 0;
}

In Russian version there is a mistake in the constraints of h. Must be 200, not 260.

for n=2,k=3
ans=2*(2-3)*(2-6)*(2-9)*.....
The author must include the condition that n>=k..

I coded O(n^3) that was accepted fairly easy... But I know there is O(n^2) algo but I don't know how to implement it.. Any Ideas?

There only 10 situations!!!!!
//1. in
//2. input
//3. inputon
//4. inputone

//5. out
//6. output
//7. outputon
//8. outputone

//9. puton
//10. one

Check their in inverse order.

   bool check(char const* s){
        while(*s != '\n'){
               if (s == "one") s += 3;
              // there s == "one" only pseudocode, you may check
             //  as memcmp(s, "one",3) == 0
               else  // ......

               //.............

               // 10 times else
               else if (s == "in") s +=2;
               else
                  return false;
         }
        return true;
   }

what a question haha. just read the question carefully

I got tl5 using recursion solution, and i dont know how to optimize it.
Please give me some hints how to solve it better