CSES - Datatähti 2023 alku - Results
Submission details
Task:Kertoma
Sender:adex720
Submission time:2022-11-13 17:53:31 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.88 s1, 2, 3details
#20.88 s1, 2, 3details
#30.84 s1, 2, 3details
#4--1, 2, 3details
#5--1, 2, 3details
#6--1, 2, 3details
#7--2, 3details
#8--2, 3details
#9--2, 3details
#10--2, 3details
#11ACCEPTED0.20 s3details
#12ACCEPTED0.19 s3details
#130.24 s3details
#14ACCEPTED0.43 s3details
#15ACCEPTED0.63 s3details
#16ACCEPTED0.76 s3details

Code

import java.io.File;
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)); //  SGFHSDFGHSFDGSDFGSGFD
            //return pienempiKuin10(numerot);
        }

        if (yhteensa <= 2000) {
            /*return*/ pieni(numerot, yhteensa);
        }

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

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

        int lisa = 0;

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

        }

       // return luku + lisa;
    }

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

        return new int[]{0, 1, 0};
    }

    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 int 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);     //  ADSFASDFADSFSDGFHSRTHSTHSGFDHS
                    return perus;
                }
            }

            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;
        }

        return perus;
    }

    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:

input
0 0 1 0 0 0 0 0 0 0

correct output
2

user output
2

Error:
Exception in thread "main" java.lang.StackOverflowError
	at Kertoma3.kertoma(Kertoma3.java...

Test 2

Group: 1, 2, 3

Verdict:

input
0 0 0 0 0 0 1 0 0 0

correct output
3

user output
3

Error:
Exception in thread "main" java.lang.StackOverflowError
	at Kertoma3.kertoma(Kertoma3.java...

Test 3

Group: 1, 2, 3

Verdict:

input
0 0 1 0 1 0 0 0 0 0

correct output
4

user output
4

Error:
Exception in thread "main" java.lang.StackOverflowError
	at Kertoma3.kertoma(Kertoma3.java...

Test 4

Group: 1, 2, 3

Verdict:

input
2 0 1 1 0 0 1 0 2 0

correct output
10

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict:

input
9 3 1 1 2 2 3 1 6 1

correct output
27

user output
(empty)

Test 6

Group: 1, 2, 3

Verdict:

input
10 4 3 4 3 2 2 4 3 7

correct output
36

user output
(empty)

Test 7

Group: 2, 3

Verdict:

input
71 53 36 30 25 29 42 24 34 29

correct output
199

user output
(empty)

Test 8

Group: 2, 3

Verdict:

input
71 33 46 38 27 45 36 21 35 35

correct output
205

user output
(empty)

Test 9

Group: 2, 3

Verdict:

input
93 38 35 26 43 54 38 25 41 34

correct output
222

user output
(empty)

Test 10

Group: 2, 3

Verdict:

input
100 33 33 45 36 43 38 54 56 36

correct output
242

user output
(empty)

Test 11

Group: 3

Verdict: ACCEPTED

input
3419 1797 1845 1849 1879 1791 ...

correct output
5959

user output
5959

Test 12

Group: 3

Verdict: ACCEPTED

input
4776 2695 2709 2781 2616 2753 ...

correct output
8391

user output
8391

Test 13

Group: 3

Verdict:

input
20097 12282 12229 12214 12406 ...

correct output
32001

user output
32000

Test 14

Group: 3

Verdict: ACCEPTED

input
47934 29918 29878 29713 29984 ...

correct output
71718

user output
71718

Test 15

Group: 3

Verdict: ACCEPTED

input
84691 54156 54277 54533 54296 ...

correct output
123123

user output
123123

Test 16

Group: 3

Verdict: ACCEPTED

input
99098 63339 63878 64182 63904 ...

correct output
142663

user output
142663