AKU NEGARAKU
連結：https://ac.nowcoder.com/acm/contest/12207/A
來源：牛客網
題目描述
1st Academy is an international leadership training academy based in Kuala Lumpur. Every year, the company trains thousands of people to be supplied to companies around the world. To be fair amongst all the trainees, the company will do the selection process using numbering system. The trainees will choose a number from 1 to N, and one number is not limited to only one trainee. The N represents the total number of companies that request trainees from the academy. A number, M, would be picked at random, and the selection starts with a trainee whose number is 1, and then in every M’th people after that, wrapping around to 1 after N, and ignoring trainees already selected. For example, if N = 15 and M = 6, trainees would be selected in the order: 6, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7. All the selected trainees except the last one (which is number 7) will be supplied to companies outside of Malaysia.
However, Leong preferred to stay and work in Malaysia. To him, there is no better place other than Malaysia. He does not mind being located anywhere as long it is Malaysia. As a friend of him, you could help him to choose a number that will save him from being located outside.
Input
輸入描述:
Input will consist of a series of lines, each line containing the number of companies (N) with 1 \leq N \leq 15001≤N≤1500, and a skipping value (M) with 1 \leq M \leq 501≤M≤50. The values will be terminated by a line consisting of double zeros (0 0) as shown in sample input output.
輸出描述:
Output will consist of a series of lines, one for each line of the input. Each line will consist of the number M according to the above scheme.
示例1
輸入
複制
15 6
550 23
0 0
輸出
複制
7
470
約瑟夫環，公式
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_cxx;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define endl "\n"
//#define x first
//#define y second
int yy[1050];
void init1(){
for (int i = 1; i <= 1010; i ++) yy[i] = i + 1;
}
void init2(){
for (int i = 1; i <= 1010; i ++) yy[i] = 101;
}
void init3(){
for (int i = 1; i <= 1010; i ++) yy[i] = 123;
}
void init4(){
for (int i = 1; i <= 1010; i ++) yy[i] = i * 2;
}
void init5(){
for (int i = 1; i <= 1010; i ++) yy[i] = 9 + i;
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int N = 1e3;
const int M = 3 * N;
const int mod = 1e9 + 7;
const int PP = 131;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
signed main(){
int n, m;
while(cin >> n >> m){
if (n == 0 && m == 0) break;
int ans = 0;
for (int i = 2; i <= n; i ++){
ans = (ans + m) % i;
}
cout << ans + 1 << endl;
}
return 0;
}
ELI’S CURIOUS MIND
連結：https://ac.nowcoder.com/acm/contest/12207/C
來源：牛客網
題目描述
Eli is a teenager who loves to study chemistry. She recently joined a chemistry research lab.
Dr. Phil wants her to just play around with some chemicals and observe their reaction.
Therefore, he gave her a one-row tray of test tubes with the different chemical inside of them
and told her:
"Mix these chemical together anyhow that you like, but the you have to follow two rules:
Never make a mixture that has two chemicals that their tubes are next to each other.
Keep adding more chemical to the mixture until it is not violating the new rule. "
For example, in the image you can see she was given 5 tubes and she is able to make 4
different mixture without violating the rule: {1,3,5},\ {2,4},\ {2,5},\ {1,4}\ .{1,3,5}, {2,4}, {2,5}, {1,4} .
But she cannot mix 1 and 3 only because she still can add 5 without violating the rules.
She is curious to know how many different mixtures she can make without violating the rule with any
given number of tubes. That’s why she asks you write a code to calculate it for her.
輸入描述:
The input will consist of a sequence of numbers N,\ 1 ≤ N ≤ 76\ .N, 1≤N≤76 . Each number will be on a
separate line. The input will be terminated by 0\ .0 .
輸出描述:
Output the number of different mixture she can make without violating the rule mentioned
above on a single line as show in the sample. The number of all subsets will be less than 2^{31}\ .2
31
.
示例1
輸入
複制
1
2
3
4
5
30
輸出
複制
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 3
Case #5: 4
Case #6: 4410
從n個東西跳出任意個，使剩下的沒用相鄰的，問有多少種方案，先爆搜找規律，爆搜的順序，枚舉目前選了幾個，目前枚舉到了哪個，最後如果确實不能選的話，并且選了的大于1個的話就方案數加1‘
#include<iostream>
using namespace std;
typedef long long ll;
ll num[77];
int cnt=0;
int main(){
num[3]=1;
num[4]=3;
num[5]=4;
num[6]=5;
for(int i=7;i<=76;i++){
num[i]=num[i-2]+num[i-3];
}
ll n;
while(cin>>n&&n!=0){
cout<<"Case #"<<++cnt<<": "<<num[n]<<endl;
}
}
/*
#include<iostream>
#define OKK (!select[i]&&(!select[i-1]||i-1<=0)&&(!select[i+1]||i+1>=maxn))
//判斷目前這個能不能選，如果前面和後面都沒選，目前這個就能選
using namespace std;
typedef long long ll;
bool select[77];
const ll maxn=77;
ll ans=0;
ll sum=0;
void dfs(int k,int ok){ //目前選了幾個，目前枚舉了幾個
bool flag=0;
for(int i=1;i<=sum;i++){
if(OKK) flag=1; //如果還有能選的話就不增加
}
for(int i=ok+1;i<=sum;i++){
if(OKK) {
select[i]=1;
dfs(k+1,i+1);
select[i]=0;
}
}
if(!flag&&k>1) {
//for(int i=1;i<=sum;i++) if(select[i]) cout<<i<<"!!!\n";
//cout<<endl;
ans++;}
}
ll book[100];
int main(){
for(int i=1;i<=76;i++){
//cout<<i<<":\n";
sum=i;
ans=0;
dfs(0,0);
book[i]=ans;
cout<<ans<<",\n";
}
}
*/
SUM OF SUB RECTANGLE AREAS
連結：https://ac.nowcoder.com/acm/contest/12207/F
來源：牛客網
題目描述
The following code snippet calculates the sum of the areas of all the sub rectangular grid in a rectangular grid from (0,0) to (N,N)\ .(N,N) . Find an efficient way to compute that.
sum = 0
for r1 = 0 to N-1
for c1 = 0 to N-1
for r2 = r1+1 to N
for c2 = r2+1 to N
sum = sum + (r2-r1)*(c2-c1)
print(sum)
輸入描述:
Input starts with T the number of test cases. Each test case consists of a single integer N.
輸出描述:
For each test output the sum (as computed above). Please note that even though W and H will fit into 64 bit integer, the sum may not be.
示例1
輸入
複制
5
1
2
3
4
1000
輸出
複制
1
16
100
400
27944805889000000
java大數的應用
import java.util.Scanner;
import java.math.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
sc.nextLine();
while((T --) != 0) {
String str = sc.nextLine();
BigInteger num = new BigInteger(str);
BigInteger two = num.add(BigInteger.ONE);
BigInteger three = two.add(BigInteger.ONE);
BigInteger ok = num.multiply(two).multiply(three);
BigInteger ans = ok.divide(new BigInteger("6"));
System.out.println(ans.pow(2));
}
}
}
SUM OF SUB RECTANGLE AREAS
連結：https://ac.nowcoder.com/acm/contest/12207/F
來源：牛客網
題目描述
The following code snippet calculates the sum of the areas of all the sub rectangular grid in a rectangular grid from (0,0) to (N,N)\ .(N,N) . Find an efficient way to compute that.
sum = 0
for r1 = 0 to N-1
for c1 = 0 to N-1
for r2 = r1+1 to N
for c2 = r2+1 to N
sum = sum + (r2-r1)*(c2-c1)
print(sum)
輸入描述:
Input starts with T the number of test cases. Each test case consists of a single integer N.
輸出描述:
For each test output the sum (as computed above). Please note that even though W and H will fit into 64 bit integer, the sum may not be.
示例1
輸入
複制
5
1
2
3
4
1000
輸出
複制
400
27944805889000000
java的大數
import java.util.*;
import java.math.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
BigInteger[] num=new BigInteger[500];
num[1]=BigInteger.ONE;
num[2]=BigInteger.ONE;
for(int i=3;i<500;i++){
num[i]=num[i-1].add(num[i-2]);
}
//
while(sc.hasNextInt()){
int x=sc.nextInt();
if(x==-1) break;
System.out.println("Hour: "+x+": "+num[x].toString()+" cow(s) affected");
}
}
}
![POJ 2352 Stars 【線段樹】[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)