possible answer 1 or 2

It' strange task. My solution is SO STUPID. Watch at 2 last numbers of (k,n), where k = {1,2,3,4}



Edited by author 21.03.2022 17:49

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...
^_^

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a,n=0;
        a = in.nextInt();
        a = (int) (Math.pow(1,a)+Math.pow(2,a)+Math.pow(3,a)+Math.pow(4,a));
        int b[] = new int[11000];
        while(a>0){
            if(a%10==0)n++;
            else break;
            a = a/10;
        }
        System.out.print(n);
    }
}

if {(1^n + 2^n + 3^n + 4^n) % 10} is equal to 0, then we find 1 zero.
if {(1^n + 2^n + 3^n + 4^n) % 100} is equal to 0, then we find 2 zeros.
and so on....

now, how to calculate {(1^n + 2^n + 3^n + 4^n) % 10}:

Look,
 {(1^n + 2^n + 3^n + 4^n) % 10}
=((1^n % 10) + (2^n % 10) + (3^n % 10) + (4^n % 10)) % 10   [simple modulo equivalencies]

now,
 (4^n % 10)
= ((((((4%10)*4)%10)*4)%10)*4)%10 . . . . . . . (n times)    [(4%10), then multiply by 4, then mod 10, loop for n times]
similarly for (2^n % 10) and (3^n % 10).   No need for 1, because (1^n % 10) is always 1.

In this way, calculate the rusult of {(1^n + 2^n + 3^n + 4^n) % m} for m = 10, 100, ans so on...  and count zeros... :)


** to know more about modulo equivalencies,
http://en.wikipedia.org/wiki/Modulo_operation

** solution C++:
(don't see the solution before trying, at first try yourself)

http://github.com/shahed-shd/Online-Judge-Solutions/blob/master/Timus-Online-Judge/1295.%20Crazy%20Notions.cpp


Edited by author 13.08.2015 15:51

Edited by author 13.08.2015 23:02

my prog got AC but on 65,85,105... it answers 2,but I think the answer is 1.
yes,my second prog answers 1 and got AC too.
a 20-number period incorrect!

Edited by author 20.05.2013 20:57

uses
  SysUtils;
var
  a : array[0..10000] of longint;
  n, m, i, x, y : longint;
begin
  readln(n);
  if n = 1 then
    writeln(1)
  else if n mod 4 = 0 then
    writeln(0)
  else if (n mod 4 = 3) or (n = 25) or (n = 5) then
    writeln(2)
  else
    writeln(1);
  readln;
end.

Edited by author 09.07.2013 16:05

В чём ошибка ни как разобраться не могу.


#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <fstream>

using namespace std;

int step (int a , int b){
    int cur , i;
    cur = 1;
    for (i = 0; i < b; i++){
        cur = cur *a;
    }
    return cur;
}

int main(){
    int  n, c , i, p;
    cin >> n;
    p = 0;
    c = step(1,n) + step(2,n) + step(3,n) + step(4,n);
    for(p = 0; (c%10) == 0 ; c = c/10){
          if(c%10 == 0){
             p++;
          }
    }
    cout << p;
    return 0;
}
В зарание спасибо.

first it get ce
function xx(d:longint):longint;
and get crash(stack) with
function xx:longint;

Can some body help me to optimize my C# solution? I have TL 10 (it works approximately 0.8s if N=30000).

PLEASE, DO NOT OFFER TO USE THE PERIOD OF THE IMPLEMENTED FUNCTION!

Here is my code:

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

#if (!ONLINE_JUDGE)
using System.IO;
#endif

namespace _295__acm.timus.ru_
{
    class InfinumNumber
    {
        public const int Base = 10000;
        public static InfinumNumber Zero = new InfinumNumber(0);
        public static InfinumNumber PlusOne = new InfinumNumber(1);
        private LinkedList<int> value;
        public int Length
        {
            get
            {
                return value.Count;
            }
        }

        private static void MoveForward(ref LinkedListNode<int> k)
        {
            if (k.Next == null) k.List.AddLast(0);
            k = k.Next;
        }

        public InfinumNumber()
        {
            value = new LinkedList<int>();
        }
        public InfinumNumber(int value)
        {
            this.value = new LinkedList<int>();
            this.value.AddLast(value % Base);
            value /= Base;
            if (value != 0)
            {
                this.value.AddLast(value % Base);
                value /= Base;
            }
            if (value != 0) this.value.AddLast(value);
        }
        public static InfinumNumber operator +(InfinumNumber a, InfinumNumber b)
        {
            int modulo = 0;
            int length = Math.Min(a.Length, b.Length);
            InfinumNumber rezult = new InfinumNumber();
            LinkedListNode<int> i = a.value.First;
            LinkedListNode<int> j = b.value.First;
            for (int k = 0; k < length; k++)
            {
                int current = i.Value + j.Value + modulo;
                modulo = 1;
                if (current > Base) current -= Base;
                else modulo = 0;
                rezult.value.AddLast(current);
                i = i.Next;
                j = j.Next;
            }
            if (modulo > 0) rezult.value.AddLast(modulo);
            if (length < b.Length) i = j;
            while (i != null)
            {
                if (modulo > 0)
                {
                    rezult.value.Last.Value += i.Value;
                    modulo = 0;
                }
                else rezult.value.AddLast(i.Value);
                i = i.Next;
            }
            return rezult;
        }
        public static InfinumNumber operator *(InfinumNumber a, InfinumNumber b)
        {
            int modulo = 0;
            InfinumNumber rezult = new InfinumNumber(0);
            LinkedListNode<int> i = a.value.First, j = b.value.First;
            LinkedListNode<int> k, k0 = rezult.value.First;
            for (i = b.value.First; i != null; i = i.Next)
            {
                k = k0;
                modulo = 0;
                for (j = a.value.First; j != null; j = j.Next)
                {
                    k.Value += j.Value * i.Value + modulo;
                    modulo = k.Value / Base;
                    k.Value %= Base;
                    MoveForward(ref k);
                }
                k.Value += modulo;
                MoveForward(ref k0);
            }
            while (rezult.Length > 1 && rezult.value.Last.Value == 0) rezult.value.RemoveLast();
            return rezult;
        }
        public int Zeros()
        {
            int results = 0;
            for (LinkedListNode<int> t = this.value.First; t != null; t = t.Next)
            {
                int value = t.Value;
                for(int i = 0; i < 4; i++)
                {
                    if (value % 10 == 0) results++;
                    else return results;
                    value /= 10;
                }
            }
            return results;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

#if (!ONLINE_JUDGE)
            Console.SetIn(new StreamReader(@"..\..\input.txt"));
            Console.SetOut(new StreamWriter(@"..\..\output.txt"));
#endif
            int n = int.Parse(Console.ReadLine());
            InfinumNumber pow2 = new InfinumNumber(1), pow3 = new InfinumNumber(1),
                t2 = new InfinumNumber(2), t3 = new InfinumNumber(3);

            for (int i = n; i > 0; i = (i >> 1))
            {
                if ((i & 1) == 1)
                {
                    pow2 *= t2;
                    pow3 *= t3;
                }
                t2 = t2 * t2;
                t3 = t3 * t3;
            }
            Console.WriteLine((pow2 * (pow2 + InfinumNumber.PlusOne) + InfinumNumber.PlusOne + pow3).Zeros());

#if (!ONLINE_JUDGE)
                Console.Out.Flush();
#endif
        }
    }
}

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

public class B1295
{
    public static void main (String [] args)
     {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
    BigInteger t1=BigInteger.valueOf(2).pow(n);
        BigInteger t2=BigInteger.valueOf(3).pow(n);
        BigInteger t3=BigInteger.valueOf(4).pow(n);
    BigInteger t=BigInteger.valueOf(0);
    t=t.add(t1);
    t=t.add(t2);
    t=t.add(t3);
    t=t.add(BigInteger.valueOf(1));
    BigInteger k=BigInteger.valueOf(0);
    while(t.mod(BigInteger.valueOf(10))==BigInteger.valueOf(0))
    {
        k=k.add(BigInteger.valueOf(1));
            t=t.divide(BigInteger.valueOf(10));
    }
    System.out.println(k);
    }
}

This program give AC

Edited by author 19.07.2011 12:09

Edited by author 19.07.2011 12:09

I've got AC with two variants of solution. Brute force and period. Period was {1,1,2,0}, but it is not correct!

Edited by author 01.04.2011 14:38

Edited by author 01.04.2011 14:38

I can't understand Why I got "Wrong Answer" in TEST#14......? Give me some tests !!!!!
This is my code.---
import java.util.Scanner;

public class T_1295 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n==1){
            System.out.println(1);
            return;
        }
        if(n%4==1 || n%4==3){
            System.out.println(2);
            return;
        }
        if(n%4==0){
            System.out.println(0);
            return;
        }
        if(n%4==2){
            System.out.println(1);
            return;
        }
    }
}

input:
5
output:
2

give me test 5 please