Untitled
unknown
plain_text
a year ago
14 kB
1
Indexable
Never
<div class="box_qu">
<span class="rank4">Level 4 </span>
<br>
<dl>
<dt>Lucky number</dt>
<dd><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Trong một số nước châu Á, 8 và 6 được coi là những
chữ số may mắn. Bất cứ số nguyên nào chỉ chứa chữ số 8 và 6 được coi là số may
mắn, ví dụ 6, 8, 66, 668, 88, 886 …. Nguyên là một học sinh rất thích toán.
Nguyên thích các số may mắn nhưng chỉ thích các số có dạng</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">S = 8…86…6</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">trong đó S có ít nhất một chữ số và chữ số 6 và 8
không nhất thiết phải đồng thời xuất hiện. Ví dụ, 8, 88, 6, 66, 86, 886, 8866 …
là các số có dạng S.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Cho trước một số nguyên dương X (1 < X < 10 000),
Nguyên muốn tìm số may mắn nhỏ nhất dạng S, có không quá 200 chữ số và chia hết
cho X.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Nhiệm vụ của bạn là viết một chương trình tìm số đó
cho Nguyên.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Input</font></span></b></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều
test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ
dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Trên mỗi dòng tiếp theo chứa một số nguyên X tương ứng
với mỗi bộ dữ liệu.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Ouput</font></span></b></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Với mỗi bộ dữ liệu, ghi ra số may mắn dạng S nhỏ nhất
chia hết cho X. Trường hợp không tồn tại số S có không quá 200 chữ số như vậy,
ghi -1.</font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000">Sample</font></span></b></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><b><span style="padding: 0in; border: 1pt windowtext; border-image: none; color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt; mso-border-alt: none windowtext 0in;">Input</span></b><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><span style="mso-tab-count: 1;"> </span></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">4</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">6</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">8</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">43</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">5<span style="mso-tab-count: 1;"> </span></span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"> </span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><b><span style="padding: 0in; border: 1pt windowtext; border-image: none; color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt; mso-border-alt: none windowtext 0in;">Output</span></b></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">Case #1</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">6</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">Case #2</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">8</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">Case #3</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">86</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">Case #4</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="color: rgb(34, 34, 34); line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;">-1</span></p><font color="#000000" face="Times New Roman" size="3">
</font><p style="margin: 0in 0in 10pt;"><span style="line-height: 115%; font-family: "Times New Roman","serif"; font-size: 12pt;"><font color="#000000"> </font></span></p><font color="#000000" face="Times New Roman" size="3">
</font><br></dd>
</dl>
<dl class="lang">
<dt>Sample Input : </dt>
<dd><a href="/common/satti/contestProb/contestProbDown.do?downType=in&contestProbId=AVkVRYpvfjsAAAFG" style="text-decoration: underline;font-weight: normal;">input.txt</a></dd>
<dt></dt>
<dd><a href="javascript:;" onclick="pop_sampleInput('AVkVRYpvfjsAAAFG')" style="text-decoration: underline;font-weight: normal;">sample_input pop-up</a></dd>
</dl>
<!-- <dl class="lang"> -->
<!-- <dt>Sample Output : </dt> -->
<!-- </dl> -->
<dl class="lang">
<dt>Language</dt>
<dd>
<input type="radio" value="C" id="lang" name="lang" onclick="selectCodeLang('C');">C(gcc-4.6.3)
<input type="radio" value="P" id="lang" name="lang" onclick="selectCodeLang('P');">C++(gcc-4.6.3)
<input type="radio" value="J" id="lang" name="lang" onclick="selectCodeLang('J');">Java(java-1.6.0_12)
<input type="button" onclick="loadInitCodeLang();" value=" Initialize the source code ">
<input type="button" onclick="pop_aboutEditor();" value=" Shortcuts for Web Editor ">
</dd>
</dl>
<div class="count">
<table>
<thead>
<tr>
<th colspan="3">Try Count <strong>3</strong> / Total Count<strong> 99</strong></th>
</tr>
<tr>
<th><p>Time of submission</p></th>
<th><p>Solution</p></th>
<th>Result</th>
</tr>
</thead>
<tbody>
<tr>
<td>13:31:25</td>
<td><a href="#" class="btno_code" onclick="pop_code('AYmbQjMsxckRAAQF','AVkVRYpvfjsAAAFG', 'AYppMELciDgRAASx'); return false;"><span>Code</span> </a></td>
<td>
<span class="pass">Accept</span>
</td>
</tr>
<tr>
<td>13:24:29</td>
<td><a href="#" class="btno_code" onclick="pop_code('AYmbQjMsxckRAAQF','AVkVRYpvfjsAAAFG', 'AYppKe0ch_MRAASx'); return false;"><span>Code</span> </a></td>
<td>
<span class="pass">Accept</span>
</td>
</tr>
<tr>
<td>13:13:03</td>
<td><a href="#" class="btno_code" onclick="pop_code('AYmbQjMsxckRAAQF','AVkVRYpvfjsAAAFG', 'AYppH3J8h7sRAASx'); return false;"><span>Code</span> </a></td>
<td>
<span class="pass">Accept</span>
</td>
</tr>
</tbody>
</table>
</div>
</div>
package Buoi28.Lucky_number;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N;
static boolean flag;
static String result;
public static void input(Scanner sc) {
N = sc.nextInt();
result = "";
}
public static int isCheck(String number) {
int F = (number.charAt(0) - '0') % N;
for (int i = 1; i < number.length(); i++) {
int a = number.charAt(i) - '0';
F = (F * 10 + a) % N;
}
return F;
}
public static void backtrack(int k, int limit) {
if (!flag) {
return;
}
if (k > limit) {
return;
}
int soDu = 0;
for (int i = 0; i < k; i++) {
soDu = (soDu * 10 + 8) % N;
}
for (int i = 0; i < limit - k; i++) {
soDu = (soDu * 10 + 6) % N;
}
if (soDu == 0) {
for (int i = 0; i < k; i++) {
result += "8";
}
for (int i = 0; i < limit - k; i++) {
result += "6";
}
flag = false;
return;
}
backtrack(k + 1, limit);
}
public static void solve() {
String str = N + "";
flag = true;
for (int i = str.length(); i < 200; i++) {
backtrack(0, i);
}
if (result != "") {
System.out.println(result);
} else {
System.out.println(-1);
}
}
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
long start = System.currentTimeMillis();
System.setIn(new FileInputStream("input.txt"));
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
input(sc);
System.out.println("Case #" + test_case + "");
solve();
}
long end = System.currentTimeMillis();
System.out.println((double) (end - start) / 1000);
}
}