結果
| 問題 | No.262 面白くないビットすごろく |
| ユーザー |
 tanzaku
|
| 提出日時 | 2015-08-01 01:31:16 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 229 ms / 2,000 ms |
| コード長 | 12,811 bytes |
| コンパイル時間 | 2,569 ms |
| コンパイル使用メモリ | 89,920 KB |
| 実行使用メモリ | 39,300 KB |
| 最終ジャッジ日時 | 2024-07-18 00:20:19 |
| 合計ジャッジ時間 | 3,207 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 49 ms
37,100 KB |
| testcase_01 | AC | 229 ms
39,300 KB |
| testcase_02 | AC | 49 ms
37,044 KB |
| testcase_03 | AC | 221 ms
39,208 KB |
ソースコード
import java.io.*;
import java.math.*;
import java.util.*;
import static java.util.Arrays.*;
public class Main {
private static final int mod = (int)1e9+7;
final Random random = new Random(0);
final IOFast io = new IOFast();
/// MAIN CODE
public void run() throws IOException {
// int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
int TEST_CASE = 1;
while(TEST_CASE-- != 0) {
/*
for(long i = 0, j = 1; j <= 1_000_000_000_000L; i++) {
if(i == 100000000) {
i = 0;
System.err.print(j + ",");
}
j += Long.bitCount(j);
}
System.err.println();
*/
long n = io.nextLong();
long[] ume = new long[]{1L,1469980682L,3043866212L,4668805409L,6304910373L,7993963848L,9642632564L,11294354943L,13027785740L,14738125641L,16528261375L,18210846386L,19866094009L,21598491427L,23305273534L,25096174497L,26851772374L,28602397046L,30427698867L,32270214646L,34179892637L,35795799216L,37474898933L,39197471652L,40939570400L,42754518130L,44462028976L,46246138687L,48061009294L,49915842586L,51804505761L,53529119448L,55324780533L,57133698007L,59013445746L,60879847551L,62731107733L,64657845640L,66594902248L,68606219970L,70213317069L,71896995173L,73611431536L,75356722003L,77182126886L,78884623046L,80667255480L,82482422734L,84337635812L,86217961301L,87953309938L,89746820666L,91556662143L,93439998092L,95303593667L,97158013922L,99080204117L,101016865959L,103042167188L,104735939624L,106520038461L,108339020461L,110194551904L,112090962920L,113932646967L,115853066778L,117756428334L,119756595296L,121611143237L,123494368506L,125404818570L,127360339056L,129354551818L,131294634763L,133318905970L,135350966231L,137462808125L,139052375614L,140732668145L,142445346067L,144194746393L,146037422438L,147724195504L,149512054409L,151331584274L,153185209653L,155051645119L,156798952109L,158596635939L,160402984627L,162286550795L,164149606192L,166003338830L,167926774511L,169866379992L,171876516828L,173576727178L,175365124328L,177188326764L,179046824749L,180935812837L,182776411125L,184711441709L,186615413487L,188617425859L,190457184794L,192340450187L,194259404542L,196219122517L,198200809867L,200148332580L,202170968418L,204206289209L,206291552308L,207999147186L,209789717168L,211606934845L,213471105767L,215354169177L,217198961226L,219130300531L,221046311026L,223051245661L,224881948287L,226765329947L,228690056611L,230647419412L,232625258768L,234578074839L,236597532732L,238637796475L,240718182584L,242543758169L,244441961634L,246354023499L,248340289572L,250293791186L,252267865239L,254282368803L,256342539975L,258381856246L,260332956441L,262353169362L,264392085346L,266499308735L,268531551868L,270653190668L,272777094984L,274954969328L,276550885608L,278235349289L,279949996554L,281699656520L,283532815989L,285230291483L,287018460850L,288843338529L,290697914218L,292555622135L,294299027632L,296108809336L,297913802581L,299797478106L,301659455418L,303513296426L,305438074433L,307378730113L,309375584150L,311084691351L,312874881380L,314691888318L,316556574461L,318438834135L,320283900459L,322215373230L,324132816437L,326137829796L,327967124398L,329850743236L,331776265114L,333733585567L,335710857866L,337664009017L,339683323432L,341723231862L,343789429912L,345507238667L,347300064350L,349113030840L,350984406135L,352860264736L,354707032557L,356636401290L,358564384537L,360569937186L,362394197650L,364277970856L,366198335844L,368164629325L,370136993397L,372090932249L,374111296941L,376151464705L,378224220960L,380058390875L,381957670005L,383870119640L,385856452156L,387803833108L,389785718954L,391799556548L,393861322106L,395892667666L,397847294362L,399867029816L,401906744673L,404011963610L,406045283138L,408166458655L,410293988630L,412459892513L,414170300487L,415960418167L,417777139873L,419642241648L,421523913358L,423369329089L,425300867467L,427219090689L,429224980146L,431052903006L,432936691509L,434863107905L,436819529994L,438796401986L,440750473367L,442769590824L,444808941609L,446887863691L,448715363575L,450613672574L,452525875722L,454512303700L,456465371949L,458440607830L,460454459144L,462516131473L,464552796690L,466505438580L,468525009072L,470565134403L,472670820245L,474703374234L,476824486461L,478949396296L,481137046691L,482947439062L,484844914786L,486755371546L,488739231350L,490705646259L,492663323054L,494681424791L,496736570450L,498791098622L,500733994162L,502758835083L,504792318352L,506906580542L,508935069724L,511049944011L,513166144224L,515389888649L,517288857480L,519289749375L,521307331285L,523399099799L,525438600325L,527525826917L,529645152611L,531830142929L,533911179954L,535991669365L,538110881857L,540290279141L,542445766977L,544627454221L,546846436546L,549136811513L,550918245602L,552577704794L,554309590979L,556033975615L,557829972985L,559563840963L,561330089610L,563154351847L,564994400089L,566933008719L,568618071111L,570404156594L,572223399213L,574077826799L,575973613140L,577815644715L,579740475323L,581642857022L,583642878785L,585412682639L,587185448355L,589004843649L,590849466513L,592776838356L,594584205659L,596480632590L,598390213848L,600373164701L,602276789225L,604131558058L,606055535834L,607996922408L,610014086322L,611936152792L,613942070950L,615953831172L,618055837482L,619832855781L,621609731741L,623425191203L,625271673298L,627194398350L,629008378139L,630905954546L,632817224875L,634802011556L,636703471280L,638556986940L,640483343578L,642421663991L,644434745133L,646369655949L,648375252409L,650387040722L,652490864964L,654340820929L,656224576189L,658146134026L,660104803135L,662085614135L,664034735323L,666056469887L,668092915894L,670191528127L,672123851671L,674129434810L,676141175724L,678244658509L,680275412064L,682374196306L,684492287082L,686688081834L,688498052941L,690271265396L,692090271191L,693934884550L,695861454783L,697669335632L,699566093251L,701476114233L,703459014946L,705362572698L,707217077730L,709141525004L,711083438845L,713099812794L,715022516642L,717028460170L,719040292107L,721142705765L,723002026267L,724885629032L,726803561592L,728761045579L,730747568720L,732693287993L,734717019390L,736749758874L,738856174302L,740777465961L,742783307821L,744795165468L,746896572050L,748933922639L,751024347007L,753141880458L,755336643853L,757242843585L,759125818601L,761035892927L,762989904072L,764984543942L,766926219065L,768950249380L,770981663499L,773102984407L,775002837011L,777003979124L,779020939116L,781115568136L,783154062627L,785241482314L,787360097555L,789546215920L,791553252818L,793534166666L,795550462220L,797612465334L,799687356918L,801743227036L,803862443625L,806016345293L,808158770188L,810211805541L,812331967883L,814480115181L,816665287720L,818815284449L,821033071135L,823291446296L,825336664996L,827085965369L,828930392300L,830720144582L,832614810573L,834456466214L,836329001352L,838244378913L,840200563740L,842172566043L,844015128001L,845924301194L,847830932678L,849827622308L,851765990426L,853747688137L,855773169362L,857835953013L,859806361441L,861660536604L,863582897550L,865519592653L,867544389704L,869447143816L,871446393635L,873463619464L,875554302728L,877522802074L,879503038972L,881526923742L,883590032966L,885658701687L,887720236940L,889838183538L,891996345815L,894045653774L,895894981736L,897822674154L,899754550956L,901760199509L,903674751149L,905672137367L,907685190026L,909772129132L,911755883600L,913735370979L,915747908991L,917808707287L,919885714570L,921941106979L,924059753965L,926210825894L,928324426778L,930270736126L,932294263359L,934327743215L,936441420445L,938472256198L,940594928117L,942709938290L,944923194197L,946936098999L,949049124016L,951165540848L,953382717840L,955503787985L,957723191654L,959946162612L,962209863199L,964024768740L,965922590824L,967834326487L,969819285239L,971779514592L,973744657012L,975763287764L,977816739031L,979866439343L,981812882713L,983836311144L,985870025629L,987983393422L,990014429317L,992137825273L,994252783159L,996463258969L,998367757387L,};
long s = 1;
long v = -1;
for(int i = 1; i <= ume.length; i++, s += 100000000) {
if(i == ume.length || ume[i] > n) {
v = ume[i-1];
break;
}
}
for(; v < n; s++) {
v += Long.bitCount(v);
}
io.out.println(v == n ? s : -1);
}
}
/// TEMPLATE
static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
static <T> void swap(T[] x, int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; }
static void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; }
void main() throws IOException {
// IOFast.setFileIO("rle-size.in", "rle-size.out");
try { run(); }
catch (EndOfFileRuntimeException e) { }
io.out.flush();
}
public static void main(String[] args) throws IOException { new Main().main(); }
static class EndOfFileRuntimeException extends RuntimeException {
private static final long serialVersionUID = -8565341110209207657L; }
static
public class IOFast {
private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
private PrintWriter out = new PrintWriter(System.out);
void setFileIn(String ins) throws IOException { in.close(); in = new BufferedReader(new FileReader(ins)); }
void setFileOut(String outs) throws IOException { out.flush(); out.close(); out = new PrintWriter(new FileWriter(outs)); }
void setFileIO(String ins, String outs) throws IOException { setFileIn(ins); setFileOut(outs); }
private static int pos, readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500*8*2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static { for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; }
public int read() throws IOException { if(pos >= readLen) { pos = 0; readLen = in.read(buffer); if(readLen <= 0) { throw new EndOfFileRuntimeException(); } } return buffer[pos++]; }
public int nextInt() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
public long nextLong() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
public char nextChar() throws IOException { while(true) { final int c = read(); if(!isSpace[c]) { return (char)c; } } }
int reads(int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } if(str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
int reads(char[] cs, int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } cs[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
public char[] nextLine() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isLineSep); try { if(str[len-1] == '\r') { len--; read(); } } catch(EndOfFileRuntimeException e) { ; } return Arrays.copyOf(str, len); }
public String nextString() throws IOException { return new String(next()); }
public char[] next() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); return Arrays.copyOf(str, len); }
public int next(char[] cs) throws IOException { int len = 0; cs[len++] = nextChar(); len = reads(cs, len, isSpace); return len; }
public double nextDouble() throws IOException { return Double.parseDouble(nextString()); }
public long[] nextLongArray(final int n) throws IOException { final long[] res = new long[n]; for(int i = 0; i < n; i++) { res[i] = nextLong(); } return res; }
public int[] nextIntArray(final int n) throws IOException { final int[] res = new int[n]; for(int i = 0; i < n; i++) { res[i] = nextInt(); } return res; }
public int[][] nextIntArray2D(final int n, final int k) throws IOException { final int[][] res = new int[n][]; for(int i = 0; i < n; i++) { res[i] = nextIntArray(k); } return res; }
public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException { final int[][] res = new int[n][k+1]; for(int i = 0; i < n; i++) { for(int j = 0; j < k; j++) { res[i][j] = nextInt(); } res[i][k] = i; } return res; }
public double[] nextDoubleArray(final int n) throws IOException { final double[] res = new double[n]; for(int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; }
}
}