CSES - Datatähti 2023 alku - Results
Submission details
Task:Kertoma
Sender:adex720
Submission time:2022-11-13 17:21:16 +0200
Language:Java
Status:READY
Result:46
Feedback
groupverdictscore
#1ACCEPTED22
#2ACCEPTED24
#30
Test results
testverdicttimegroup
#1ACCEPTED0.12 s1, 2, 3details
#2ACCEPTED0.12 s1, 2, 3details
#3ACCEPTED0.12 s1, 2, 3details
#4ACCEPTED0.17 s1, 2, 3details
#5ACCEPTED0.17 s1, 2, 3details
#6ACCEPTED0.17 s1, 2, 3details
#7ACCEPTED0.17 s2, 3details
#8ACCEPTED0.17 s2, 3details
#9ACCEPTED0.17 s2, 3details
#10ACCEPTED0.17 s2, 3details
#110.23 s3details
#120.22 s3details
#130.32 s3details
#140.49 s3details
#150.70 s3details
#160.80 s3details

Code

import java.io.FileNotFoundException;
import java.math.BigInteger;
import java.util.Scanner;

public class Kertoma3 {

    public static void main(String[] args) throws FileNotFoundException {

        Scanner scanner = new Scanner(System.in);
        // Scanner scanner = new Scanner(new File("maarat.txt"));
        String[] numerotString = scanner.nextLine().split(" ");
        int[] numerot = new int[10];
        int yhteensa = 0;

        for (int i = 0; i < 10; i++) {
            numerot[i] = Integer.parseInt(numerotString[i]);
            yhteensa += numerot[i];
        }

        if (yhteensa <= 6) {
            System.out.print(pienempiKuin10(numerot));
            return;
        }

        if (yhteensa <= 1000) {
            pieni(numerot, yhteensa);
            return;
        }

        int[] tuhat = getKertomanPituus(yhteensa);
        int alku = tuhat[0];
        int bitteja = tuhat[1];

        int maara = BigInteger.TEN.pow(yhteensa).multiply(BigInteger.valueOf(5)).bitLength() + 2;
        int puuttuu = maara - bitteja - 5;

        BigInteger kertoma = BigInteger.valueOf(alku * 1000L);
        int luku = alku * 1000;
        while (true) {
            int bits = kertoma.bitLength();
            if (bits >= puuttuu) {
                System.out.println(luku + ": " + (bits - puuttuu));
                System.out.print(luku);
                break;
            }
            luku++;
            kertoma = kertoma.multiply(BigInteger.valueOf(luku));

        }
    }

    public static int[] getKertomanPituus(int m) {
        if (m < 2568) return new int[]{0, 0};
        if (m < 5736) return new int[]{1, 8530};
        if (m < 9131) return new int[]{2, 19053};
        if (m < 12674) return new int[]{3, 30332};
        if (m < 16326) return new int[]{4, 42100};
        if (m < 20066) return new int[]{5, 54233};
        if (m < 23878) return new int[]{6, 66656};
        if (m < 27753) return new int[]{7, 79321};
        if (m < 31682) return new int[]{8, 92193};
        if (m < 35660) return new int[]{9, 105246};
        if (m < 39681) return new int[]{10, 118459};
        if (m < 43742) return new int[]{11, 131816};
        if (m < 47838) return new int[]{12, 145305};
        if (m < 51969) return new int[]{13, 158915};
        if (m < 56130) return new int[]{14, 172635};
        if (m < 60320) return new int[]{15, 186458};
        if (m < 64538) return new int[]{16, 200378};
        if (m < 68781) return new int[]{17, 214388};
        if (m < 73048) return new int[]{18, 228483};
        if (m < 77338) return new int[]{19, 242658};
        if (m < 81649) return new int[]{20, 256909};
        if (m < 85982) return new int[]{21, 271233};
        if (m < 90334) return new int[]{22, 285624};
        if (m < 94705) return new int[]{23, 300082};
        if (m < 99094) return new int[]{24, 314602};
        if (m < 103501) return new int[]{25, 329183};
        if (m < 107924) return new int[]{26, 343821};
        if (m < 112363) return new int[]{27, 358515};
        if (m < 116818) return new int[]{28, 373262};
        if (m < 121288) return new int[]{29, 388060};
        if (m < 125772) return new int[]{30, 402909};
        if (m < 130271) return new int[]{31, 417805};
        if (m < 134782) return new int[]{32, 432748};
        if (m < 139307) return new int[]{33, 447736};
        if (m < 143845) return new int[]{34, 462768};
        if (m < 148395) return new int[]{35, 477842};
        if (m < 152958) return new int[]{36, 492958};
        if (m < 157532) return new int[]{37, 508113};
        if (m < 162117) return new int[]{38, 523308};
        if (m < 166714) return new int[]{39, 538541};
        if (m < 171321) return new int[]{40, 553810};
        if (m < 175939) return new int[]{41, 569116};
        if (m < 180568) return new int[]{42, 584457};
        if (m < 185206) return new int[]{43, 599832};
        if (m < 189855) return new int[]{44, 615240};
        if (m < 194513) return new int[]{45, 630682};
        if (m < 199180) return new int[]{46, 646156};
        if (m < 203857) return new int[]{47, 661660};
        if (m < 208542) return new int[]{48, 677196};
        if (m < 213237) return new int[]{49, 692762};
        if (m < 217940) return new int[]{50, 708357};
        if (m < 222652) return new int[]{51, 723981};
        if (m < 227372) return new int[]{52, 739633};
        if (m < 232101) return new int[]{53, 755313};
        if (m < 236837) return new int[]{54, 771020};
        if (m < 241581) return new int[]{55, 786754};
        if (m < 246333) return new int[]{56, 802515};
        if (m < 251093) return new int[]{57, 818301};
        if (m < 255860) return new int[]{58, 834112};
        if (m < 260635) return new int[]{59, 849948};
        if (m < 265416) return new int[]{60, 865809};
        if (m < 270205) return new int[]{61, 881693};
        if (m < 275001) return new int[]{62, 897601};
        if (m < 279804) return new int[]{63, 913533};
        if (m < 284614) return new int[]{64, 929488};
        if (m < 289430) return new int[]{65, 945465};
        if (m < 294253) return new int[]{66, 961464};
        if (m < 299082) return new int[]{67, 977485};
        if (m < 303918) return new int[]{68, 993527};
        if (m < 308760) return new int[]{69, 1009591};
        if (m < 313608) return new int[]{70, 1025676};
        if (m < 318462) return new int[]{71, 1041781};
        if (m < 323322) return new int[]{72, 1057907};
        if (m < 328189) return new int[]{73, 1074053};
        if (m < 333061) return new int[]{74, 1090218};
        if (m < 337939) return new int[]{75, 1106403};
        if (m < 342822) return new int[]{76, 1122607};
        if (m < 347712) return new int[]{77, 1138830};
        if (m < 352607) return new int[]{78, 1155072};
        if (m < 357507) return new int[]{79, 1171333};
        if (m < 362413) return new int[]{80, 1187611};
        if (m < 367324) return new int[]{81, 1203908};
        if (m < 372240) return new int[]{82, 1220223};
        if (m < 377162) return new int[]{83, 1236555};
        if (m < 382089) return new int[]{84, 1252904};
        if (m < 387021) return new int[]{85, 1269271};
        if (m < 391958) return new int[]{86, 1285654};
        if (m < 396900) return new int[]{87, 1302055};
        if (m < 401847) return new int[]{88, 1318472};
        if (m < 406799) return new int[]{89, 1334905};
        if (m < 411755) return new int[]{90, 1351355};
        if (m < 416717) return new int[]{91, 1367820};
        if (m < 421683) return new int[]{92, 1384302};
        if (m < 426654) return new int[]{93, 1400799};
        if (m < 431629) return new int[]{94, 1417312};
        if (m < 436609) return new int[]{95, 1433840};
        if (m < 441594) return new int[]{96, 1450383};
        if (m < 446583) return new int[]{97, 1466941};
        if (m < 451576) return new int[]{98, 1483514};
        if (m < 456574) return new int[]{99, 1500102};
        if (m < 461576) return new int[]{100, 1516705};
        if (m < 466583) return new int[]{101, 1533322};
        if (m < 471593) return new int[]{102, 1549953};
        if (m < 476608) return new int[]{103, 1566598};
        if (m < 481627) return new int[]{104, 1583257};
        if (m < 486651) return new int[]{105, 1599930};
        if (m < 491678) return new int[]{106, 1616617};
        if (m < 496709) return new int[]{107, 1633318};
        if (m < 501745) return new int[]{108, 1650032};
        if (m < 506784) return new int[]{109, 1666759};
        if (m < 511828) return new int[]{110, 1683500};
        if (m < 516875) return new int[]{111, 1700253};
        if (m < 521926) return new int[]{112, 1717020};
        if (m < 526981) return new int[]{113, 1733800};
        if (m < 532040) return new int[]{114, 1750592};
        if (m < 537102) return new int[]{115, 1767397};
        if (m < 542169) return new int[]{116, 1784214};
        if (m < 547239) return new int[]{117, 1801044};
        if (m < 552312) return new int[]{118, 1817887};
        if (m < 557390) return new int[]{119, 1834741};
        if (m < 562471) return new int[]{120, 1851608};
        if (m < 567555) return new int[]{121, 1868487};
        if (m < 572644) return new int[]{122, 1885377};
        if (m < 577735) return new int[]{123, 1902280};
        if (m < 582830) return new int[]{124, 1919194};
        if (m < 587929) return new int[]{125, 1936119};
        if (m < 593031) return new int[]{126, 1953057};
        if (m < 598137) return new int[]{127, 1970006};
        if (m < 603246) return new int[]{128, 1986966};
        if (m < 608358) return new int[]{129, 2003937};
        if (m < 613473) return new int[]{130, 2020920};
        if (m < 618592) return new int[]{131, 2037913};
        if (m < 623715) return new int[]{132, 2054918};
        if (m < 628840) return new int[]{133, 2071934};
        if (m < 633969) return new int[]{134, 2088960};
        if (m < 639101) return new int[]{135, 2105998};
        if (m < 644236) return new int[]{136, 2123045};
        if (m < 649374) return new int[]{137, 2140104};
        if (m < 654516) return new int[]{138, 2157173};
        if (m < 659660) return new int[]{139, 2174253};
        if (m < 664808) return new int[]{140, 2191342};
        if (m < 669959) return new int[]{141, 2208443};
        if (m < 675112) return new int[]{142, 2225553};
        return new int[]{0, 1};
    }

    public static int pienempiKuin10(int[] numerot) {
        if (numerot[2] == 1) { // 2 4 5 6 8 9

            if (numerot[0] == 1) { // 5 6 9
                if (numerot[1] == 1)
                    return 5;
                if (numerot[7] == 1)
                    return 6;
                return 9;
            } else { // 2 4 8
                if (numerot[4] == 0)
                    return 2;
                if (numerot[0] == 0)
                    return 4;
                return 8;
            }

        } else { // 1 3 7
            if (numerot[1] == 1)
                return 1;
            if (numerot[6] == 1)
                return 3;
            return 7;
        }
    }

    public static void pieni(int[] numerot, int yhteensa) {
        int jaljella = numerot[0];
        int[] maarat = new int[8];
        int kerroin = 97656; // * 5n+1  8 kertaa,
        for (int i = 0; i < 8; i++) {
            int maara = (int) (jaljella / (double) kerroin);

            jaljella -= maara;
            maarat[7 - i] = maara;

            kerroin -= 1;
            kerroin *= 0.2;
        }

        int bitteja = BigInteger.TEN.pow(yhteensa).bitLength();

        int max = maarat[0] * 5; // Jos kaikki nollat olisivat luvun lopussa, tämä luku olisi

        int min = 10;
        int perus = (int) ((min + max) * 0.5f);
        BigInteger edellinenPienempi = kertoma(new BigInteger(min + ""));
        int edellinenPienempiLuku = min - 1;
        while (true) {
            BigInteger kertoma = kertoma(new BigInteger(perus + ""), new BigInteger(edellinenPienempiLuku + 1 + "")).multiply(edellinenPienempi);
            int pituus = kertoma.bitLength();

            int ero = pituus - bitteja;
            if (ero >= 0 && ero <= 4) {
                int len = kertoma.toString().length();
                // System.out.println("kertoma: " + perus + ", pituus: " + len + ", oikea: " + yhteensa);
                if (len - 1 == yhteensa) {
                    System.out.print(perus);
                    return;
                }
            }

            if (ero > 0) {
                if (max == perus) break;
                max = perus;
            } else {
                if (min == perus) break;
                min = perus;
                edellinenPienempi = kertoma;
                edellinenPienempiLuku = perus;
            }
            perus = min + (max - min) / 2;
        }


    }

    public static BigInteger kertoma(BigInteger luku) {
        if (luku.compareTo(BigInteger.ONE) == 0) {
            return luku;
        }

        return kertoma(luku.subtract(BigInteger.ONE)).multiply(luku);
    }

    public static BigInteger kertoma(BigInteger luku, BigInteger asti) {
        if (luku.compareTo(asti) == 0) {
            return luku;
        }

        return kertoma(luku.subtract(BigInteger.ONE), asti).multiply(luku);
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
0 0 1 0 0 0 0 0 0 0

correct output
2

user output
2

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
0 0 0 0 0 0 1 0 0 0

correct output
3

user output
3

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
0 0 1 0 1 0 0 0 0 0

correct output
4

user output
4

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 0 1 1 0 0 1 0 2 0

correct output
10

user output
10

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
9 3 1 1 2 2 3 1 6 1

correct output
27

user output
27

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 4 3 4 3 2 2 4 3 7

correct output
36

user output
36

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
71 53 36 30 25 29 42 24 34 29

correct output
199

user output
199

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
71 33 46 38 27 45 36 21 35 35

correct output
205

user output
205

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
93 38 35 26 43 54 38 25 41 34

correct output
222

user output
222

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
100 33 33 45 36 43 38 54 56 36

correct output
242

user output
242

Test 11

Group: 3

Verdict:

input
3419 1797 1845 1849 1879 1791 ...

correct output
5959

user output
5959: 12
5959

Test 12

Group: 3

Verdict:

input
4776 2695 2709 2781 2616 2753 ...

correct output
8391

user output
8390: 1
8390

Test 13

Group: 3

Verdict:

input
20097 12282 12229 12214 12406 ...

correct output
32001

user output
32001: 14
32001

Test 14

Group: 3

Verdict:

input
47934 29918 29878 29713 29984 ...

correct output
71718

user output
71718: 14
71718

Test 15

Group: 3

Verdict:

input
84691 54156 54277 54533 54296 ...

correct output
123123

user output
123123: 15
123123

Test 16

Group: 3

Verdict:

input
99098 63339 63878 64182 63904 ...

correct output
142663

user output
142662: 0
142662